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

1、1. 下面程序段的執(zhí)行次數(shù)為( A )for(i=0;i v n- 1;i+)for(j=n;j > i;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. edcbaB .decba C.dceab D. abcde4. 循環(huán)隊列用數(shù)組 AO,m 1存放其元素值，已知其頭尾指針分別

2、是front和rear，則當前隊列中的元素個數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1D. read-front5不帶頭結(jié)點的單鏈表head 為空的判定條件是(A )A. head=NULLB .head-next=NULLC. head-next=head D. head!=NULL6 在一個單鏈表中，若 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;

3、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. 數(shù)據(jù)元素可

4、以是多個字符11. 二維數(shù)組 M 的元素是 4個字符(每個字符占一個存儲單元)組成的串，行下標 i 的范圍從 0到 4，列下標 j 的范圍從 0 到5， M 按行存儲時元素 M35 的起始地址與 M 按列存儲時下列哪 一元素的起始地址相同 ( B ) A. M24B .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. 設高

5、度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點， 則此類二叉樹中所包含的結(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)化得到的二叉樹叫做這棵樹對應的二叉樹。下列結(jié)論 哪個正確 ( A )A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同B . 樹的后根遍

6、歷序列與其對應的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同D. 以上都不對 16. 具有 6 個頂點的無向圖至少應有多少條邊才能確保是一個連通圖( 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)各元素等概率情況下查 找成功所需的平

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

8、入序列 1,2,3,4,5,經(jīng)push,push,pop,push,pop,push,push 后，輸出序列為 2,3 。4在一個無向圖中，所有頂點的度數(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ù)分別

9、為n 和n-1 。9. 對 20 個記錄進行歸并排序時，共需要進行 5 趟歸并，在第三趟歸并時是把長度為 4 的有序 表兩兩歸并為長度為 8 的有序表。三、問答題 1. 簡述下面算法的功能(棧和隊列的元素類型均為 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. 已知一棵二叉樹的中序遍歷序列和先序遍

10、歷序列為，試問能不能唯一確定一棵二叉樹。若給 定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？ 由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。 由先序遍歷和后序遍歷序列不能唯一確 定一棵二叉樹 .。一、選擇題1. 下面程序段的執(zhí)行次數(shù)為( )for(i=0;i v n- 1;i+) for(j=n;j > i;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 (最多元素為 mO)為空的條件是：()A. ST-topO B .ST-top = 0C.ST-topmO D. ST-top = mO3

11、. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸岀序列是()A. edcba B .decba C.dceab D. abcde4. 在一個單鏈表中，若 p 所指的結(jié)點不是最后結(jié)點，在 p 之后插入 s 所指結(jié)點，則執(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 在一個鏈隊中，假設 f 和 r 分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時()A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6

12、 串是一種特殊的線性表， 其特殊性體現(xiàn)在 ()A. 可以順序存儲 B . 數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符 7. 稀疏矩陣一般的壓縮方法有兩種， 即() A. 二維數(shù)組和三維數(shù)組 B .三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表 8 將遞歸算法轉(zhuǎn)換成對應的非遞歸算法時，通常需要使用 ()A. 棧 B .隊列 C. 鏈表 D. 樹 9二維數(shù)組 M 的元素是 4 個字符(每個字符占一個存儲單元)組成的串，行下標 i的范圍從0到4,列下標j的范圍從0到5, M按行存儲時 元素 M35 的起始地址與 M 按列存儲時下列哪一元素的起始地址相同 ()A.

13、 M24B .M34C. M35D. M4410. 數(shù)組 A 中，每個元素 A 的長度為 3 個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時， 元素 A85 的起始地址為 ()A. SA+144B .SA+180 C. 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é)

14、點的二叉樹有 ()種 A. 3 B .4 C. 5 D. 614.在一非空二叉樹的中序遍歷序列中，根結(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 .n2C. (n+1)2 D. (n-1)2二、填空題 1

15、. 算法的計算量的大小稱為計算的 _。2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的和以及他們之間的相互關(guān)系， 并對這種結(jié)構(gòu)定義相應的運算 ,設計岀相應的,而確保經(jīng)過這些運算后所得的新結(jié)構(gòu)是結(jié)構(gòu)類型。3在一個單鏈表中刪除p 結(jié)點，應執(zhí)行下列操作：q=p-next;p-data=p-next-data;p-next=;free(q);4.有一空桟，現(xiàn)有輸入序列5,4,3,2,1,經(jīng) push,push,pop,push,pop,push,push 后，輸岀序列為。結(jié)點，另一個指向, 存儲結(jié)構(gòu)是7.對于一棵含有5在雙向鏈表中每個結(jié)點包含兩個指針域，一個指向 結(jié)點。6一維數(shù)組的邏輯結(jié)構(gòu)是40 個結(jié)點的理想平衡樹，它的高度為

16、8. 假定對長度n= 50的有序表進行折半搜索，則對應的判定樹高度為，判定樹中前5層的結(jié)點數(shù)為,最后一層的結(jié)點數(shù)為。9. 假定一組記錄的排序碼為 (46， 79，56，38， 40，80)，對其進行歸并排序的過程中，第二趟歸并后的結(jié)果為 。10. 假定一組記錄的排序碼為(46， 79， 56， 38， 40， 80)，對其進行快速排序的一次劃分的結(jié)果為 。三、簡答題 1.假定有四個元素 A,B,C,D 依次進棧，進棧過程中允許出棧，試寫出所有可能的出 棧序列？ 2.一棵含有 n 個結(jié)點的 k 叉樹，可能達到的最大深度和最小深度各為多少？3. 設有5000 個無序的元素，希望用最快速度挑選出其中

17、前 10 個最大的元素，在以下的排序方法中，采 用哪種方法最好？為什么？(快速排序，堆排序，基數(shù)排序)一、選擇題 1. B 2. B 3. C 4. B5C 6B 9C 10A 11B 12. C 13. B 14.5.C 15. C 16. A 17. C18. A19. C二、填空題 1.復雜度 2 物理結(jié)構(gòu) ， 邏輯結(jié)構(gòu) ，算法 , 原來的 3q-next; 4. 4,3前驅(qū) ， 后續(xù) 6 線性結(jié)構(gòu) , 順序結(jié)構(gòu) 7. 5 8. 5, 3119。 9.38 46 56 7940 84。10.(84,79,56,38,40,46)。三、問答題 1.答：共有 14種可能的出棧序列為： ABC

18、D, ABDC, ACBD, ACDB, BACD, ADCB,BADC, BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA2. 答： 顯然能達到最大深度的是單支樹其深度為n；深度最小的是完全 k叉樹。3. 答： 用堆排序最好，因為堆排序不需要等整個排序結(jié)束就可挑出前10 個最大元素，而快速排序和基數(shù)排序都需等待整個排序結(jié)束才能知道前10 個最大元素。1. 下面程序段的執(zhí)行次數(shù)為( A )for(i=0;i v n- 1;i+) for(j=n;j > i;j-)state;A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n

19、+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. abcde4. 循環(huán)隊列用數(shù)組 A0,m 1存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1D. read-front5 不帶頭結(jié)點的單鏈表head為空的判

20、定條件是( A ) A. head=NULLB .head-next=NULLC. head-next=head D. head!=NULL6在一個單鏈表中，若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-next=p;7. 從一個具有 n 個結(jié)點的單鏈表中查找其值等于 x 結(jié)點時，在查找成功的情況下，需平均比較 多少個結(jié)點 ( D ) A. n B .n2 C. (n-1)2 D. (n+1)28 從一個棧頂

21、指針為 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個字符(每個字符占一個存儲單元)組成的串，行下標i的范圍從0到 4，列下標 j 的范圍從 0 到 5， M 按行存儲時元素 M35 的起始地址與 M 按列存儲時下列哪 一元素的起始地址

22、相同 ( B ) A. M24B .M34 C. M35D. 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. 設高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點， 則此類二叉樹中所包含的結(jié)點數(shù)至少為： ( B )A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是 de

23、bac,它的前序遍歷序列是( D )A. acbed B .decab C. deabc D. cedba15. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中 序遍歷和后序遍歷。這里,我們把 由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應的二叉樹。下列結(jié)論 哪個正確 ( A )A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同B .樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同D. 以上都不對 16. 具有 6 個頂點的無向圖至少應有多少條邊才能確保是一個連通圖 ( A )A. 5 B .6 C. 7 D

24、. 817. 順序查找法適合于存儲結(jié)構(gòu)為 ( B )的線性表 A. 散列存儲 B .順序存儲或鏈接存儲 C. 壓縮存儲 D. 索引存儲1 8.采用順序查找方法查找長度為 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, 77, 82, 95, 100 ,當

25、二分查找值 82 為的結(jié)點時,幾次比較后查找成功( C )二、填空題(每空 1 分,共 20 分)1. 在線性表的順序存儲中,元素之間的邏輯關(guān)系是通過物理存儲位置,決定的；在線性表的鏈接 存儲中, 元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。2對于一個具有 N 個結(jié)點的單鏈表,在已知的結(jié)點P后插入一個新結(jié)點的時間復雜度為0(1),在給定值為X的結(jié)點后插入一個新結(jié)點的時間復雜度為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.對于一

26、棵具有 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. 簡述下面算法的功能(

27、棧和隊列的元素類型均為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. 已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問能不能唯一確定一棵二叉樹。若給 定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？ 由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。 由先序遍歷和后序遍歷序列不能唯一確 定一棵二叉

28、樹 .。一、選擇題1. 下面程序段的執(zhí)行次數(shù)為( ) for(i=0;i v n- 1;i+)for(j=n;j > i;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 (最多元素為 mO)為空的條件是：()A. ST-topO B .ST-top = 0C.ST-topmO D. ST-top = mO3. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸岀序列是()A. edcba B .decba C.dceab D. abcde4. 在一個單鏈表中，若 p 所指的結(jié)點不是最后結(jié)點，在

29、 p 之后插入 s 所指結(jié)點，則執(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 在一個鏈隊中，假設 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.

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

31、，該數(shù)組按行存放時， 元素 A85 的起始地址為 ()A. SA+144 B .SA+18O C. 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. 614.在一非空二叉樹的中序遍歷序列中，根結(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. nB .n2C. (n+1)2D. (n-1)2二、填空題 1. 算法的計算量的大小稱為計算的 _。2數(shù)