數(shù)據(jù)結(jié)構(gòu)書面作業(yè)練習(xí)題69

1、習(xí)題六 樹和二叉樹圖8.7 4棵二叉樹圖8.8 4棵二叉樹3.在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是BA. t > left=NULLB. t > ltag=1C. t > ltag=1 且 t > left=NULL D.以上都不對(duì)4 .二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的線索，這種說法_BA.正確B.錯(cuò)誤5 .二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法A.正確B.錯(cuò)誤6 .由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹，這種說法B_oA.正確B.錯(cuò)誤7 .設(shè)高度為h的二叉樹上只有度為 0和度為2的

2、結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù) 至少為_B_。A. 2hB. 2h-1 C. 2h+1 D. h+1a8 .如圖8.9所示二叉樹的中序遍歷序列 B_oA. abcdgef B. dfebagc C. dbaefcgD. defbagc圖8.9一棵二叉樹9 .已知某二叉樹的后序遍歷序列是dabec ,中序遍歷序列是 debac ,它的前序遍歷序列是D oA. acbed B. decab C. deabc D.cedba10 .設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是B 。A. a在b的右方B. a在b的左方C . a是b的祖先D . a是b的子孫11 .假定在一棵二

3、叉樹中，雙分支結(jié)點(diǎn)數(shù)為 個(gè)。BA. 15B . 1615 ,單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為C. 17D . 4712 .某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是dgbaechf , 則其后序遍abdgcefh ,中序遍歷的結(jié)點(diǎn)訪問順序是歷的結(jié)點(diǎn)訪問順序是 DA. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca13 .二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法_B_OA.正確B.錯(cuò)誤14 .按照二叉樹的定義，具有 3個(gè)結(jié)點(diǎn)的二叉樹有_C_種。A. 3B. 4C. 5D. 615 . 一棵二叉樹如圖8.10所示，

4、其中序遍歷的序列為 _B_OA. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh圖8.10 一棵二叉樹16 .樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。 這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論 A是正確的。A.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B.樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D.以上都不對(duì)17 .深度為5的二叉樹至多有 C一個(gè)結(jié)點(diǎn)。A.16 B. 32 C. 31 D. 1018

5、 .在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_A。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)19 .樹最適合用來表示_C_。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)20 .任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_A_A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)21 .實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用_C_存儲(chǔ)結(jié)構(gòu)。A.二叉鏈表B.廣義表存儲(chǔ)結(jié)構(gòu)C.三叉鏈表D.順序存儲(chǔ)結(jié)構(gòu)22.對(duì)一個(gè)滿二叉樹， m個(gè)樹葉,A.

6、n=h+mB. h+m=2nn個(gè)結(jié)點(diǎn)，深度為h ,則_D_。C. m=h-1D. n=2 h-123.如果某二叉樹的前序?yàn)閟tuwv ,中序?yàn)閡wtvs ,那么該二叉樹的后序?yàn)锳. uwvtsB. vwutsC. wuvtsD. wutsv24.具有五層結(jié)點(diǎn)的二叉平衡樹至少有B一個(gè)結(jié)點(diǎn)。F(n)=F(n-1)+F(n-2)+1, 1 是根節(jié)點(diǎn),F(n-1)是左子樹的節(jié)點(diǎn)數(shù)量，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量A. 10 B. 12 C. 15 D. 1725.設(shè)n, m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是_C。A. n 在m 右方B. n 是m 祖先 C. n 在m左方D. n

7、 是 m子孫1.有一棵樹如圖8.12所示，回答下面的問題: 這棵樹的根結(jié)點(diǎn)是 K1_ ;這棵樹的葉子結(jié)點(diǎn)是 K2,K5,K7,K4_;結(jié)點(diǎn)k3的度是_2;這棵樹的度是3_;這棵樹的深度是_4;(6)結(jié)點(diǎn)k3的子女是_K5,K6_ ;結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_K1_ ;2 .指出樹和二叉樹的三個(gè)主要差別_樹的結(jié)點(diǎn)個(gè)數(shù)至少為 1 ,而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0;樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2;樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分 。3 .從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是_利用二叉樹的已有算法解決樹的有關(guān)問題。4 . 一棵二叉樹的結(jié)

8、點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，如圖8.13所示，則該叉樹的鏈接表示形式為。5 .深度為k的完全二叉樹至少有_2k-1_個(gè)結(jié)點(diǎn)。至多有_2k-1_個(gè)結(jié)點(diǎn)，若按自上而下， 從左到右次序給結(jié)點(diǎn)編號(hào)(從1開始)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_2k-2+1。6 .在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n 2,則有n0=_n2+1 。7 . 一棵二叉樹的第i (i>1)層最多有_2i-1一個(gè)結(jié)點(diǎn)；一棵有n (n>0 )個(gè)結(jié)點(diǎn)的滿二叉 樹共有2l0g2n+1卜1 個(gè)葉子和 2l0g2n+1 -1_個(gè)非終端結(jié)點(diǎn)。8 .結(jié)點(diǎn)最少的樹為只有一個(gè)結(jié)點(diǎn)的樹_,結(jié)點(diǎn)最少的

9、二叉樹為_空二叉樹。9 .現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc ,問有_5_種不同形態(tài)的二叉樹可以得到這一遍歷 結(jié) 果， 這 些 二 叉 樹 分 別 是10 .根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有5_種不同的形態(tài)，它們分別是參照樓上 。11 .由如圖8.17所示的二叉樹，回答以下問題：其中序遍歷序列為_dgbaechif_ ;其前序遍歷序列為abdgcefhi _；其后序遍歷序列為_gdbeihfca ;(4) 該 二 叉 樹 的 中 序 線 索 二 叉 樹 為(6)該二叉樹的后序線索二叉樹為 該二叉樹對(duì)應(yīng)的森林是12.已知一棵樹如圖 8.20所示，轉(zhuǎn)化為一棵二叉樹，表示為圖8.17 一棵二

10、叉樹10 , 12 , 18為結(jié)點(diǎn)權(quán)值所構(gòu)造的Huffman樹為,其帶權(quán)路徑長(zhǎng)度為_165_ 。6.3算法設(shè)計(jì)題：1 .試編寫算法，對(duì)一棵以孩子 -兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)。2 . 一棵度為2的樹與一棵二叉樹有何區(qū)別 ？3 . 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度和最小深度各為多少？4 .證明：一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù) n 0和非葉子結(jié)點(diǎn)數(shù)n 1之間滿足以下關(guān)系n0=(k-1)n 1+15 .請(qǐng)對(duì)下圖所示二叉樹進(jìn)行后序線索化，為每個(gè)空指針建立相應(yīng)的前驅(qū)或后繼線索。6 .畫出和下列已知序列對(duì)應(yīng)的樹T:樹的先根次序訪問序列為 GFKDAIEBCHJ樹的后根次序訪問序列為DIAEKF

11、CJHBFG7 .假設(shè)用于通訊的電文僅有八個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。試為這個(gè)字母設(shè)計(jì)哈夫曼編碼。使用 0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。8 .假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK 。請(qǐng)畫出該樹。9 .編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。習(xí)題七圖7.1單項(xiàng)選擇題1 .在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_A倍。A. 1/2B. 1C. 2D. 42 .在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂

12、點(diǎn)的出度之和的_B_倍。A. 1/2B. 1C. 2D. 43 . 一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有_C_條邊。A. nB. n(n-1)C. n(n-1)/2D. 2n4 .具有4個(gè)頂點(diǎn)的無向完全圖有_A_條邊。A. 6 B. 12 C. 16 D. 205 .具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有_A_條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 86 .在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要C_條邊。A. n B. n+1 C. n-1 D. n/2_ D _。7 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是A. n B. (n-1) 2 C. n

13、-1 D. n 28 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為A;所有鄰接表中的接點(diǎn)總數(shù)是JDC。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. eC.2e D. n+e9 .已知一個(gè)圖如圖 9.5所示，若從頂點(diǎn) a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為D A. a,b,e,c,d,f A. a,b,c,e,d,f;按寬度搜索法進(jìn)行遍歷,B. e,c,f,e,b,dB. a,b,c,e,f,d則可能得到的一種頂點(diǎn)序列為C. a,e,b,c,f,dC. a,e,b,c,f,d圖9.5一個(gè)無向圖2）。D. a,e,d,f,

14、c,bD. a,c,f,d,e,b10 .已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖9.6所示。圖9.6一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_C_OA. v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_B_OA. v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4D.v1,v4,v3,v5,v211 .采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_OA

15、.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷12 .采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹的_D。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷13 .判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用D.A.求關(guān)鍵路徑的方法B.求最短路徑的 Dijkstra 方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法7.2 填空題(將正確的答案填在相應(yīng)俄空中)1. n個(gè)頂點(diǎn)的連通圖至少_n-1條邊。2 .在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或v vi,vj 屬于圖G的邊集合，則對(duì)應(yīng)元素Aij 等于_1_,否則等于0_。3 .在無向圖G的鄰接矩陣A中，若Aij等于1,則A皿

16、i 等于_1_。4 .已知圖G的鄰接表如圖9.7所示，其從頂點(diǎn) v1出發(fā)的深度有限搜索序列為 ,其 從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為。圖9.7 圖G的鄰接表i個(gè)結(jié)點(diǎn)的入度的方法是i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是35 .已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第6 .已知一個(gè)圖的鄰接矩陣表示，刪除所有從第7 .31 .已知如圖所示的有向圖，請(qǐng)給出該圖的(1 )每個(gè)頂點(diǎn)的入/出度；(2)鄰接距陣；(3)鄰接表；(4)逆鄰接表；(5)強(qiáng)連通分量。2 .請(qǐng)用克魯斯卡爾普里姆兩種算法分別構(gòu)造最小生成樹:(1)(23.試列出下圖中全部的拓?fù)渑判蛐虼鮑。V9 ,其鄰接矩陣如下：(1)請(qǐng)畫出該AOE圖。(2)計(jì)算完成整個(gè)

17、計(jì)劃需要的時(shí)間。(3)求出該AOE網(wǎng)的關(guān)鍵路徑。V1V2V3V4V5V6V7V8V9V1工645ocococococV2ococococ1ococococV3ococococ1ococococV4ocococococ2ocococV5ococococococ97ocV6ocococococococ4ocV7ococococococococ2V8ococococococococ4V9ocococococococococ習(xí)題八 查 找8.1單項(xiàng)選擇題1 .順序查找法適合于存儲(chǔ)結(jié)構(gòu)為_B 的線性表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)2 .對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須

18、_C_oA.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序3 .采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_C.A. nB. n/2C. (n+1)/2D. (n-1)/24 .采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_D_OA. O (n2)B. O(nlog 2n)C. O(n)D. O(log 2n)5 .有一個(gè)有序表為1,3,9, 12 , 32 , 41 , 45 , 62 , 75 , 77 , 82 , 95 , 100,當(dāng) 分查找值82為的結(jié)點(diǎn)時(shí)， C_次比較后查

19、找成功。A. 1 B. 2 C. 4 D. 86 .設(shè)哈希表長(zhǎng) m=14 ,哈希函數(shù) H(key)=key%11 。表中已有4個(gè)結(jié)點(diǎn):H (15)=4; H (38)=5; H (61)=6; H (84)=7如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是_D_OA. 8B. 3C. 5D. 97 .有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況 下查找成功所需的平均比較次數(shù)為_B_。A. 35/12B. 37/12C. 39/12D. 43/128 .2 填空題(將正確的答案填在相應(yīng)的空中)1 .順序查找法的平均查找長(zhǎng)度為;二分查找法的平均查找長(zhǎng)度為;分

20、塊查找法(以二分查找確定塊)的平均查找長(zhǎng)度為 ;哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為。2 .二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)_,且是有序的3 .在散列函數(shù)H(key)=key%p 中，p應(yīng)取_小于表長(zhǎng)的最大素?cái)?shù) _。4 .假設(shè)在有序線性表 A1.20上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為_1,則比較二次查找成功的結(jié)點(diǎn)數(shù)為 _2,則比較三次查找成功的結(jié)點(diǎn)數(shù)為 _4_,則比較四 次查找成功的結(jié)點(diǎn)數(shù)為 _8_,則比較五次查找成功的結(jié)點(diǎn)數(shù)為 _5_,平均查找長(zhǎng)度為3.7 o5 .對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_O (n);若采用二分法查找，則時(shí)間復(fù)雜度為 _O

21、(log2n ) _;6 .在散列存儲(chǔ)中，裝填因子 a的值越大，則存取元素時(shí)發(fā)生沖突的可能性越大_；的值越小，則。7 .3綜合練習(xí)題：選取哈稀函數(shù) H (k) = (3k)MOD 11 。用開放定址法處理沖突，di=i (i=1 , 2,3 ,). 試在0-10的散列地址空間中對(duì)關(guān)鍵字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。習(xí)題九 排序9.1單項(xiàng)選擇題1.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D_oA.希爾排序B.起泡排序C.插入排序D.選擇排序3 .在待排序的元素序列基本有序的前提下，效率最高的排序方法

22、是 A_oA.插入排序B.選擇排序C.快速排序D.歸并排序4 . 一組記錄的關(guān)鍵字為(46 , 79 , 56 , 38 , 40 , 84 ),則利用堆排序的方法建立的初始 堆為。A. 79 , 46 , 56 , 38 , 40 , 80B. 38 , 46, 56 , 79 , 40 , 84 ,C. 84 , 79 , 56 , 46 , 40 , 38D. 84 , 56 , 79 , 40 , 46 , 385 . 一組記錄的關(guān)鍵字為(46 , 79 , 56 , 38 , 40 , 84 ),則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為C_。A. 3840 46

23、56 79 84B. 4038 46 79 56 84C. 40 , 38 , 46 , 56 , 79 , 84D. 40 , 38 , 46 , 84 , 56 , 796 . 一組記錄的關(guān)鍵字為(25 , 48 , 16 , 35 , 79 , 82 , 23 , 40 , 36 , 72 ),其中含有 5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)彳L趟歸并后的結(jié)果為A_ oA. 162535 4823 4079823672B. 16 , 25 , 35 , 48 , 79 , 82 , 23 , 36 , 40 , 72C. 16 , 25 , 48 , 35 , 79 , 82

24、, 23 , 36 , 40 , 72D. 162535 4879 23364072827 .排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn) 行比較，將其放入已排序序列的正確位置上的方法，稱為_C_。A.希爾排序B.起泡排序C.插入排序D.選擇排序8 .排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空） 的一端的方法，稱為_D。A.希爾排序B.歸并排序C.插入排序D.選擇排序9.用某種排序方法對(duì)線性表( 元素序列的變化情況如下：25,84,21,47,20,15,21,25,15,20,21,25,(4)15,20,21,25,152768352047276835843527476884273547688425 , 84 , 21 , 47 , 15 , 27 , 68 , 35 , 20 )進(jìn)行排序時(shí),則所采用的排序方法是_D.A.選擇排序B.希爾排序C.歸并排序D.快速排序10 .下述幾種排序方法中，平均查找長(zhǎng)度最小的是_C。D.歸并排序D.歸并排序A.插入排序B.選擇排序C.快速