第一章 數(shù)據(jù)結(jié)構(gòu)與算法筆試題基礎(chǔ)

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法一.算法的基本概念計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報。2.算法的基本要素：算法中對數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲量需求二.算法的復(fù)雜度1.算法的時間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量2.算法的空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間三.數(shù)據(jù)結(jié)構(gòu)的定義1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)

2、構(gòu)和圖形結(jié)構(gòu)四種。2.數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間種的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分解、復(fù)制和修改等。五.線性結(jié)構(gòu)和非線性結(jié)構(gòu)根據(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)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個根結(jié)點(diǎn)；每個結(jié)點(diǎn)最多有一個前件，最多只有一個后件。非線性結(jié)構(gòu)：如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。常見的線性

3、結(jié)構(gòu)：線性表、棧、隊(duì)列六.線性表的定義線性表是n 個元素構(gòu)成的有限序列（A1，A2，A3）。表中的每一個數(shù)據(jù)元素，除了第一個以外，有且只有一個前件。除了最后一個以外有且只有一個后件。即線性表是一個空表，或可以表示為（a1,a2,an）, 其中ai(I=1,2,n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點(diǎn)。非空線性表有如下一些特征：（1）有且只有一個根結(jié)點(diǎn)a1,它無前件；（2）有且只有一個終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。線性表中結(jié)點(diǎn)的個數(shù)n稱為線性表的長度。當(dāng)n=0時稱為空表。七.線性表的順序存儲結(jié)構(gòu)線性表的順序表

4、指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具備如下兩個基本特征：1.線性表中的所有元素所占的存儲空間是連續(xù)的；2.線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。即線性表邏輯上相鄰、物理也相鄰，則已知第一個元素首地址和每個元素所占字節(jié)數(shù)，則可求出任一個元素首地址。假設(shè)線性表的每個元素需占用K個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系:LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+(i-1)*K 其

5、中，LOC(a1)是線性表的第一個數(shù)據(jù)元素a1的存儲位置，通常稱做線性表的起始位置或基地址。因?yàn)樵陧樞虼鎯Y(jié)構(gòu)中，每個數(shù)據(jù)元素地址可以通過公式計(jì)算得到，所以線性表的順序存儲結(jié)構(gòu)是隨機(jī)存取的存儲結(jié)構(gòu)。在線性表的順序存儲結(jié)構(gòu)下，可以對線性表做以下運(yùn)算：插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)八.順序表的插入運(yùn)算線性表的插入運(yùn)算是指在表的第I個位置上，插入一個新結(jié)點(diǎn)x，使長度為n的線性表（a1,a2 aian）變成長度為n+1的線性表(a1,a2x,aian).該算法的時間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，執(zhí)行次數(shù)是n-I+1。當(dāng)I=n+1,最好情況，時間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時

6、間復(fù)雜度o(n)算法的平均時間復(fù)雜度為o(n)九.順序表的刪除運(yùn)算線性表的刪除運(yùn)算是指在表的第I個位置上，刪除一個新結(jié)點(diǎn)x，使長度為n的線性表（a1,a2 aian）變成長度為n-1的線性表(a1,a2ai-1,ai+1an).當(dāng)I=n,時間復(fù)雜度o(1),當(dāng)I=1,時間復(fù)雜度o(n) ,平均時間復(fù)雜度為o(n)十.棧及其基本運(yùn)算1.什么是棧？棧實(shí)際上也是一個線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（TOP），另一端為棧底（BOTTOM）。當(dāng)表中沒有元素時稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素

7、總是最先被插入的元素，從而也是最后才能被刪除的元素。假設(shè)棧S=（a1,a2,a3,an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3an的次序進(jìn)棧，退棧的第一個元素應(yīng)該是棧頂元素。即后進(jìn)先出。2.棧的順序存儲及其運(yùn)算用S（1：M）作為棧的順序存儲空間。M為棧的最大容量。棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：在棧頂位置插入一個新元素。首先將棧頂指針進(jìn)一（TOP+1），然后將新元素插入到棧頂指針指向的位置。退棧運(yùn)算：指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一（TOP-1）讀棧頂元素：將棧頂元素賦給一個指定的變量。

8、棧頂指針不會改變。十一.隊(duì)列及其基本運(yùn)算1.什么是隊(duì)列隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做對頭，允許插入的一端叫做對尾。隊(duì)列的修改是先進(jìn)先出。往隊(duì)尾插入一個元素成為入隊(duì)運(yùn)算。從對頭刪除一個元素稱為退隊(duì)運(yùn)算。2.循環(huán)隊(duì)列及其運(yùn)算在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置直到隊(duì)尾指針 rear指向的位置之間所有的元素均為隊(duì)列中的元素。

9、在實(shí)際使用循環(huán)隊(duì)列時，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個標(biāo)志S：隊(duì)列空，則S=0，rear=front=m 隊(duì)列滿，則S=1，rear=front=m循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算n 入隊(duì)運(yùn)算指在循環(huán)隊(duì)列的隊(duì)尾加入一個新元素，首先rear=rear+1,當(dāng)rear=m+1時，置rear=1,然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)S=1，rear=front,說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。n 退隊(duì)運(yùn)算指在循環(huán)隊(duì)列的排頭位置退出一個元素并賦給指定的變量。首先front=front+1,并當(dāng)front=m+1時，置front=1,然后將排頭指針指向的元素賦給

10、指定的變量。當(dāng)循環(huán)隊(duì)列為空S=0，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。十二.線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算1.線性單鏈表的基本概念一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，因此，為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。這兩部分信息組成數(shù)據(jù)元素ai的存儲映象，成為結(jié)點(diǎn)。它包括兩個域：其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。N個結(jié)點(diǎn)鏈結(jié)成一個鏈表，即為線性表(a1, a2,an)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。又由于此鏈

11、表的每個結(jié)點(diǎn)中只包含一個指針域，故又稱線性鏈表或單鏈表。有時，我們在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，它指向表中第一個結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可存儲如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲指向第一個結(jié)點(diǎn)的指針（即第一個元素結(jié)點(diǎn)的存儲位置）。在單鏈表中，取得第I個數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲結(jié)構(gòu) 鏈表的形式：單向，雙向2.線性單鏈表的存儲結(jié)構(gòu)3帶鏈3.帶列的棧與隊(duì)列棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。十三.線性鏈表的基本運(yùn)算 1.線性鏈表的插入 2.線性鏈表的刪除十四.雙向鏈表的結(jié)

12、構(gòu)及其基本運(yùn)算在雙向鏈表的結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前驅(qū)。十五.循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的特點(diǎn)是表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。因此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。十六.樹的定義樹是一種簡單的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)的特點(diǎn)：1.每個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個，稱為樹的根結(jié)點(diǎn)。2.每一個結(jié)點(diǎn)可以有多個后件結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)3.一個結(jié)點(diǎn)所擁有的后件個數(shù)稱為樹的結(jié)點(diǎn)度4.樹的最大層次稱為樹的深度。十七.二叉樹的定義及其基本性質(zhì)1.二叉樹是另一種樹型結(jié)構(gòu)，它

13、的特點(diǎn)是每個結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.二叉樹的基本性質(zhì)在二叉樹的第I層上至多有2i-1個結(jié)點(diǎn)。深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)(k=1)在任意一個二叉樹中，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個；具有n 個結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1。一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。3.滿二叉樹與完全二叉樹滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。在滿二叉樹的第K層上有2K-1個結(jié)點(diǎn)，且深度為M的滿二叉樹右2M-1個結(jié)點(diǎn)完全二叉樹

14、：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有N個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1完全二叉樹總結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2 若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/24.二叉樹的存儲結(jié)構(gòu)二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹具有下列重要特性：性質(zhì)1在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)(i1)。 利用歸納法容易證得此性質(zhì)。 i=1時，只有一個根結(jié)點(diǎn)。 顯然，2i-1=20=1是對的。 現(xiàn)在假定對所有的j，1jnext=head）29.與單向鏈表相比，雙向鏈表的優(yōu)點(diǎn)之一是（更容易訪問相鄰結(jié)點(diǎn)） 30. 在（D）中，只要指出表中任何一個結(jié)點(diǎn)的位

15、置，就可以從它出發(fā)依次訪問到表中其他所有結(jié)點(diǎn)。A線性單鏈表 B雙向鏈表 C線性鏈表 D循環(huán)鏈表31. 以下數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)結(jié)構(gòu)的是（C）A隊(duì)列 B線性表C二叉樹 D棧32.樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（有且只有1）33.具有3個結(jié)點(diǎn)的二叉樹有（5種形態(tài)） 34. 在一棵二叉樹上第8層的結(jié)點(diǎn)數(shù)最多是（128） 注：2K-135. 在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為（16） 注：2n-136. 在深度為5的滿二叉樹中，共有（31）個結(jié)點(diǎn)。 注：2n137.設(shè)一棵完全二叉樹共有699個結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（350）說明：完全二叉樹總結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為

16、（N+1）/2；若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2。38. 設(shè)有下列二叉樹，對此二叉樹中序遍歷的結(jié)果是（B）AABCDEF BDBEAFCCABDECF DDEBFCA39.已知二叉樹后序遍歷序列是dabec，中序遍歷序列debac，它的前序遍歷序列是（cedba） 40. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）41.若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是（gdbehfca）42. 串的長度是（串中所含字符的個數(shù)） 43.設(shè)有兩個串p和q，求q在

17、p中首次出現(xiàn)位置的運(yùn)算稱做（模式匹配）44. N個頂點(diǎn)的連通圖中邊的條數(shù)至少為（N-1）45.N個頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有（N）46.對長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（N）47. 最簡單的交換排序方法是（冒泡排序） 48.假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（n(n-1)/2） 49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）50. 在最壞情況下，下列順序方法中時間復(fù)雜度最小的是（堆排序） 51. 希爾排序法屬于（插入類排序）52. 堆排序法屬于（選擇類排序）53. 在下列幾種排序方法中，要求內(nèi)存量最大的是（

18、歸并排序） 54. 已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)采用（直接插入排序）55. 算法的基本特征是可行性、確定性、 有窮性 和擁有足夠的情報。1.一個算法通常由兩種基本要素組成：一是對數(shù)據(jù)對象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。1. 算法的復(fù)雜度主要包括時間復(fù)雜度和 空間 復(fù)雜度。2. 實(shí)現(xiàn)算法所需的存儲單元多少和算法的工作量大小分別稱為算法的空間復(fù)雜度和時間復(fù)雜度 。3.所謂數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算，也包括對數(shù)據(jù)元素進(jìn)行分析。4.數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的 數(shù)據(jù)元素 的集合。5.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈

19、表屬于 存儲結(jié)構(gòu) 。6.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯 結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。7. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu) 以及對數(shù)據(jù)的操作運(yùn)算。8.數(shù)據(jù)元素之間的任何關(guān)系都可以用 前趨和后繼 關(guān)系來描述。9.數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。10.常用的存儲結(jié)構(gòu)有順序、鏈接、 索引 等存儲結(jié)構(gòu)。11. 順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置 相鄰 的存儲單元中。12. 棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素 。13. 隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與 退隊(duì)運(yùn)算 。14. 在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為 可利用棧

20、。15.棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是 鏈?zhǔn)酱鎯晚樞虼鎯?。16.當(dāng)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時，其主要特點(diǎn)是 邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰 。17. 循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就 進(jìn)1 。18.當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于對頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 上溢 。19.當(dāng)循環(huán)隊(duì)列為空時，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為 下溢 。20. 在一個容量為25的循環(huán)隊(duì)列中，若頭指針front=16，尾指針rear=9，則該循環(huán)隊(duì)列中共有 18 個元素。注：當(dāng)rearfront時，元素個數(shù)rearfront。21

21、. 在一個容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有3 個元素。22.順序查找一般是指在 線性表 中查找指定的元素。23.在計(jì)算機(jī)中存放線性表，一種最簡單的方法是 順序存儲 。24.在程序設(shè)計(jì)語言中，通常定義一個 一維數(shù)組 來表示線性表的順序存儲空間。25.在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)（即前件或后件）。26.在 線性單鏈表中 ，每一個結(jié)點(diǎn)只有一個指針域，由這個指針只能找到后繼結(jié)點(diǎn)，但不能找到前驅(qū)結(jié)點(diǎn)。27. 為了要在線

22、性鏈表中插入一個新元素，首先要給該元素分配一個 新結(jié)點(diǎn) ，以便用于存儲該元素的值。28. 在線性鏈表中刪除一個元素后，只需要改變被刪除元素所在結(jié)點(diǎn)的前一個結(jié)點(diǎn)的 指針域 即可。29. 用鏈表表示線性表的突出優(yōu)點(diǎn)是 便于插入和刪除操作 。30. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前件 。31. 在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件個數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為 0 。32. 設(shè)一棵二叉樹中有3個葉子結(jié)點(diǎn)，8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 13。33. 設(shè)一棵完全二叉樹共有739個結(jié)點(diǎn)，則在該二叉樹中有 370 個葉子結(jié)點(diǎn)。34. 設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則在該二叉樹中有 350 個

23、葉子結(jié)點(diǎn)。35. 在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍歷、 中序 遍歷和后序遍歷。36. 若串S=Program，則其子串的數(shù)目是 29 。 注：n(n+1)/2+137. 若串S=”MathTypes”，則其子串的數(shù)目是 46 。38. 對長度為n的線性表進(jìn)行插入一個新元素或刪除一個元素時，在最壞情況下所需要的比較次數(shù)為 n 。39. 在長度為n的有序線性表中進(jìn)行順序查找。最壞的情況下，需要的比較次數(shù)為 n 。40. 在長度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為 log2n 。41. 長度為n的順序存儲線性表中，當(dāng)在任何位置上插入

24、一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 n/2 。42. 排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見的排序方法有插入排序、 交換排序 和選擇排序等。43. 快速排序法可以實(shí)現(xiàn)通過一次交換而消除多個 逆序 。44. 快速排序法的關(guān)鍵是對線性表進(jìn)行 分割 。45. 冒泡排序算法在最好的情況下的元素交換次數(shù)為 0 。46. 在最壞情況下，冒泡排序的時間復(fù)雜度為 n(n-1) /2 。47. 對于長度為n的線性表，在最壞情況下，快速排序所需要的比較次數(shù)為 n(n-1) /2 。48.在最壞情況下，簡單插入排序需要比較的次數(shù)為 n(n-1) /2 。49.在最壞情況下，希爾排序需要比

25、較的次數(shù)為 O(n1.5) 。注：括號里是n的1.5次方。50. 在最壞情況下，簡單選擇排序需要比較的次數(shù)為 n(n-1) /2 。51. 在最壞情況下，堆排序需要比較的次數(shù)為 o(nlog2n) 。52.對于輸入為N個數(shù)進(jìn)行快速排序算法的平均時間復(fù)雜度是 O(Nlog2 N)。第二章程序設(shè)計(jì)基礎(chǔ)一.程序設(shè)計(jì)方法與風(fēng)格當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格是“清晰第一，效率第二”的觀點(diǎn)。1.在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率。與程序的效率相比，人們更重視程序的( C )。 A.安全性 B.一致性 C.可理解性D.合理性2.對建立良好的程序設(shè)計(jì)風(fēng)格,下面的描述正確的是(A )A.程序應(yīng)簡

26、單、清晰、可讀性好 B.符號名的命名只要符合語法 C.充分考慮程序的執(zhí)行效率 D.程序的注釋可有可無3. 在設(shè)計(jì)程序時應(yīng)采納的原則之一是( D)。A.不限制GOTO語句的使用B.減少或取消注解行 C.程序越短越好 D.程序結(jié)構(gòu)應(yīng)有助于讀者理解4.程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。5.源程序文檔化要求程序應(yīng)加注釋，注釋一般分為序言性注釋和 功能性注釋 。6.在編寫程序時，需要注意 數(shù)據(jù)說明的風(fēng)格，以便使程序中的數(shù)據(jù)說明更易理解和維護(hù)。7.當(dāng)程序設(shè)計(jì)語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性 程序設(shè)計(jì)語言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成

27、分和(傳輸成分)。二.結(jié)構(gòu)化程序設(shè)計(jì)1結(jié)構(gòu)化程序設(shè)計(jì)的原則8.結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則是：自頂向下、逐步求精、模塊化、限制使用goto語句 2結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)9.結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是(B) A.程序的規(guī)模 B.程序的易讀性 C.程序的執(zhí)行效率 D.程序的可移植性 10.結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是(順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu))。結(jié)構(gòu)化程序設(shè)計(jì)方法是程序設(shè)計(jì)的先進(jìn)方法和工具。下面為三種基本的控制結(jié)構(gòu)：順序結(jié)構(gòu)：是一種簡單的程序設(shè)計(jì)，它是最基本，最常用的結(jié)構(gòu)選擇結(jié)構(gòu)：又稱為分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，有兩類循環(huán)語句：當(dāng)型循環(huán)結(jié)構(gòu)（先判斷后執(zhí)行循

28、環(huán)體）和直到型循環(huán)結(jié)構(gòu)（先執(zhí)行循環(huán)體后判斷）按結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)出的程序具有兩大明顯的優(yōu)點(diǎn)：1、程序易于理解、使用和維護(hù)。2、提高了編程工作效率，降低了軟件開發(fā)成本。3.結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用11.結(jié)構(gòu)化程序設(shè)計(jì)的主要特點(diǎn)是（每個控制結(jié)構(gòu)只有一個入口和一個出口）12.下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則的是(B)。A.自頂向下 B.由底向上 C.模塊化 D.限制使用GOTO語句在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中,要注意如下要素:使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；選用的控制結(jié)構(gòu)只準(zhǔn)許的一個入口和一個出口；程序語句組成容易識別的塊，每塊只有一個

29、入口和一人出口；復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)；語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬；嚴(yán)格控制GOTO語句的使用。其意思有三：1.用一個非結(jié)構(gòu)化的程序設(shè)計(jì)語言去實(shí)現(xiàn)一個結(jié)構(gòu)化的構(gòu)造；2.如不使用GOTO語句會使功能模糊；3.在某種可以改善而不是損害程序可讀性的情況下。三.面向?qū)ο蟮某绦蛟O(shè)計(jì)1. 關(guān)于面向?qū)ο蠓椒?5.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個 實(shí)體 傳統(tǒng)的程序設(shè)計(jì)方法是面向過程的，其核心方法是以算法 為核心。面向?qū)ο蠓椒ê图夹g(shù)以 對象 為核心。對象是由 數(shù)據(jù) 和 容許的操作 組成的封裝體，與客觀實(shí)體有直接的對應(yīng)關(guān)系。對象

30、之間通過傳遞消息 互相聯(lián)系，以模擬現(xiàn)實(shí)世界中不同事物彼此之間的聯(lián)系。 面向?qū)ο蠓椒ɑ跇?gòu)造問題領(lǐng)域的對象模型，以對象為中心構(gòu)造軟件系統(tǒng)。它的基本作法是用對象 模擬問題領(lǐng)域中的實(shí)體，以 對象間的聯(lián)系 刻畫實(shí)體間的聯(lián)系。 軟件重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同的或者相似軟件元素的過程。 重用是提高軟件生產(chǎn)率的最主要的方法。2. 面向?qū)ο蠓椒ǖ幕靖拍睿▽ο?、類、消息、繼承、多態(tài)性）13.面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象?類 14.類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的 實(shí)例對象：面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個實(shí)體，是構(gòu)成系統(tǒng)一個基本單位，它由一

31、組表示靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。（是由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的所有操作封裝在一起構(gòu)成的統(tǒng)一體。）屬性：是對象所包含的信息，它在設(shè)計(jì)對象時確定，一般只能通過執(zhí)行對象的操作來改變。操作：描述了對象執(zhí)行的功能，若通過信息傳遞，還可為其它對象使用。操作過程對外是封閉的，用戶只能看到這一操作實(shí)施后的結(jié)果，對象的這一特性，即是對象的封裝體。15.對象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行(封裝)。16.封裝是一種（信息屏蔽）技術(shù)，封裝的目的是使對象的定義和實(shí)現(xiàn)分離。17.以下不屬于對象的基本特點(diǎn)的是(C)。 A.分類性 B.多態(tài)性 C.繼承性 D.封裝性對象有

32、如下一些基本特點(diǎn)即標(biāo)識惟一性、分類性、多態(tài)性、封裝性和模塊獨(dú)立性。18.下面關(guān)于對象的描述錯誤的是（A）A.任何對象都必須有繼承性B.對象是屬性和方法的封裝體 C.對象間的通迅靠消息傳遞 D.操作是對象的動態(tài)屬性19.信息隱蔽的概念與下述哪能一種概念直接相關(guān)（模塊獨(dú)立性）20.可以把具有相同屬性的一些不同對象歸類，稱為 對象類 。類：是具有其同屬性、共同方法的對象的集合。所以，類是對象的抽象，這描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實(shí)例。類同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。對象可以是一個具體的對象也可以是泛指一般的對象，而實(shí)例必然是指一個具體的對

33、象。21.在面向?qū)ο蠓椒ㄖ?，一個對象請求另一對象為其服務(wù)的方式是通過發(fā)送(消息)消息：面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相合合作來推動的，對象間這種合作需要一個機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱為“消息”。消息就是一個實(shí)例與另一個實(shí)例之間傳遞的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。一個消息由下述三部分組成：1、接收消息的對象的名稱。 2、消息標(biāo)識符（即消息名）3、零個或多個參數(shù)。22.在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為 繼承 。23.一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用此方法提高了軟件的可重用性繼承：是面向?qū)ο蠓椒ǖ囊粋€主要特征。繼承是使用已有的定義作為基礎(chǔ)建立新類的定義技

34、術(shù)。也就是說繼承是指能夠直接獲得已有的功能和突出的優(yōu)點(diǎn)，而不必重復(fù)定義它們。繼承具有傳遞性，可分為單繼承與多重繼承。單繼承是指一個類只允許有一人父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指一個類允許有多個父類。多態(tài)性：對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動，這種現(xiàn)象即為多態(tài)性。多態(tài)性機(jī)制可提高軟件系統(tǒng)的靈活性，可重用性和可擴(kuò)充性。24.子程序通常分為兩類： 過程 和函數(shù)，前者是命令的抽象，后者是為了求值。第三章 軟件工程重點(diǎn)：需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件測試和軟件調(diào)試的作用、方法等一、 軟件工程基本概念 1. 軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的重要部分

35、，包括程序、數(shù)據(jù)及相關(guān)的 文檔 。其中，程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語句）序列。2. 下列敘述中，正確的是(D)。 A.軟件就是程序清單 B.軟件就是存放在計(jì)算機(jī)中的文件 C.軟件應(yīng)包括程序清單及運(yùn)行結(jié)果 D.軟件包括程序和文檔 3. 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）4. 軟件工程的出現(xiàn)是由于（軟件危機(jī)的出現(xiàn)） 5. 開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱做（軟件危機(jī)）軟件工程概念的出現(xiàn)源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題?？傊?，可以將軟件

36、危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。6. 開發(fā)大型軟件時，產(chǎn)生困難的根本原因是(大型系統(tǒng)的復(fù)雜性)。7. 軟件危機(jī)出現(xiàn)于20世紀(jì)60年代末，為了解決軟件危機(jī)，人們提出了 軟件工程學(xué) 的原理來設(shè)計(jì)軟件這就是軟件工程誕生的基礎(chǔ)。8. 下列不屬于軟件工程的3個要素的是（D）A.工具 B.過程 C.方法 D.環(huán)境軟件工程過程與軟件生命周期9. 軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的 資源 和活動。通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生命周期10.軟件生命周期中所花費(fèi)用最多的階段是（軟件維護(hù)）11.軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成(定義、開發(fā)、運(yùn)行維

37、護(hù))。 12. 軟件生命周期一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測試、交付使用以及維護(hù)等活動。軟件工程的目標(biāo)與原則13. 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境，主體內(nèi)容是軟件開發(fā)方法學(xué)。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。14. 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括軟件開發(fā)技術(shù)和（軟件工程管理） 15. 軟件工程的原則包括抽象、信息隱藏、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。軟件開發(fā)工具與軟件開發(fā)環(huán)境16. 開發(fā)軟件時對提高開發(fā)人員工作效率至關(guān)重

38、要的是（先進(jìn)的軟件開發(fā)工具和環(huán)境） 17. 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的 軟件工具集合。常用的軟件開發(fā)方法和技術(shù)可以分為三大類：瀑布型、增量型和變換型。瀑布型開發(fā)方法將軟件生命周期的各項(xiàng)活動規(guī)定為按固定順序連接的若干階段，強(qiáng)調(diào)早期的需求分析和開發(fā)的階段性，強(qiáng)調(diào)產(chǎn)品測試；但是不能適應(yīng)需求的變化。增量型則先建立一個不完全的系統(tǒng)，通過對需求的理解再進(jìn)一步擴(kuò)充和完善。例：瀑布模型突出的缺點(diǎn)是不適應(yīng)（D）的變動A.算法B.平臺C)程序語言D.用戶需求二、結(jié)構(gòu)化分析方法 需求分析與需求分析方法18. 在軟件生產(chǎn)過程中，需求信息的給出是(軟件用戶)。19. 需求分析中，開發(fā)人員要從用戶那里了解(軟

39、件做什么)。20. 需求分析階段的任務(wù)是確定 (軟件系統(tǒng)功能) 21. 需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過程。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型和 控制模型 22. 需求分析階段的工作：需求獲取、需求分析、編寫需求規(guī)格說明書、需求評審 下列工具中屬于需求分析常用工具的是(D)。A)PAD B)PFD C)NS D)DFD結(jié)構(gòu)化分析方法常用的需求分析方法：（1）結(jié)構(gòu)化分析方法。主要包括：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法(SA)，面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法 (JSD)和面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法(DSSD)（2）面向?qū)ο蟮姆治龇椒?OOA)23. 結(jié)構(gòu)化方法的核心和基

40、礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論 24. 下列不屬于結(jié)構(gòu)化分析的常用工具的是(D)。A)數(shù)據(jù)流圖 B)數(shù)據(jù)字典 C)判定樹 D)PAD圖25. 在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖（DFD）作為描述工具的軟件開發(fā)階段是 (B)A)可行性分析 B)需求分析 C)詳細(xì)設(shè)計(jì) D)程序編碼 26. 數(shù)據(jù)流圖用于抽象描述一個軟件的邏輯模型數(shù)據(jù)流圖由一些特定的圖符構(gòu)成。下列圖符名標(biāo)識的圖符不屬于數(shù)據(jù)流圖合法圖符的是(A)。A)控制流 B)加工 C)數(shù)據(jù)存儲 D)源和潭說明：數(shù)據(jù)流圖中的主要圖形元素與說明：27. 在數(shù)據(jù)流圖(DFD)中的箭頭代表的是(數(shù)據(jù)流) 28. 在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示(數(shù)據(jù)的流向)

41、。29. 在結(jié)構(gòu)化分析方法中，用于描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件的文檔稱為 數(shù)據(jù)字典軟件需求規(guī)格說明書30. 軟件需求規(guī)格說明書 是需求分析階段的最后結(jié)果31. 下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是（D）A.便于用戶、開發(fā)人員進(jìn)行理解和交流 B.反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù) C.作為確認(rèn)測試和驗(yàn)收的依據(jù) D.便于開發(fā)人員進(jìn)行需求分析32. (數(shù)據(jù)描述)是對軟件系統(tǒng)所必須解決的問題做出的詳細(xì)說明說明：需求規(guī)格說明書一般包括以下內(nèi)容：概述、數(shù)據(jù)描述、性能描述、功能描述、參考文獻(xiàn)目錄等。其中概述從系統(tǒng)角度描述軟件的目標(biāo)和任務(wù)；功能描述中描述了為解決用戶問題所需要

42、的每一項(xiàng)功能的過程細(xì)節(jié)；性能描述說明系統(tǒng)應(yīng)達(dá)到的性能和應(yīng)該滿足的限制條件、檢測的方法和標(biāo)準(zhǔn)。三、 結(jié)構(gòu)化設(shè)計(jì)方法 軟件設(shè)計(jì)的基本概念33. 在軟件開發(fā)中，下面任務(wù)不屬于設(shè)計(jì)階段的是(D)A)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) B) 給出系統(tǒng)模塊結(jié)構(gòu) C)定義模塊算法 D)定義需求并建立系統(tǒng)模型34. 軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)、接口和過程設(shè)計(jì)，其中軟件的過程設(shè)計(jì)是指(系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述)。說明：結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口定義：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述

43、。35. 下面不屬于軟件設(shè)計(jì)原則的是（C）A.抽象 B.模塊化 C.自底向上 D.信息隱藏 36. 耦合和內(nèi)聚是評價模塊獨(dú)立性的兩個主要標(biāo)準(zhǔn)，其中 內(nèi)聚 反映了模塊內(nèi)各成分之間的聯(lián)系，耦合反映了模塊間互相連接的緊密程度。 37. 內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展，一個模塊的內(nèi)聚性越強(qiáng)，則該模塊的模塊獨(dú)立性越 強(qiáng) 。一個模塊與其它模塊的耦合性越強(qiáng)，則它的模塊獨(dú)立性越弱 。 38. 下列敘述中，正確的是（C）A.接口復(fù)雜的模塊，其耦合程度一定低 B.耦合程度弱的模塊，其內(nèi)聚程度一定低 C.耦合程度弱的模塊，其內(nèi)聚程度一定高 D.以上都不對39.下列選項(xiàng)中，不屬于模塊間耦合的是(B)。A.數(shù)據(jù)

44、耦合B.同構(gòu)耦合C.異構(gòu)耦D.公用耦合40.軟件設(shè)計(jì)中，有利于提高模塊獨(dú)立性的一個準(zhǔn)則是( C)。A.低內(nèi)聚低耦合 B.低內(nèi)聚高耦合 C.高內(nèi)聚低耦合 D.高內(nèi)聚高耦合概要設(shè)計(jì)41. 軟件的概要設(shè)計(jì)又稱為總體結(jié)構(gòu)設(shè)計(jì)，其主要任務(wù)是建立軟件系統(tǒng)的總體結(jié)構(gòu)，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫，編寫概要設(shè)計(jì)文檔，概要設(shè)計(jì)文檔評審。42. 在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是 (C)A.詳細(xì)設(shè)計(jì) B.需求分析 C.總體設(shè)計(jì) D.編程調(diào)試43. 在概要設(shè)計(jì)階段，常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是 結(jié)構(gòu)圖 (sc)，也稱程序結(jié)構(gòu)圖。生成的結(jié)構(gòu)圖中，帶有箭頭的連線表示(模塊之間的調(diào)用關(guān)系)，矩形表示模塊。 44. 在概要設(shè)計(jì)階段，一般采用面向數(shù)據(jù)流的設(shè)計(jì)方法。數(shù)據(jù)流的類型有 變換型 和事務(wù)型。將變換型映射成結(jié)構(gòu)圖稱為 變換分析 。將事務(wù)型映射成結(jié)構(gòu)圖稱為 事務(wù)分析 。 45. 好的軟件設(shè)計(jì)結(jié)構(gòu)通常 頂層 高扇出，中間扇出較少，底層 高 扇入。 46