C語言計(jì)算機(jī)二級公共基礎(chǔ)知識天突擊復(fù)習(xí)教程

二級公共基礎(chǔ)知識突擊學(xué)習(xí)全國計(jì)算機(jī)等級考試二級教程公共基礎(chǔ)知識考試說明及考綱程序設(shè)計(jì)基本概念及算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)總體章節(jié)全國計(jì)算機(jī)等級考試

1、公共基礎(chǔ)知識考試說明及考綱

基本要求

1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6.掌握數(shù)據(jù)的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)?？荚噧?nèi)容

一、基本數(shù)據(jù)結(jié)構(gòu)與算法

1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。

二、程序設(shè)計(jì)基礎(chǔ)1.程序設(shè)計(jì)方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計(jì)。3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計(jì)，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。4.數(shù)據(jù)庫設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。考試方式1、公共基礎(chǔ)的考試方式為筆試，與VisualFOXPRO的筆試部分合為一張?jiān)嚲?。公共基礎(chǔ)部分占全卷的30分。2、公共基礎(chǔ)知識有10道選擇題和5道填空題。學(xué)習(xí)方法理解基本概念多做練習(xí)適當(dāng)記憶一些名詞與所學(xué)的VF程序設(shè)計(jì)知識結(jié)合起來，以增加對知識的理解能力全國計(jì)算機(jī)等級考試

2、程序設(shè)計(jì)基本概念及算法程序概念

什么是程序？

△指令的集合。（解釋指令）

△通過硬件控制系統(tǒng)自動(dòng)完成某一功能。

△通過一系列代碼實(shí)現(xiàn)。

程序怎樣執(zhí)行？怎樣編寫？

△計(jì)算機(jī)本身僅能識別二進(jìn)制代碼“0”、“1”。△編程最直接、最低級的就是機(jī)器語言?！鳛榻鉀Q機(jī)器語言難理解、記憶等問題。出現(xiàn)符號語言?！鳛槭咕幊探咏匀徽Z言，出現(xiàn)高級語言。如C、PASCAL、FORTRAN2.1算法2.1.1算法(algorithm)基本概念對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。關(guān)于問題及問題解決方案的具體描述。

算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報(bào)）等５個(gè)重要特點(diǎn)。有窮性：在有限時(shí)間有限步驟內(nèi)執(zhí)行完畢。確定性：在執(zhí)行過程中命令只可由一個(gè)方式，不可有歧義必須唯一?？尚行裕簩轭}的描述可行。有一定的輸入輸出又稱為有足夠的情報(bào)2.1.2算法的基本要素

1、對數(shù)據(jù)對象的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等一個(gè)算法一般可以用順序、選擇、循環(huán)三種基本機(jī)構(gòu)組合而成。2.2算法復(fù)雜度2.2.1時(shí)間復(fù)雜度依據(jù)算法算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。通常有事后統(tǒng)計(jì)法和事前分析估算法。一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作構(gòu)成的，算法時(shí)間取決于兩者的綜合效果。復(fù)雜性執(zhí)行效率（事前評估\事后分析）算法的時(shí)間復(fù)雜度：算法在執(zhí)行過程中所需要執(zhí)行的基本運(yùn)算次序。2.2.2算法的空間復(fù)雜度

算法空間復(fù)雜度：算法在執(zhí)行過程中所用到的存儲空間大小一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間一個(gè)算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間一個(gè)上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。例題講解算法的時(shí)間復(fù)雜度是指A)執(zhí)行算法程序所需要的時(shí)間B)算法程序的長度C)算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D)算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、

【1】和擁有足夠的情報(bào)。算法的空間復(fù)雜度是指

A)算法程序的長度 B)算法程序中的指令條數(shù)

C)算法程序所占的存儲空間D)執(zhí)行過程中所需要的存儲空間在計(jì)算機(jī)中，算法是指

A)加工方法 B)解題方案的準(zhǔn)確而完整的描述

C)排序方法 D)查詢方法算法分析的目的是

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)找出算法中輸入和輸出之間的關(guān)系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元多少分別稱為算法的【1】。數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)

B．非線性結(jié)構(gòu)A順序存儲

B鏈?zhǔn)酱鎯€性表、數(shù)組棧、廣義表隊(duì)列、串樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面數(shù)據(jù)結(jié)構(gòu)可描述為Group=（D，R）樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)ABCDEFGH樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

圖形結(jié)構(gòu)——節(jié)點(diǎn)間的連結(jié)是任意的元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容順序存儲元素n……..元素i……..元素2元素1存儲內(nèi)容順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。順序存儲結(jié)構(gòu)的三個(gè)弱點(diǎn)：1.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。2.長度變化較大時(shí)，需按最大空間分配。3.表的容量難以擴(kuò)充。例題講解數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于【1】

。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的

A)存儲結(jié)構(gòu) B)物理結(jié)構(gòu)

C)邏輯結(jié)構(gòu) D)物理和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】

兩大類。順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置

【2】的存儲單元中。數(shù)據(jù)處理的最小單位是

A)數(shù)據(jù) B)數(shù)據(jù)元素C)數(shù)據(jù)項(xiàng) D)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及

A)數(shù)據(jù)的存儲結(jié)構(gòu) B)計(jì)算方法C)數(shù)據(jù)映象D)邏輯存儲線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是

A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B)隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

C)隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)

D)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)2.3.2線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作特點(diǎn)：

1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。

2、所有元素所占的存儲空間是連續(xù)的

3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的

2.做插入、刪除時(shí)需移動(dòng)大量元素。

3.空間估計(jì)不明時(shí)，按最大空間分配?！?.a2a1an…..ai+1ai01i-1in-1

1-1插入運(yùn)算ai-1…..a2a1alength…ai+1aixai-1…..a2a1

aiai+1…alength

alength……ai+1

aix

插入算法的分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：

刪除算法的分析在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：

分析結(jié)論順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮。2.4棧和隊(duì)列2.4.1棧和隊(duì)列的定義

棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。2.4.1.1棧的定義棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底（bottom):不允許插入和刪除的一端。a1a2….an進(jìn)棧出棧棧頂棧底隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；2.4.1.2隊(duì)列的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an隊(duì)列示意圖隊(duì)頭隊(duì)尾2.4.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算a2a1a1a2top用順序存儲結(jié)構(gòu)表示的棧。

順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個(gè)簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\(yùn)算：壓（進(jìn)）棧：PUSH出棧：POP例題講解棧和隊(duì)列的共同特點(diǎn)是

A)都是先進(jìn)先出B)都是先進(jìn)后出

C)只允許在端點(diǎn)處插入和刪除元素D)沒有共同點(diǎn)如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e4,e3,e2,e1 D)任意順序下列關(guān)于棧的敘述中正確的是Ａ）在棧中只能插入數(shù)據(jù)B）在棧中只能刪除數(shù)據(jù)C）棧是先進(jìn)先出的線性表D）棧是后進(jìn)先出的線性表下列關(guān)于隊(duì)列的敘述中正確的是Ａ）在隊(duì)列中只能插入數(shù)據(jù)B）在隊(duì)列中只能刪除數(shù)據(jù)C）隊(duì)列是先進(jìn)先出的線性表D）隊(duì)列是后進(jìn)先出的線性表?xiàng)５字翖ｍ斠来未娣旁谹、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE

棧通常采用的兩種存儲結(jié)構(gòu)是

A)線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B)散列方式和索引方式

C)鏈表存儲結(jié)構(gòu)和數(shù)組D)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是【1】

。下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是

A)線性鏈表B)棧C)循環(huán)鏈表 D)順序表2.6樹樹的基本概念二叉樹的定義及其存儲結(jié)構(gòu)二叉樹的前序、中序和后序遍歷2.6.1樹的定義由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。

A

C

GT2D

HIT3J

M

BEL

KT1F現(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。介紹幾個(gè)概念：結(jié)點(diǎn)（Node）：樹中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹的分支。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹數(shù)。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。孩子（Child）：結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為這些結(jié)點(diǎn)的雙親。深度（Depth)：樹中結(jié)點(diǎn)的最大層次數(shù)。森林（Forest）：M棵互不相交的樹的集合。

A

C

GT2D

HIT3J

M

BEL

KT1F2.6.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結(jié)構(gòu)，特點(diǎn)是樹中每個(gè)結(jié)點(diǎn)只有兩棵子樹，且子樹有左右之分，次序不能顛倒?？斩鏄?/p>

僅有根結(jié)點(diǎn)

右子樹為空左子樹為空左右子樹均非空因?yàn)闃涞拿總€(gè)結(jié)點(diǎn)的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。二叉數(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諗?shù)(n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。

特別要注意：二叉數(shù)不是樹的特殊情況。aabb兩棵不同的二叉數(shù)A、

二叉樹的第i層上至多有2i-1（i1）個(gè)結(jié)點(diǎn)。(2)二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個(gè)節(jié)點(diǎn)。A、

二叉樹的第i層上至多有2i-1（i1）個(gè)結(jié)點(diǎn)。

B、

深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)。(2)二叉樹的基本性質(zhì)423167891011121314155此樹的深度h=4，共有24-1=15個(gè)節(jié)點(diǎn)。A、

二叉樹的第i層上至多有2i-1（i1）個(gè)結(jié)點(diǎn)。B、

深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)。C、

若在任意一棵二叉樹中，有n0個(gè)葉子結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則：n0=n2+1(2)二叉樹的基本性質(zhì)423167891011121314155n0=8n2=7（3）滿二叉樹423167891011121314155特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。423167891011125

非完全二叉樹（4）完全二叉樹423167891011125

完全二叉樹特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。（5）樹與二叉樹的區(qū)別A．樹的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0。B．樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2。C．樹的結(jié)點(diǎn)無左、右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左、右之分。

樹

二叉樹2、二叉樹的存儲結(jié)構(gòu)

(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)T[16]若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。11ABcFED

●●●●●●●●●124

8

910563712131415(1)順序存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)2h-1=24-1=15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費(fèi)。2.6.3二叉樹的遍歷查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問一次。按先左后右的原則，一般使用三種遍歷：前序遍歷:

根左右

訪問根結(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹。中序遍歷:左根右

按中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。后序遍歷:左右根

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。

（2）遍歷算法先序遍歷：中序遍歷：后序遍歷：ADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA例題講解已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是

A)acbedB)decabC)deabc

D)cedba

已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是

A)有且只有1 B)1或多于1C)0或1 D)至少2在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A)32 B)31C)16 D)15若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是

A)bdgcefhaB)gdbecfhaC)bdgaechf

D)gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有【1】根。下列敘述中正確的是

A)線性表是線性結(jié)構(gòu)

B)棧與隊(duì)列是非線性結(jié)構(gòu)

C)線性鏈表是非線性結(jié)構(gòu) D)二叉樹是線性結(jié)構(gòu)具有3個(gè)結(jié)點(diǎn)的二叉樹有

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)

設(shè)有下列二叉樹：

對此二叉樹前序遍歷的結(jié)果為A)ZBTTCPXA B)ATBZXCTPC)ZBTACTXPD)ATBZXCPT設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為

A)12 B)13C)14 D)15

設(shè)有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA設(shè)樹T的深度為4,其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1。則T中的葉子結(jié)點(diǎn)數(shù)為n0=n2+1A）8B）7C）6D）5設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則該二叉樹中有（350）個(gè)葉子結(jié)點(diǎn)。

設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（DEBFCA）。2.7查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）2.7.1查找查找是在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點(diǎn)查找失敗：找不到滿足條件的結(jié)點(diǎn)。2.7.1.1順序查找（線性查找）查找過程：對給定的一關(guān)鍵字K，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端?？梢圆捎脧那跋蚝蟛?，也可采用從后向前查的方法?！ぴ谄骄闆r下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長度較大?！ぴ谙旅鎯煞N情況下只能采取順序查找：

a.線性表為無序表（元素排列是無序的）；

b.即使是有序線性表，但采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。2.7.1.2折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。分三種情況：1）若中間項(xiàng)的值等于x,則說明已查到。2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。2.7.2排序2.7.2.1概述1、排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。2、排序過程的組成步驟：首先比較兩個(gè)關(guān)鍵字的大??；然后將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。排序方法插入排序選擇排序交換排序歸并排序直接插入排序折半插入排序簡單選擇排序堆排序起泡排序快速排序2.7.2.2插入排序

直接插入、折半插入1、直接插入排序:

基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。需要n(n-1)/2次比較該算法適合于n較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例對于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次2、折半插入排序

折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。折半插入排序的條件：在有序序列中插入一個(gè)關(guān)鍵字。例：有6個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對第6個(gè)記錄排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找結(jié)束，插入位置為low或high+1)(42>36)(42<53)

1、簡單選擇排序思想：首先從1~n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后再從第2個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。時(shí)間復(fù)雜度為O(n2)，最壞情況下需要比較

n(n-1)/2次適用于待排序元素較少的情況。2.7.2.3選擇排序

簡單選擇排序、堆排序初態(tài)83916839168391683916ijkijkijkijk1

3986互換ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟

2

堆排序

也是一種選擇排序。是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個(gè)非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。

(1)堆的示例

897624331510112536497856(a):堆頂元素取最大值(b):堆頂元素取最小值(2)實(shí)現(xiàn)堆排序需解決兩個(gè)問題：

（1）如何由一個(gè)無序序列建成一個(gè)堆？（2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個(gè)新的堆？堆排序需要比較的次數(shù)為O(nlog2n)2.7.2.4交換排序交換排序的特點(diǎn)在于交換。有冒泡和快速排序兩種。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個(gè)與第2個(gè)比較，大則交換；第2個(gè)與第3個(gè)比較，大則交換，……關(guān)鍵字最大的記錄交換到最后一個(gè)位置上；第二趟：對前n-1個(gè)記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個(gè)位置上；依次類推，則完成排序。正序：時(shí)間復(fù)雜度為O(n)逆序：時(shí)間復(fù)雜度為O(n2)

適合于數(shù)據(jù)較少的情況。

排序n個(gè)記錄的文件最多需要n-1趟冒泡排序。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字思想：小的浮起，大的沉底。49364165117836653641563641654136415611783636414911564925252511494956111111252525252、快速排序(對冒泡排序的改進(jìn)）思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達(dá)到整個(gè)序列有序。關(guān)鍵字通常取第一個(gè)記錄的值為基準(zhǔn)值。做法：附設(shè)兩個(gè)指針low和high

，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)關(guān)鍵字為

key

，首先從high所指位置起向前搜索，找到第一個(gè)小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，然后從low

所指位置起向后搜索，找到第一個(gè)大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，重復(fù)這兩步直至low=high為止。時(shí)間復(fù)雜度：O(log2n)快速排序過程示意圖：有序序列618235267key初始序列235266718lowhigh一次交換185266723lowhigh二次交換18

2366752high三次交換[186]23[6752]//完成一趟排序后分別進(jìn)行快速排序lowhigh2.7.2.5內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點(diǎn)，故在不同情況下可作不同的選擇。通常需考慮的因素有：待排序的記錄個(gè)數(shù)；記錄本身的大?。挥涗浀逆I值分布情況等。若待排序的記錄個(gè)數(shù)n較小時(shí)，可采用簡單排序方法。若n較大時(shí)，應(yīng)采用快速排序或堆排序。若待排序的記錄已基本有序，可采用起泡排序。例題講解在長度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為

【2】。長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為【1】

。假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為

A)log2n B)n2C)O(n1..5) D)n(n-1)/2已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是

A)堆排序B)直接插入排序C)快速排序D)直接選擇排序在下列幾種排序方法中，要求內(nèi)存量最大的是

A)插入排序

B)選擇排序C)快速排序 D)歸并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A)冒泡排序

B)選擇排序C)快速排序D)歸并排序

希爾排序?qū)儆?/p>

A)交換排序B)歸并排序C)選擇排序 D)插入排序?qū)﹂L度為n的線性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)為Ａ)n+1B)nC)(n+1)/2D)n/22.8其他串圖2.8.1串串的定義和基本運(yùn)算串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個(gè)有窮字符序列。串中字符的數(shù)目n被稱作串的長度。當(dāng)n=0時(shí)，串中沒有任何字符，其串的長度為0，通常被稱為空串。

s1=“”s2=“”s1中沒有字符，是一個(gè)空串；而s2中有兩個(gè)空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。兩個(gè)串相等：兩個(gè)串的長度相等，并且各個(gè)對應(yīng)的字符也都相同。例如，有下列四個(gè)串a(chǎn)，b，c，d：

a=“program”b=“Program”c=“pro”d=“program”

圖有向圖無向圖在有向圖中，<V1，V3>表示從V1到V3的一條弧。

V1為弧尾或初始點(diǎn)，V3為弧頭或終端點(diǎn)。在無向圖中，(V1，V3)表示V1和V3之間的一條邊。V1V3V2V4V1V3V2V4圖沒有層次關(guān)系層有層次關(guān)系2.8.2圖的基本概念連通圖：選中任意一個(gè)點(diǎn)都可以到其它節(jié)點(diǎn)非連通圖：E無法與A,B,C,D建立聯(lián)系強(qiáng)連通圖：n個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為n-1條．n個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有n條．EABCDE例題講解串的長度是

A)串中不同字符的個(gè)數(shù)B)串中不同字母的個(gè)數(shù)

C)串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于零D)串中所含字符的個(gè)數(shù)若串s=“MathTypes”，則其子串的數(shù)目是

【3】。

n個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有

A)n-1 B)n(n-1)C)n D)n+1

設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)位置的運(yùn)算稱作

A)連接 B)模式匹配C)求子串D)求串長n個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為

A)0 B)1C)n-1 D)n全國計(jì)算機(jī)等級考試

3.程序設(shè)計(jì)基礎(chǔ)

3.1程序設(shè)計(jì)方法與風(fēng)格3.1.1程序設(shè)計(jì)方法1、結(jié)構(gòu)化設(shè)計(jì)方法模塊內(nèi)部程序各部分要按照自頂向下的結(jié)構(gòu)劃分各程序部分應(yīng)按功能組合各程序之間的聯(lián)系盡量通過調(diào)用子程序來實(shí)現(xiàn)，不用或少用GOTO方式2.語句的結(jié)構(gòu)每條語句簡單明了盡量不用或少用GOTO語句盡量只采用3種基本控制結(jié)構(gòu)編程3.輸入和輸出對所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查輸入輸出格式保持一致設(shè)計(jì)良好的輸出報(bào)表三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)三種基本結(jié)構(gòu)的特點(diǎn)只有一個(gè)入口只有一個(gè)出口每一個(gè)基本結(jié)構(gòu)中的每一部分都有機(jī)會(huì)執(zhí)行到結(jié)構(gòu)內(nèi)不存在“死循環(huán)”3.2.2設(shè)計(jì)原則自頂向下逐步求精模塊化限制使用goto語句類(Class)一個(gè)類定義了一組大體上相似的對象。一個(gè)類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。類是在對象之上的抽象，對象是類的具體化，是類的實(shí)例封裝(Encapsulation)將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構(gòu)成一個(gè)具有類類型的對象的描述。對象的內(nèi)部實(shí)現(xiàn)受保護(hù)，外界不能訪問封裝簡化了程序員對對象的使用例題講解結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是

A)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)B)分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)

C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu)D)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)在設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是

A)不限制goto語句的使用B)減少或取消注解行

C)程序越短越好 D)程序結(jié)構(gòu)應(yīng)有助于讀者理解結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是

A)程序的規(guī)模 B)程序的效率

C)程序設(shè)計(jì)語言的先進(jìn)性 D)程序易讀性以下不屬于對象的基本特點(diǎn)的是

A)分類性B)多態(tài)性C)繼承性 D)封裝性

對建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是

A)程序應(yīng)簡單、清晰、可讀性好 B)符號名的命名只要符合語法

C)充分考慮程序的執(zhí)行效率 D)程序的注釋可有可無在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的

A)安全性 B)一致性C)可理解性 D)合理性程序的3種基本控制結(jié)構(gòu)是

A)過程、子過程和分程序 B)順序、選擇和重復(fù)

C)遞歸、堆棧和隊(duì)列 D)調(diào)用、返回和轉(zhuǎn)移下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則的是

A)自頂向下 B)由底向上

C)模塊化 D)限制使用goto語句對象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行

A)結(jié)合 B)隱藏C)封裝 D)抽象在面向?qū)ο蠓椒ㄖ?，一個(gè)對象請求另一個(gè)對象為其服務(wù)的方式是通過發(fā)送A）調(diào)用語句B）命令C）口令D）消息信息屏蔽的概念與下述哪一種概念直接相關(guān)A）軟件結(jié)構(gòu)定義B）模塊獨(dú)立性C）模塊類型劃分D）模塊偶合度下列對象概念描述錯(cuò)誤的是A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動(dòng)態(tài)屬性全國計(jì)算機(jī)等級考試

二級公共基礎(chǔ)知識

(4)4.軟件工程基礎(chǔ)4.1基本概念1.軟件工程軟件工程是指應(yīng)用計(jì)算機(jī)科學(xué)、數(shù)學(xué)及管理科學(xué)等原理，以工程化的原則和方法來解決軟件問題的工程。其目的是提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低軟件成本。2.軟件危機(jī)早期的軟件主要指程序，采用個(gè)體工作方式，缺少相關(guān)文檔，質(zhì)量低，維護(hù)困難，這些問題稱為“軟件危機(jī)”，軟件工程概念的出現(xiàn)源自于軟件危機(jī)。3.軟件生命周期將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)3個(gè)階段。維護(hù)是持續(xù)時(shí)間最長，花費(fèi)代價(jià)最大的一個(gè)階段，軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)代價(jià)4.軟件工程三要素方法：完成軟件工程項(xiàng)目的技術(shù)手段工具：支持軟件的開發(fā)、管理、文檔生成過程：支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理4.2結(jié)構(gòu)化分析方法基本思想將系統(tǒng)分析看成工程項(xiàng)目，有計(jì)劃、有步驟地進(jìn)行工作。開發(fā)策略自頂向下，逐層分解分析結(jié)果一套分層的數(shù)據(jù)流圖(DFD)：用來描述數(shù)據(jù)流從輸入到輸出的變換流程一個(gè)數(shù)據(jù)字典(DD)：用來描述DFD中的每個(gè)數(shù)據(jù)流、文件以及組成數(shù)據(jù)流或文件的數(shù)據(jù)項(xiàng)一組小說明（加工邏輯說明）：用來描述每個(gè)基本加工的加工邏輯PAD程序設(shè)計(jì)圖PFD程序流程圖N-S方格圖（方格表示分支）DFD數(shù)據(jù)流圖4.3.總體設(shè)計(jì)設(shè)計(jì)原則分解—協(xié)調(diào)原則自頂向下的原則信息屏蔽、抽象的原則一致性原則明確性原則模塊間的耦合度盡可能小，模塊內(nèi)部組合盡可能緊湊（內(nèi)聚性高）耦合度：兩個(gè)或兩個(gè)模塊之間關(guān)聯(lián)的緊密程度稱為4.4軟件測試4.4.1意義目的為了發(fā)現(xiàn)錯(cuò)誤希望能以最少的人力和時(shí)間發(fā)現(xiàn)潛在的各種錯(cuò)誤和缺陷保證系統(tǒng)質(zhì)量和可靠性的關(guān)鍵步驟4.4.2測試方法人工測試機(jī)器測試4.4.3白盒測試結(jié)構(gòu)測試將軟件看成透明的白盒，根據(jù)程序的內(nèi)部結(jié)構(gòu)和邏輯結(jié)構(gòu)來設(shè)計(jì)測試?yán)?，對程序的路徑和過程進(jìn)行測試，檢查是否滿足設(shè)計(jì)的要求4.4.4黑盒測試功能測試將軟件看成黑盒子，在完全考慮軟件內(nèi)部結(jié)構(gòu)和特性的情況下，測試軟件的外部特性4.5程序調(diào)試4.5.1任務(wù)根據(jù)測試時(shí)發(fā)現(xiàn)的錯(cuò)誤，找出原因和具體的位置，進(jìn)行改正有程序開發(fā)人員來進(jìn)行，誰開發(fā)的程序就由誰來進(jìn)行調(diào)試方法：強(qiáng)行排錯(cuò)法回溯法原因排除法（演繹、歸納、二分法)例題講解為了提高測試的效率，應(yīng)該

A)隨機(jī)選取測試數(shù)據(jù)B)取一切可能的輸入數(shù)據(jù)作為測試數(shù)據(jù)

C)在完成編碼以后制定軟件的測試計(jì)劃D)集中對付那些錯(cuò)誤群集的程序軟件生命周期中所花費(fèi)用最多的階段是

A)詳細(xì)設(shè)計(jì) B)軟件編碼C)軟件測試D)軟件維護(hù)下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是

A)便于用戶、開發(fā)人員進(jìn)行理解和交流

B)反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)

C)作為確認(rèn)測試和驗(yàn)收的依據(jù)

D)便于開發(fā)人員進(jìn)行需求分析下列不屬于軟件工程的3個(gè)要素的是Ａ)工具 Ｂ)過程Ｃ)方法 Ｄ)環(huán)境開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱作

A)軟件投機(jī) B)軟件危機(jī)C)軟件工程D)軟件產(chǎn)生下面不屬于軟件設(shè)計(jì)原則的是Ａ)抽象 Ｂ)模塊化Ｃ)自底向上Ｄ)信息隱蔽開發(fā)大型軟件時(shí)，產(chǎn)生困難的根本原因是

A)大系統(tǒng)的復(fù)雜性 B)人員知識不足

C)客觀世界千變?nèi)f化 D)時(shí)間緊、任務(wù)重軟件工程的出現(xiàn)是由于

A)程序設(shè)計(jì)方法學(xué)的影響 B)軟件產(chǎn)業(yè)化的需要

C)軟件危機(jī)的出現(xiàn) D)計(jì)算機(jī)的發(fā)展軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持，其中必要的測試數(shù)據(jù)屬于

A)硬件資源 B)通信資源C)支持軟件D)輔助資源在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列不屬于結(jié)構(gòu)化分析的常用工具的是

A)數(shù)據(jù)流圖 B)數(shù)據(jù)字典C)判定樹 D)PAD圖在軟件生產(chǎn)過程中，需求信息的給出是

A)程序員B)項(xiàng)目管理者

C)軟件分析設(shè)計(jì)人員 D)軟件用戶下列工具不是需求分析常用工具的是Ａ)PAD Ｂ)PFDＣ)N-S Ｄ)DFD模塊獨(dú)立性是軟件模塊化所提出的要求，衡量模塊獨(dú)立性的度量標(biāo)準(zhǔn)則是模塊的

A)抽象和信息隱蔽 B)局部化和封裝化

C)內(nèi)聚性和耦合性 D)激活機(jī)制和控制方法軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成

A)定義、開發(fā)、運(yùn)行維護(hù)B)設(shè)計(jì)階段、編程階段、測試階段

C)總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編程調(diào)試D)需求分析、功能定義、系統(tǒng)設(shè)計(jì)在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是

A)

路徑的集合B)循環(huán)的集合C)目標(biāo)的集合D)地址的集合完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導(dǎo)出測試用例的測試方法是

A)黑箱測試法B)白箱測試法C)錯(cuò)誤推測法D)安裝測試法在結(jié)構(gòu)化設(shè)計(jì)方法中，生成的結(jié)構(gòu)圖(SC)中，帶有箭頭的連線表示

A)模塊之間的調(diào)用關(guān)系 B)程序的組成成分

C)控制程序的執(zhí)行順序 D)數(shù)據(jù)的流向下列選項(xiàng)中，不屬于模塊間耦合的是

A)數(shù)據(jù)耦合B)同構(gòu)耦合C)異構(gòu)耦合D)公用耦合下列敘述中，不屬于測試的特征的是

A)測試的挑剔性 B)完全測試的不可能性

C)測試的可靠性 D)測試的經(jīng)濟(jì)性需求分析中開發(fā)人員要從用戶那里了解

A)軟件做什么 B)用戶使用界面

C)輸入的信息 D)軟件的規(guī)模下列不屬于軟件調(diào)試技術(shù)的是

A)強(qiáng)行排錯(cuò)法 B)集成測試法

C)回溯法 D)原因排除法為了避免流程圖在描述程序邏輯時(shí)的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為

A)PAD圖 B)N-S圖C)結(jié)構(gòu)圖 D)數(shù)據(jù)流圖軟件復(fù)雜性度量的參數(shù)包括

A)效率 B)規(guī)模C)完整性 D)容錯(cuò)性下列敘述中，正確的是

A)軟件就是程序清單B)軟件就是存放在計(jì)算機(jī)中的文件

C)軟件應(yīng)包括程序清單及運(yùn)行結(jié)果D)軟件包括程序和文檔軟件設(shè)計(jì)中，有利于提高模塊獨(dú)立性的一個(gè)準(zhǔn)則是

A)低內(nèi)聚低耦合 B)低內(nèi)聚高耦合

C)高內(nèi)聚低耦合 D)高內(nèi)聚高耦合軟件生命周期中花費(fèi)時(shí)間最多的階段是

A)詳細(xì)設(shè)計(jì) B)軟件編碼C)軟件測試D)軟件維護(hù)下列敘述中，不屬于結(jié)構(gòu)化分析方法的是

A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

B)面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法

C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法

D)面向?qū)ο蟮姆治龇椒ㄔ敿?xì)設(shè)計(jì)的結(jié)果基本決定了最終程序的

A)代碼的規(guī)模 B)運(yùn)行速度

C)質(zhì)量 D)可維護(hù)性下列不屬于靜態(tài)測試方法的是

A)代碼檢查 B)白盒法

C)靜態(tài)結(jié)構(gòu)分析 D)代碼質(zhì)量度量在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須局別哪些功能的階段是A）概要設(shè)計(jì)B）詳細(xì)設(shè)計(jì)C）可行性分析D）需求分析檢查軟件產(chǎn)品是否符合需求定義的過程稱為A）確認(rèn)測試B）集成測試C）驗(yàn)證測試D）驗(yàn)收測試數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成，下列圖符名標(biāo)識的圖符不屬于數(shù)據(jù)流圖合法圖符的是A）控制流B）加工C）數(shù)據(jù)存儲D）源和潭下面不屬于軟件設(shè)計(jì)原則的是A）抽象B）模塊化C）自底向上D）信息屏蔽程序流程圖（PFD）中的箭頭代表的是A）數(shù)據(jù)流B）控制流C）調(diào)用關(guān)系D）組成關(guān)系下列工具中為需求分析常用工具的是A）PADB）PFDC）N-SD）DFD在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是A）詳細(xì)設(shè)計(jì)B）需求分析C）總體設(shè)計(jì)D）編程調(diào)試軟件調(diào)試的目的是A）發(fā)現(xiàn)錯(cuò)誤B）改正錯(cuò)誤C）改善軟件的性能D）挖掘軟件的潛能軟件需求分析階段的工作，可以分為四個(gè)方面：需求獲取，需求分析，編寫需求規(guī)格說明書，以及A）階段性報(bào)告B）需求評審C）總結(jié)D）都不正確全國計(jì)算機(jī)等級考試

5.數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)5.數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)5.1基本概念

1.數(shù)據(jù)(Data)2.數(shù)據(jù)庫(DB)3.數(shù)據(jù)庫管理系統(tǒng)(DBMS)主要功能包括數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義與檢查數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS一般提供相應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言數(shù)據(jù)操縱語言數(shù)據(jù)控制語言

4.數(shù)據(jù)庫管理員主要工作包括：數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫維護(hù)改善系統(tǒng)性能，提高系統(tǒng)效率5.數(shù)據(jù)庫系統(tǒng)（DBS）由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、系統(tǒng)平臺之硬件平臺（硬件）和軟件平臺（軟件）構(gòu)成。6.數(shù)據(jù)庫管理技術(shù)的發(fā)展人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段7.數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫系統(tǒng)的三級模式（1）概念模式（2）外模式（3）內(nèi)模式內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲形式概念模式處于中層，它放映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求5.2數(shù)據(jù)模型5.2.1數(shù)據(jù)模型的基本概念數(shù)據(jù)模型是數(shù)據(jù)特性的抽象數(shù)據(jù)模型描述的內(nèi)容數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型概念數(shù)據(jù)模型（概念模型）邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）物理數(shù)據(jù)模型（物理模型）5.2.2E-R模型（實(shí)體聯(lián)系模型）基本概念（1）實(shí)體（2）屬性（3）聯(lián)系一對一（1：1）一對多（1：M或M：1）多對多（M：N）5.2.3層次模型一種樹形結(jié)構(gòu)5.2.4網(wǎng)狀模型一個(gè)不加任何條件限制的無向圖優(yōu)于層次模型使用時(shí)設(shè)計(jì)系統(tǒng)內(nèi)部的物理因素較多，用戶操作不方便，其數(shù)據(jù)模式與系統(tǒng)實(shí)現(xiàn)不甚理想5.2.5關(guān)系模型采用二維表來表示，簡稱表。二維表的性質(zhì)：元素個(gè)數(shù)有限性、元組的惟一性、元組的次序無關(guān)性、屬性的次序無關(guān)性、分量值域的同一性關(guān)系操縱：查詢、增加、刪除和修改數(shù)據(jù)庫設(shè)計(jì)目前一般采用生命周期法，分若干階段需求分析階段概念設(shè)計(jì)階段邏輯設(shè)計(jì)階段物理設(shè)計(jì)階段編碼階段測試階段運(yùn)行階段進(jìn)一步修改階段在數(shù)據(jù)庫設(shè)計(jì)中采用前四個(gè)階段，并且重點(diǎn)以數(shù)據(jù)結(jié)構(gòu)與模型的設(shè)計(jì)為主線5.4數(shù)據(jù)庫概念設(shè)計(jì)設(shè)計(jì)的過程

3種設(shè)計(jì)次序（自頂向下、由底向上、由內(nèi)向外）例題講解下列有關(guān)數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)庫是一個(gè)DBF文件 B)數(shù)據(jù)庫是一個(gè)關(guān)系

C)數(shù)據(jù)庫是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合 D)數(shù)據(jù)庫是一組文件下列有關(guān)數(shù)據(jù)庫的描述，正確的是

A)數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程

B)數(shù)據(jù)的物理獨(dú)立性是指當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，數(shù)據(jù)的存儲結(jié)構(gòu)不變

C)關(guān)系中的每一列稱為元組，一個(gè)元組就是一個(gè)字段

D)如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)關(guān)系的關(guān)鍵字，則稱其為本關(guān)系的外關(guān)鍵字在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是Ａ)數(shù)據(jù)庫系統(tǒng) Ｂ)文件系統(tǒng)Ｃ)人工管理 Ｄ)數(shù)據(jù)項(xiàng)管理下述關(guān)于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是Ａ)數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余Ｂ)數(shù)據(jù)庫系統(tǒng)避免了一切冗余Ｃ)數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類型一致Ｄ)數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)下列SQL語句中，用于修改表結(jié)構(gòu)的是

A)ALTER B)CREATEC)UPDATED)INSERT數(shù)據(jù)庫系統(tǒng)的核心是

A)數(shù)據(jù)庫 B)數(shù)據(jù)庫管理系統(tǒng)

C)模擬模型 D)軟件工程數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)之間的關(guān)系是

A)數(shù)據(jù)庫包括數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)

B)數(shù)據(jù)庫系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)

C)數(shù)據(jù)庫管理系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫系統(tǒng)

D)3者沒有明顯的包含關(guān)系關(guān)系模型允許定義3類數(shù)據(jù)約束，下列不屬于數(shù)據(jù)約束的是

A)實(shí)體完整性約束 B)參照完整性約束

C)域完整性約束 D)用戶自定義的完整性約束關(guān)系表