數(shù)據(jù)結(jié)構(gòu)期終考試試卷a-清華大學(xué)(更新版)
【正文】 void pop ( )。 //返回隊(duì)頭元素的值 void push (const Typeamp。 //隊(duì)列的構(gòu)造函數(shù) queue (const queueamp。 j = d。 while ( d n /3 ) d = 3*d+1。 return prightChild。 T)。 template class Type class inOrderThreadTree { //中序線索化二叉樹(shù)類(lèi) public: ThreadNodeType * getRoot ( ) { return root。假如不限定在具有相等權(quán)值的邊中的選擇次序，結(jié)果可能就可能不唯一了。 二 、簡(jiǎn)作題（每 小題 5 分，共 15 分） 針對(duì)如下的帶權(quán)無(wú)向圖 其中，每條邊上所注的 ei為該邊的編號(hào)，冒號(hào)后面是該邊所對(duì)應(yīng)的權(quán)值。當(dāng)把問(wèn)題轉(zhuǎn)化為刪除葉結(jié)點(diǎn)的 k0 時(shí)，可能會(huì)引起結(jié)點(diǎn)的調(diào)整或合并。 當(dāng)鏈表越長(zhǎng)，遞歸工作棧的深度越深，需要的存儲(chǔ)越多。 data 存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)， link 是鏈接指針。 L = Llink。若要將該序列的數(shù)據(jù)調(diào)整成為一個(gè)堆，那么需要執(zhí)行的數(shù)據(jù)比較次數(shù)最多是多少？ (4) 設(shè)堆的高度為 h = ?log2(n+1)?，當(dāng)每次調(diào)用 siftDown 算法時(shí)都要從子樹(shù)的根結(jié)點(diǎn)調(diào)整到葉結(jié)點(diǎn)，假設(shè)某子樹(shù)的根在第 i 層（ 1≤ i≤ h1），第 h 層的葉結(jié)點(diǎn) 不參加比較。（不必畫(huà)圖） (2) 使用 Kruskal 算法求 出上圖的最小生成樹(shù)。 ? ? ???????? ????????? ??? 21 1121 1 1121 ?? nn US 三、簡(jiǎn) 作題（共 10 分） ? ? 1121 ,41 1121 2 ????????? ?????????? ??? ?? nn US 由前一式得到 76?? ，由后一式得到 109?? ，綜合得 76?? 因 n = 100，有 76100 ???m ， 6670 0 ??m , 可取 m = 117。 試依據(jù)上述類(lèi)聲明，分別編寫(xiě)下面的函數(shù)。 } (2) template class Type 6 ThreadNodeType * getPreorderNext (ThreadNodeType *p) { if ( pleftThread == 0 ) return pleftChild。 p = getPreorderFirst ( p )。 i++ ) { Type temp = a[i]。 } } (1) 閱讀此算法，說(shuō)明它的功能。 operator= (const queueamp。 //從隊(duì)列的隊(duì)頭刪除元素 //…… //其他成員函數(shù) } template class Type class stack { 8 public: stack ( )。 //返回棧頂元素的值 } 試?yán)脳：完?duì)列的成員函數(shù)，編寫(xiě)以下針對(duì)隊(duì)列的函數(shù)的實(shí)現(xiàn)代碼（ 要求非遞歸實(shí)現(xiàn) ）。 Type tmp。 (2) bool queue::operator== (const queueamp。 ()。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1