武漢大學(xué)數(shù)據(jù)結(jié)構(gòu)考試試題(附答案)

1、1. 下面程序段的執(zhí)行次數(shù)為（ A ） for(i=0;in-1;i+) for(j=n;ji;j-) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ）A. 110 B .108 C. 100 D. 1203. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循環(huán)隊列用數(shù)組A0,m1存放其元素值，已知其頭尾指針分別是front和rear

2、,則當(dāng)前隊列中的元素個數(shù)是（ D ）A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5不帶頭結(jié)點的單鏈表head為空的判定條件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6 在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（ B）A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-

3、next=p;7. 從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較多少個結(jié)點（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9串是一種特殊的線性表，其特殊性體現(xiàn)在( B ) A. 可以順序存儲 B .數(shù)據(jù)元素是一個字符C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符11二維數(shù)組M的元素是4個字符（

4、每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時下列哪一元素的起始地址相同( B ) A. M24 B .M34 C. M35 D. M4412. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為( C )A. SA+144 B .SA+180 C. SA+222 D. SA+22513. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為：( B )A. 2h B .2h-1 C.

5、 2h+1 D. h+114. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是( D )A. acbed B .decab C. deabc D. cedba15. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把 由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。下列結(jié)論哪個正確( A )A. 樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B .樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D. 以上都不對 16. 具有6個頂點的無向圖

6、至少應(yīng)有多少條邊才能確保是一個連通圖( A )A. 5 B .6 C. 7 D. 817. 順序查找法適合于存儲結(jié)構(gòu)為( B )的線性表 A. 散列存儲 B .順序存儲或鏈接存儲C. 壓縮存儲 D. 索引存儲18.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為( C )A. n B .n2 C. (n+1)2 D. (n-1)219. 有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為( B )A. 3512 B .3712 C. 3912 D. 431220.有一個有序表為1，3，9，12，32，41，45，62，75，7

7、7，82，95，100，當(dāng)二分查找值82為的結(jié)點時，幾次比較后查找成功（ C ）二、填空題（每空1分，共20分）1.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置，決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。2對于一個具有N個結(jié)點的單鏈表，在已知的結(jié)點P后插入一個新結(jié)點的時間復(fù)雜度為O(1),在給定值為X的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O(N)。 3.有一空桟，現(xiàn)有輸入序列1,2,3,4,5,經(jīng)push,push,pop,push,pop,push,push后，輸出序列為 2,3 。4在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 2 倍 5.

8、對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為 n-1。6. 在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有 6個7.在霍夫曼編碼中，若編碼長度只允許小于等于4，則除了已對兩個字符編碼為0和10外，還可以最多對 4 個字符編碼。8. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 n 和 n-1 。9. 對20個記錄進行歸并排序時，共需要進行 5 趟歸并，在第三趟歸并時是把長度為 4 的有序表兩兩歸并為長度為 8 的有序表。三、問答題 1. 簡述下面算法的功能（棧和隊列的元素類型均為int） void algo

9、3(Queue &Q) Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue(Q,d);Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue(Q,d); 算法的功能：利用棧作輔助，將隊列中的數(shù)據(jù)元素進行逆置2. 已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。由先序遍歷和后序遍歷序列不能唯一確定一棵二叉樹.。一、選擇題1. 下面程序段的執(zhí)行次數(shù)為（

10、） for(i=0;in-1;i+) for(j=n;ji;j-) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 判定一個棧ST（最多元素為m0）為空的條件是：（ ）A. ST-top0 B .ST-top0C. ST-topm0 D. ST-topm03. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ）A. edcba B .decba C. dceab D. abcde 4. 在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（ ）A. s-next=p;p-next=s

11、;B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p;5 在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時（ ）A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）A. 可以順序存儲 B .數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符7. 稀疏矩陣一般的壓縮方法有兩種，即( ) A. 二維數(shù)組和三維數(shù)組 B .三元組和散列C. 三元組和十字鏈表 D. 散列和十字鏈表8 將遞歸算

12、法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用( )A. 棧 B .隊列 C. 鏈表 D. 樹 9二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時下列哪一元素的起始地址相同( )A. M24 B .M34 C. M35 D. M4410. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為( )A. SA+144 B .SA+180 C. SA+222 D. SA+22511. 如果T2是由有

13、序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的( )A. 前序 B .中序 C. 后序 D. 層次序12.一個有n個頂點的無向圖最多有多少邊( )A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉樹的定義，具有3個結(jié)點的二叉樹有( )種 A. 3 B .4 C. 5 D. 6 14.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊( )A. 只有右子樹上的所有結(jié)點 B .只有右子樹上的部分結(jié)點 C. 只有左子樹上的部分結(jié)點 D. 只有左子樹上的所有結(jié)點15. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的多少倍( )A. 12 B .1 C. 2 D. 416.

14、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的( )A. 先序遍歷 B .中序遍歷 C. 后序遍歷 D. 按層遍歷17.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為( )A. n B .n2 C. (n+1)2 D. (n-1)2二、填空題1. 算法的計算量的大小稱為計算的_ _。2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 和 以及他們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算,設(shè)計出相應(yīng)的 ,而確保經(jīng)過這些運算后所得的新結(jié)構(gòu)是 結(jié)構(gòu)類型。3在一個單鏈表中刪除p結(jié)點，應(yīng)執(zhí)行下列操作： q=p-next; p-data=p-next-data; p-next= ; free(q);4.有一空桟，

15、現(xiàn)有輸入序列5,4,3,2,1,經(jīng)push,push,pop,push,pop,push,push后，輸出序列為 。5在雙向鏈表中每個結(jié)點包含兩個指針域，一個指向 結(jié)點，另一個指向 結(jié)點。 6一維數(shù)組的邏輯結(jié)構(gòu)是 ,存儲結(jié)構(gòu)是 。 7.對于一棵含有40個結(jié)點的理想平衡樹，它的高度為_ 。8.假定對長度n50的有序表進行折半搜索，則對應(yīng)的判定樹高度為 ,判定樹中前5層的結(jié)點數(shù)為 ,最后一層的結(jié)點數(shù)為 。 9. 假定一組記錄的排序碼為（46，79，56，38，40，80），對其進行歸并排序的過程中，第二趟歸并后的結(jié)果為_ 。10. 假定一組記錄的排序碼為（46，79，56，38，40，80），對其

16、進行快速排序的一次劃分的結(jié)果為_。三、簡答題 1.假定有四個元素A,B,C,D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列？2.一棵含有n個結(jié)點的k叉樹，可能達到的最大深度和最小深度各為多少？ 3. 設(shè)有5000個無序的元素，希望用最快速度挑選出其中前10個最大的元素，在以下的排序方法中，采用哪種方法最好？為什么？（快速排序，堆排序，基數(shù)排序） 一、選擇題1. B 2. B 3. C 4. B 5C 6B 9C 10A 11B 12. C 13. B 14. C 15. C 16. A 17. C 18. A 19. C 二、填空題1.復(fù)雜度 2 物理結(jié)構(gòu) ， 邏輯結(jié)構(gòu) ，算法 ,

17、原來的 3 q-next; 4. 4,3 5. 前驅(qū) ， 后續(xù) 6 線性結(jié)構(gòu) , 順序結(jié)構(gòu) 7. 5 8. 5 , 31 , 19 。 9. 38 46 56 7940 84 。10. (84,79,56,38,40,46) 。三、問答題 1.答：共有14種可能的出棧序列為：ABCD, ABDC, ACBD, ACDB, BACD, ADCB, BADC, BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA 2. 答： 顯然能達到最大深度的是單支樹其深度為n；深度最小的是完全k叉樹。3. 答： 用堆排序最好，因為堆排序不需要等整個排序結(jié)束就可挑出前10個最大元素，而快速排序和

18、基數(shù)排序都需等待整個排序結(jié)束才能知道前10個最大元素。 1. 下面程序段的執(zhí)行次數(shù)為（ A ） for(i=0;in-1;i+) for(j=n;ji;j-) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ）A. 110 B .108 C. 100 D. 1203. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循環(huán)隊列用數(shù)組A0,m

19、1存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊列中的元素個數(shù)是（ D ）A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5不帶頭結(jié)點的單鏈表head為空的判定條件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6 在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（ B）A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-nex

20、t=p-next;p=s; D. p-next=s;s-next=p;7. 從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較多少個結(jié)點（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9串是一種特殊的線性表，其特殊性體現(xiàn)在( B ) A. 可以順序存儲 B .數(shù)據(jù)元素是一個字符C. 可以鏈接存儲 D.

21、 數(shù)據(jù)元素可以是多個字符11二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時下列哪一元素的起始地址相同( B ) A. M24 B .M34 C. M35 D. M4412. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為( C )A. SA+144 B .SA+180 C. SA+222 D. SA+22513. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的

22、結(jié)點數(shù)至少為：( B )A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是( D )A. acbed B .decab C. deabc D. cedba15. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把 由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。下列結(jié)論哪個正確( A )A. 樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B .樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍

23、歷序列相同D. 以上都不對 16. 具有6個頂點的無向圖至少應(yīng)有多少條邊才能確保是一個連通圖( A )A. 5 B .6 C. 7 D. 817. 順序查找法適合于存儲結(jié)構(gòu)為( B )的線性表 A. 散列存儲 B .順序存儲或鏈接存儲C. 壓縮存儲 D. 索引存儲18.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為( C )A. n B .n2 C. (n+1)2 D. (n-1)219. 有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為( B )A. 3512 B .3712 C. 3912 D. 431220.有一個有

24、序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值82為的結(jié)點時，幾次比較后查找成功（ C ）二、填空題（每空1分，共20分）1.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置，決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。2對于一個具有N個結(jié)點的單鏈表，在已知的結(jié)點P后插入一個新結(jié)點的時間復(fù)雜度為O(1),在給定值為X的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O(N)。 3.有一空桟，現(xiàn)有輸入序列1,2,3,4,5,經(jīng)push,push,pop,push,pop,push,push后，輸出序列為 2,3 。4在一個

25、無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 2 倍 5.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為 n-1。6. 在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有 6個7.在霍夫曼編碼中，若編碼長度只允許小于等于4，則除了已對兩個字符編碼為0和10外，還可以最多對 4 個字符編碼。8. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 n 和 n-1 。9. 對20個記錄進行歸并排序時，共需要進行 5 趟歸并，在第三趟歸并時是把長度為 4 的有序表兩兩歸并為長度為 8 的有序表。三、問答題 1. 簡述下面算法的

26、功能（棧和隊列的元素類型均為int） void algo3(Queue &Q) Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue(Q,d);Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue(Q,d); 算法的功能：利用棧作輔助，將隊列中的數(shù)據(jù)元素進行逆置2. 已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。由先序遍歷和后序遍歷序列不能唯一確定

27、一棵二叉樹.。一、選擇題1. 下面程序段的執(zhí)行次數(shù)為（ ） for(i=0;in-1;i+) for(j=n;ji;j-) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 判定一個棧ST（最多元素為m0）為空的條件是：（ ）A. ST-top0 B .ST-top0C. ST-topm0 D. ST-topm03. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ）A. edcba B .decba C. dceab D. abcde 4. 在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)

28、點，則執(zhí)行（ ）A. s-next=p;p-next=s;B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p;5 在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時（ ）A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）A. 可以順序存儲 B .數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符7. 稀疏矩陣一般的壓縮方法有兩種，即( ) A. 二維數(shù)組和三維數(shù)組 B .三元組和散列

29、C. 三元組和十字鏈表 D. 散列和十字鏈表8 將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用( )A. 棧 B .隊列 C. 鏈表 D. 樹 9二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時下列哪一元素的起始地址相同( )A. M24 B .M34 C. M35 D. M4410. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為( )A. SA+144 B .SA+180 C.

30、 SA+222 D. SA+22511. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的( )A. 前序 B .中序 C. 后序 D. 層次序12.一個有n個頂點的無向圖最多有多少邊( )A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉樹的定義，具有3個結(jié)點的二叉樹有( )種 A. 3 B .4 C. 5 D. 6 14.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊( )A. 只有右子樹上的所有結(jié)點 B .只有右子樹上的部分結(jié)點 C. 只有左子樹上的部分結(jié)點 D. 只有左子樹上的所有結(jié)點15. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的多少倍( )A. 12 B .1 C. 2 D. 416.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的( )A. 先序遍歷 B .中序遍歷 C. 后序遍歷 D. 按層遍歷17.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為( )A. n B .n2 C. (n+1)2 D. (n-1)2二、填空題1. 算法的計算量的大小稱為計算的_ _。2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 和 以及他們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算,設(shè)計出相應(yīng)的 ,而確保經(jīng)過