數(shù)據(jù)結(jié)構(gòu)題庫-應(yīng)用題

1、數(shù)據(jù)結(jié)構(gòu)一一應(yīng)用題復(fù)習(xí)概要2022年4月寫出執(zhí)行下列程序段時，語句S的執(zhí)行次數(shù)。for （i=1; i=i; j-）S;假設(shè)n為2的乘冪，并且n2，試求下列算法的時間復(fù)雜度及變量count的值(以n的 函數(shù)形式表示)int Time(int n)( int count:=0; x:=2;while (xRL = P-RL; P-RL = Q; Q-RL-LL = Q; Q-LL = P;Q-RL = P; P-LL-RL = Q; Q-LL = P-LL; P-LL = Q;P-LL-RL = P-RL; P-RL-LL = P-LL;4.設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e和

2、f依次通過棧S，試分析下列各組出棧次序， 每組所用的最大容量。（1）a,b,c,d,e,f； （2）f,e,d,c,b,a； （3）b,d,c,f,e,a5,有字符串A+B*C-D，試寫出利用棧操作將該字符串序列改為ABC*+D-的操作步驟，這 里用X和S分別表示字符的進(jìn)棧和出棧操作（例如把字符ABCD改為ACBD的操作步 驟為 XSXXSSXS）。XSXXSXXSSSXXSS6. 一棵二叉樹的結(jié)點(diǎn)數(shù)采用順序存儲結(jié)構(gòu)，存于下列數(shù)組T中，畫出該二叉樹。123456789101112131415161718192021228JdgeJ1hbGH7.已知一棵樹的雙親表示如下，其中各兄弟結(jié)點(diǎn)依此排列，

3、試畫出該樹及對應(yīng)的孩子兄弟 表示的二叉樹。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15DataABCDEFGHIJKLMNOParent0111223344566788.有一個完全二叉樹按層次順序存放在一維數(shù)組中，如下所示：請指出結(jié)點(diǎn)P的父結(jié)點(diǎn)， 左子女，右子女。123 45 6789 10 11 12HkACDPFJXBQZ9,將下列二叉鏈表改為先序線索鏈表12345678dataABCDEFGHLTag00101000lchild24070000RTag00001000rchild3568000010.下表給出用帶二個標(biāo)識的按先序遍歷進(jìn)行順序存儲的二叉樹，對于結(jié)點(diǎn)

4、k,規(guī)定：ltag(k)=0, k 有左孩子；ltag(k)=1，k 無左孩子；rtag(k)=0，k 有右孩子；rtag(k)=1，k 無右孩子。12345678910ltag0011110101dataAGEIDJHCFBrtag000101011111.已知一棵二叉樹的后序遍歷為CDBGHFIEA，中序遍歷為CBDAGFHEI。畫出此二叉樹 并寫出其先序遍歷序列。C D F IG H12.中序序列：DBHEAFICG后序遍歷為DHEBIFGCA一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹并寫出它的后序遍歷的序 列。先序序列：ABDEHCFIG13.已知一棵二叉樹的中序遍歷為DBH

5、EAFICG,后序遍歷為DHEBIFGCA。畫出此二叉樹 并寫出其先序遍歷序列。先序遍歷：ABDEHCFIG一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹的中序線索二叉鏈表。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹的二叉鏈表。先序序列：ABDFCEG中序序列：BFDAEGC一棵二叉樹的先序、中序和后序序列分別如下，試求出空格處的內(nèi)容，并畫出該二叉樹。先序： B n F K IC E H J G中序：D B K F I A H E J C G后序：D K I F B H J E G C A先序：ABDFKICEHJG中

6、序：DBKFIAHEJCG后序：DKIFBHJEGCA二叉樹的先序、中序和后序序列分別如下，試求出空格處的內(nèi)容，并構(gòu)造出該二叉樹先序序列d BC 4 EF q B中序序列 BDE AG 一巳H后序序列衛(wèi)DC R GH E A已知一棵二叉樹的層次遍歷序列為ABCDEFGHIJ，中序遍歷序列為DBGEHJACIF，請 畫出該二叉樹。對下面的兩棵樹，分別畫出其順序存儲結(jié)構(gòu)。一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于下列數(shù)組T中，畫出該二叉數(shù)。1234 56 78 9 101112 13 141516 17 18 19 20 21T eaf d gcjlhb用權(quán)分別為2，3，6, 7，8次序的葉子結(jié)

7、點(diǎn)構(gòu)造一棵哈夫曼樹（結(jié)點(diǎn)標(biāo)出權(quán)值），若葉 子結(jié)點(diǎn)次序改為8, 7，6，3，2，所構(gòu)造的哈夫曼樹是否相同？30為葉子結(jié)點(diǎn)的權(quán)值，（1）構(gòu)造一棵哈夫曼樹;22,以數(shù)據(jù)集3，4，5，8，12，18，20，（2）計(jì)算其帶權(quán)路徑長度。23,按照給定的權(quán)值10，12，14，5，30，40，構(gòu)造相應(yīng)的赫夫曼樹。24,以數(shù)據(jù)集15, 3，14，2, 6，9,16，17為葉子結(jié)點(diǎn)的權(quán)值，（1）構(gòu)造一棵哈夫曼樹;（2）計(jì)算其帶權(quán)路徑長度。25.有一電文中使用5各字符A,B,C,D,E，他們出現(xiàn)的頻率依次為4，7, 5，2，9，試為每 個字符設(shè)計(jì)哈夫曼編碼。WPL=60A: 001B: 10C: 01D: 000E

8、: 1127,畫出根據(jù)Prim算法對下列連通網(wǎng)從頂點(diǎn)A出發(fā)構(gòu)造其最小生成樹的過程。28.已知某系統(tǒng)在通信聯(lián)絡(luò)中可能出現(xiàn)8種字符，A,B,C,D,V,W,X,Y其概率分別為0.05,0.29，0.07，0.08，0.14，0.23, 0.03, 0.11，試設(shè)計(jì)赫夫曼編碼。ABCDEA01110B00101C00010D00000E0000031.如右圖所示有向圖寫出鄰接矩陣求出其最小生成樹29,設(shè)有帶權(quán)無向圖如右圖所示請寫出該圖的鄰接矩陣。請畫出該圖的鄰接表。列出從頂點(diǎn)1出發(fā)深度優(yōu)先遍歷該圖所得到的 一個頂點(diǎn)序列。列出從頂點(diǎn)1出發(fā)廣度優(yōu)先遍歷該圖所得到的 一個頂點(diǎn)序列。請畫出該圖的一棵最小生成

9、樹。30.已知圖G的鄰接矩陣如下，分別寫出從頂點(diǎn)A出發(fā)的深度優(yōu)先和廣度優(yōu)先搜索序列。32,已知圖的鄰接矩陣如下，圖的頂點(diǎn)依此為V0,V1,V2,V3,V4,V5,V6,分別寫出從V0, V5出發(fā)的深度優(yōu)先和廣度優(yōu)先的遍歷序列。深度：0 1 342565 3 0 1 6 2 4 廣度：0 1 234655 3 4 6 0 1 233.已知圖的鄰接矩陣如左下方所示：(1)畫出其鄰接表；(2)若在它的鄰接表存儲結(jié)構(gòu)中， 每個頂點(diǎn)鄰接序號是從小到大鏈接時，寫出它根據(jù)鄰接表以頂點(diǎn)V1為出發(fā)點(diǎn)的廣度優(yōu) 先搜索序列和深度優(yōu)先搜索序列。V1V2V3V4V5V6V10101100V20010101V300000

10、12V40000003C4V50011014C5二V6_ 000000 _5A34.有向圖G的鄰接表如右上所示，若在圖中增加弧C1,C6和C6,C1，該鄰接表需做何種 修改？（可直接在給出的鄰接表上修改）假定無向圖G有6個結(jié)點(diǎn)和9條邊，并依次輸入這9條邊為（0，1），（0，2），（0，4）， （0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。試從頂點(diǎn) 0 出發(fā)分別寫出按深 度優(yōu)先搜索和廣度優(yōu)先搜索進(jìn)行遍歷得到的遍歷結(jié)點(diǎn)序列。深度：0 1 2345廣度：0 1 245 3對于帶權(quán)的連通圖G （如左下圖所示），從V6出發(fā)構(gòu)造最小生成樹。0v I卜.1v2-?null|?.*-

11、n _ j v 5*4-*_$v3 null I37.已知一有向圖G的鏈接表存儲結(jié)構(gòu)如右上所示，畫出有向圖，并寫出從結(jié)點(diǎn)V1出發(fā)的深度優(yōu)先遍歷結(jié)點(diǎn)序列。38.已知圖的鄰接矩陣如下，（1）試畫出其鄰接表；（2）若在它的鄰接表存儲結(jié)構(gòu)中，每個 頂點(diǎn)的鄰接點(diǎn)序號是從小到大鏈接，寫出以頂點(diǎn)V1為出發(fā)點(diǎn)的唯一的深度優(yōu)先遍歷序 列。畫出以頂點(diǎn)V1為初始源點(diǎn)遍歷下圖所得到的DFS和BFS生成森林畫出從頂點(diǎn)A出發(fā)圖的DFS和BFS生成樹。ABCDEF010101101000010111101000001001101010已知圖的鄰接矩陣如下所示，已知圖的鄰接表如上所示，根據(jù)鄰接表寫出從V0出發(fā)的深度優(yōu)先和廣度

12、優(yōu)先遍歷序列。畫出根據(jù)Prim算法對下列連通網(wǎng)從頂點(diǎn)A出發(fā)構(gòu)造其最小生成樹的過程。下圖表示一個地區(qū)的交通圖，頂點(diǎn)表示城市，邊表示城市間的公路，邊上的數(shù)值（權(quán)） 表示修建公路的代價，要求從頂點(diǎn)A出發(fā)構(gòu)造能連通每個城市且總代價最低的5條公 路。45,求出下圖的最小生成樹。46.請畫出左下帶權(quán)圖的一棵最小生成樹。如右上有向圖中，頂點(diǎn)表示課程，弧表示課程間的先后次序，例如弧C1,C3表示先學(xué)習(xí) 課程C1再學(xué)習(xí)課程c3，如果某人每次只能學(xué)習(xí)一門課程則它應(yīng)該如何安排學(xué)習(xí)？給出左下圖的所有拓?fù)湫蛄?。請寫出右上圖所有可能的拓?fù)湫蛄?。設(shè)有向圖 G=(V, E), V=1, 2, 3, 4, 5, 6, E=,

13、, , , , , 。請寫出圖G中頂點(diǎn)的所有拓?fù)湫蛄小? 1 2 5 4 30 2 1 5 4 30 2 5 1 4 351.已知某圖鄰接表如下圖所示，分別寫出從V0, V3出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷序列。52.求出左下圖的所有拓?fù)湫蛄小?3. 一項(xiàng)工程P有6個子工程組成，這些子工程間的優(yōu)先關(guān)系用下列的有向無環(huán)圖表示，使 給出工程P的4種可能的施工順序。P1P2P4P3P5P6P1P2P4P5P3P6P1P4P2P3P5P6P1P4P2P5P3P6P1P4P3P2P5P6P1P4P3P5P2P6P1P4P5P2P3P6P1P4P5P3P2P6P4P1P2P3P5P6P4P1P2P5P3P6P

14、4P1P3P2P5P6P4P1P3P5P2P6P4P1P5P2P3P6P4P1P5P3P2P654.按下列鄰接矩陣分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先和廣度優(yōu)先遍歷生成 樹。r 1 r0000001010-200100010003000100010040000100010500000100018110000000070010000001810010000109000010100110_100001000055.已知圖的鄰接矩陣如下，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點(diǎn)的鄰接點(diǎn)序號是從小到 大鏈接時，寫出其拓?fù)溆行蛐蛄?。V101110000V 200100100V 300001000V 40

15、0000010V 500000011V 600001001V 700000000V 8000000001 2 3 4 6 5 7 8簡答下列各題：（1）什么叫二叉排序樹？（2）按給定的輸入序列：45，24，53，12，42，90構(gòu)成一棵二叉排序樹；（3）由n個結(jié)點(diǎn)組成的二叉排序樹是唯一的嗎？如不唯 一，請舉例說明；（4）如何用二叉排序樹方法對關(guān)鍵字序列：45, 24, 53，12, 42, 90 進(jìn)行排序。從一棵空的二叉排序樹開始，將以下關(guān)鍵碼值依次插入：25,13,15,31,7,20,37,請畫出插 入全部完成后的二叉排序樹。58.對于給定結(jié)點(diǎn)的數(shù)據(jù)集合D=55,13, 20,15,31,

16、7, 18依次取出D中各數(shù)據(jù)，構(gòu)成一棵二叉排序樹BT。求等概率情況下的平均查找長度ASL。畫出在二叉排序樹BT中刪除“13”后的樹的結(jié)構(gòu)。ASL=(1+2+3*2+4*2+5)/7=22/7or(參考：中序遍歷序列為準(zhǔn)則)59.分別建立結(jié)點(diǎn)值（關(guān)鍵字值）為 12, 24, 30, 37, 45, 53, 96 及 37, 24, 12, 30, 53,45, 96的二叉排序樹，并說明在查找等概率情況下的平均查找長度。60.61.62.63.對給定的關(guān)鍵字序列7, 16, 4, 8, 20,9, 6, 18, 5，畫出對應(yīng)的二叉排序樹， 并再畫出刪除關(guān)鍵字為16的結(jié)點(diǎn)后的二 叉排序樹。一棵二叉排

17、序樹結(jié)構(gòu)如右圖所示，各結(jié)點(diǎn) 的值從小到大依次為18,請標(biāo)出各結(jié) 點(diǎn)的值。設(shè)有一個長為10的有序表S1 ., 10,畫 出對其進(jìn)行折半查找的判定樹，并求出等 概率情況下查找成功的平均查找長度。畫出長度為18的有序順序表進(jìn)行二分法查找的判定樹，并指出在等概率時查找成功的平均查找長度ASL以及查找失敗時所需 的最多的關(guān)鍵字比較次數(shù)。設(shè)二叉排序樹中關(guān)鍵字有1到1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述 關(guān)鍵字序列中哪一個不可能是在二叉排序樹上查到的序列？ (1) 2, 252, 401, 398, 330, 344, 397, 363； (2) 924, 220, 911, 244, 89

18、8, 258, 362, 363； (3) 925, 202, 911, 240, 912, 245, 363； (4) 2, 399, 387, 219, 266, 382, 384, 278, 363有一組關(guān)鍵值序列(38, 19, 65, 97, 49, 41, 95, 1, 73)，采用冒泡排序方法由小到 大進(jìn)行排序，請寫出每趟的結(jié)果。19,38,65,49,41,95,1,73,9719,38,49,41,65,1,73,9519,38,41,49,1,65,7319,38,41,1,49,6519,38,1,41,4919,1,38,41,1,19,38Or38, 19,65, 9

19、7, 48, 41, 95, 731, 19, 38, 41, 65, 97, 48, 73, 951, 19, 38, 41, 48, 65, 97, 73, 951, 19, 38, 41, 48, 65, 73, 97, 951, 19, 38, 41, 48, 65, 73, 95, 9766,設(shè)有序列38, 27, 54, 86, 65, 2, 16, 38，寫出用快速排序法對該序列進(jìn)行升序排序 的每一趟結(jié)果。16, 27, 2,38,65,86,54,382, 16, 27,38,38,54,65,86對下列數(shù)據(jù)表，寫出采用快速排序算法排序的每一趟的結(jié)果，并標(biāo)明第一趟排序過程中 的

20、數(shù)據(jù)移動情況。(60，20, 31, 1, 5, 44, 55, 61, 200, 30, 80, 150, 4, 29)設(shè)待排序文件的關(guān)鍵碼為(512,275,908,677,503,765,612,897,154,170)以第一元素為分 界元素進(jìn)行快速排序(按關(guān)鍵碼值遞增順序)，請給出第一趟掃描后的結(jié)果。對下列數(shù)據(jù)表，寫出采用快速排序算法排序的每一趟的結(jié)果。(100，12, 20, 31, 1, 5,44,66,61,200,30,80,150,4,8)已知待排序文件各記錄的排序碼順序如下:72,73,71,23,94,16,05,68，請列出快速排序過 程中每一趟的排序結(jié)果。初始輸入序列

21、的關(guān)鍵值如下：(72, 73, 71, 23, 94, 16, 05, 68, 48, 19, 26)試采 用二路歸并排序法進(jìn)行從小到大的排序，寫出該序列在每遍掃描時的合并過程。72,_23,23,衛(wèi)，16,_94,05,68,19,_48,2623,71,72,J1，05,16,68,94,19,26,4805,16,23,68,71,72,73,94,19,26,4805,16,19,23,26,48,68,71,72,73,9472.利用堆排序的“篩選”方法將序列36, 27, 41, 10, 13, 21, 19, 25調(diào)整為“小頂堆”。73,將下面數(shù)據(jù)建成一個“大頂堆”(70，12,

22、 20, 31, 1, 5, 44, 66, 61, 200, 30, 80, 150,4,28)有一個數(shù)據(jù)序列：25,50,70,100,43,7,12。現(xiàn)采用堆排序算法進(jìn)行排序，寫出每趟的結(jié)果。設(shè)有哈希函數(shù)為：H(key) = key MOD 11，哈希表的長度為11，解決沖突的方法為線性 探測再散列法，關(guān)鍵字的輸入序列為：(18, 34, 58, 26, 75, 67, 48, 93, 81)，試構(gòu) 造此哈希表，并求出在等概率情況下查找成功和不成功時的平均查找長度。成功 不成功012345678910346758264893188175121122151110987654321ASL 成

23、功=(1+2+1+1+2+2+1+5+1)/9=16/9ASL 不成功=(1+10+9+8+7+6+5+4+3+2+1)/11=56/1176.設(shè)哈希表容量為7，給定表30，36, 47, 52, 34，散列函數(shù)H(k)=k mod 6，采用線性探測再散列法解決沖突，求(1)構(gòu)造此哈希表；(2)求查找數(shù)34需要進(jìn)行比較的次數(shù)77.設(shè)有一哈希表如圖所示，該哈希表用二次探測再散列法解決沖突，其哈希函數(shù)為：H(K)=K mod 13,從該哈希表中檢索出關(guān)鍵碼35需幾次比較？請寫出比較順序。012345678910111235332148102535 mod 13 = 9(9+1) mod 13 = 10(9-1) mod 13 = 8(9+4) mod 13 = 0 (O