《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題-答案

1、1. 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是 c C、哈希表2. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長度為 2，那么第 5 個(gè)元素的地址是 B B、1083. 假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為 head, 那么該鏈表為空的判定條件是 C C、head -next= =head4. 假設(shè)進(jìn)棧序列為 1， 2， 3， 4，5， 6，且進(jìn)棧和出棧可以穿插進(jìn)行，那么不可能出現(xiàn)的出棧序列是D D、 2，3，5，1，6，45. 以下關(guān)鍵字序列中，構(gòu)成小根堆的是 A A、12，21，49，33， 81，56，69，416. 以下數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是 A A、B 樹7. 用順序存儲(chǔ)的方法

2、來存儲(chǔ)一棵二叉樹，存放在一維數(shù)組A1.N 中，假設(shè)結(jié)點(diǎn) Ai 有右孩子，那么其右孩子是 C 。C 、 A2i+18. 設(shè)樹T的高度為4,其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1,那么T中葉子數(shù)為D D、89. 有數(shù)據(jù) 53 , 30, 37, 12, 45, 24, 96 ,從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹,假設(shè)希望高度最小,那么應(yīng)選擇 下面哪個(gè)序列輸入 B B、37, 24, 12, 30, 53, 45, 9610. 對下面有向圖給出了四種可能的拓?fù)湫蛄?其中錯(cuò)誤的選項(xiàng)是 C C、5, 1 , 6, 3, 4, 211. m階B-樹中所有非終端除根之外結(jié)點(diǎn)中的關(guān)鍵字個(gè)

3、數(shù)必須大于或等于(B )B、m/2-112. 散列文件也稱為 ( C )B 、索引文件13. 數(shù)據(jù)結(jié)構(gòu)是 D D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合14. 從邏輯關(guān)系來看,數(shù)據(jù)元素的直接前驅(qū)為 0 個(gè)或 1 個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是 C C線性結(jié)構(gòu)和樹型結(jié)構(gòu)15. 設(shè)p為指向雙向循環(huán)鏈表中某個(gè)結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個(gè)鏈域分別用 pTlink和p rlink表示，那么同樣表示p 指針?biāo)赶蚪Y(jié)點(diǎn)的表達(dá)式是 D D、p llink rlink16. 假設(shè)棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m ，topi 代表第 i 個(gè)棧( i =1,2) 棧頂，棧 1的底在 v1 ，棧 2的底在

4、 Vm ，那么棧滿的條件是 B B、top1+1=top217. 假設(shè)一棵二叉樹有 11個(gè)葉子結(jié)點(diǎn)，那么該二叉樹中度為 2 的結(jié)點(diǎn)個(gè)數(shù)是 A A、 1018. 樹的先根序列等同于與該樹對應(yīng)的二叉樹的 A A、先序序列19. 下面關(guān)于哈希(Hash，雜湊)查找的說法正確的選項(xiàng)是(C )C不存在特別好與壞的哈希函數(shù)，要視情況而定20. 以下序列中， D 是執(zhí)行第一趟快速排序后所得的序列。D 、 68 ， 11 ， 69， 23， 18 93， 7321. 以下關(guān)鍵字序列中，構(gòu)成小根堆的是 ( D )D、 ( 15， 28， 46， 37， 84， 58， 62， 41)22. ISAM文件和VAS

5、M文件屬于(C )C索引順序文件23. 下面程序段的時(shí)間復(fù)雜度為 C for (i=0; im; i+)for (j=0; jnext=s-next ；s-next=p ；25. 為便于判別有向圖中是否存在回路，可借助于 D D拓?fù)渑判蛩惴?6. 假設(shè)以S和X分別表示進(jìn)棧和退棧操作，那么對初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是D D、SSSXXSXX27. 設(shè)有一順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,那么棧的容量至少應(yīng)該是( B )B、328. 假設(shè)以數(shù)組 Am 存放循環(huán)隊(duì)列的元素。 隊(duì)列的長度為 length ，

6、指針 rear 指向隊(duì)尾元素的下一個(gè)存儲(chǔ)位置， 那么隊(duì)頭元 素所在的存儲(chǔ)位 置為 B 。B、(rear-length+m)%m29. 在一個(gè)鏈隊(duì)列中， front 和 rear 分別為頭指針和尾指針，那么插入一個(gè)結(jié)點(diǎn) s 的操作為 D 。 D、rear-next=s;rear=s;30. 對于哈希函數(shù) H(key)=key%13, 被稱為同義詞的關(guān)鍵字是 D D、25 和 5131. 采用二叉鏈表存儲(chǔ)的 n 個(gè)結(jié)點(diǎn)的二叉樹，共有空指針 A 個(gè)。A、 n+132. 連通網(wǎng)的最小生成樹是其所有生成樹中 D D、邊的權(quán)值之和最小的生成樹33. 對記錄序列 (314，298，508，123，486，

7、145)依次按個(gè)位和十位進(jìn)行兩趟基數(shù)排序之后所得結(jié)果為B B、 508，314，123，145，486，29834. 任何一個(gè)無向連通圖的最小生成樹 ( C )。C一棵或多棵35. 無向圖的鄰接矩陣是一個(gè) ( C )C、對稱矩陣36. 設(shè)無向圖G-=(V,E)和G =(V ,E),如G為G的生成樹，那么以下說法中不正確的選項(xiàng)是 (B )。B、G為G連通分量37. 以 v1 為起始結(jié)點(diǎn)對以下列圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是 D D、v1 ， v2 ， v5， v6， v7 ， v3， v438. 下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是 B B、 0,1,00,1139. 希爾排序的增量

8、序列必須是 B 。B、遞減的40. 采用起泡排序法對 n 個(gè)關(guān)鍵字進(jìn)行升序排序，假設(shè)要使排序過程中比擬關(guān)鍵字的次數(shù)最多，那么初始時(shí)的序列應(yīng)滿足條件 D D 、關(guān)鍵字從大到小排列41. 在以下內(nèi)部排序中 ( A ) 是不穩(wěn)定的。42.43.44.45.、1.2.3.4.5.6.7.8.9.10.11.12.13.A、希爾排序分別以以下序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是(C )。A 100，80， 90，60，120，110，130在查找過程中，沖突指的是C 。C不同鍵值對應(yīng)相同的存儲(chǔ)地址對有14個(gè)元素的有序表 A1.14作二分查找，查找元素 A4時(shí)的被比擬元素依次為D D

9、A7，A3，A5，A4以v1為起始結(jié)點(diǎn)對以下列圖進(jìn)行廣度度優(yōu)先遍歷，正確的遍歷序列是 A A、v1，v2，v3，v4，v5，v6，v7填空題(本大題共10小題，每題2分，假設(shè)有兩個(gè)空格，每個(gè)空格1分，共20分)數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素 的存儲(chǔ)和 數(shù)據(jù)之間關(guān)系的存儲(chǔ)。假設(shè)一個(gè)算法中的語句頻度之和為T(n)=1921n+4nlogn,那么算法的時(shí)間復(fù)雜度為nlogn。下面程序段的時(shí)間復(fù)雜度是_ log 3n _。i=1 ；while (in ext- next=L17. 邊 種不同的拓?fù)湫蛄小?8. 從空樹起，依次插入關(guān)鍵字11, 27，35, 48，52, 66和73構(gòu)造所得的二叉排序樹，在等

10、概率查找的假設(shè)下，查找成功時(shí)的平均查找長度為384。19. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 L中只有一個(gè)元素結(jié)點(diǎn)的條件是隊(duì)列。20. 求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時(shí)間與圖中邊稠密、邊稀疏的數(shù)目正相關(guān)。21. 一棵完全二叉樹中共有768結(jié)點(diǎn)，那么該樹中共有 5個(gè)葉子結(jié)點(diǎn)。22. 實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需要8、64存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。23. Prim普里姆算法適用于求2h-1的網(wǎng)的最小生成樹；kruskal克魯斯卡爾算法適用于求2h-1的網(wǎng)的最小生成樹。24. 對長度為20的有序表進(jìn)行二分查找的判定樹的高度為n-1 。25. 設(shè)一棵完

11、全二叉樹有128個(gè)結(jié)點(diǎn)，那么該完全二叉樹的深度為n ，有個(gè)葉子結(jié)點(diǎn)。26. 高度為h的完全二叉樹中最少有棧 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。27. 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，那么對應(yīng)的最小生成樹上有3條邊。28. 構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有0(n2)條弧。29. 表達(dá)式求值是 42,13,94,55,05,46,17應(yīng)用的一個(gè)典型例子。30. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 e1,e2,e3,e4,e5,e6 依次通過棧S，個(gè)元素出棧后即進(jìn)入隊(duì)列Q,假設(shè)6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，那么棧的容量至少應(yīng)該是。31. 快速排序算法在最差的情況下其時(shí)間復(fù)雜度是 。32.

12、 對序列55，46，13，05，94，17, 42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是 。三、應(yīng)用題本大題共 5小題，每題6分，共30分1.二叉樹的先序遍歷序列 ABCDEFGH，中序遍歷序列為 CBEDFAGH，畫出二叉樹答案：二叉樹形態(tài)2.如圖請給出鄰接表、鄰接矩陣及逆鄰接表。參考答案如下:-1)1鄰接表：注意邊表中鄰接點(diǎn)域的值是頂點(diǎn)的序號(hào)，這里頂點(diǎn)的序號(hào)是頂點(diǎn)的下標(biāo)值vertex firstedge nextI 31 A I2逆鄰接表:I 3| A I0 10 10 o L o10 0 00 0 L 03. 由字符集s, t, a, e, 1及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如下列圖。某

13、段電文的哈夫曼編碼為請根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文答案：原來的電文為：eatst4.請畫出以下列圖所示的樹所對應(yīng)的二叉樹，并寫出對應(yīng)二叉樹的先序遍歷和中序遍歷中序遍歷為：348675215.設(shè)散列表為HT13,散列函數(shù)為H (key) = key %13。用閉散列法解決沖突，對以下關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78,31,15, 36造表。采用線性探查法尋找下一個(gè)空位，畫出相應(yīng)的散列表，并計(jì)算等概率下搜索成功的平均搜索長度。答案:使用散列函數(shù) H( key) = key mod 13，有ASLSUCC 一丄(1 + 1 + 1 + 1 + 1 + 1 +

14、 4 + 1 + 2 + 1)=101410H(12) = 12,H(23) = 10,H(45) = 6,H(57) = 5H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(佝=2,H(36) = 10.利用線性探查法造表234567891011120178150357452031233612(1)(1)(1)(1)(1)(1)(1)(2)(1)搜索成功的平均搜索長度為6. 帶權(quán)圖G如下列圖，畫出圖G的一棵最小生成樹答:7. 假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,

15、0.06,0.32,0.03,0.21,0.10，請為這 8 個(gè)字母設(shè)計(jì)哈夫曼編碼。哈夫曼編碼為：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000注意：答案不唯一8. 試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹，并計(jì)算哈夫曼樹的帶權(quán)路徑長度。12WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 畫出與如下列圖森林對應(yīng)的二叉樹答:10.答:一個(gè)散列表如以下列圖所示:35203348590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為:h=(h(key)+ i

16、*h1(key)%m i =0,1,m-1其中： h1(key)=key%11+1答復(fù)以下問題:1對表中關(guān)鍵字35, 20 , 33和48進(jìn)行查找時(shí)，所需進(jìn)行的比擬次數(shù)各為多少?2該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？答:1對關(guān)鍵字35、20、33和48進(jìn)行查找的比擬次數(shù)為3、2、1、1;2平均查找長度 ASL11.請畫出與以下二叉樹對應(yīng)的森林。12.對于給定結(jié)點(diǎn)的關(guān)鍵字集合 K=5 , 7, 3, 1, 9, 6, 4, 8, 2, 10,1試構(gòu)造一棵二叉排序樹；2求等概率情況下的平均查找長度ASL。答:2ASL=1*1+2*2+3*4+4*3)/10=2.913.給出以下列圖

17、對應(yīng)的鄰接矩陣，并給出A, B , C三個(gè)頂點(diǎn)的出度與入度答案：A鄰接矩陣為:D IE FBCA000100B101000C000111D000000E110100F010010其中頂點(diǎn)A的入度為2,出度為1；其中頂點(diǎn)B的入度為2,出度為2；其中頂點(diǎn)C的入度為1,出度為3；14. 圖5.32如下所示，求從頂點(diǎn)a到其余各頂點(diǎn)的最短路徑。給出求解過程答:終占八、最短路徑求解過程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba

18、,c,da,c,ea,c,d,f15. 閱讀以下算法，并答復(fù)以下問題：1假設(shè)串由合法的英文字母和空格組成，并以0作結(jié)束符。設(shè)串s=?？ l?am?a? student 表示空格符)，寫出f30s的返回值；2簡述算法f30的功能。int f30 (char*s)答案：(1) 4(2) 算法功能：統(tǒng)計(jì)單詞的個(gè)數(shù)。16. 閱讀以下函數(shù)，并答復(fù)以下問題：1假設(shè)隊(duì)列q中的元素為(a,b,c,d,e)其中“ a為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用Conv(&q)后的隊(duì)列q;2簡述算法Conv的功能。答案：(1) e, d, c, b, a(2) 將隊(duì)列里的值反轉(zhuǎn)17. 閱讀以下函數(shù)，并答復(fù)以下問題：整形數(shù)組L :

19、仁8中的元素依次為19, 18, 15, 17, 16, 13, 12 , 10，閱讀以下函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L,8)時(shí)，對L進(jìn)行的頭兩趟pass分別為0和1處理結(jié)果。答案：1第一趟pass = 019 15 18 16 17 12 13 102第二趟pass = 119 15 16 18 12 17 10 1318. 帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的請?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使其成為一個(gè)完整算長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為:keyn extvoid f33 (LinkList

20、 L, LinkList H口，int m)答案:(1) NULL2p-next=Hjp=q19. 以下函數(shù)的功能是，對以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表表中不存在值相同的數(shù)據(jù)元素進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到 La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請?jiān)诳杖碧幪钊脒m宜內(nèi)容，使其成為一個(gè)完整的算法答案:1pre-next=pb2pre-next=pa3pre-next=pb20. 閱讀算法f30，并答復(fù)以下問題：以下算法為有向圖拓?fù)渑判?，請?jiān)诳杖碧幪钊脒m宜的內(nèi)容，使其成為一個(gè)完整的算法答案：(1top=-1 2top=graphj.count

21、3graphk.count=021. 閱讀算法f31，并答復(fù)以下問題：以下算法功能為在數(shù)組a的前n(n=1)個(gè)元素中找出第k(1=kai+1, 將二者交換；以后重復(fù)上述二趟 過程,直至整個(gè)數(shù)組有序。請?jiān)诳杖碧幪钊脒m宜的內(nèi)容，使其成為一個(gè)完整的算法。答案：(1)ai=t(2)(i=2;inext) return ERROR;p=head-next; q=p-next; p-next =NULL; while(q)p=q; q=q-next; p-next=head-next; head-next=p; 2. 編寫一個(gè)函數(shù)，要求借助一個(gè)棧把一個(gè)數(shù)組中的數(shù)據(jù)元素逆置。 其中，棧類型為 SeqStac

22、k ，可以直接使用 InitStack(SeqStack*) Push(SeqStack*,ElemType) 、 Pop(SeqStack*,ElemType*) 函數(shù)。 參考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;in;i+) / 數(shù)組元素依次入棧Push(s,arri);for(i=0;ileft);num2=twochild1(b-right);if ( b-left!=NULL&b-right!=NULL) return (num1+num2+1);else return (

23、num1+num2);4. 假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說明如下所示：typedef char DataType;typedef struct node DataType data;struct node *lchild, *rchild;/左右孩子指針struct node *parent;/指向雙親的指針 BinTNode;typedef BinTNode * BinTree;假設(shè) px 為指向非空二叉樹中某個(gè)結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得 px 所指結(jié)點(diǎn)在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡要表達(dá)實(shí)現(xiàn)求后繼操作的方法；參考答案：1分兩種情

24、況討論當(dāng) *px 的右子樹不為空時(shí)，那么從 *px 的右孩子開始，沿其左孩子往下查找，直到找到一個(gè)沒有左孩子的節(jié)點(diǎn)為止，那么該 結(jié)點(diǎn)為 *px 在中序序列中的后繼；當(dāng) *px 的右孩子為空時(shí)，那么沿 *px 的雙親指針鏈向上查找，直至找到其左子樹中包含 *px 的最年輕祖先，那么該祖先結(jié)點(diǎn) 為 *px 在中序序列中的后繼。(2)編寫算法求 px 所指結(jié)點(diǎn)的中序序列后繼，并在算法語句中加注注釋。2 BinTree f34(BinTree px)BinTree q=px-rchild;if(q!=NULL)/ 沿左孩子往下查找px=q;while(px-lchild!=NULL)px=px-lchild;else沿雙親指針鏈向上查找while(px!=NULL & px-rchild=q)q=px;px=px-parent;return px;/ 返回所找到的中序序列后繼結(jié)點(diǎn)的指針 /或者無后繼結(jié)點(diǎn)時(shí)返回空指針參考答案：void AllSPdfs(AdjList g,v