數(shù)據(jù)結(jié)構(gòu)期終考試試卷a-清華大學(xué)-wenkub
2023-01-21 06:19:04 本頁(yè)面
【正文】 據(jù)結(jié)構(gòu)》期 終 考試試卷 （ A） 班級(jí) 學(xué)號(hào) 姓名 一 、簡(jiǎn)答題（每 小題 6 分，共 30 分） (1) 假設(shè)一個(gè)線性鏈表的類(lèi)名為 linkedList，鏈表結(jié)點(diǎn)的類(lèi)名為 ListNode，它包含兩個(gè)數(shù)據(jù)成員 data 和 link。 } } 試問(wèn)此程序在什么情況下不實(shí)用？給出具體修改后的可實(shí)用的程序？ (1) 此程序在內(nèi)存容量不足時(shí)不適用。 void PrintList (ListNode *L) { while ( L != NULL ) { cout Ldata endl。從某一非葉結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵碼需 要的最大磁盤(pán)訪問(wèn)次數(shù)是多少？ (3) 在 m 階 B 樹(shù)中關(guān)鍵碼個(gè)數(shù) n 與 B 樹(shù)最大高度 h 的關(guān)系為 h = log?m/2?((n+1)/2)+1?？偣驳拇疟P(pán)訪問(wèn)次數(shù)為 h’+(hh’)+3(h1)+1 = 4h2 = 4(log?m/2?((n+1)/2)+1)2 = = 4log?m/2?((n+1)/2)+2 (4) 給定一個(gè)有 n 個(gè)數(shù)據(jù)元素的序列，各元素的值隨機(jī)分布。試問(wèn)最大數(shù)據(jù)比較次數(shù)是多少？最少數(shù)據(jù)比較次數(shù)是多少？ (5) 兩個(gè)長(zhǎng)度為 n 的有序表 ，當(dāng)其中一個(gè)有序表的數(shù)據(jù)全部都小于另一個(gè)有序表的數(shù)據(jù)時(shí)， 關(guān)鍵碼的比較次數(shù)達(dá)到最小（ = n） 。要求給出生成樹(shù)構(gòu)造過(guò)程中依次選擇出來(lái)的邊的序列（用邊的編號(hào)表示），權(quán)值相等時(shí)編號(hào)小的邊優(yōu)先。 (1) 使用 Prim 算法 (2) e1 e5 e9 e7 e11 e15 e13 e2 e17 3 2 1 2 3 2 1 4 7 E F G A B C H I J D e2: 4 e3: 4 e8:4 e4:5 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 E F G A B C H I J D e4:5 e2: 4 e3: 4 e8:4 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 4 (2) 使用 Kruskal 算法 e9 e13 e5 e7 e15 e1 e11 e2 e17 1 1 2 2 2 3 3 4 7 (3) 這樣 選取的最小生成樹(shù)是唯 一的 。請(qǐng)根據(jù)上述要求確定散列表的容量，并 用除留余數(shù)法 設(shè)計(jì)相應(yīng)的散列函數(shù)。 //線索或子女指針 Type data。 //樹(shù)的根指針 }。 (2) ThreadNodeType * getPreorderNext (ThreadNodeType *p) //尋找結(jié)點(diǎn) *p 的在中序線索化二叉樹(shù)中前序下的后繼結(jié)點(diǎn)。 四、算法設(shè)計(jì)題（每小題 5 分，共
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1