數(shù)據(jù)結(jié)構(gòu)(復(fù)習(xí)題目)

1、頁(yè)眉內(nèi)容一是非題（線性結(jié)構(gòu)）4 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。錯(cuò)5 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。錯(cuò)6 .在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：錯(cuò)P->next=S;S->next=P->next;。7 對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。對(duì)8 .順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)10. 線性表的順序存儲(chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。對(duì)11. 棧和隊(duì)列是操作上受限制的線性表。對(duì)12. 隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。錯(cuò)13. 隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。

2、錯(cuò)15 .棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。錯(cuò)16 隊(duì)列是一種運(yùn)算受限的線性表對(duì)（樹(shù)形結(jié)構(gòu)）1. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹(shù)，則無(wú)此限制，所以，二叉樹(shù)是樹(shù)的特殊情形。錯(cuò)2. 二叉樹(shù)是一棵結(jié)點(diǎn)的度最大為二的樹(shù)。錯(cuò)3. 赫夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。對(duì)5. 假設(shè)B是一棵樹(shù)，B'是對(duì)應(yīng)的二叉樹(shù)。則B的后根遍歷相當(dāng)于B'的后序遍歷。錯(cuò)6. 通常，二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)。錯(cuò)7. 中序線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。對(duì)8126.7.9.1.2.34561.23二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面

3、。對(duì)（圖形結(jié)構(gòu)）錯(cuò)錯(cuò)一個(gè)無(wú)向圖的連通分量是其極大的連通子圖。對(duì)連通圖的生成樹(shù)是一個(gè)包含圖G所有n個(gè)頂點(diǎn)和任意n-1條邊的子圖。錯(cuò)鄰接表可以表示有向圖，也可以表示無(wú)向圖。（）對(duì)（查找）二叉排序樹(shù)的平均查找長(zhǎng)度為O（logn）o對(duì)二叉排序樹(shù)的最大查找長(zhǎng)度與（LOG2N）同階。錯(cuò)選用好的HASH函數(shù)可避免沖突。錯(cuò)折半查找不適用于有序鏈表的查找。對(duì)一般來(lái)說(shuō)，折半查找不適用于有序鏈表的查找。對(duì)二叉排序樹(shù)的查找和折半查找的時(shí)間性能相同。錯(cuò)（排序）對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。對(duì)對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于冒泡排序。錯(cuò)在最壞情況下，堆排序的時(shí)間性能是O（nlogn）,比快速排

4、序好對(duì)選擇題。1-19是線性、樹(shù)形、圖形結(jié)構(gòu)，20-29是查找和排序）1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.順序組織和鏈接組織C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.基本類(lèi)型和組合類(lèi)型2、線性表L在（B）情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。A.不需彳改L的結(jié)構(gòu)B.需不斷對(duì)L進(jìn)行刪除、插入C.需經(jīng)常修改L中結(jié)點(diǎn)值D.L中含有大量結(jié)點(diǎn)3、若入棧順序?yàn)?A、B、C、D、E,則下列（D ）出棧序列是不可能的。A. A、B、C、D、EC. C、 D、 B、 E、 A4、遞歸程序可借助于（Ca.線性表 b.隊(duì)列5、在下列數(shù)據(jù)結(jié)構(gòu)中（C（ B ）具有先進(jìn)后出B. B、C、D、A、ED. D、E、C、A

5、、B）轉(zhuǎn)化為非遞歸程序。c:棧 d.數(shù)組）具有先進(jìn)先出（FIFO ）特性，（FILO ）特性。a.線性表b.棧 c.隊(duì)列 d .廣義表6、若對(duì)編號(hào)為1,2,3的列車(chē)車(chē)廂依次通過(guò)扳道棧進(jìn)行調(diào)度，不能得到（e）的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,17、假設(shè)用于通訊的電文僅由6個(gè)字符組成，字母在電文中出現(xiàn)的頻率分別為7,19,22,6,32,14。若為這6個(gè)字母設(shè)計(jì)哈夫曼編碼（設(shè)生成新的二叉樹(shù)的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉樹(shù)總是插入在最右），則頻率為7的字符編碼是（g）,頻率為32的字符編碼是（c）。a:00b:01c:10d:

6、11e:011f:110g:1110h:11118、對(duì)二叉排序樹(shù)（C）可得到有序序列。a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷9、設(shè)一棵二叉樹(shù)BT的存儲(chǔ)結(jié)構(gòu)如下：Ichild data rchild30 0 6000BC DEFGH5 4 087 006782A0其中Ichild , rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。則11該二叉樹(shù)白高度為3；第3層有四個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)為第1層）。A.2B.3C.4D.510、在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中，空指針數(shù)（B）。a.不定b.n+1c.nd.n-111、若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，

7、則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是（C）。A.40B.55C.59D.6112、已知某二叉樹(shù)的先序遍歷次序?yàn)閍bcdefg中序遍歷次序?yàn)閎adcgfe,則該二叉樹(shù)的后序遍歷次序?yàn)椋–）。層次遍歷次序?yàn)椋╝）a: abcdefg b: cdebgfac: bdgfecad: edcgfba13、.圖示的三棵二叉樹(shù)中（C）為最優(yōu)二叉樹(shù)。14、對(duì)一棵完全二叉樹(shù)進(jìn)行層序編號(hào)。則編號(hào)為n的結(jié)點(diǎn)若存在右孩子，其位序是（d ）。編號(hào)為n的結(jié)點(diǎn)若存在雙親，其位置是（a）。a:n/2b: 2nc:2n-1d:2n+1e:n f: 2(n+1)15、設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為與森林F對(duì)應(yīng)的二叉樹(shù)

8、根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是他_。A. m1B. m1+m2C. m3 D. m2+m3ml、m2 和 m3 ,則16、下列二叉樹(shù)中,（a）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。a:最優(yōu)二叉樹(shù)b:次優(yōu)查找樹(shù)c:二叉平衡樹(shù)？?d:二叉排序樹(shù)17、設(shè)無(wú)向圖G=（V,E）和G=（V',Ej,若G是G的生成樹(shù)，則下面不正確的說(shuō)法是（b）。A.G是G的子圖B.G是G的連通分量C.G是G的無(wú)環(huán)子圖D.G是G的極小連通子圖且V=V18、任何一個(gè)連通圖的最小生成樹(shù)回_。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在19、已知某無(wú)向圖的鄰接表如下所示；（19）是其原圖。E（20）是按該鄰接表遍歷所得深

9、度優(yōu)先生成樹(shù)。C（21）是按該鄰接表遍歷所得廣度優(yōu)先生成樹(shù)。D0 a3211 b3z»l 11 R>l I I 二習(xí) I -N n->4Finn5 fn>3-nB. a bA. a b20、下列查找方法中（a）適用于查找單鏈表。A）順序查找B）折半查找C）分塊查找D）hash查找21、哈希表的查找效率取決于（d）。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是22、在Hash函數(shù)H（k尸kMODm中，一般來(lái)說(shuō)，m應(yīng)取（C）。A.奇數(shù)B.偶數(shù)C.素?cái)?shù)D.充分大的數(shù)23、在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢，可采用方法。A.

10、設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找24、靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于（B）。A.前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ)B.前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作C.前者只能順序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序25、根據(jù)插入次序(80,90,100,110,85,70,75,60,72)建立二叉排序樹(shù)。圖（a）是最終變化的結(jié)果。c:d:26、若有序表中關(guān)鍵字序列為:14, 20 , 25, 32 , 34, 45 , 57 , 69 , 77, 83 , 92。對(duì)其進(jìn)行折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是（C ）。查找32時(shí)需

11、進(jìn)行(C)次比較。27、已知哈希表地址空間為A0.8,哈希函數(shù)為H(k尸kmod7,采用線性探測(cè)再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲(chǔ)的下標(biāo)為(h);在等概率情況下查找成功的平均查找長(zhǎng)度為(C)。A.0B.1C.2D.3E.4F.5G.6H.728、若從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序，則該二叉樹(shù)是(C)。A.二叉排序樹(shù)B.赫夫曼樹(shù)C.堆D.平衡二叉樹(shù)29、已知一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42下列選擇中(D)是快速排序一趟排序的結(jié)

12、果。(B)是歸并排序一趟排序的結(jié)果。(A)是初始堆(大堆頂)。A) 86,75,77,58,42,19,56,35,48,26.B) 26,56,35,86,19,75,58,77,42,48.C) 35,26,19,42,58,48,56,75,86,77.D) 42,26,48,35,19,56,77,58,75,86.三.填空題(1-13是線性、樹(shù)形、圖形結(jié)構(gòu)，14-15是查找和排序)1、數(shù)據(jù)結(jié)構(gòu)通常有下列4類(lèi)基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖型結(jié)構(gòu)。2、線性表的順序存儲(chǔ)結(jié)構(gòu)是以物理存儲(chǔ)地址來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系的。3、遞歸過(guò)程可借助于數(shù)據(jù)結(jié)構(gòu)（棧）改寫(xiě)成非遞歸過(guò)程。4、設(shè)循環(huán)

13、隊(duì)列存于一維數(shù)組Qm中，尾指針rear指示隊(duì)尾元素在隊(duì)列中的當(dāng)前位置，?頭指針front指示隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則隊(duì)列長(zhǎng)度=（rear-front+m）%m）。5、在二叉樹(shù)的第i層上至少有1個(gè)結(jié)點(diǎn)，至多有2i-1個(gè)結(jié)點(diǎn)，深度為k的二叉樹(shù)至多有2k_-1個(gè)結(jié)點(diǎn).6、對(duì)樹(shù)的遍歷有先序遍歷樹(shù)和后序遍歷樹(shù)。若以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，則樹(shù)的先序遍歷可借用二叉樹(shù)的先尼迪也算法來(lái)實(shí)現(xiàn)，而樹(shù)的后序遍歷可借用二叉樹(shù)的中序遍歷算法來(lái)實(shí)現(xiàn)。7、設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3,則與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的左子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（m1-1）,右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（m2

14、+m3）。8、若某二叉樹(shù)有n0個(gè)葉子結(jié)點(diǎn)，有n1個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是（2n0+n1-1）。9、如果對(duì)完全二叉樹(shù)中結(jié)點(diǎn)從1開(kāi)始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定編號(hào)為i(i>1)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為（i/2）;所有編號(hào)（>n/2）的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。10、若某二叉樹(shù)中，有20個(gè)結(jié)點(diǎn)沒(méi)有孩子，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是59_。11、n個(gè)頂點(diǎn)的連通圖至少有n-1條邊,至多有n（n-1）/2 條邊。12、對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有（鄰接表（鄰接矩陣）等方法。13、在一個(gè)無(wú)向圖的鄰接表中,若表結(jié)點(diǎn)的個(gè)數(shù)是m,則圖中邊的條數(shù)是m/2條。14、若有序表

15、中關(guān)鍵字序列為:12, 22, 33, 4477, 88,99 , 100 , 101 對(duì)其進(jìn)行折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是3 ）。查找99時(shí)需進(jìn)行（2 ）次比較。15、用中序遍歷對(duì)二叉排序樹(shù)進(jìn)行訪問(wèn)可得到有序序列。已知Hash函數(shù)為 H (K) =K mod 13,散列地址為0 -14,用二次探測(cè)再散列處理沖突，關(guān)鍵字（23, 34, 56, 2475 , 12 , 49,52 , 36，92)的分布如圖，則平均成功的查找長(zhǎng)度為（0 12345678910 11 12 13 1452 369256342324751249圖示結(jié)構(gòu)題(1-4是線性、樹(shù)形、圖形結(jié)構(gòu)，5-6是查找排序)1 .已知在電文中只出現(xiàn)頻率為(5,26,7,23,20,19)的6個(gè)字符，畫(huà)出你建的哈夫曼樹(shù)，并給出其哈夫曼編碼。2 .已知某二叉樹(shù)的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG請(qǐng)畫(huà)出該二叉樹(shù)。3將圖示森林轉(zhuǎn)換為二叉樹(shù)，并對(duì)該二叉樹(shù)先序遍歷。4.某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：012345678910111213141516171819ABCDEFGHI(1)試畫(huà)出此二叉樹(shù)的圖形表示。(2)將