哈工大2005年《數(shù)據(jù)結(jié)構(gòu)與算法》期末試題

[期末]數(shù)據(jù)結(jié)構(gòu)與算法試卷試卷類型:期末試卷年份:05授課教師:廖明宏有無答案:無答案2005數(shù)據(jù)結(jié)構(gòu)與算法試卷一．填空題（每空1分，共10分）假定對線性表(38,25,74,52,48)進(jìn)行散列存儲，采用H(K)=K%7作為散列數(shù)若分別采用線性探查法和鏈接法處理沖突則對各自散列表進(jìn)行查找的平查找長度分別為 和 。假定一組記錄的排序碼為(46,79,56,38,40,80)對其進(jìn)行歸并排序的過程中第二趟歸并后的結(jié)果為 。在堆排序的過程中對任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時間復(fù)雜度為 整個堆排序過程的時間復(fù)雜度為 。00元素的個數(shù)是該頂點(diǎn)的。對于下面的帶權(quán)圖G3，若從頂點(diǎn)v0出發(fā)，則按照普里姆（Prim）算法生的最小生成樹中，依次得到的各條邊為 。3，9，6，2，55度為二．選擇題（每題1分，共10分）1．快速分類在的情況下不利于發(fā)揮其長處.A.待分類的數(shù)據(jù)量太大B.待分類的數(shù)據(jù)相同值過多C.待分類的數(shù)據(jù)已基本有序D.待分類的數(shù)據(jù)值差過大.兩路歸并排序中，歸并的趟數(shù)是。O(n)B.O(log2n)C.O(nlog2n)D.O(n2)注意行為規(guī)范遵守考場紀(jì)律16KK。有關(guān)B.無關(guān)C.不能確定D.都不對對于一個索引順序文件，索引表中的每個索引項對應(yīng)主文件中的。一條記錄B.多條記錄C.D.三條以上記錄4100，12A.112B.144C.148D.412若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用存儲結(jié)構(gòu)。A.散列B.順序C.鏈?zhǔn)紻.索引ni要移動表中個數(shù)據(jù)元素。A.n+iB.n-iC.n-i+1D.n-i-18．棧和隊列的相同之處是。A.元素的進(jìn)出滿足先進(jìn)后出B.元素的進(jìn)出滿足后進(jìn)先出C.只允許在端點(diǎn)進(jìn)行插入和刪除操作D.無共同點(diǎn)9．在一棵高度為k的二叉樹中，最多含有()個結(jié)點(diǎn)。A．2k-1B．2k-lC．2k-1D．k10．任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序()。A．發(fā)生改變B．不發(fā)生改變C．不能確定D．以上都不對三．判斷題，正確的在括號內(nèi)畫∨，錯誤的在括號內(nèi)畫╳。（每小題1分，共10分）1．（任何二元樹都唯一對應(yīng)一個森林，反之亦然。.（）（）AOE0（起始點(diǎn)0（（）（）順序存儲方式只能用于存儲線性結(jié)構(gòu)。()用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊列就是循環(huán)隊列。()倒排文件的主要優(yōu)點(diǎn)為便于節(jié)省空間（。一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,40,38,46,56,79,84（。算法分析的目的是分析算法的易讀性（四．簡答題簡述如何用兩個棧模擬一個隊列的入隊和出隊操作.(6G5（7）寫出先根遍歷得到的結(jié)點(diǎn)序列；寫出按層遍歷得到的結(jié)點(diǎn)序列；畫出轉(zhuǎn)換后得到的二元樹圖G5五．算法設(shè)計設(shè)二元樹采用左右鏈存