數(shù)據(jù)結(jié)構(gòu)期末考試題目及答案 PPT課件

1、1,一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。 查找成功的平均查找長(zhǎng)度：ASL SUCC=14/10= 1.4,2,設(shè)ag 7個(gè)字符出現(xiàn)的概率為: =3, 35, 13, 15, 20, 5, 9, 畫出哈夫曼樹，設(shè)計(jì)最優(yōu)二進(jìn)制碼并計(jì)算平均碼長(zhǎng)。 哈夫曼 編碼： 平均碼長(zhǎng)：(4*3+2*35+3*13+3*15+2*20+4*5+3*9)/100,3,給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。 要遵循

2、中序遍歷的軌跡來畫出每個(gè)前驅(qū)和后繼。 中序遍歷序列：55 40 25 60 28 08 33 54,4,在KMP算法中，已知模式串為ADABCADADA ，請(qǐng)寫出模式串的nextj值。 next,5,對(duì)于如圖所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出： (1) 試給圖的鄰接表； (2) 給出根據(jù)建立的鄰接表從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹； (3) 給出根據(jù)建立的鄰接表從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹。 DFS： BFS：,6,試對(duì)下圖所示的AOE網(wǎng)絡(luò)，解答下列問題。 (1) 求每個(gè)事件的最早開始時(shí)間

3、Vei和最遲開始時(shí)間VlI。 (2) 求每個(gè)活動(dòng)的最早開始時(shí)間e( )和最遲開始時(shí)間l( )。 (3) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖。,關(guān)鍵路徑是：， 即有兩條關(guān)鍵路徑：（v1，v2，v5，v7，v9）和（v1，v2，v5，v8，v9）,7,已知一個(gè)圖的頂點(diǎn)集V各邊集G如下： V = 0，1，2，3，4，5，6，7，8，9； E = （0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9） （1）畫出圖的鄰接矩陣表示和鄰接表表示，假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的 （2）分別寫出用鄰接矩陣表示和鄰接表表示時(shí)從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。,8,畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。,9,根據(jù)圖 a, 用prim算法從頂點(diǎn)v2開始求最小生成樹。畫出求解的各步驟。,10,對(duì)下圖的無向