1、數(shù)據(jù)結構試題單選題在數(shù)據(jù)結構的討論中把數(shù)據(jù)結構從邏輯上分為 內(nèi)部結構與外部結構線性結構與非線性結構（C）靜態(tài)結構與動態(tài)結構 緊湊結構與非緊湊結構。采用線性鏈表表示一個向量時,A 必須是連續(xù)的C 一定是不連續(xù)的3、采用順序搜索方法查找長度為要求占用的存儲空間地址（ D ）B部分地址必須是連續(xù)的D可連續(xù)可不連續(xù)的順序表時，搜索成功的平均搜索長度為（4、AnBn/2在一個單鏈表中，若q結點是C（n-1）/2p結點的前驅(qū)結點，若在qD （n +1）/2p之間插入結點S，則執(zhí)行s Ti nk = p t link; p t link = s;p t link = s; st link = q;p t l

2、ink = st link； st link = p;q t link = s; st link = p;如果想在4092個數(shù)據(jù)中只需要選擇其中最小的A起泡排序設有兩個串t12、若需要利用形參直接訪問實參,A指針B 引用13、下面程序段的時間復雜度為（for (int i=0;i<m;i+)for (int j=0;j<n;j+)aij=i*j;A O（m 2）B O（n 2）14、下面程序段的時間復雜度為（int f(unsigned int n) if(n= =0 | n= =1)return 1;else return n*f(n-1);則應把形參變量說明為（值B )D 變量

3、C O(m*n)參數(shù)。D O(m+n)A O（1）B O（n）線性表若是采用鏈式存儲結構時, 必須是連續(xù)的15、部分地址必須是連續(xù)的C O（n2）要求內(nèi)存中可用存儲單元的地址D O(n !)5個，采用（B堆排序C錦標賽排序和p，求p在t中首次出現(xiàn)的位置的運算叫做（B模式匹配C 串替換每一個數(shù)組元素Aij占用3個存儲字，行下標）方法最好。D 快速排序一定是不連續(xù)的連續(xù)或不連續(xù)都可以）°D串連接i從1到8，列下標j從1到A 求子串7、在數(shù)組A中，10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲字數(shù)是16、數(shù)據(jù)結構的定義為（D，S），其中D是（B ）的集合。A算

4、法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結構10、在循環(huán)隊列中用數(shù)組 A0.m-1存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當前隊列中的元素個數(shù)是（D)oA(front - rear+ 1) % mB(rear - front + 1) % mC(front - rear+ m) % mD(rear - front + m) % m11、一個數(shù)組元素ai與（A)的表示等價。A* (a+i )B a+iC *a+iD& a+i（ C ）°A 80B 100C 240D 2708、 將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（A ）°A 棧B隊列C循環(huán)隊列

5、D 優(yōu)先隊列9、 一個隊列的進隊列順序是1,2, 3, 4，則出隊列順序為（ C ）°17、算法分析的目的是（A ） °A找岀數(shù)據(jù)結構的合理性B研究算法中輸入和輸岀的關系C分析算法的效率以求改進D分析算法的易懂性和文檔性18、 在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行（B ）°A s->link=p;p->link=s;B s->link=p->link;p->link=s;C s->link=p->link;p=s;D p->link=s;s->link=p;19、 設單鏈表中

6、結點結構為（data,link）.已知指針q所指結點是指針p所指結點的直接前驅(qū)，若在 *q與*p之間插入結點*s，則應執(zhí)行下列哪一個操作（ B ）A s->link=p->link; p->link=s;B q->link=s; s->link=pC p->link=s->link;s->link=p;D p->link=s; s->link=q;20、設單鏈表中結點結構為(data,link).若想摘除結點*p的直接后繼，則應執(zhí)行下列哪一個操作 (A )A p->link=p->link->link;p=p->

7、;link; p->link=p->link->link;C p->link=p->link;21、設單循環(huán)鏈表中結點的結構為(data,link )p=p->link->link;，且rear是指向非空的帶表頭結點的單循環(huán)鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執(zhí)行下列哪一個操作(A s=rear; rear=rear->link;delete s;B rear=rear->link;deleterear;C rear=rear->link->link;delete rear;D s=rear->link->

8、;link;typedef int Data Type;typedef struct Data Type dataMaxsize;Int front, rear; Queue;若有一個Queue類型的隊列Q,試問判斷隊列滿的條件應是下列哪一個語句(A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;rear->link->link=s->link;delete s;22、設單循環(huán)鏈表中結點的結構為(data,link 表當前指針，在循環(huán)鏈表中檢測，且first為指向鏈表表頭的指針， current是否達到鏈表表尾的語句是( D

9、)。curre nt 為鏈A current->link =nullB first->link=currentC first=currentD current->link=first23、一個棧的入棧序列為b，c,則出棧序列不可能的是C c,a,b24、c,b,aB b,a,c棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是(C )。a,c,bA )。25、top=0B top=maxSize棧和隊列的共同特點是(C )。都是先進后岀只允許在端點處插入和刪除C top=maxSize都是先進先岀沒有共同點D top=-126、假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f+

10、1= =rB 葉仁=ff和r ,則判斷隊空的條件為(DC f= =0D f= =r).27、當利用大小為的數(shù)組順序存儲一個隊列時，該隊列的最大長度為(A n-2B n-1D n+128、當利用大小為個元素時，首先應執(zhí)行的數(shù)組順序存儲一個棧時，假定用 top= =n 表示?？?，則向這個棧插入一 ()語句修改top指針。A top+;29、設鏈式棧中結點的結構為(C Q.front + Q.rear= = Maxsize;31、設有一個遞歸算法如下：D Q.front= = (Q.rea 葉1)% Maxsize;int fact (int n ) if (n<=0) return 1;el

11、se return n*fact(n-1);下面正確的敘述是(B )A計算fact(n)需要執(zhí)行n次遞歸C此遞歸算法最多只能計算到fact(8)32、設有一個遞歸算法如下int x (intif (n<=3)else returnn) return 1;x(n_2)+x(n_4)+1;試問計算x(x(8)時需要計算(D )次33、設有廣義表D(a,b,D),其長度為A aB 334、廣義表A(a),則表尾為(B fact(7)=5040D以上結論都不對函數(shù)。C 16D 18次B )，深度為(CB top-;C top=0;D top;data, link ) ，且 top是指向棧頂?shù)闹羔?/p>

12、。若想摘除鏈式棧的棧頂 結點，并將被摘除結點的值保存到x中，則應執(zhí)行下列(A )操作。B ()35、下列廣義表是線性表的有(空表(a)A x=top->data; top=top->link;C x=top; top=top->link;30、設循環(huán)隊列的結構是：B top=top->link; x=top->data;D x=top->data;A E ( a,(b,c)36、遞歸表、再入表、純表、線性表之間的關系為A 再入表 > 遞歸表 > 純表 > 線性表E(a,E)C E (a,b)E(a,L()遞歸表 > 線性表 >

13、再入表 > 純表const int Maxsize=100;C 遞歸表 > 再入表 > 純表 > 線性表D遞歸表 > 再入表 > 線性表 > 純表37、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是(B )的二叉樹。A 24C 48B da1+I*mD 53m個存儲單元，若第一個結點的地址為da1,C da1-l*mD da1+(l+1)*m）以數(shù)組方式存儲D以鏈接方式存儲的線性表。）順序存儲或鏈接存儲D 索引存儲的有序表時，元素的平均搜索長度為（B n+1D n+e48、平均搜索長度為（C不直接依賴于C ）n D 上述都不對四種四種A空或只有一個

14、結點B高度等于其結點數(shù)C任一結點無左孩子D任一結點無右孩子38、 對于任何一棵二叉樹T,如果其終端結點數(shù)為no,度為2的結點為n2.，則（A ）A n o= n2+1 B n 2= n o+1 C n 0= 2n 2+1D n 2=2n o+139、由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（B）B 7340、已知一個順序存儲的線性表，設每個結點需占 則第I個結點的地址為（A ）oA da1+（l-1）*m41、34具有35個結點的完全二叉樹的深度為42、對線性表進行折半搜索時，要求線性表必須 A 以鏈接方式存儲且結點按關鍵碼有序排列C以數(shù)組方式存儲且結點按

15、關鍵碼有序排列43、順序搜索算法適合于存儲結構為（A散列存儲C壓縮存儲44、 采用折半搜索算法搜索長度為nA O （n2）B O （n log 2n）C O （log 2n）45、對于一個具有n個頂點和e條邊的無向圖，進行拓撲排序時，總的時間為C n-146、判斷一個有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（A求關鍵路徑的方法B 求最短路徑的Dijkstra方法C深度優(yōu)先遍歷算法D廣度優(yōu)先遍歷算法47、在10階B-樹中根結點所包含的關鍵碼個數(shù)最多為（ C ），最少為（A10對包含n個元素的散列表進行搜索，O （log 2n）B O （n）填空題（）數(shù)據(jù)的邏輯結構被分為集合結構

16、、線性結構、樹形結構、圖形結構數(shù)據(jù)的存儲結構被分為順序結構、鏈接結構、索引結構、散列結構3、 一種抽象數(shù)據(jù)類型包括（數(shù)據(jù)）和（操作）兩個部分。4、 設有兩個串p和q，求p在q中首次出現(xiàn)的位置的運算稱為（模式匹配）5、棧、隊列邏輯上都是（線性存儲）結構。6、線性結構反映結點間的邏輯關系是（一對一）的，圖中的數(shù)據(jù)元素之間的關系是（多對多）的，樹形結構中數(shù)據(jù)元素間的關系是（一對多）的。7、棧中存取數(shù)據(jù)的原則（后進先出），隊列中存取數(shù)據(jù)的原則（先進先出）& 串是由（ 零個或多個）字符組成的序列。（長度為零的串）稱為空串，（由一個或多個空格組成的串）稱為空格串。9、設目標串T= ” abccdc

17、dccbaa ”，模式P= ” cdcc ”則第（6）次匹配成功。10、 一維數(shù)組的邏輯結構是（線性結構），存儲結構是（順序存儲表示）。對于二維數(shù)組，有（行優(yōu)先順序）和（列優(yōu)先順序）兩種不同的存儲方式，對于一個二維數(shù)組Amn,若采用按行優(yōu)先存放的方式，則任一數(shù)組元素Aij相對于A00的地址為（n*i+j ）。11、 向一個順序棧插入一個元素時，首先使（棧頂指針）后移一個位置，然后把待插入元素（寫） 到這個位置上。從一個順序棧刪除元素時，需要前移一位（棧頂指針）。12、 在一個循環(huán)隊列Q中，判斷隊空的條件為（ Q.front= =Q.rear ）,判斷隊滿的條件為（Q.rea 葉1）%MaxSi

18、ze= =q.front）13、對于一棵具有n個結點的樹，該樹中所有結點的度數(shù)之和為（n-1）。14、 一棵高度為5的滿二叉樹中的結點數(shù)為（63 ）個，一棵高度為3滿四叉樹中的結點數(shù)為（85）個。15、若對一棵二叉樹從0開始進行結點編號，并按此編號把它順序存儲到一維數(shù)組中，即編號為0的結點存儲到 a0中，其余類推，則ai元素的左子女結點為（2*i+1 ），右子女結點為（2*i+2），雙親結點（i>=1 ）為（i-1）/2 n ）.16、在一個最大堆中，堆頂結點的值是所有結點中的（最大值），在一個最小堆中，堆頂結點的 值是所有結點中的（最小值）。17、 已知具有n個元素的一維數(shù)組采用順序存

19、儲結構，每個元素占k個存儲單元，第一個元素的地址為 LOC（a1），那么，LOC（ai）= L0C（a1）+（i-1）*k。18、 在霍夫曼編碼中，若編碼長度只允許小于等于4,則除掉已對兩個字符編碼為 0和10夕卜，還可以最多對（4 ）個字符編碼。19、 設高度為h的空二叉樹的高度為-1，只有一個結點的二叉樹的高度為0，若設二叉樹只有度為2上度為0的結點，則該二叉樹中所含結點至少有（2h+1）個。20、由一棵二叉樹的前序序列和（中序序列）可唯一確定這棵二叉樹。21、以折半搜索方法搜索一個線性表時，此線性表必須是（順序）存儲的（有序）表。22、 已知完全二叉樹的第 8層有8個結點，則其葉子結點數(shù)

20、是（68 ）o若完全二叉樹的第7有10 個葉子結點，則整個二叉樹的結點數(shù)最多是（235 ）23、 對于折半搜索所對應的判定樹，它既是一棵（二叉搜索樹），又是一棵（理想平衡樹）。24、假定對長度n=50的有序表進行折半搜索，則對應的判定樹高度為（5）,判定樹中前5層的結點數(shù)為（3 1），最后一層的結點數(shù)為（19）。25、 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（2）倍。在一個具有n個頂點的無向完全圖中，包含有（n（n-1）/2 ）條邊，在一個具有 n個頂點的有向完全圖中，包含有（n（n-1）條邊。26、 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為（n ）和（n

21、-1 ）27、 設線性表中元素的類型是實型，其首地址為1024，則線性表中第 6個元素的存儲位置是（1044）。28、 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選擇（插入排序），若初始數(shù)據(jù)基本反序， 則最好選擇（選擇排序）。29、算法是對特定問題的求解步驟的一種描述，它是（指令）的有限序列，每一條（指令）表示 一個或多個操作。30、 對于一個具有n個頂點肯e條邊的無向圖，進行拓樸排序時，總的進間為（ n）31、 構造哈希函數(shù)有三種方法，分別為（平方取中）法、（除留余數(shù)）法、（折迭移位）法。32、處理沖突的三種方法，分別為 （線性探測）、（隨機探測）、（鏈地址法）。33、 對于含有n個頂點和e

22、條邊的無向連通圖，利用普里姆算法產(chǎn)生的最小生成樹， 其時間復雜 度為（0（n2）、利用克魯斯卡爾算法產(chǎn)生的最小生成樹，其時間復雜度為（0（elog 2e）34、 快速排序在平均情況下的時間復雜度為（0 （nlog 2n），在最壞情況下的時間復雜度為（0（n2）;快速排序在平均情況下的空間復雜度為（0（ log 2n）,在最壞情況下的空間復雜度為（0（ n ）。35、假定一組記錄的排序碼為（46，79,5 6,38,40,80)，對其進行歸并排序的過程中，第二趟排序后的結果是（3 84 65 679 408 0)36、假定一組記錄的排序碼為（46，79,5 6,3 8,40,80)，對其進行快速

23、排序的第一次劃分的結果是（3 84 0 46567 98 0)。37、 一個結點的子樹的（個數(shù)）稱為該結點的度。度為（ 零）的結點稱為葉結點或終端結點。度不為（零）的結點稱為分支結點或非終端結點。樹中各結點度的（ 最大值 ）稱為樹的度。38、 設Ki=Kj（1<=i<=n, 1<=jv=n,jv>i）且在排序前的序列中 Ri領先于R （i<j）,若排序后的序 列中Ri仍領先于 Rj，則這種排序方法是（穩(wěn)定的），反之是（不穩(wěn)定的）。40、在堆排序的過程中，對任一分支結點進行調(diào)整運算的時間復雜度為（0（log 2n），整個排序過程的時間復雜度為（0（ nlog 2n）

24、。41、在索引表中，每個索引項至少包含有（關鍵碼值）域和（子表地址）域這兩項。42、假定一個線性表為（” abed ”，” baabd ”，” beef ”，” cfg ”，” ahij”，” bkwte ”，” ccdt ” / aayb ”），若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a，b，c三個子表的長度分別為（3），（3），（2）。43、 對于包含5 0個關鍵碼的3階B-樹，其最小高度為（4），最大高度為（5）。44、從一棵B-樹刪除關鍵碼的過程，若最終引起樹根結點的合并，則新樹比原樹的高度（減1）45、假定要對長度n=100的線性表進行散列存儲，

25、并采用開散列法處理沖突， 則對于長度m=20的散列表，每個散列地址的同義詞子表的長度平均為（5）。46、在散列存儲中，裝載因子 a又稱為裝載系數(shù)，若用 m表示散列表的長度，n表示待散列存儲 的元素的個數(shù)，則a等于（n/m ）。47、 在有向圖的鄰接矩陣中，第 i行中“ 1 ”的個數(shù)是第i個頂點的（岀度），第i列中“ T的個 數(shù)是第i個頂點的（入度）。在無向圖的鄰接矩陣中，第 i行（列）中“ 1 ”的個數(shù)是第i個頂點的（度），矩陣中“ 1 ”的個數(shù)的一半是圖中的（邊數(shù)）。48、在對m階B-樹中，每個非根結點的關鍵碼數(shù)最少為（m/2 n -1 ）個，最多為（m-1 ）個，其子樹棵數(shù)最少為（m/2

26、n ），最多為（m ）。三、判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位（X）o2、 數(shù)據(jù)的邏輯結構是指各數(shù)據(jù)元素之間的邏輯關系，是用戶按使用需要建立的（V）.3、數(shù)據(jù)結構是指相互之間存在一種或多種關系的數(shù)據(jù)元素的全體（X）。4、從邏輯關系上講，數(shù)據(jù)結構主要分為兩大類：線性結構和非線性結構（V）。5、線性表的邏輯順序與物理順序總是一致的（X）。6、二維數(shù)組是其數(shù)組元素為線性表的線性表（X）。7、每種數(shù)據(jù)結構都應具備三種基本運算：插入、刪除、搜索（V）。8、 非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。（X ）9、 空串與由空格組成的串沒有區(qū)別。（X ）10、 將T在S中首次出現(xiàn)的位置作為 T

27、在S中的位置的操作稱為串的模式匹配。（V）11、 深度為h的非空二叉樹的第h層最多有2h-1個結點（X ）12、 完全二叉樹就是滿二叉樹。（X）13、 已知一棵二叉樹的前序序列和中序序列可以唯一地構造岀該二叉樹。（V ）14、 帶權連通圖的最小生成樹的權值之和一定小于它的其它生成樹的權值之和。（V）15、線性表的順序存儲結構的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰。(1 ) AB-*C+(3)AB&&EF>!|16、若有一個結點是二叉樹中某個子樹的中序遍歷結果序列的最后一個結點，則它一定是該子樹的前序遍歷結果序列的最后一個結點。（V）17、任一棵二叉搜索樹的平均

28、搜索時間都小于用順序搜索法搜索同樣結點的順序表的平均搜索 時間。（X）18、 最優(yōu)二叉搜索樹一定是平衡的二叉搜索樹。（V）19、 AOE網(wǎng)是一種帶權的無環(huán)連通圖。（V ）20、對于同一組待輸入的關鍵碼集合，雖然各關鍵碼的輸入次序不同，但得到的二叉搜索樹都是 相同的（X）。21、二叉排序樹可以是一棵空樹（ V ）22、 線性表中所有結點的類型必須相同。（V ）23、n個結點的有向圖，若它有 n（n - 1）條邊，則它一定是強連通的。（ V ）24、任何無環(huán)的有向圖，其結點都可以排在一個拓撲序列里。（ V）25、 隊列邏輯上是一個下端口和上端能增加又能減少的線性表（X ）26、 二叉樹是樹的一種特

29、殊情況（V ）27、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中頂點個數(shù)有關，而與圖的邊數(shù)無關（V）。28、 鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。（X）29、 連通分量是無向圖中的極小連通子圖。（X）30、 在AOE網(wǎng)絡中一定只有一條關鍵路徑。（X）31、 關鍵活動不按期完成就會影響整個工程的完成時間。（V）32、 平衡二叉樹的左右子樹深度之差的絕對值不超過1 o （V ）33、 快速排序是對起泡排序的一種改進。（V ）34、直接選擇排序穩(wěn)定。（X ）35、 堆排序占用的輔助空間很大。（X ）36、在散列法中采取開散列法來解決沖

30、突時，其裝載因子的取值一定在（0,1）之間。（X）37、 B-樹是一種動態(tài)索引結構，它既適用于隨機搜索，也適用于順序搜索。（X）38、 在散列法中，一個可用散列函數(shù)必須保證絕對不產(chǎn)生沖突。（X）39、 任何一個關鍵活動延遲，那么整個工程將會延遲。（V）40、 任何一個關鍵活動提前完成，那么整個工程將會提前完成。（X）四、運算應用題1、在一個有n個元素的順序表的第i個元素（1 - i -n）之前插入一個新元素時，需要向 后移動多少個元素？ 答案：需要向后移動 n-i + 1個元素2、當一個棧的進棧序列為 1234567時，可能的出棧序列有多少種？6457321是否是合理的岀棧序列？答案：可能的岀

31、棧序列有種，6457321不是合理的岀棧序列3、簡單（直接）選擇排序是一種穩(wěn)定的排序方法嗎？試舉例說明？答案：是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉岀反例即可。 275275*512061i = 1 061275*512275i = 2 061275 *512275i = 3 061275 *275512 4、設有序順序表為 10, 20, 30, 40, 50, 60, 70，采用折半搜索時，搜索成功的平均搜索長度是多少？答案：ASLsucc = （1*1 + 2*2 + 3*4 ） / 7 = 17 / 75、在結點個數(shù)為n（n>1）的各棵樹中，高度最小的樹的高度是多少？

32、它有多少個葉結點？多少 個分支結點？高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？答案：結點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉結點，1個分支結點；高度最大的樹的高度為 n-1,有n層；它有1個葉結點，n-1個分支結點。6、一棵高度為h的滿k叉樹有如下性質(zhì)：第h層上的結點都是葉結點，其余各層上每個結點都 有k棵非空子樹，如果按層次自頂向下，同一層自左向右，順序從1開始對全部結點進行編號，試 問：（1）各層的結點個數(shù)是多少？（2）編號為i的結點的父結點（若存在）的編號是多少？（3）編號為i的結點的第m個孩子結點（若存在）的編號是多少？（4）編號為i的結點有右兄

33、弟的條件是什么？其右兄弟結點的編號是多少？（5）若結點個數(shù)為n,則高度h是n的什么函數(shù)關系？答案：（1）各層的結點個數(shù)是 口（i=0,1,2,.,h）（2）編號為i的結點的父結點（若存在）的編號是（i+k-2）/k（3） 編號為i的結點的第m個孩子結點（若存在）的編號是（i-1）*k+m+1（4 ）當（i-1）%k<>0時有右兄弟，右兄弟的編號為i+1（5）若結點個數(shù)為 n，則高度h和n的關系為：h=log k（n*（k-1）+1）-1（n=0時h=-1）7、寫岀下列中綴表達式的后綴形式：（1）A* - B + C（2） （A + B） * D + E / （F + A * D）

34、+ C（3） A && B| ! （E > F）注：按 C+ 的優(yōu)先級）!（A && !（ （B < C）|（C > D） ） ）|（C < E）答案：各中綴表達式的后綴形式如下：(2) AB+D*EFAD*+/+C+(4) ABC<CD>|!&& !CE<|Cu1413121110 9 8 = 4298、畫岀下列廣義表的圖形表示和它們的存儲表示: D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1)廣義表（2）的圖形表示為:9、題目：1

35、1、將下面的森林變換成二叉樹（7分）廣義表（2）的存儲表示為:425答案：其中的一個拓撲序列為：V1，將給定的圖簡化為最小的生成樹,12、1V2，V3，V4，要求從頂點V5，V6，V7出發(fā)。（7分）答案:11、根據(jù)所給有向圖，寫岀一個拓撲序列。（5 分）（7 分）0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設計赫夫曼編碼。答案：為方便起見，設各種字符的權值w=5,29,7,8,14,23,3,11。因為n=8，所以要構造的赫夫曼樹共有m=2n-1=2*8-1=15個結點。生成的赫夫曼樹為下圖所示。概率為0.05的字符編碼為：0110概率為0.03的字符編碼為

36、：0111概率為0.29的字符編碼為：10概率為0.14的字符編碼為：110概率為0.07的字符編碼為：1110概率為0.08的字符編碼為：111114、已知一棵二叉樹的前序遍歷的結果是ABECDFGHIJ,中序遍歷的結果是 EBCDAFHIGJ,答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹，所得二叉樹如圖：這棵二叉樹的后序遍歷序列為：EDCBIHJGFA15、在結點個數(shù)為 n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結點？多少 個分支結點？高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？答案：結點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉

37、結點，1個分支結點；高度最大的樹的高度為 n-1,有n層；它有1個葉結點，n-1個分支結點。16、 對于一個高度為 h的AVL樹，其最少結點數(shù)是多少？反之，對于一個有n個結點的AVL 樹,其最大高度是多少？最小高度是多少？答案：設高度為h(空樹的高度為-1)的AVL樹的最少結點為 Nh，則Nh = F h+3 -1。Fh是斐波那契數(shù)。又設 AVL樹有n個結點，則其最大高度不超過3/2*log 2(n+1),最小高度為log 2(n+1) n -1。17、 7-7 設有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677,

38、765, 897, 908 。試畫岀對其進行折半搜索時的判定樹，并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。答案：折半搜索時的判定樹為：ASLsucc=1/14(1+2*2+3*4+4*7) =45/14ASLunsucc=1/15(3*1+4*14 ) =59/1518、試對下圖所示的 AOE網(wǎng)絡10(1) 這個工程最早可能在什么時間結束。(2) 求每個事件的最早開始時間Vei和最遲開始時間Vli。(3) 求每個活動的最早開始時間e()和最遲開始時間l()。(4) 確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程unknown ( w-1 );fo

39、r ( int i = 1 ; i <= w; i+ ) cout <<w<<'cout << endl;Ve01915293843Vl01915373843答案:提前完成。答案：按拓樸有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間 Vl，然后再計算各個活動的最早可能開始時間e和最遲允許開始時間I,根據(jù)l-e是否等于0來確定關鍵活動，從而確定關鍵路徑。調(diào)用語句為12 2unknown (4)<1,2><1,3><3,2><2,4><2,5><3,5><

40、4,6i><5,6>334 4t行結果n ( int n ) e00151919152938 44L17015271927372、給出遞歸過程的扌l(wèi)-e170080128vd unknowcout <<此工程最早完成時間為43，關鍵路徑為<1,3><3,2><2,5><5,6>if ( int ( nn19、已知有五個待排序的記錄，其關鍵字分別為：256，301，751，129，937,863076，438請用快速排序的方法將它們從小到大排列。答案：第一次排序：(076，129)，256，第二次排序:076，129，

41、256，第三次排序:076，129，256，第四次排序:076，129，256，301，第五次排序:076，129，256，301，742 ， 694 ，/ 10 ) ) unknown ( int ( n / 10 );調(diào)用語句為unknown ( 582 )。(751，937，863，742，694，301，439 )!，301，694，742)，751，( 863，937 )438，(694，742)，751，( 863，937 )301，694，742，751，( 863，937)438，(438438，694，742，751，863，937285答案：3、給岀遞歸過程的執(zhí)行結果int

42、 unknown ( int m ) int value;if ( ! m ) value = 3 ;else value = unknown ( m-1 ) + 5 ;20、設有150個記錄要存儲到散列表中，并利用線性探查法解決沖突，要求找到所需記錄的平均比較次數(shù)不超過 2次。試問散列表需要設計多大？(設 堤散列表的裝載因子，則有ASLsucc=(1+1/ (1- ：) )/2)。答案：已知要存儲的記錄數(shù)為n = 150,查找成功的平均查找長度為ASLsucc < 2，則有：ASLsucc=1/2(1+1/(1-< 2 解得 辱 2/3 ，又有：Cfen/m=150/m兩式聯(lián)立得

43、：150/m < 2/3,解得：m > 225.所以散列表需要設計 225個單位。五、算法分析題1、給岀下列遞歸過程的執(zhí)行結果void unknown ( int w ) if ( w ) return value;執(zhí)行語句為 cout << unknown (3)。答案： 184、 設有一個二維數(shù)組 Amn，假設A00存放位置在644 (10)，A22存放位置在676每個元素占一個空間，問A33 ( 10)存放在什么位置？腳注(10)表示用10進制表示。答案：設數(shù)組元素 Ai j存放在起始地址為Loc(i,j)的存儲單元中。因為：Loc(2,2)= Loc(0,0)+

44、2*n+2=644+2*n+2=676所以：n=(676-2-644)/2=15所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692(10)，5、 設單鏈表結構為struct ListNode int data ;ListNode * link pct link = pb; pc = pb ; pb = pb T|ink；下面的程序是以單鏈表為存儲結構 ，實現(xiàn)二路歸并排序的算法，要求鏈表不另外占用存儲空 間，排序過程中不移動結點中的元素，只改各鏈結點中的指針，排序后r仍指示結果鏈表的第一個 結點。在初始狀態(tài)下，所有待排序記錄鏈接在一個以 r為頭指針的單鏈表中。例如

45、，r*在算法實現(xiàn)時，利用了一個隊列做為輔助存儲，存儲各有序鏈表構成的歸并段的鏈頭指針。初始時，各初始歸并段為只有一個結點的有序鏈表。隊列的數(shù)據(jù)類型為Queue，其可直接使用的63A相關操作有置空隊列操作：makeEmpty ();將指針x加入到隊列的隊尾操作：EnQueue ( ListNode * x );退出隊頭元素，其值由函數(shù)返回的操作：ListNode *DlQueue ();判隊列空否的函數(shù)，空則返回1,不空則返回0: int IsEmpty ()。解決方法提示：程序首先對待排序的單鏈表進行一次掃描，將它劃分為若干有序的子鏈表，其表頭指針存放在一個指針隊列中。當隊列不空時，從隊列中退

46、岀兩個有序子鏈表，對它們進行二路歸并，結果鏈表的表頭指 針存放到隊列中。如果隊列中退岀一個有序子鏈表后變成空隊列，則算法結束。這個有序子鏈表即為所求。在算法實現(xiàn)時有 6處語句缺失，請閱讀程序后補上。(1) 兩路歸并算法void merge ( ListNode * ha ，ListNode * hb，ListNode * & he ) ListNode *pa，*pb，*pe ;if ( hatdata <= hbtdata ) he = ha; pa = hatlink； pb = hb ; else he = hb; pb = hbtlink; pa = ha ; pe =

47、he;while ( pa && pb )if ( pa t data <= pb tdata) pe t link = pa;pe = pa;pa = pa t link;elseif ( pa ) pe t link = pa; else pe t link = pb;(2) 歸并排序主程序void mergesort ( ListNode * r ) ListNode * s，t;Queue Q ;if ( ! r ) return;s = r;Q.EnQueue ( r );while ( s ) t = st link ;while ( t != 0 &

48、& st data <= tt data ) s = t; t = t t link;if ( t ) st link = 0 ; s = t;Q.EnQueue ( s );while ( !Q.lsEmpty( ) ) r = Q.DlQueue ();if ( Q.IsEmpty ( ) ) break;s = Q.DlQueue ();merge ( r，s，t );Q.EnQueue ( t );6、請讀下列程序，該程序是在單鏈表中刪除一個結點的算法，為空岀的地方填上正確的語句。(7分)void demo2(LinkList head，L istNode *p)/hea

49、d是帶頭結點的單鏈表，刪除P指向的結點ListNode *q=head;while(q&& q->next!=p ) q=q->next;if (q) Error( “ *p not in head ” );q->next=p->next;free(p);10、已知一完全二叉樹從根結點開始，自頂向下，同一層自左向右連續(xù)編號，根結點的編號為0 ,閱讀以下程序請回答該程序所實現(xiàn)的功能：templatevclass type >void linkedtosequent(Bintreenode<Type> *t,type a ,int i)if

50、 (t!=Null)a=t->getData();linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2);主程序調(diào)用方式：linkedtosequent(t.root,a,0);答案：該程序的功能是：將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序(數(shù)組)表示。8、設散列表為HT13,散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突，對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1)采

51、用線性探查法尋找下一個空位，畫岀相應的散列表，并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。 采用雙散列法尋找下一個空位 ，再散列函數(shù)為 RH ( key) = (7* key) % 10 + 1,尋找下一個空 位的公式為 Hi = (H i-1 + RH ( key) % 13, H 1 = H ( key)。畫出相應的散列表，并計算等概率下搜 索成功的平均搜索長度。答案：使用散列函數(shù)H(key)=key mod 13 有：H (12 ) =12 , H (23) =10 , H (45) =6 , H (57) =5 , H (20) =7 , H (03) =3 , H

52、 (78 ) =0 , H (31 ) =5 , H (15 ) =2 , H (36) =10利用線性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索長度為：ASLsucc =1/10( 1+1+1+1+1+1+4+1+2+1) =14/10搜索不成功的平均搜索長度為：ASLunsucc =1/13(2+1+3+2+1+5+4+3+2+1+5+4+3) =36/13利用雙散列法造表：Hi = (H i-1 + RH(key) ) %13, Hi =H(key)012345678910111278150357452031

53、36231211111135119、閱讀下面程序，指岀其算法的功能并求岀其時間復雜度(1) int Prime(int n)int i=2,x=(int)sqrt(n); while(i<=x) if(n%i=0)break; i+;if(i>x) return 1;else return 0;(2)int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=i;s+=p;return s;答案：(1 )程序功能是判斷n是否是一個素數(shù)，若是則返回數(shù)值1，否則返回數(shù)值 0,該算法的時間復雜度為O (sqrt(n).(2)程序功能是計算刀ni=1 i!，該算法的時間復雜度為O (n).10、判斷一個帶表頭結點的雙向循環(huán)鏈表L是否對稱相等的算法如下所示，請在算法的處填入正確的語句。int symmetry(DblList DL) int sym=1;DblNode p=DL->rLink, q=DL->lLink;Whi