數據結構期終考試試卷a-清華大學(已修改)
2025-01-18 06:19 本頁面
【正文】 1 2022 年《數據結構》期 終 考試試卷 （ A） 班級 學號 姓名 一 、簡答題（每 小題 6 分，共 30 分） (1) 假設一個線性鏈表的類名為 linkedList，鏈表結點的類名為 ListNode，它包含兩個數據成員 data 和 link。 data 存儲該結點的數據， link 是鏈接指針。下面給定一段遞歸打印一個鏈表中所有結點中數據的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout Ldata endl。 PrintList ( Llink )。 } } 試問此程序在什么情況下不實用？給出具體修改后的可實用的程序？ (1) 此程序在內存容量不足時不適用。因為需要一個遞歸工作棧。 當鏈表越長，遞歸工作棧的深度越深，需要的存儲越多?？刹捎梅沁f歸算法節(jié)省存儲。 void PrintList (ListNode *L) { while ( L != NULL ) { cout Ldata endl。 L = Llink。 } } (2) 如果每個結點占用 2 個磁盤塊因而需要 2 次磁盤訪問才能實現讀寫，那么在一棵有 n 個關鍵碼的 2m 階 B 樹中，每次搜索需要的最大磁盤訪問次數是多少？ (2) 在 2m 階 B 樹中關鍵碼個數 n 與 B 樹高度 h 之間的關系為 h≤ log m ((n+1)/2)+1，那么 每次搜索最大磁盤訪問次數為 2hmax = 2log m ((n+1)/2)+2。 2 (3) 給定一棵保存有 n 個關鍵碼的 m 階 B 樹。從某一非葉結點中刪除一個關鍵碼需 要的最大磁盤訪問次數是多少？ (3) 在 m 階 B 樹中關鍵碼個數 n 與 B 樹最大高度 h 的關系為 h = log?m/2?((n+1)/2)+1。若設尋找被刪關鍵碼所在非葉結點讀盤次數為 h’，被刪關鍵碼是結點中的 ki，則從該結點的 pi出發(fā)沿最左鏈到葉結點的讀盤次數為 hh’。當把問題轉化為刪除葉結點的 k0 時，可能會引起結點的調整或合并。極端情況是從葉結點到根結點的路徑上所有結點都要調整，除根結點外每一層讀入 1 個兄弟結點，寫出 2 個結點，根結點寫出 1 個結點，假設內存有足夠空間，搜索時讀入的盤塊仍然保存在內存，則結點調整時 共讀寫盤 3(h1)+1。總共的磁盤訪問次數為 h’+(hh’)+3(h1)+1 = 4h2 = 4(log?m/2?((n+1)/2)+1)2 = = 4log?m/2?((n+1)/2)+2 (4) 給定一個有 n 個數據元素的序列，各元素的值隨機分布。若要將該序列的數據調整成為一個堆，那么需要執(zhí)行的數據比較次數最多是多少？ (4) 設堆的高度為 h = ?log2(n+1)?，當每次調用 siftDown 算法時都要從子樹的根結點調整到葉結點，假設某子樹的根在第 i 層（ 1≤ i≤ h1），第 h 層的葉結點 不參加比較。從子樹根結點到葉結點需要比較 hi 層，每層需要 2 次比較：橫向在兩個子女里選一個，再縱向做父子結點的比較。因此， 在堆中總的比較
公司管理相關推薦
鄂ICP備17016276號-1