數(shù)據(jù)結(jié)構(gòu)期終考試試卷a-清華大學(xué)-wenkub.com
2025-01-03 06:19 本頁面
【正文】 }。 } while ( !() ) { t2 = ()。 Push(t1)。 //從右隊列退出 , 進臨時隊列 if ( t1 != t2 ) { finished = false。 (t1)。 Type t1, t2。 ()。 ()。 （ 5 分） 六、算法設(shè)計題（每小題 5 分，共 15 分） (1) include “stack” template class Type void reverse (queueTypeamp。 Q)。 //棧頂元素退棧 Typeamp。 //判斷?？辗瘛?item)。 //賦值操作 bool isEmpty ( )。 qu)。（為清楚起見，本次循環(huán)未涉及的 不移動的數(shù)據(jù)可以不寫出，每行僅寫出一個 for 循環(huán)的變化） (3) 以上各次循環(huán)的數(shù)據(jù)移動次數(shù)分別是多少。 } a[j] = temp。 while ( j = d amp。 while ( d 0 ) { for ( int i = d。 p = getPreorderNext ( p )。 } (3) template class Type void preorder ( inOrderThreadTreeTypeamp。 while ( prightThread != 0 amp。 //應(yīng)用以上兩個操作，在中序線索化二叉樹上做前序遍歷。 //尋找以 p 為 根指針的中序線索化二叉樹在前序下的第一個結(jié)點。 } //其他公共成員函數(shù) …… private: ThreadNodeType *root。 //線索標(biāo)志 ThreadNodeType *leftChild, *rightChild。 三 、簡 作題（共 10 分） 假設(shè)一個散列表中已裝入 100 個表項并采用線性探查法解決沖突，要求搜索到表中已有表項時的平均搜索次數(shù)不超過 4，插入表中沒有的表項時找到插入位置的平均探查次數(shù)不超過 。（不必畫圖） (3) 上面求出的最小生成樹是唯一的嗎？試舉理由說明。 (1) 使用 Prim 算法，從頂點 A 出發(fā)求出上圖的最小生成樹。因此， 在堆中總的比較次數(shù)為 )ihj( 2 j22j222j22)ih(22 1h 1j j1h1h 1j j1h1h 1j 1jh1h 1i 1i ??????????? ???? ????????? 代換 因為 2h1≤ n≤ 2h1，且 ????? ?1h1j jh 22jlim ，則 n42n22j22 1h1j j1h ?????? ???? 3 (5) 設(shè)有兩個分別有 n 個數(shù)據(jù)元素的有序表，現(xiàn)要對它們進行兩路歸并，生成一個有 2n 個數(shù)據(jù)元素的有序表。極端情況是從葉結(jié)點到根結(jié)點的路徑上所有結(jié)點都要調(diào)整，除根結(jié)點外每一層讀入 1 個兄弟結(jié)點，寫出 2 個結(jié)點，根結(jié)點寫出 1 個結(jié)點，假設(shè)內(nèi)存有足夠空間，搜索時讀入的盤塊仍然保存在內(nèi)存，則結(jié)點調(diào)整時 共讀寫盤 3(h1)+1。 2 (3) 給定一棵保存有 n 個關(guān)鍵碼的 m 階 B 樹?？刹捎梅沁f歸算法節(jié)省存儲。 PrintList ( Llink )。 1 2022 年《數(shù)
公司管理相關(guān)推薦
鄂ICP備17016276號-1