c語言公共基礎(chǔ)復(fù)習(xí)重點

1、第二部分二級公共基礎(chǔ)歷年試題分布： 數(shù)據(jù)結(jié)構(gòu)與算法（3-5個選擇題，一般4題；1-3個填空題，一般2題，約12分） 程序設(shè)計基礎(chǔ)（1-2個選擇題，一般1題；0-2個填空題，一般 0-1個，約4分） 軟件工程基礎(chǔ)（2-3個選擇題，一般 2題；1-2個填空題，一般 2個，約8分） 數(shù)據(jù)庫設(shè)計基礎(chǔ)（2-3個選擇題，一般 2題；1-2個填空題，一般 2個，約8分）第一章數(shù)據(jù)結(jié)構(gòu)與算法第一部分算法大綱要求：算法的基本概念；算法復(fù)雜度的概念和意義（時間與空間復(fù)雜度）一、算法的基本概念算法：是指一組有窮的指令集，是解題方案的準(zhǔn)確而完整的描述。通俗的說，算法就是計算機解題的過程注：程序的編制不可能優(yōu)于算法。二

2、、算法的基本特征 （）1、可行性：能夠得到滿意的結(jié)果。2、確定性：算法的每一個步驟都必須有明確的定義。3、有窮性：一個算法必須在執(zhí)行有窮步后結(jié)束，即算法必須能夠終止。即必須能在有限的時間內(nèi)做完。4、 擁有足夠的情報（有零個輸入或多個輸入，有一個或多個輸出）：算法是否有效，取決于算法提供的情報是 否足夠。例：1算法的有窮性是指（）【08年4月】AA）算法程序的運行時間是有限的B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長度是有限的D）算法只能被有限的用戶使用三、算法設(shè)計基本方法1、列舉法2、歸納法3、遞推法4、遞歸法5、減半遞推技術(shù)6、回溯法四、 算法復(fù)雜度 （時間復(fù)雜度和空間復(fù)雜度）（）1

3、、時間復(fù)雜度：執(zhí)行算法所需要的計算工作量，也就是 耗費的時間量。是對算法時間效率的度量。2、空間復(fù)雜度：執(zhí)行這個算法所 需要的內(nèi)存空間， 是對算法所需存儲空間的度量。3、 時間復(fù)雜度與空間復(fù)雜度是從兩個方面對算法的效率進行度量，兩者之間沒有必然的聯(lián)系。例：1算法的空間復(fù)雜度是指（）?！?9年9月】 AA.算法在執(zhí)行過程中所需要的計算機存儲空間B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的臨時工作單元數(shù)2. 算法復(fù)雜度主要包括時間和 【05年9月】復(fù)雜度。3. 下列敘述中正確的是（）【06年9月】DA ） 一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大B ） 一

4、個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜必定小D）上述三種說法都不對第二部分數(shù)據(jù)結(jié)構(gòu)大綱要求：數(shù)據(jù)結(jié)構(gòu)的定義，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概 念。一、數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念1、數(shù)據(jù)結(jié)構(gòu)一一是指由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成的集合。通常也指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)兩種。2、 數(shù)據(jù)的邏輯結(jié)構(gòu)一一反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。（）3、數(shù)據(jù)的存儲結(jié)構(gòu)一一數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)，即各數(shù)據(jù)元素在計算機中的存儲關(guān)系。（）4

5、、數(shù)據(jù)存儲結(jié)構(gòu)不僅要存放各數(shù)據(jù)元素的信息，還要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。5、邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)之間的關(guān)系（）一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。例：1.下列描述中 正確的是（）【05年9月】DA）個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率2. 下列敘述正確的是（）【07年4月】BA ）算法的效率

6、只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B）算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C） 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是對應(yīng)的（可以一對多）D）算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)（ 不相關(guān)）3. 下列敘述中正確的是（）【07年9月】。A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B）由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C）程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D）以上三種說法都不對4. 數(shù)據(jù)的存儲結(jié)構(gòu)是指（ ）【05年4月】DA）存儲在外存中的數(shù)據(jù)B）數(shù)據(jù)在外存中的數(shù)據(jù)C）數(shù)據(jù)在計算機中的順序存儲方式D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計

7、算機中的表示如：一年四季的數(shù)據(jù)結(jié)構(gòu)用圖形表示為6、數(shù)據(jù)結(jié)構(gòu)的符號表示：B=（ D，R）B :數(shù)據(jù)結(jié)構(gòu)，D:數(shù)據(jù)元素的集合，R :數(shù)據(jù)元素之間的前后件關(guān)系。7、數(shù)據(jù)結(jié)構(gòu)的圖形表示：方框：表示數(shù)據(jù)兀素有向線段：表示數(shù)據(jù)兀素的前后件關(guān)系。（按邏輯結(jié)構(gòu)的分類）（）8、根據(jù)數(shù)據(jù)結(jié)構(gòu)各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，將數(shù)據(jù)結(jié)構(gòu)分為: 線性結(jié)構(gòu)非線性結(jié)構(gòu)9、線性結(jié)構(gòu)所滿足的條件： 有且只有一個根結(jié)點； 每一個結(jié)點最多有一個直接前驅(qū)，也最多有一個直接后繼；線性結(jié)構(gòu)又稱為線性表，如：線性表、棧、隊列、循環(huán)對列、線性鏈表、循環(huán)鏈表等屬線性結(jié)構(gòu)。（）10、非線性結(jié)構(gòu)：如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)

8、構(gòu)。女口：樹、二叉樹等屬非線性結(jié)構(gòu)（）例：1.下列敘述中正確的是（）【06年4月】A）線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B）棧與隊列是非線性結(jié)構(gòu)C）雙向鏈表是非線性結(jié)構(gòu)D）只有根結(jié)點的二叉樹是線性結(jié)構(gòu)2. 線性表的正確說法是（）【05年4月】BA）存儲空間不一定連續(xù)，前件和后件可以任意排列B）存儲空間不一定連續(xù)，前件必須排在后件的前面C）存儲空間一定連續(xù)，前件和后件可以任意排列D）存儲空間一定連續(xù)，前件必須排在后件的前面11、空的數(shù)據(jù)結(jié)構(gòu)既可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)，要根據(jù)該結(jié)構(gòu)進行的運算而定。二、線性表大綱要求：線性表的定義，線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算1、線性表是最簡單、最常

9、用的一種線性數(shù)據(jù)結(jié)構(gòu)。2、 非空線性表有以下三個結(jié)構(gòu)特征： 有且只有一個根結(jié)點，它無前件； 有且只有一個終端結(jié)點，它無后件； 除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件（直接前驅(qū)），也有且只有一個后件（直接后繼）。3、線性表中結(jié)點的個數(shù) n稱為線性表的長度，當(dāng)n=0時，稱為空表。4、線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點： 線性表中所有元素 所占的存儲空間是連續(xù)的 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的5、以順序存儲方式存儲的線性表稱為順序表，順序表的基本運算有： 插入運算要在第i （1=i=n ）個元素之前插入一個新元素時，首先要從最后一個元素開始，直到第i個元素之間

10、共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。 刪除運算在一般情況下，要刪除第i（ 1=i=1）個結(jié)點（）3、 深度為m的二叉樹最多有個結(jié)點（）4、 在任意一棵二叉樹中，度為0的結(jié)點（葉子結(jié)點）總是比度為2的結(jié)點多一個（）5、有n個結(jié)點的二叉樹，其深度至少為log 2n+1 ,其中l(wèi)og 2n表示取log 2n的整數(shù)部分（）例：1.在下列關(guān)于二叉樹的敘述，選出正確的一項（）DA.在二叉樹中，任何一個結(jié)點的度都是2 B.二叉樹的度為2C.在二叉樹中至少有一個結(jié)點的度是2D. 一棵二叉樹的度可以小于 22. 一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)

11、點數(shù)最多為【05年9月】 個。323. 某二叉樹有5個度為2的結(jié)點以及3個度為1的結(jié)點，則該二叉樹中共有 個結(jié)點?！?9年9月】【07年94. 一棵二叉樹中共有 70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()月】。A ) 219 B ) 221 C ) 229 D ) 231十二、滿二叉樹1 、滿二叉樹一一除最后一層外，每一層的所有結(jié)點都有兩個子結(jié)點(滿二叉樹如下圖)2 、滿二叉樹的每一層上的結(jié)點數(shù)都達到最大值。3、滿二叉樹的第 K層上有 21個結(jié)點。如：上圖第 3層有4個結(jié)點()4、 深度為m的滿二叉樹有 21個結(jié)點。女口：上圖深度為3共有7個結(jié)點() 例：1.在深度為7的

12、滿二叉樹中，葉子結(jié)點的個數(shù)為()【06年4月】CA) 32B)31C)64D)632. 在深度為7的滿二叉樹中，度為 2的結(jié)點個數(shù)為【07年4月】。3. 某二叉樹中有n個度為2的結(jié)點,則該二叉樹中的葉( )【07年4月】A) n+1 B)n-1C)2nD)n/2【07年94. 一棵二叉樹中共有 70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()月】。A) 219B)221C) 229 D)231十三、完全二叉樹1、完全二叉樹一一除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。AABCAABCBC(a)完全二叉樹IDJ叵(b)完全二叉樹CDEG(c)

13、非完全二叉樹(d)非完全二叉樹2、在完全二叉樹中，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。3、 右分支下的子孫結(jié)點的最大層次為p，則其左分支下的子孫結(jié)點的最大層次為p或p+1。4、滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。5、 具有n個結(jié)點的完全二叉樹的深度為log 2n+1 ()6、設(shè)完全二叉樹共有 N個結(jié)點。如果從根結(jié)點開始，按層序(每一層從左到右)用自然數(shù)1到N給結(jié)點進行編號，則對編號為K (K=1 , 2,，N )的結(jié)點有以下結(jié)論： 若K=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若K1，則該結(jié)點的父結(jié)點編號為INT(K/2) 若2K=N,則編號為K的結(jié)點的左子結(jié)點編號為2K;否則

14、該結(jié)點無左子結(jié)點，也沒有右子結(jié)點。 若2K+1=N則編號為K的結(jié)點的右子結(jié)點編號為2K+1,否則該結(jié)點無右子結(jié)點。4 . . 5 .6 .例如：D E rF(按層序編號的完全叉樹)例：上圖編號為2的結(jié)點(即K=2),那么該結(jié)點的左子結(jié)點的編號應(yīng)為4 (2*2=4)十四、二叉樹的遍歷（指不重復(fù)地訪問二叉樹中的所有結(jié)點）（）大綱要求：二叉樹的前序、中序、后序遍歷BCD E F1 、前序遍歷（根左右或DLR）方法：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 如上圖前序遍歷的結(jié)果是：ABDECF2 、中序扁歷（左根右或LDR）方法：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 如上圖中序遍歷

15、遍歷的結(jié)果是：DBEAFC3 、后序扁歷（左右根或LRD）方法：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 如上圖后序遍歷遍歷的結(jié)果是：DEBFCA例：1.對如下二叉樹）【06年4月】D進行后序遍歷的結(jié)果為A）ABCDEFB)DBEAFC C)ABDECFD)DEBFCA卜五、查找技術(shù)大綱要求：順序查找與二分法查找算法 （1 ）順序查找1 、查找方法：從線性表的第一個元素開始，依次將線性中的元素與被查元素進行比較，若相等則表示找到；若所有的元素都與被查元素進行了比較但都不相等，則表示查找失敗。（）2 、若在長度為N的線性表中查找，在最壞情況下需要比較N次，記為O（N）。（ ）3 、如果線

16、性表為無序表（即未按升序或降序排列），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。（）4 、即使是有序線表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。（）（2）二分法查找1、查找方法：將待查找元素 X與線性表的中間項值進行比較，若中間項的值等于X,則找到；若 XX大于中間項的值，則在線0為止。（）Iog2 N（ ）【05年4月】B小于中間項的值，則在線性表的前半部分以相同的方法進行查找；若 性表的后半部分以相同的方法進行查找，直到查找成功或子表長度為2、若在長度為N的線性表中進行二分查找，在最壞情況下，需要比較3、二分法查找只適用于順序存儲的有序表。（）例：1.對長度為N的線性表進行

17、順序查找，在最壞情況下所需要的比較次數(shù)為（A）Log2 nB）nC）n+1D） n/22. 下列敘述中正確的是【10年3月】CA）對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數(shù)為n(n/2)B）對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為C）對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為（Iog2n）D）對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為（n Iog2n）3. 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是（）【05年9月】A）順序存儲的有序線性表B）線性鏈表C）二叉鏈表D）有序性鏈表卜六、排序技術(shù)大綱要求：基本排序算法（交換類排序、選擇

18、類排序、插入類排序）（一）交換類排序法（1）冒泡排序法1 、排序方法：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換；然后，從后到前掃描剩下的 線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小，若相鄰兩個元素中，后面的元素 小于前面的元素，則將它們互換；重復(fù)上述過程，直到剩下的線性表變空為止。（）2 、最壞情況比較次數(shù)為：N（N-1）/2（ ）注：成有序。（2）快速排序法1、排序方法：從線性表中選取一個元素，設(shè)為T,將線性表后面小于 T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱

19、為兩個子表）,T插入到其分界線的 位置處，這個過程稱為線性表的分割 ；對分割后的各子表再按上述原則進行分割，直到所有子表為空為止，則此時的線性表就變成了有序表（ ）2、 最壞情況比較次數(shù)為：N（N-1）/2（ ）3、 快速排序方法在被排序數(shù)據(jù)已基本有序的情況下最不利于發(fā)揮其長處。（）注:快速排序法的關(guān)鍵是對線性表進行分割，以及對各分割出的子表再進行分割。（二）插入類排序法（1 ）簡單插入排序法插入排序一一將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。1 、方法：在線性表中，只包含第1個元素的子表顯然可以看成是有序表。然后，從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入

20、到前面已經(jīng)有序的子表中。（）2 、最壞情況比較次數(shù)為：N（N-1）/2（ ）注：簡單插入排序的效率與冒泡排序法的效率相同。（）（2）希爾排序法1、方法：將整個無序序列分割成若干個小的子序列分別進行插入排序。分割方法：將相隔某個增量H的元素構(gòu)成一個子序列，在排序過程中，逐次減小這個增量，最后當(dāng)H減到1時，進行一次插入排序，排序就完成了。（ ）1.52、最壞情況比較次數(shù)為：N （）（三）選擇類排序法（1）簡單選擇排序法1 、方法：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。（）2 、最壞情況比較次數(shù)為：N（N-1）/2（ ）（2）堆排序

21、法1 、方法：首先將一個無序序列建成堆，然后將堆頂元素與堆中最后一個元素交換；不考慮已經(jīng)換到最后的那個元素，只考慮前n-1個元素構(gòu)成的子序列，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)整為堆，反復(fù)做前一步，直到剩下 的子序列為空為止。2 、最壞情況比較次數(shù)為：NLOG專）注：堆排序方法不適合規(guī)模較小的線性表，對較大規(guī)模的線性表是很有效的。例：1.冒泡排序在最壞情況下的比較次數(shù)是（）【07年9月】。A）n（ n + 1） 12B） nIog2 nC） n （n 1） 12 D）n 12）【08年4月】2. 對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n（n-1）/2的排序

22、方法是（A ）快速排序 B）冒泡排序 C）直接插入排序D）堆排序第二章程序設(shè)計基礎(chǔ)第一部分程序設(shè)計方法與風(fēng)格大綱要求：程序設(shè)計方法與風(fēng)格（一）程序設(shè)計方法就程序設(shè)計方法和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計和面向?qū)ο蟮某绦蛟O(shè)計階段。（二）程序設(shè)計風(fēng)格程序設(shè)計的總體風(fēng)格是： 強調(diào)簡單和清晰，程序必須是可以理解的（可讀性好），即“清晰第一，效率第二（）形成良好程序設(shè)計風(fēng)格應(yīng)考慮以下幾個因素：（，不需要背，但要熟悉）（1）源程序文檔化 （要有必要的注釋）1、注釋一般分為序言性注釋和功能性注釋。序言性注釋：位于每個程序的開頭部分，它給出程序的整體說明。 功能性注釋：一般嵌在程序體之中，主要描述其后

23、的語句或程序做什么。（2）數(shù)據(jù)說明的方法注意數(shù)據(jù)說明的風(fēng)格，以便使程序中的數(shù)據(jù)說明更易于理解和維護（3）語句的結(jié)構(gòu)（優(yōu)先考慮清晰性）程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化，一般應(yīng)注意以下幾占：八、1、程序編寫應(yīng)優(yōu)先考慮清晰性；2、避免采用復(fù)雜的條件語句；3、盡量減少使用“否定”條件的條件語句；4、要模塊化，使模塊功能盡可能單一化；5、利用信息隱蔽，確保每一個模塊的獨立性；6、從數(shù)據(jù)出發(fā)去構(gòu)造程序；7、不要修補不好的程序，要重新編寫；8、盡可能使用庫函數(shù)；9、避免使用臨時變量而使程序的可讀性下降；（4）輸入和輸出（輸入數(shù)據(jù)前后要有提示信息）輸入和輸出方式和格式應(yīng)盡

24、可能方便用戶的使用，因為系統(tǒng)能否被用戶接受，往往取決于輸入和輸出的風(fēng)格。例：1.下列敘述中，不符合良好程序設(shè)計風(fēng)格要求的是（）【07年9月】。A）程序的效率第一，清晰第二B ）程序的可讀性好C）程序中要有必要的注釋D）輸入數(shù)據(jù)前要有提示信息第二部分結(jié)構(gòu)化程序設(shè)計大綱要求：結(jié)構(gòu)化程序設(shè)計（一）結(jié)構(gòu)化程序設(shè)計方法的主要原則（背）自頂向下，逐步求精（細化），模塊化，限制使用 goto語句。（二）結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)（背）順序結(jié)構(gòu)、選擇結(jié)構(gòu)（分支結(jié)構(gòu)）、循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）（三）在結(jié)構(gòu)化程序設(shè)計的具體實施中，要注意把握以下要素：1、使用順序、選擇、循環(huán)等控制結(jié)構(gòu)2、控制結(jié)構(gòu)只準(zhǔn)許有一個入口和一個出

25、口3、復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進行組合嵌套4、嚴格控制GOTO語句的使用例：1.下列選項中不屬于結(jié)構(gòu)化程序設(shè)計方法的是（）【06年4月】A）自頂向下B）逐步求精C）模塊化D）可復(fù)用第三部分面向?qū)ο蟮某绦蛟O(shè)計大綱要求：面向?qū)ο蟮某绦蛟O(shè)計方法，對象、方法、屬性及繼承與多態(tài)性（一）面向?qū)ο蠓椒ㄓ幸韵轮饕獌?yōu)點：1、與人類習(xí)慣的思維方法一致2、穩(wěn)定性好3、可重用性好4、易于開發(fā)大型軟件產(chǎn)品5、可維護性好注：面向?qū)ο蠓椒ㄅc面向過程的方法的本質(zhì)區(qū)別在于一一面向?qū)ο蠓椒ㄊ鞘褂矛F(xiàn)實世界的概念抽象地思 考問題從而自然地解決問題，它強調(diào)模擬現(xiàn)實世界中的概念而不強調(diào)算法。（二）面向?qū)ο蠓椒ǖ幕靖拍睿?）對象

26、1、對象一一是由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的所有操作所組成的統(tǒng)一體。對象可以 用來表示客觀世界中的任何實體，在應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何 事件都可以作為對象，它既可以是具體的物理實體的抽象，也可以是人為的概念，或者是任 何明確邊界和意義的東西。2、屬性一一對象所包含的信息，它是在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。3、操作一一描述對象執(zhí)行的功能，若通過消息傳遞，還可以為其它對象使用。通常把對象的操作也稱為方法或服務(wù)。4、 對象的基本特點：（背） 標(biāo)識唯一性：指對象是可區(qū)分的，并且由對象的內(nèi)在本質(zhì)來區(qū)分。 分類性：可以將具有相同屬性和操作的對象

27、抽象成類。 多態(tài)性：指同一個操作可以是不同對象的行為。 封裝性：從外面看只能看到對象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法；信息隱蔽就是通過封裝性來實現(xiàn) 的。（記） 模塊獨立性好對象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強。5、面向?qū)ο蟪绦蛟O(shè)計的三大特征：繼承、封裝、多態(tài)（背）（2）類1、類一一具有共同屬性、共同方法的對象的集合。類是對象的抽象，它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實例。（背）2、類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。 例：1.在面向?qū)ο蠓?/p>

28、法中，【06年4月】描述的是具有相似屬性與操作的一組對象。2. 在面向?qū)ο蠓椒ㄖ校惖膶嵗Q為【05年4月】。（3）消息1、 消息一一指對象間的相互合作需要一個機制協(xié)助進行，這樣的機制稱為“消息”。2、消息是一個實例與另一個實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息， 它統(tǒng)一了數(shù)據(jù)流和控制流。（記）3、一個對象能夠接受不同形式、不同內(nèi)容的多個消息；相同形式的消息可以送往不同的對象； 不同的對象對于形式相同的消息可以有不同的解釋，能夠做出不同的反映；一個對象可以同時往多 個對象傳遞信息，兩個對象也可以同時向某個對象傳遞消息。4、 消息由三部分組成：接收消息的對象的名稱；消息標(biāo)

29、識符（也稱消息名）；零個或多個參數(shù)。 女口： MYFORM.BOX（10,20）其中MYFOR是接收消息的對象名， BOX是消息名，10和20是消息的參數(shù)。繼承1 、繼承一一類之間共享屬性和操作的機制稱為繼承。廣義地說，即是指能夠直接獲得已有的性質(zhì)和牲征，而不必重復(fù)定義它們。2 、繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征。提高了軟件的可重用性和擴充性。（記）3 、繼承分為單繼承和多重繼承。單繼承一一一個類只允許有一個父類。多重繼承一一一個類允許有多個父類。（5）多態(tài)性1、 多態(tài)性同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。（記）2、多態(tài)性不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進

30、一步減少了信息冗余，而且顯著地提高了軟件 的可重用性和可擴充性。第三章軟件工程基礎(chǔ)第一部分軟件工程基本概念大綱要求：軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。（一）軟件的定義及其特點1、計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 背）例：1.軟件是指（）【07年9月】A）程序B）程序和文檔C）算法加數(shù)據(jù)結(jié)構(gòu)D）程序、數(shù)據(jù)與相關(guān)文檔的完整集合2、軟件的特點 軟件是一種邏輯實體，而不是物理實體，具有抽象性。 軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程。 軟件在運行、使用期間不存在磨損、老化問題。 軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性

31、，受計算機系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題。 軟件復(fù)雜性高，成本昂貴。（是人類有史以來生產(chǎn)的復(fù)雜度最高的工業(yè)產(chǎn)品） 軟件開發(fā)涉及諸多的社會因素。3、 軟件分類：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）（理解各種軟件屬于哪一類） 應(yīng)用軟件包括：事務(wù)處理軟件，工程與科學(xué)計算軟件，實時處理軟件，嵌入式軟件，人工智能軟件等。例 女口：辦公自動化軟件、成績管理系統(tǒng)等。 系統(tǒng)軟件包括：操作系統(tǒng)，編譯程序，匯編程序，網(wǎng)絡(luò)軟件，數(shù)據(jù)庫管理系統(tǒng)等。 支撐軟件包括：需求分析工具軟件，設(shè)計工具軟件，編碼工具軟件，測試工具軟件，維護工具軟件等（二）軟件工程1、軟件工程：是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套

32、方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。2、 軟件工程包括三個要素：方法、工具和過程。（背）3、1968年在北大西洋公約組織會議（NATO會議）上，軟件工程作為一個概念首次被提出，這在軟件技術(shù) 發(fā)展史上是一件大事。注：軟件工程概念的出現(xiàn)源自軟件危機。（記）例：1.下列描述中正確的是（C）【05年9月】A）軟件工程只是解決軟件項目的管理問題B）軟件工程只是解決軟件產(chǎn)品的生產(chǎn)率問題C）軟件工程的主要思想是強調(diào)在軟件開發(fā)工程中需要應(yīng)用工程化原則D）軟件工程只是解決軟件開發(fā)過程中的技術(shù)問題（三）軟件工程過程1、軟件工程過程一一是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。2、軟件工程過程的4種基本活動： P

33、（Plan）軟件規(guī)格說明。規(guī)定軟件的功能及其運行時的限制。 D（Do）軟件開發(fā)。產(chǎn)生滿足規(guī)格說明的軟件。 C（Check）軟件確認。確認軟件能夠滿足客戶提出的要求。 A（Acti on）軟件演進。為滿足客戶的變更要求，軟件必須在使用的過程中演進。（四）軟件生命周期（軟件生命周期）1軟件生命周期一一軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。（背）2、軟件生命周期的三個階段：軟件定義、軟件開發(fā)、軟件運行維護（費用最多的階段）（背，知道上圖中每個活動屬于哪個階段）注：軟件開發(fā)階段包括一一設(shè)計（包括概要設(shè)計和詳細設(shè)計）、實現(xiàn)（編碼）和測試 軟件運行維護階段包括一一使用、維護和

34、退役例：1.下列敘述中正確的是（）【05年9月】A）軟件交付使用后還需要進行維護B）軟件一旦交付使用就不需要再進行維護C）軟件交付使用后期生命周期就結(jié)束D）軟件維護是指修復(fù)程序中被破壞的指令2. 軟件生命周期可分為定義階段，開發(fā)階段和維護階段。詳細設(shè)計屬于【10年3月】A定義階段B）開發(fā)階段C）維護階段D）上述三個階段（五）軟件工程的目標(biāo)與原則1、軟件工程的基本目標(biāo)：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用。2、軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工 3、軟件工程的基本原則：抽象、信

35、息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。（六）軟件開發(fā)工具與軟件開發(fā)環(huán)境1、軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。2、工具和環(huán)境的使用進一步提高了軟件的開發(fā)效率、維護效率和軟件質(zhì)量。3、計算機輔助軟件工程（CASE ）是當(dāng)前軟件開發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。第二部分結(jié)構(gòu)化分析方法大綱要求：結(jié)構(gòu)分析方法，數(shù)據(jù)流圖、數(shù)據(jù)字典、軟件需求規(guī)格說明書一、需求分析階段可以概括為四個方面：1、需求獲取2、需求分析3、編寫需求規(guī)格說明書（是需求分析的階段成果）4、需求評審注： （）二、需求分析方法1、結(jié)構(gòu)化分析方法 面向數(shù)據(jù)流的結(jié)構(gòu)化分析（SA） 面向數(shù)據(jù)結(jié)構(gòu)的 Ja

36、cks on方法（JSD） 面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD2、面向?qū)ο蟮姆治龇椒ǎ?0A三、結(jié)構(gòu)化分析的常用工具（1）數(shù)據(jù)流圖（DFD數(shù)據(jù)流圖一一是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。主要用于概要設(shè)計階段。（，記）數(shù)據(jù)流圖的主要圖形元素：（,記）1、 加工（轉(zhuǎn)換）輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。2、*數(shù)據(jù)流一一沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。3、 一存儲文件（數(shù)據(jù)源）表示處理過程中存放各種數(shù)據(jù)的文件。4、 |源，潭一一表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。例：1.1數(shù)據(jù)流圖中帶有箭頭的線段表示的是（）【08年9月】A

37、 ）控制流B ）事件驅(qū)動C）模塊調(diào)用D）數(shù)據(jù)流注：典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。2）數(shù)據(jù)字典（DD）數(shù)據(jù)字典一一是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典的作用是對 DFD中出現(xiàn)的被命名的圖形元素的確切解釋。通常數(shù)據(jù)字典包含的信息有:名稱、別名、何處使用/如何使用、內(nèi)容描述、補充信息等。數(shù)據(jù)字典中出現(xiàn)的符號：符號含義=表示“等于”，“定義為”，“由什么構(gòu)成”|表示“或”即選擇括號中用“ | ”號分隔的各項中的某一項+ 表示“與”，“和”nm表示“重復(fù)”，即括號中的項要重復(fù)若干次，n,m是重復(fù)次數(shù)的上下限（表示“可選”，即括號中的項可以沒有*表示“注釋”.表示“連接符”（3）判定樹（4）判定表四

38、、軟件需求規(guī)格說明書 軟件需求規(guī)格說明書（SRS）是需求分析階段的得出的最主要的文檔，也是主要成果，是軟件開發(fā)中的重要文檔之一。（，記）例：1.在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是（）【08年4月】A ）可行性分析報告B）軟件需求規(guī)格說明書C）概要設(shè)計說明書D）做成測試計劃2. 軟件開發(fā)過程主要分為需求分析、設(shè)計、編碼與測試四個階段，其中階段產(chǎn)生 軟件需求規(guī)格說明書”軟件需要規(guī)格說明書的作用：1、便于用戶、開發(fā)人員進行理解和交流。2、反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)。3、作為確認測試和驗收的依據(jù)注：軟件需求規(guī)格說明書應(yīng)具有完整性，無岐義性、正確性、可驗證性、可修改性

39、等特征，其中最重 要的是無岐義性。第三部分結(jié)構(gòu)化設(shè)計方法大綱要求：結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細設(shè)計一、軟件設(shè)計的基礎(chǔ)1、軟件設(shè)計是軟件工程的重要階段，是一個把軟件需求轉(zhuǎn)換為軟件表示的過程。2、從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。（，背） 軟件結(jié)構(gòu)設(shè)計一一是定義軟件系統(tǒng)主要部件之間的關(guān)系。 數(shù)據(jù)設(shè)計一一是將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。 接口設(shè)計一一是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。 過程設(shè)計一一是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。3、從工程管理角度來看，軟件設(shè)計分兩步完成：概要設(shè)計和詳細設(shè)計。（，背） 概要設(shè)計：又稱結(jié)

40、構(gòu)設(shè)計，是將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級接口、全局數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式。 詳細設(shè)計：確立每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。例：1.從工程管理角度，軟件設(shè)計一般分為兩步完成，它們是（）【06年9月】A ）概要設(shè)計與詳細設(shè)計 B ）數(shù)據(jù)設(shè)計與接口設(shè)計 C ）軟件結(jié)構(gòu)設(shè)計與數(shù)據(jù)設(shè)計 D）過程設(shè)計與數(shù)據(jù)設(shè)計二、軟件設(shè)計的基本原理（1）是把事物本質(zhì)的共同特性提取出來而不考慮其他細節(jié)。（2）模塊化一指解決一個復(fù)雜問題時自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。（3）信息隱蔽一一在一個模塊內(nèi)包含的信息，對于不需要這些信息的其他模塊來說是不能訪問的，一般采用封裝技術(shù)來實現(xiàn)。（4）模塊獨立性一一每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單（即高內(nèi)聚低耦合）。（,背）衡量軟件的模塊獨立性：使用耦合性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn)。（，背）內(nèi)聚性一一指一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程序的度量，內(nèi)聚由弱到強分別為：偶然內(nèi) 聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚和功能內(nèi)聚（記）耦合性一一指模塊間互相連接的緊密程度的度量，耦合由高到低分別為：內(nèi)容耦合、公共耦合、外 部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非