數(shù)據(jù)結(jié)構(gòu)期終考試試卷a-清華大學(xué)(存儲版)
【正文】 Type * getPreorderFirst (ThreadNodeType *p)。 if (prightThread == 0 ) return prightChild。 while ( p != NULL ) { cout pdata endl。 j = i。 7 (2) 對于下面給出的整數(shù)數(shù)組，追蹤第一趟 while ( d 0 ) 內(nèi)的每次 for 循環(huán)結(jié)束時數(shù)組中數(shù)據(jù)的變化。 qu)。 //棧的構(gòu)造函數(shù) bool isEmpty ( )。 (1) “逆轉(zhuǎn)”函數(shù) template class Type void reverse (queueTypeamp。 while ( !() ) { tmp = ()。 Q) { //成員函數(shù) queueType Q1, Q2。 (t2)。 (t2)。 。 } while ( !() ) { t2 = ()。 //從左隊列退出 , 進(jìn)臨時隊列 t2 = ()。 } }。 Q) { //普通函數(shù) stack Type S。 getTop ( )。 //將新元素插入到隊列的隊尾 void pop ( )。 //隊列的復(fù)制構(gòu)造函數(shù) queueamp。 } d /= 3。 i n。 T ) { ThreadNodeType *p = getRoot()。 四、算法設(shè)計題（每小題 5 分，共 15 分） (1) tamplate class Type ThreadNodeType * getPreorderFirst (ThreadNodeType *p) { return p。 //樹的根指針 }。請根據(jù)上述要求確定散列表的容量，并 用除留余數(shù)法 設(shè)計相應(yīng)的散列函數(shù)。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列（用邊的編號表示），權(quán)值相等時編號小的邊優(yōu)先。總共的磁盤訪問次數(shù)為 h’+(hh’)+3(h1)+1 = 4h2 = 4(log?m/2?((n+1)/2)+1)2 = = 4log?m/2?((n+1)/2)+2 (4) 給定一個有 n 個數(shù)據(jù)元素的序列，各元素的值隨機(jī)分布。 void PrintList (ListNode *L) { while ( L != NULL ) { cout Ldata endl。 1 2022 年《數(shù)據(jù)結(jié)構(gòu)》期 終 考試試卷 （ A） 班級 學(xué)號 姓名 一 、簡答題（每 小題 6 分，共 30 分） (1) 假設(shè)一個線性鏈表的類名為 linkedList，鏈表結(jié)點的類名為 ListNode，它包含兩個數(shù)據(jù)成員 data 和 link。可采用非遞歸算法節(jié)省存儲。極端情況是從葉結(jié)點到根結(jié)點的路徑上所有結(jié)點都要調(diào)整，除根結(jié)點外每一層讀入 1 個兄弟結(jié)點，寫出 2 個結(jié)點，根結(jié)點寫出 1 個結(jié)點，假設(shè)內(nèi)存有足夠空間，搜索時讀入的盤塊仍然保存在內(nèi)存，則結(jié)點調(diào)整時 共讀寫盤 3(h1)+1。 (1) 使用 Prim 算法，從頂點 A 出發(fā)求出上圖的最小生成樹。 三 、簡 作題（共 10 分） 假設(shè)一個散列表中已裝入 100 個表項并采用線性探查法解決沖突，要求搜索到表中已有表項時的平
公司管理相關(guān)推薦
鄂ICP備17016276號-1