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

1、1. 下面程序段的執(zhí)行次數(shù)為( A ) for(i=0;i <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è)元素的長(zhǎng)度為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存放其元素值，已知其頭尾指針?lè)謩e

2、是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1 D. 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. M24 B .M34 C. M35 D. M4412. 數(shù)組 A 中，每個(gè)元素A 的長(zhǎng)度為 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)的無(wú)向圖至少應(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ǔ)B .n2C.18 .采用順序查找方法查找長(zhǎng)度為 n 的線性表每個(gè)元素的平均查找長(zhǎng)度為( C )A. n(n+1)2 D. (n-1)219 . 有一個(gè)長(zhǎng)度為12 的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)

7、為 ( 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)系是通過(guò)物理存儲(chǔ)位置，決定的；在線性表的鏈接存儲(chǔ)中， 元素之間的邏輯關(guān)系是通過(guò)鏈域的指針值決定的。 2 對(duì)于一個(gè)具有N 個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn) P 后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1), 在給定值為 X 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(N)。3

8、.有一空棧，現(xiàn)有輸入序列1,2,3,4,5，經(jīng)push,push,pop,push,pop,push,push 后，輸出序列為 2,3 。4在一個(gè)無(wú)向圖中，所有頂點(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. 在霍夫曼編碼中， 若編碼長(zhǎng)度只允許小于等于4， 則除了已對(duì)兩個(gè)字符編碼為 0 和 10 外， 還可以最多對(duì) 4 個(gè)字符編碼。8. 對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)和 e 條邊的連通圖，其生成樹中的頂

9、點(diǎn)數(shù)和邊數(shù)分別為 n 和n-1。9. 對(duì) 20 個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行5 趟歸并，在第三趟歸并時(shí)是把長(zhǎng)度為4 的有序表兩兩歸并為長(zhǎng)度為 8 的有序表。三、問(wèn)答題 1. 簡(jiǎn)述下面算法的功能(棧和隊(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、遍歷序列為，試問(wèn)能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。 由先序遍歷和后序遍歷序列不能唯一確定一棵二叉樹.。一、選擇題1. 下面程序段的執(zhí)行次數(shù)為( )for(i=0;i <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)A. ST-top0 B .ST-top =0C.2. 判定一個(gè)棧ST (最多元素為m0 )為空的條件是：(ST-topm0 D. ST-top = m03. 一個(gè)棧

11、的入棧序列是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. M24

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

14、， 具有 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. 采用順序查找方法查找長(zhǎng)度為 n 的線性表每個(gè)元素的平均查找長(zhǎng)度為 ()A. n B .n2C. (n+1)2 D. (

15、n-1)2二、填空題 1. 算法的計(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)過(guò)這些運(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

16、個(gè)結(jié)點(diǎn)的理想平衡樹，它的高度為8.假定對(duì)長(zhǎng)度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)行歸并排序的過(guò)程中， 第二趟歸并后的結(jié)果為 。10. 假定一組記錄的排序碼為( 46， 79 ， 56 ， 38， 40 ， 80)，對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為 。三、簡(jiǎn)答題 1.假定有四個(gè)元素A,B,C,D 依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫出所有可能的出棧序列？2.一棵含有n 個(gè)結(jié)點(diǎn)的 k 叉樹，可能達(dá)到的最大深度和最小深度各為多少？ 3.

17、 設(shè)有5000 個(gè)無(wú)序的元素，希望用最快速度挑選出其中前10 個(gè)最大的元素，在以下的排序方法中，采用哪種方法最好？為什么？(快速排序，堆排序，基數(shù)排序)1、 選擇題 1. B 2. B 3. C 4. B 5 C 6 B9 C 10 A 11 B 12. C 13. B 14.C15. C16. A17. C18.A 19.C2、 填空題1.復(fù)雜度 2物理結(jié)構(gòu)， 邏輯結(jié)構(gòu)， 算法 , 原來(lái)的 3q-next; 4. 4,35.前驅(qū) ， 后續(xù) 6 線性結(jié)構(gòu), 順序結(jié)構(gòu)7. 58. 5,3119。9.38 46 56 7940 84。 10.(84,79,56,38,40,46)。三、問(wèn)答題1.答

18、：共有14 種可能的出棧序列為： ABCD, 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 <n-1;i+) for(j=n;j >i;j-)state;A. n(n+2)2 B .(n-1)(n+2)

19、2 C. n(n+1)2 D. (n-1)(n+2)2. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100 ， 每個(gè)元素的長(zhǎng)度為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存放其元素值，已知其頭尾指針?lè)謩e是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( D )A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-

20、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; 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

21、 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ù)元素可以是多個(gè)字符11. 二維數(shù)組 M 的元素是 4 個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i 的范圍從 0到 4，列下標(biāo)j 的范圍從 0 到 5 ， M 按行存儲(chǔ)時(shí)元素M35

22、 的起始地址與 M 按列存儲(chǔ)時(shí)下列哪一元素的起始地址相同 ( B ) A. M24 B .M34 C. M35 D. M4412. 數(shù)組 A 中，每個(gè)元素A 的長(zhǎng)度為 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. 已知某二叉樹的

23、后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是( 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)的無(wú)向圖至少應(yīng)有多少條邊才能確保是一個(gè)連通

24、圖( A )A. 5 B .6 C. 7 D. 817 . 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為( B)的線性表A. 散列存儲(chǔ) B . 順序存儲(chǔ)或鏈接存儲(chǔ) C.壓縮存儲(chǔ) D. 索引存儲(chǔ)18 .采用順序查找方法查找長(zhǎng)度為 n 的線性表每個(gè)元素的平均查找長(zhǎng)度為( C )A. n B .n2 C.(n+1)2 D. (n-1)219 . 有一個(gè)長(zhǎng)度為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，

25、77， 82， 95， 100 ，當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，幾次比較后查找成功( C ) 二、填空題(每空1 分，共 20 分)1.在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)物理存儲(chǔ)位置，決定的；在線性表的鏈接存儲(chǔ)中， 元素之間的邏輯關(guān)系是通過(guò)鏈域的指針值決定的。 2 對(duì)于一個(gè)具有N 個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn) P 后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(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è)無(wú)向圖中，所有頂點(diǎn)的

26、度數(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. 在霍夫曼編碼中， 若編碼長(zhǎng)度只允許小于等于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í)是把長(zhǎng)度為4 的有序表兩兩歸并為長(zhǎng)度為 8 的有序表。三、問(wèn)答

27、題 1. 簡(jiǎn)述下面算法的功能(棧和隊(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. 已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問(wèn)能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。 由先序遍歷和后序遍歷序

28、列不能唯一確定一棵二叉樹.。一、選擇題 1. 下面程序段的執(zhí)行次數(shù)為( )for(i=0;i <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 (最多元素為 m0)為空的條件是：()A. ST-top0 B .ST-top = 0C.ST-topm0 D. ST-top = m03. 一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是()A. edcba B .decba C.dceab D. abcde4. 在一個(gè)單鏈表中，若 p 所指

29、的結(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 串是一種特殊的線性表， 其特殊性體現(xiàn)在()A. 可以順序存儲(chǔ) B . 數(shù)據(jù)元素是一個(gè)字符C. 可以鏈接存儲(chǔ)D. 數(shù)據(jù)元素可以是多個(gè)字符7.稀疏矩陣一般的壓縮方法有兩種，

30、即 () 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. M24B .M34 C. M35 D. M4410. 數(shù)組 A 中，每個(gè)元素A 的長(zhǎng)度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo)j 從 1 到 10，從首地址 SA

31、開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素 A85 的起始地址為 ()A. SA+144 B .SA+180 C. SA+222 D. SA+22511.如果 T2 是由有序樹 T 轉(zhuǎn)換而來(lái)的二叉樹，那么 T 中結(jié)點(diǎn)的后序就是T2 中結(jié)點(diǎn)的 ()A. 前序 B . 中序 C. 后序D. 層次序 12. 一個(gè)有 n 個(gè)頂點(diǎn)的無(wú)向圖最多有多少邊()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 .采用順序查找方法查找長(zhǎng)度為n 的線性表每個(gè)元素的平均查找長(zhǎng)度為 ()A. n B .n2C. (n+1)2 D. (n-1)2二、填空題 1. 算法的計(jì)算量的大小稱為計(jì)算的 _。2 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 和 以及他們之間的相互