數(shù)據(jù)結(jié)構(gòu)期終考試試卷a-清華大學(xué)-免費閱讀
【正文】 (t2)。 } } while ( !() ) { t1 = ()。 while ( !() ) { t1 = getFront()。 } while ( !() ) { tmp = ()。 Q)。 item )。 getFront ( )。 六 、算法設(shè)計題（每小題 5 分，共 15 分） 下面是隊列和棧的類聲明： template class Type class queue { public: queue ( )。 a[jd] temp ) { a[j] = a[jd]。 templateclass Type void unknown (Type a[ ], int n) { int d = 1, j。 prightChild != NULL ) p = prightChild。 (3) void preorder (inOrderThreadTreeTypeamp。 //結(jié)點中所包含的數(shù)據(jù) }。因為在邊上的權(quán)值相等時先選編號小的，限定了選擇的機會。 而當兩個有序表的數(shù)據(jù)交錯排列時 ， 關(guān)鍵碼的比較次數(shù)達到最大（ = 2n1） 。若設(shè)尋找被刪關(guān)鍵碼所在非葉結(jié)點讀盤次數(shù)為 h’，被刪關(guān)鍵碼是結(jié)點中的 ki，則從該結(jié)點的 pi出發(fā)沿最左鏈到葉結(jié)點的讀盤次數(shù)為 hh’。因為需要一個遞歸工作棧。下面給定一段遞歸打印一個鏈表中所有結(jié)點中數(shù)據(jù)的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout Ldata endl。 } } (2) 如果每個結(jié)點占用 2 個磁盤塊因而需要 2 次磁盤訪問才能實現(xiàn)讀寫，那么在一棵有 n 個關(guān)鍵碼的 2m 階 B 樹中，每次搜索需要的最大磁盤訪問次數(shù)是多少？ (2) 在 2m 階 B 樹中關(guān)鍵碼個數(shù) n 與 B 樹高度 h 之間的關(guān)系為 h≤ log m ((n+1)/2)+1，那么 每次搜索最大磁盤訪問次數(shù)為 2hmax = 2log m ((n+1)/2)+2。從子樹根結(jié)點到葉結(jié)點需要比較 hi 層，每層需要 2 次比較：橫向在兩個子女里選一個，再縱向做父子結(jié)點的比較。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列（用邊的編號表示），權(quán)值相等時編號小的邊優(yōu)先。用除留余數(shù)法設(shè)計散列函數(shù)： 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 5 Hash(key) = key % 113 (注： 117 不是質(zhì)數(shù)， 117 = 9 * 13) 四、算法設(shè)計題（每小題 5 分，共 15 分） 設(shè)中序線索化二叉樹的類聲 明如下： template class Type struct ThreadNode { //中序線索化二叉樹的結(jié)點類 int leftThread, rightThread。 (1) ThreadNode
公司管理相關(guān)推薦
鄂ICP備17016276號-1