1、一、簡(jiǎn)答題：（每小題3分，共15分）1.2.3.4.5.在哈希查找法中，為什么平均查找長(zhǎng)度與關(guān)鍵字個(gè)數(shù)無(wú)關(guān)？ 對(duì)于無(wú)向圖，如何用遍歷算法判斷圖中是否存在回路？ Huffman樹(shù)是否唯一？請(qǐng)舉例說(shuō)明。棧和隊(duì)列各有哪些基本操作？二、判斷正誤：（每小題1分，共5分）在一個(gè)與堆序列對(duì)應(yīng)的完全二叉樹(shù)中，從根結(jié)點(diǎn)到任一個(gè)葉結(jié)點(diǎn)的路徑 上的關(guān)鍵字序列有何特點(diǎn)？為什么？正確在（）內(nèi)打/，否則打 。（）1.折半搜索只適用于有序表，包括有序順序表和有序單鏈表。（）2.由樹(shù)的中序表示和前序表示可以導(dǎo)出樹(shù)的后序表示。（）3.查找n個(gè)關(guān)鍵字的散列表時(shí)，平均查找長(zhǎng)度與n無(wú)關(guān)。（）4.希爾排序是一種不穩(wěn)定的排序方法。（）5

2、.給定一個(gè)關(guān)鍵字集合，將得到唯一的一棵二叉排序樹(shù)，與關(guān)鍵字的插 入順序無(wú)關(guān)。三、單項(xiàng)選擇題：（每小題1分，共5分）某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、C、D、E、F、G,后序序列為B、D、C、 A、F、G、E,則該二叉樹(shù)根的右子是：A） EB）F C）DD）G在長(zhǎng)度為n的順序表的第i （ 1 i 個(gè)位置上插入一個(gè)元素，元素的移動(dòng) 次數(shù)為：A） n-i+1 B） n-i C） iD） i-13 .下面關(guān)于圖的存儲(chǔ)的敘述中正確的是0）鄰接矩陣占用的存儲(chǔ)空間只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)；B）鄰接矩陣占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)；C）鄰接表占用的存儲(chǔ)空間只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與

3、邊數(shù)無(wú)關(guān)；D）鄰接表占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。在待排序記錄已基本有序的前提下，下述排序方法中效率最高的是：A）直接插入排序 B）簡(jiǎn)單選擇排序C）快速排序D）歸并排序棧S最多能容納4個(gè)元素。現(xiàn)在6個(gè)元素按A、B、C、D、E、F的順序進(jìn) 棧，下列哪一個(gè)序列是不可能的出棧序列？A） A、B、C、D、E、FB） A、F、E、D 、C、BC） C、B、E、D、A、F D） C、D、B、F、 E、 A、填空題:（每小題2分，共20分）向一個(gè)有n個(gè)元素的有序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng) 個(gè)元素。2.設(shè)廣義表 L=（）,（），則 head（L）是； tail（L）是

4、L的長(zhǎng)度是;深度是。3 在雙向循環(huán)單鏈表中，刪除指針P所指結(jié)點(diǎn)的操作 是; 。4.設(shè)根結(jié)點(diǎn)的層數(shù)為1,則高度為k的二叉樹(shù)具有的結(jié)點(diǎn)數(shù)目，最 少為，最多為。5.10000個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹(shù)，在等概率查找的假設(shè)下，查 找成功時(shí)的平均查找長(zhǎng)度的最大值可能達(dá)到。 有3個(gè)結(jié)點(diǎn)的、不同結(jié)構(gòu)的二叉樹(shù)共有棵。將10階的下三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組C中， 則C數(shù)組的大小應(yīng)為。8.在n個(gè)結(jié)點(diǎn)的線索二叉鏈表中，有.個(gè)線索指針。已知二維數(shù)組A1020采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占2 個(gè)存儲(chǔ)單元,并且A00的存儲(chǔ)地址是1024,則A618的存儲(chǔ)地址是字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成

5、不同的 字符串，至多可以組成個(gè)不同的字符串。五、構(gòu)造題：（每小題6分，共30分）1.已知關(guān)鍵字序列：(SUN, MON, TUE, WED, THU, FRI, SAT),哈希函數(shù)為：H（K）= （K中最后一個(gè)字母在字母表中的序號(hào)）MOD 7用線性探測(cè)法處理沖突，要求構(gòu)造一個(gè)裝填因子為0.7的哈希表，并 分別計(jì)算出在等概率情況下查找成功與不成功的平均查找長(zhǎng)度。一個(gè)二叉樹(shù)按順序方式存儲(chǔ)在一個(gè)一維數(shù)組中，如圖1所示（空 元素對(duì)應(yīng)虛結(jié)點(diǎn)）。（1 ）畫(huà)出二叉樹(shù)，（2 ）給出后序遍歷序列。012 34567 89 10 11 12 13 14ABCDEFGHJ假設(shè)字符a, b, c, d, e, f的使用頻度分別是0.07, 0.09, 0.12, 0.22, 0.23, 0.27，畫(huà)出哈夫曼樹(shù)，并給出a, b, c, d, e, f的哈夫曼編碼。已知無(wú)向圖如圖2所示，（1）給出圖的鄰接表。（2）從C開(kāi)始，給出深度優(yōu)先遍歷序列和深度優(yōu)先搜索樹(shù)。5 .將下列關(guān)鍵字序列篩成一個(gè)大根堆:（A, C, D, G, H, M, P, Q, R, X）,要求給出建堆過(guò)程圖示。六