數(shù)據(jù)結(jié)構(gòu)》期終考試試卷（a）-清華大學(xué)-預(yù)覽頁
【正文】 若要將該序列的數(shù)據(jù)調(diào)整成為一個堆，那么需要執(zhí)行的數(shù)據(jù)比較次數(shù)最多是多少？ (4) 設(shè)堆的高度為 h = ?log2(n+1)?，當每次調(diào)用 siftDown 算法時都要從子樹的根結(jié)點調(diào)整到葉結(jié)點，假設(shè)某子樹的根在第 i 層（ 1≤ i≤ h1），第 h 層的葉結(jié)點 不參加比較。 而當兩個有序表的數(shù)據(jù)交錯排列時 ， 關(guān)鍵碼的比較次數(shù)達到最大（ = 2n1） 。（不必畫圖） (2) 使用 Kruskal 算法求 出上圖的最小生成樹。因為在邊上的權(quán)值相等時先選編號小的，限定了選擇的機會。 ? ? ???????? ????????? ??? 21 1121 1 1121 ?? nn US 三、簡 作題（共 10 分） ? ? 1121 ,41 1121 2 ????????? ?????????? ??? ?? nn US 由前一式得到 76?? ，由后一式得到 109?? ，綜合得 76?? 因 n = 100，有 76100 ???m ， 6670 0 ??m , 可取 m = 117。 //結(jié)點中所包含的數(shù)據(jù) }。 試依據(jù)上述類聲明，分別編寫下面的函數(shù)。 (3) void preorder (inOrderThreadTreeTypeamp。 } (2) template class Type 6 ThreadNodeType * getPreorderNext (ThreadNodeType *p) { if ( pleftThread == 0 ) return pleftChild。 prightChild != NULL ) p = prightChild。 p = getPreorderFirst ( p )。 templateclass Type void unknown (Type a[ ], int n) { int d = 1, j。 i++ ) { Type temp = a[i]。 a[jd] temp ) { a[j] = a[jd]。 } } (1) 閱讀此算法，說明它的功能。 六 、算法設(shè)計題（每小題 5 分，共 15 分） 下面是隊列和棧的類聲明： template class Type class queue { public: queue ( )。 operator= (const queueamp。 getFront ( )。 //從隊列的隊頭刪除元素 //…… //其他成員函數(shù) } template class Type class stack { 8 public: stack ( )。 item )。 //返回棧頂元素的值 } 試利用棧和隊列的成員函數(shù)，編寫以下針對隊列的函數(shù)的實現(xiàn)代碼（ 要求非遞歸實現(xiàn) ）。 Q)。 Type tmp。 } while ( !() ) { tmp = ()。 (2) bool queue::operator== (const queueamp。 while ( !() ) { t1 = getFront()。 ()。 } } while ( !() ) { t1 = ()。 ()。 (t
公司管理相關(guān)推薦
鄂ICP備17016276號-1