混合班“數(shù)據(jù)結構”試卷

1、2000年混合班“數(shù)據(jù)結構”試卷一、一、選擇及填空題（除非特別注明，一般每小題選擇及填空題（除非特別注明，一般每小題2分，共分，共30分）分）1、下列說法哪個正確：A）堆棧是在兩端操作、先進后出的線性表B）堆棧是在一端操作、先進先出的線性表C）隊列是在一端操作、先進先出的線性表D）隊列是在兩端操作、先進先出的線性表2已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為：A）CBEFDAB）FEDCB

2、AC）CBEDFAD）不定3、對哈希(HASH)函數(shù)H(k)=kMODm一般來說m應取A)素數(shù)B)很大的數(shù)C)偶數(shù)D)奇數(shù)4_____是HASH查找的沖突處理方法:A）求余法B)平方取中法C)二分法D)開放地址法5、下列哪種排序算法（均在內存中進行）要求內存量最大:A）選擇排序B）插入排序C）冒泡排序D）歸并排序6設有序列12、42、37、19，當使用直接插入排序從小到大排序時，其比較次數(shù)為：A）3B）4C）5D）67下列哪種排序算法數(shù)

3、據(jù)交換的次數(shù)最多:A）選擇排序B）插入排序C）冒泡排序D）歸并排序8、可用類似下列哪些算法判別一有向圖是否存在回路________:寬度優(yōu)先遍歷算法、深度優(yōu)先遍歷算法、最小生成樹算法、求關鍵路徑算法、求最短路徑的Dijkstra算法、Topst算法。9、（3分）若要維護一個數(shù)的集合，要求：1）能往該集合中插入任意一個數(shù)，且2）能隨時從該集合中刪除最小及最大的數(shù)，你認為采用的最佳數(shù)據(jù)結構是：_______________10、（3分）請列

4、出主要的算法設計方法____________________11、判別下列序列是否是最大堆，若不是，按書中的算法調整（8分）。序號原始序列是否為最大堆（YN）調整后的數(shù)的序列1（100，66，48，73，35，39，42，57，86，21）2（103，97，56，38，66，23，42，12，30，53，6，20）3（1，2，3，4，5，6，7，8，9，10）merge_pass(listextranlength)length=2mer

5、ge_pass(________②_____________)length=2其中，voidmerge(elementlist[]elementsted[]intiintmintn)將兩個已排序好的序列：list[i]...list[m]與list[m1]...list[n]歸并，并將結果放在sted[i]...sted[n]中。(1)請將上述程序中缺少的部分補上(2)對于待排序序列（100，66，48，73，35，39，42，57，8