武漢大學(xué)數(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. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為 2，則第 5 個(gè)元素的地址是 ( B )A. 110 B .108 C. 100 D. 1203. 一個(gè)棧的入棧序列是a,b,c,d,e ，則棧的不可能的輸出序列是 ( C )A. edcbaB .decba C.dceab D. abcde4. 循環(huán)隊(duì)列用數(shù)組 AO,m 1存放其元素值，已知其頭尾指針分別

2、是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1D. read-front5不帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是(A )A. head=NULLB .head-next=NULLC. head-next=head D. head!=NULL6 在一個(gè)單鏈表中，若 p 所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在 p 之后插入 s 所指結(jié)點(diǎn)，則執(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. 從一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于 x 結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 多少個(gè)結(jié)點(diǎn)(D )A. n B .n2 C. (n-1)2 D. (n+1)28 從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪結(jié)點(diǎn)的值，則執(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. 可以順序存儲(chǔ) B . 數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可

4、以是多個(gè)字符11. 二維數(shù)組 M 的元素是 4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo) i 的范圍從 0到 4，列下標(biāo) j 的范圍從 0 到5， M 按行存儲(chǔ)時(shí)元素 M35 的起始地址與 M 按列存儲(chǔ)時(shí)下列哪 一元素的起始地址相同 ( B ) A. M24B .M34 C. M35 D. M4412. 數(shù)組 A 中，每個(gè)元素 A 的長度為 3個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到 10，從首地址 SA 開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A85 的起始地址為 ( C )A.SA+144 B .SA+180 C. SA+222 D. SA+22513. 設(shè)高

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

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

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

8、入序列 1,2,3,4,5,經(jīng)push,push,pop,push,pop,push,push 后，輸出序列為 2,3 。4在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2 倍5.對(duì)于一棵具有 n 個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為 n-1 。6. 在一棵三叉樹中，度為 3 的結(jié)點(diǎn)數(shù)有 2 個(gè)，度為 2 的結(jié)點(diǎn)數(shù)有 1 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 2個(gè)， 那么度為 0 的結(jié)點(diǎn)數(shù)有 6 個(gè)7. 在霍夫曼編碼中， 若編碼長度只允許小于等于 4，則除了已對(duì)兩個(gè)字符編碼為 0和 10外，還可 以最多對(duì) 4 個(gè)字符編碼。8. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別

9、為n 和n-1 。9. 對(duì) 20 個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行 5 趟歸并，在第三趟歸并時(shí)是把長度為 4 的有序 表兩兩歸并為長度為 8 的有序表。三、問答題 1. 簡述下面算法的功能(棧和隊(duì)列的元素類型均為 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); 算法的功能：利用棧作輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置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. 判定一個(gè)棧ST (最多元素為 mO)為空的條件是：()A. ST-topO B .ST-top = 0C.ST-topmO D. ST-top = mO3

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

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

13、 M24B .M34C. M35D. M4410. 數(shù)組 A 中，每個(gè)元素 A 的長度為 3 個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)， 元素 A85 的起始地址為 ()A. SA+144B .SA+180 C. SA+222 D. SA+22511.如果 T2 是由有序樹 T 轉(zhuǎn)換而來的二叉樹，那么 T 中結(jié)點(diǎn)的后序就是 T2 中結(jié)點(diǎn)的 ()A. 前序 B .中序 C. 后序D. 層次序 12.一個(gè)有 n 個(gè)頂點(diǎn)的無向圖最多有多少邊()A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉樹的定義， 具有 3個(gè)結(jié)

14、點(diǎn)的二叉樹有 ()種 A. 3 B .4 C. 5 D. 614.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 ()A. 只有右子樹上的所有結(jié)點(diǎn)B .只有右子樹上的部分結(jié)點(diǎn) C. 只有左子樹上的部分結(jié)點(diǎn)D. 只有左子樹上的所有結(jié)點(diǎn)15. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的多少倍()A. 12 B .1 C. 2 D.416. 采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的()A. 先序遍歷B .中序遍歷 C. 后序遍歷 D. 按層遍歷17. 采用順序查找方法查找長度為n 的線性表每個(gè)元素的平均查找長度為 ()A. n B .n2C. (n+1)2 D. (n-1)2二、填空題 1

15、. 算法的計(jì)算量的大小稱為計(jì)算的 _。2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的和以及他們之間的相互關(guān)系， 并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算 ,設(shè)計(jì)岀相應(yīng)的,而確保經(jīng)過這些運(yùn)算后所得的新結(jié)構(gòu)是結(jié)構(gòu)類型。3在一個(gè)單鏈表中刪除p 結(jié)點(diǎn)，應(yīng)執(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é)點(diǎn)，另一個(gè)指向, 存儲(chǔ)結(jié)構(gòu)是7.對(duì)于一棵含有5在雙向鏈表中每個(gè)結(jié)點(diǎn)包含兩個(gè)指針域，一個(gè)指向 結(jié)點(diǎn)。6一維數(shù)組的邏輯結(jié)構(gòu)是40 個(gè)結(jié)點(diǎn)的理想平衡樹，它的高度為

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

17、前 10 個(gè)最大的元素，在以下的排序方法中，采 用哪種方法最好？為什么？(快速排序，堆排序，基數(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.復(fù)雜度 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. 答： 顯然能達(dá)到最大深度的是單支樹其深度為n；深度最小的是完全 k叉樹。3. 答： 用堆排序最好，因?yàn)槎雅判虿恍枰日麄€(gè)排序結(jié)束就可挑出前10 個(gè)最大元素，而快速排序和基數(shù)排序都需等待整個(gè)排序結(jié)束才能知道前10 個(gè)最大元素。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. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長度為 2，則第 5 個(gè)元素的地址是 ( B ) A. 110 B .108 C. 100 D. 1203. 一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸岀序列是 (C )A. edcba B .decba C.dceab D. abcde4. 循環(huán)隊(duì)列用數(shù)組 A0,m 1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1D. read-front5 不帶頭結(jié)點(diǎn)的單鏈表head為空的判

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

21、指針為 HS 的鏈棧中刪除 一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪結(jié)點(diǎn)的值，則執(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. 可以順序存儲(chǔ) B . 數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符11. 二維數(shù)組M的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到 4，列下標(biāo) j 的范圍從 0 到 5， M 按行存儲(chǔ)時(shí)元素 M35 的起始地址與 M 按列存儲(chǔ)時(shí)下列哪 一元素的起始地址

22、相同 ( B ) A. M24B .M34 C. M35D. M4412. 數(shù)組 A 中，每個(gè)元素 A 的長度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到 10，從首 地址 SA 開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素 A85 的起始地址為 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+22513. 設(shè)高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)， 則此類二叉樹中所包含的結(jié)點(diǎn)數(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)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。下列結(jié)論 哪個(gè)正確 ( A )A. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B .樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D. 以上都不對(duì) 16. 具有 6 個(gè)頂點(diǎn)的無向圖至少應(yīng)有多少條邊才能確保是一個(gè)連通圖 ( A )A. 5 B .6 C. 7 D

24、. 817. 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 ( B )的線性表 A. 散列存儲(chǔ) B .順序存儲(chǔ)或鏈接存儲(chǔ) C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)1 8.采用順序查找方法查找長度為 n 的線性表每個(gè)元素的平均查找長度為 ( C )A. n B .n2 C. (n+1)2 D. (n-1)219. 有一個(gè)長度為 12 的有序表,按二分查找法對(duì)該表進(jìn)行查找,在表內(nèi)各元素等概率情況下查 找成功所需的平均比較次數(shù)為 ( B )A. 3512 B .3712 C. 3912 D. 431220. 有一個(gè)有序表為 1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100 ,當(dāng)

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

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

27、棧和隊(duì)列的元素類型均為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); 算法的功能：利用棧作輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置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. 判定一個(gè)棧ST (最多元素為 mO)為空的條件是：()A. ST-topO B .ST-top = 0C.ST-topmO D. ST-top = mO3. 一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸岀序列是()A. edcba B .decba C.dceab D. abcde4. 在一個(gè)單鏈表中，若 p 所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在

29、 p 之后插入 s 所指結(jié)點(diǎn)，則執(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 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí)()A. r=f-next; B .r=r-next; C. f=f-next;D. f=r-next;6 串是一種特殊的線性表， 其特殊性體現(xiàn)在 ()A. 可以順序存儲(chǔ) B . 數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符 7. 稀疏矩陣一般的壓縮方法有兩種， 即() A.

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

31、，該數(shù)組按行存放時(shí)， 元素 A85 的起始地址為 ()A. SA+144 B .SA+18O C. SA+222 D. SA+22511.如果 T2 是由有序樹 T 轉(zhuǎn)換而來的二叉樹，那么 T 中結(jié)點(diǎn)的后序就是 T2 中結(jié)點(diǎn)的 ()A. 前序 B .中序 C. 后序D. 層次序 12.一個(gè)有 n 個(gè)頂點(diǎn)的無向圖最多有多少邊()A. n B .n(n-1) C. n(n-1)2 D. 2n13.按照二叉樹的定義， 具有 3個(gè)結(jié)點(diǎn)的二叉樹有 ()種 A. 3 B .4 C. 5 D. 614.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 ()A. 只有右子樹上的所有結(jié)點(diǎn)B .只有右子樹上的部分結(jié)點(diǎn) C. 只有左子樹上的部分結(jié)點(diǎn)D. 只有左子樹上的所有結(jié)點(diǎn)15. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的多少倍()A. 12 B .1 C. 2 D.416. 采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的()A. 先序遍歷 B .中序遍歷 C. 后序遍歷 D. 按層遍歷17. 采用順序查找方法查找長度為n 的線性表每個(gè)元素的平均查找長度為 ()A. nB .n2C. (n+1)2D. (n-1)2二、填空題 1. 算法的計(jì)算量的大小稱為計(jì)算的 _。2數(shù)