數(shù)據(jù)結(jié)構(gòu)—試題A

1、2008級計算機(jī)、軟件、網(wǎng)絡(luò)專業(yè) 2009 2010學(xué)年 第一學(xué)期數(shù)據(jù)結(jié)構(gòu)期末試題（A卷）一、填空題（20空X 1分=20分）1. （）是數(shù)據(jù)的最小單位，（）是討論數(shù)據(jù)結(jié)構(gòu)是涉及的最小數(shù)據(jù)單位。2 在有尾指針rear指示的循環(huán)單鏈表中，在表尾插入一個結(jié)點s的操作序列是（）；刪除開始結(jié)點的操作序列為（）。3. （）可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。4棧和隊列是兩種特殊的線性表，棧的操作特性是（）,隊列的操作特性是（），棧和隊列的主要區(qū)別在于（）。5數(shù)組通常只有兩種運(yùn)算：存取和（），這決定了數(shù)組通常采用（）結(jié)構(gòu)來實現(xiàn)存儲。6. 棵有n（n 0）個結(jié)點的滿二叉樹共有（）個葉子結(jié)點和（）個非終端結(jié)

2、點。7. 圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）8. 設(shè)有一個已按各元素值排好序的線性表， 長度為125,用折半查找與給定 值相等的元素，若查找成功，則至少需要比較（ ）次，至多需比較（） 次。9. 對n個待排序記錄序列進(jìn)行快速排序，所需要的最好時間是（），最壞 時間是（）O10. 一棵5階B_樹中，除根結(jié)點外，每個結(jié)點的子樹數(shù)目最少為（），最 多為（）。二、選擇題（10題X 2分=20分）1 .下面（）不是算法所必須具備的特性。A .有窮性B .確切性2. 鏈表不具有的特點是（）A .可隨機(jī)訪問任一元素C.不必事先估計存儲空間C.高效性D .可行性B .插入、刪除不需要

3、移動元素D .所需空間與線性表長度成正比3. 使用雙鏈表存儲線性表，其優(yōu)點是可以（）。C.節(jié)約存儲空間A .提高檢索速度B .更方便數(shù)據(jù)的插入和刪除D .很快回收存儲空間4. 一個棧的入棧序列是1, 2, 3, 4, 5,貝U棧的不可能的輸出序列是（）A. 54321B. 45321C. 43512D. 123455. 一個隊列的入隊順序是1, 2, 3, 4,貝U隊列的輸出順序是（）A . 4321B . 1234C. 1432D . 3241A 數(shù)組元素是隨機(jī)的B 對數(shù)組任一元素的存取時間是相等的C.隨時可以對數(shù)組進(jìn)行訪問D .數(shù)組的存儲結(jié)構(gòu)是不定的7 設(shè)二叉樹有n個結(jié)點，則其深度為（）。

4、A. n -1B. nC. log；1D .不能確定8. 判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（）°A .求關(guān)鍵路徑的方法B .求最短路徑的方法C.廣度優(yōu)先遍歷算法D .深度優(yōu)先遍歷算法9. 二叉排序樹中，最小值結(jié)點的（）。A .左指針一定為空B .右指針一定為空C.左、右指針均為空D .左、右指針均不為空10. （°方法是從未排序序列中挑選兀素，并將其放入已排序序列的一端。A .歸并排序 B .插入排序 C.快速排序D .選擇排序三、判斷題（10題X 1分=10分）1. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（°2. 線性結(jié)構(gòu)的基本特

5、征是：每個元素有且僅有一個直接前驅(qū)和一個直接后 繼。（°3. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。（°4. 有n個元素依次進(jìn)棧，則出棧序列有（n -1）/2種。（°5. 稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。（°6. 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。（°7. 無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣不一定是對稱的。（°8. 若二叉排序樹中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉 子結(jié)點。（°9. 對n個記錄的集合進(jìn)行快速排序，所需要的附加空間最壞情況下是O（n）（°10. m階B_樹

6、中每個結(jié)點的子樹個數(shù)都大于或等于 m/2。（°四、簡答題（5題X 4分=20分）1. 已知二叉樹的中序和后序序列分別為 CBEDAFIGH和CEDBIFHGA，試 構(gòu)造該二叉樹。2. 對給定的一組鍵值 W=（5，2, 9，11, 8, 3，7），試構(gòu)造相應(yīng)的哈夫曼樹， 并計算它的帶權(quán)路徑長度。3. 圖1是一個無向帶權(quán)圖，用Kruskal算法求其最小生成樹4 圖2為帶權(quán)有向圖，求從源點W到其他各頂點的最短路徑。5.判斷序列（3，9, 5，8，4，17, 21，6）是否為堆，如不是，按照堆排 序思想把它調(diào)整為堆。五、算法設(shè)計題（3題X 10分=30分）1. 以順序表作存儲結(jié)構(gòu)，寫一實現(xiàn)線性表就地逆