公共基礎(chǔ)知識復(fù)習(xí)重點(diǎn)(權(quán)威老師總結(jié),絕對正宗,復(fù)習(xí)考試必過,考證的同學(xué)必看)

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

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

3、時間復(fù)雜度：執(zhí)行算法所需要的計算工作量，也就是耗費(fèi)的時間量。是對算法時間效率的度量。2、空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間，是對算法所需存儲空間的度量。3、空間復(fù)雜度與空間復(fù)雜度是從兩個方面對算法的效率進(jìn)行度量，兩者之間沒有必然的聯(lián)系。例：1.算法的空間復(fù)雜度是指（ A ）。【09年9月】A.算法在執(zhí)行過程中所需要的計算機(jī)存儲空間 B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù) D.算法在執(zhí)行過程中所需要的臨時工作單元數(shù)2. 算法復(fù)雜度主要包括時間和 【05年9月】 復(fù)雜度。3. 下列敘述中正確的是（ D ）【06年9月】 A）一個算法的空間復(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)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)，即各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系。（）4、數(shù)據(jù)

5、存儲結(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月】A)一個邏輯數(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月】A）算法的效率只與

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)3. 下列敘述中正確的是( ) 【07年9月】。 A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的 B）由于計算機(jī)存儲空間是向量式的存儲結(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月】 A)存儲在外存中的數(shù)據(jù) B)數(shù)據(jù)在外存中的數(shù)據(jù) C)數(shù)據(jù)在計算機(jī)中的順序存儲方式 D)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的

7、表示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)系。 如：一年四季的數(shù)據(jù)結(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) 非線性結(jié)構(gòu)9、線性結(jié)構(gòu)所滿足的條件：有且只有一個根結(jié)點(diǎn)；每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件； 線性結(jié)構(gòu)又稱為線性表，如：線性表、棧、隊列、循環(huán)對列、線性鏈表、循環(huán)鏈表等屬線性結(jié)構(gòu)。（）10、非線性結(jié)構(gòu)：如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。如：

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

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

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

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

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

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

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

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

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

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

18、排序算法（交換類排序、選擇類排序、插入類排序） （一）交換類排序法 （1）冒泡排序法 1、排序方法：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換；然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小，若相鄰兩個元素中，后面的元素小于前面的元素，則將它們互換；重復(fù)上述過程，直到剩下的線性表變空為止。() 2、最壞情況比較次數(shù)為：N(N-1)/2() 注：冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。 （2）快速排序法 1、排序方法：從線性表中選取一

19、個元素,設(shè)為T,將線性表后面小于T的元素移到前面,而前面大于T的元素移到后面,結(jié)果就將線性表分成了兩部分(稱為兩個子表),T插入到其分界線的位置處,這個過程稱為線性表的分割;對分割后的各子表再按上述原則進(jìn)行分割,直到所有子表為空為止,則此時的線性表就變成了有序表. ()2、最壞情況比較次數(shù)為：N(N-1)/2()3、快速排序方法在被排序數(shù)據(jù)已基本有序的情況下最不利于發(fā)揮其長處。()注:快速排序法的關(guān)鍵是對線性表進(jìn)行分割,以及對各分割出的子表再進(jìn)行分割。 （二）插入類排序法 （1）簡單插入排序法 插入排序?qū)o序序列中的各元素依次插入到已經(jīng)有序的線性表中。 1、方法：在線性表中，只包含第1個元素的

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

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

22、2 2. 對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是（ ）【08年4月】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)格是：強(qiáng)調(diào)簡單和清晰，程序必須是可以理解的（可讀性好），即“清晰第一，效率第二”（）形成良好程序設(shè)計風(fēng)格應(yīng)考慮以下幾個因素：（，不需要背，但要熟悉） （1）源程序文檔化 1、注釋一般分為序言性注釋和功能性注釋。 序言性注釋

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

24、量而使程序的可讀性下降； （4）輸入和輸出 輸入和輸出方式和格式應(yīng)盡可能方便用戶的使用，因為系統(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è)計方法的主要原則（背） 自頂向下，逐步求精(細(xì)化)，模塊化，限制使用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è)計的具體實施中，要注意把握

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

26、地思考問題從而自然地解決問題，它強(qiáng)調(diào)模擬現(xiàn)實世界中的概念而不強(qiáng)調(diào)算法。（二）面向?qū)ο蠓椒ǖ幕靖拍?（1）對象1、對象是由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的所有操作所組成的統(tǒng)一體。對象可以用來表示客觀世界中的任何實體，在應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何事件都可以作為對象，它既可以是具體的物理實體的抽象，也可以是人為的概念，或者是任何明確邊界和意義的東西。 2、屬性對象所包含的信息，它是在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。 3、操作描述對象執(zhí)行的功能，若通過消息傳遞，還可以為其它對象使用。通常把對象的操作也稱為方法或服務(wù)。 4、對象的基本特點(diǎn)：（背） 標(biāo)

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

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

29、象也可以同時向某個對象傳遞消息。 4、消息由三部分組成：接收消息的對象的名稱；消息標(biāo)識符（也稱消息名）；零個或多個參數(shù)。 如：MYFORM.BOX(10,20) 其中MYFORM是接收消息的對象名，BOX是消息名，10和20是消息的參數(shù)。(4)繼承 1、繼承類之間共享屬性和操作的機(jī)制稱為繼承。廣義地說，即是指能夠直接獲得已有的性質(zhì)和牲征，而不必重復(fù)定義它們。 2、繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征。提高了軟件的可重用性和擴(kuò)充性。（記） 3、繼承分為單繼承和多重繼承。 單繼承一個類只允許有一個父類。 多重繼承一個類允許有多個父類。 (5)多態(tài)性 1、多態(tài)性同樣的消息被不同的對象接受時可導(dǎo)致完全不

30、同的行動，該現(xiàn)象稱為多態(tài)性。（記）2、多態(tài)性不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進(jìn)一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴(kuò)充性。第三章 軟件工程基礎(chǔ) 第一部分 軟件工程基本概念大綱要求：軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。(一)軟件的定義及其特點(diǎn)1、計算機(jī)軟件是計算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。（背）例：1. 軟件是指（ ）【07年9月】 A）程序B）程序和文檔 C）算法加數(shù)據(jù)結(jié)構(gòu)D）程序、數(shù)據(jù)與相關(guān)文檔的完整集合2、軟件的特點(diǎn)軟件是一種邏輯實體，而不是物理實體，具有抽象性。軟件的生產(chǎn)與硬件不同，它沒有明顯的制作

31、過程。軟件在運(yùn)行、使用期間不存在磨損、老化問題。軟件的開發(fā)、運(yùn)行對計算機(jī)系統(tǒng)具有依賴性，受計算機(jī)系統(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è)計工具軟件，編碼工具軟件，測試工具軟件，維護(hù)工具軟件等(

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

33、出的一組彼此相關(guān)的資源和活動。 2、軟件工程過程的4種基本活動： P(Plan)軟件規(guī)格說明。規(guī)定軟件的功能及其運(yùn)行時的限制。D(Do)軟件開發(fā)。產(chǎn)生滿足規(guī)格說明的軟件。C(Check)軟件確認(rèn)。確認(rèn)軟件能夠滿足客戶提出的要求。A(Action)軟件演進(jìn)。為滿足客戶的變更要求，軟件必須在使用的過程中演進(jìn)。(四)軟件生命周期1、軟件生命周期軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生命周期。（背）2、軟件生命周期的三個階段：軟件定義、軟件開發(fā)、軟件運(yùn)行維護(hù)（費(fèi)用最多的階段）（背） 注：軟件開發(fā)階段包括設(shè)計（包括概要設(shè)計和詳細(xì)設(shè)計）、實現(xiàn)（編碼）和測試 軟件運(yùn)行維護(hù)階段包括使用、維護(hù)和退役例：1. 下列敘述中正確的是（ ）【05年9月】A)軟件交付使用后還需要進(jìn)行維護(hù) B)軟件一旦交付使用就不需要再進(jìn)行維護(hù)C)軟件交付使