數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)(12.6)

1、精選文檔難度系數(shù)及復(fù)雜系數(shù)說(shuō)明：難度系數(shù)從易到難分別為：N1、N2、N3、N4、N5復(fù)雜系數(shù)從簡(jiǎn)到繁分別為：F1、F2、F3、F4、F5數(shù)據(jù)結(jié)構(gòu)第三階段作業(yè)第6章 樹(shù)和二叉樹(shù)6.1 單項(xiàng)選擇題1. 由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹(shù)是一種特殊的樹(shù)，這種說(shuō)法_B_。（N2F1）A. 正確 B. 錯(cuò)誤2. 假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 B 個(gè)。 （N2F1） A15 B16 C17 D473. 按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹(shù)有_C_種。（N2F1）A. 3 B. 4 C. 5 D. 64. 按照二叉樹(shù)的定義，具有3個(gè)不同數(shù)

2、據(jù)結(jié)點(diǎn)的不同的二叉樹(shù)有_C_種。（N3F1）A. 5 B. 6 C. 30 D. 325. 深度為5的二叉樹(shù)至多有_C_個(gè)結(jié)點(diǎn)。（N2F1）A. 16 B. 32 C. 31 D. 106. 設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為_(kāi) _A_。（N3F1）A. 2h B. 2h-1 C. 2h+1 D. h+17. 對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則_D_ 。（N3F1）A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-18. 任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_A_。（N3F1）A.不發(fā)生

3、改變 B.發(fā)生改變 C.不能確定 D.以上都不對(duì)9. 如果某二叉樹(shù)的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹(shù)的后序?yàn)開(kāi)C_。（N3F1） A. uwvts B. vwuts C. wuvts D. wutsv6.2 簡(jiǎn)答題1. 根據(jù)二叉樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)有5種不同的形態(tài)，請(qǐng)將它們分別畫(huà)出。（N2F3）2. 假設(shè)一棵 二叉樹(shù)的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。（N3F2）請(qǐng)畫(huà)出該樹(shù)。3. 以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值，畫(huà)出構(gòu)造Huffman樹(shù)的每一步圖示，計(jì)算其帶權(quán)路徑長(zhǎng)度。（N3F3）4. 一棵含有N個(gè)

4、結(jié)點(diǎn)的k叉樹(shù),可能達(dá)到的最大深度和最小深度各為多少? （N3F2）最大深度：h=N-k+1,最小深度：logkN+1第7章 圖7.1 單項(xiàng)選擇題1在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_C_倍。（N3F1）A. 1/2 B. 1 C. 2 D. 4 2任何一個(gè)無(wú)向連通圖的最小生成樹(shù) B 。（N3F1）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_B_倍。（N3F1）A. 1/2 B. 1 C. 2 D. 44一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有_C_條邊。（N2F1）A. n B. n(n-1) C. n(n-1)/2 D.

5、 2n5具有4個(gè)頂點(diǎn)的無(wú)向完全圖有_A_條邊。（N2F1）A. 6 B. 12 C. 16 D. 206具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有_A_條邊才能確保是一個(gè)連通圖。（N3F1）A. 5 B. 6 C. 7 D. 87在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要_C_條邊。（N3F1）A. n B. n+1 C. n-1 D. n/28對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是_A_。（N3F1）A. n B. (n-1)2 C. n-1 D. n29對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為_(kāi)A_；所有鄰接表中的接點(diǎn)總數(shù)是_C_。

6、（N3F1） A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一個(gè)圖如圖7.1所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為D_B_；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)。（N3F1） A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf圖 7.1 一個(gè)無(wú)向圖7.2 綜合題badcef1611151515

7、16131412211請(qǐng)用克魯斯卡爾和普里姆兩種算法分別為圖7.6、圖7.7構(gòu)造最小生成樹(shù)： （N3F3）（1） 圖7.661213212495201516106154372（2）圖7.72請(qǐng)用圖示說(shuō)明圖7.9從頂點(diǎn)a到其余各頂點(diǎn)之間的最短路徑。（N3F3）543223356abdfce圖7.93已知AOE網(wǎng)有9個(gè)結(jié)點(diǎn)：V1，V2，V3，V4，V5，V6，V7，V8，V9，其鄰接矩陣如下：(1)請(qǐng)畫(huà)出該AOE圖。(2)計(jì)算完成整個(gè)計(jì)劃需要的時(shí)間。(3)求出該AOE網(wǎng)的關(guān)鍵路徑。（N4F4）64511297424答：(1)該AOE圖為：(2)完成整個(gè)計(jì)劃需要18天。(3)關(guān)鍵路徑為：（V1，V2

8、，V5，V7，V9）和（V1，V2，V5，V8，V9，）第8章 查找8.1 單項(xiàng)選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為_(kāi)B_的線性表。（N2F1）A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈接存儲(chǔ)C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)2.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須_C_。（N2F1）A. 以順序方式存儲(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)度為_(kāi)C_.（N3F1）A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找長(zhǎng)度為n的線性表

9、時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)D_。（N3F1）AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)5.二分查找和二叉排序樹(shù)的時(shí)間性能_B_。（N2F1）A. 相同 B. 不相同6.有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，_C_次比較后查找成功。（N3F1）A. 1 B. 2 C. 4 D. 87.設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：（N3F1）addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7如用二次探測(cè)

10、再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是_D_。A. 8 B. 3 C. 5 D. 98.有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為_(kāi)B_。（N3F1）A. 35/12 B. 37/12 C. 39/12 D. 43/129對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為 C 。（N2F1）A.從第0個(gè)元素往后查找該數(shù)據(jù)元素B.從第1個(gè)元素往后查找該數(shù)據(jù)元素C.從第n個(gè)元素往開(kāi)始前查找該數(shù)據(jù)元素D.與查找順序無(wú)關(guān)10解決散列法中出現(xiàn)的沖突問(wèn)題常采用的方法是 D 。（N2F1）A.數(shù)字分析法、除余法、平方取中法B.數(shù)字

11、分析法、除余法、線性探測(cè)法C.數(shù)字分析法、線性探測(cè)法、多重散列法D.線性探測(cè)法、多重散列法、鏈地址法第9章 排序9.1 單項(xiàng)選擇題1. 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是_D_。（N2F1）A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用_C_排序法。（N2F1）A. 起泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。（N2F1）A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4.

12、 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為_(kāi)B_。（N3F1）A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為_(kāi)C_。（N3F1）A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為_(kāi)A_。（N3F1）A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，72