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

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

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

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

4、個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜必定小D）上述三種說(shuō)法都不對(duì)第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)大綱要求：數(shù)據(jù)結(jié)構(gòu)的定義，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(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ù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成的集合。通常也指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)兩種。2、 數(shù)據(jù)的邏輯結(jié)構(gòu)一一反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。（）3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一一數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，即各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系。（）4

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

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

7、算機(jī)中的表示如：一年四季的數(shù)據(jù)結(jié)構(gòu)用圖形表示為6、數(shù)據(jù)結(jié)構(gòu)的符號(hào)表示：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)的分類(lèi)）（）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)所滿(mǎn)足的條件： 有且只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)，也最多有一個(gè)直接后繼；線性結(jié)構(gòu)又稱(chēng)為線性表，如：線性表、棧、隊(duì)列、循環(huán)對(duì)列、線性鏈表、循環(huán)鏈表等屬線性結(jié)構(gòu)。（）10、非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)之為非線性結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、一步減少了信息冗余，而且顯著地提高了軟件 的可重用性和可擴(kuò)充性。第三章軟件工程基礎(chǔ)第一部分軟件工程基本概念大綱要求：軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。（一）軟件的定義及其特點(diǎn)1、計(jì)算機(jī)軟件是計(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) 軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性。 軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程。 軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題。 軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性

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

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

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

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

35、息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。（六）軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境1、軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。2、工具和環(huán)境的使用進(jìn)一步提高了軟件的開(kāi)發(fā)效率、維護(hù)效率和軟件質(zhì)量。3、計(jì)算機(jī)輔助軟件工程（CASE ）是當(dāng)前軟件開(kāi)發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。第二部分結(jié)構(gòu)化分析方法大綱要求：結(jié)構(gòu)分析方法，數(shù)據(jù)流圖、數(shù)據(jù)字典、軟件需求規(guī)格說(shuō)明書(shū)一、需求分析階段可以概括為四個(gè)方面：1、需求獲取2、需求分析3、編寫(xiě)需求規(guī)格說(shuō)明書(shū)（是需求分析的階段成果）4、需求評(píng)審注： （）二、需求分析方法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)開(kāi)發(fā)方法（DSSD2、面向?qū)ο蟮姆治龇椒ǎ?0A三、結(jié)構(gòu)化分析的常用工具（1）數(shù)據(jù)流圖（DFD數(shù)據(jù)流圖一一是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。主要用于概要設(shè)計(jì)階段。（，記）數(shù)據(jù)流圖的主要圖形元素：（,記）1、 加工（轉(zhuǎn)換）輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。2、*數(shù)據(jù)流一一沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。3、 一存儲(chǔ)文件（數(shù)據(jù)源）表示處理過(guò)程中存放各種數(shù)據(jù)的文件。4、 |源，潭一一表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。例：1.1數(shù)據(jù)流圖中帶有箭頭的線段表示的是（）【08年9月】A

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

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

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

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