混合班“數(shù)據(jù)結(jié)構(gòu)”試卷

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

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

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

4、出主要的算法設(shè)計(jì)方法____________________11、判別下列序列是否是最大堆，若不是，按書(shū)中的算法調(diào)整（8分）。序號(hào)原始序列是否為最大堆（YN）調(diào)整后的數(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)將兩個(gè)已排序好的序列：list[i]...list[m]與list[m1]...list[n]歸并，并將結(jié)果放在sted[i]...sted[n]中。(1)請(qǐng)將上述程序中缺少的部分補(bǔ)上(2)對(duì)于待排序序列（100，66，48，73，35，39，42，57，8