數(shù)據(jù)結(jié)構(gòu)期末考試試題第一套.doc

數(shù)據(jù)結(jié)構(gòu)期末考試試卷1（答題時間：120分鐘，滿分：100分）題號第一部分第二部分第三部分第四部分總分核分人得分得分評卷人一、判斷題：（共10分，每題1分）1. 順序表和一維數(shù)組一樣，都可以按下標隨機（或直接）訪問。（ ）2. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。（ ）3. 只有用面向?qū)ο蟮挠嬎銠C語言才能描述數(shù)據(jù)結(jié)構(gòu)算法。（ ）4. 在對雙向循環(huán)鏈表做刪除一個結(jié)點操作時，應(yīng)先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點鏈接好再執(zhí)行刪除結(jié)點操作。（ ）5. 遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。（ ）6. 在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。（ ）7. 二叉樹是一棵無序樹。（ ）8. 在任何情況下，快速排序需要進行關(guān)鍵碼比較的次數(shù)都是O(nlog2n)。（ ）9. 圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。（ ）10. 當從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（ ）得分評卷人二、填空題（20分，每題2分）1. 假定一棵二叉樹的結(jié)點個數(shù)為32，則它的最小深度為_。2. 在一棵二叉樹中，度為2的結(jié)點有5個，度為1的結(jié)點有6個，那么葉子結(jié)點有_個。3. 一棵深度為5的滿二叉樹的結(jié)點總數(shù)為_個。4. 假定一棵樹的廣義表表示為A(B(C, D(E, F,G), H(I, J)，則結(jié)點H的雙親結(jié)點為_。5. 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_。6. 若要對某二叉排序樹進行遍歷，保證輸出元素的值序列按增序排列，應(yīng)對該二叉排序樹采用_遍歷法。7. 元素關(guān)鍵字轉(zhuǎn)換為該元素存儲位置的函數(shù)f稱為_。8. 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_排序。9. 假定一組數(shù)據(jù)的關(guān)鍵字為46,79,56,38,40,84，則利用堆排序方法建立的初始大頂堆為_。10. 對20個記錄進行歸并排序時，共需要進行_趟歸并。得分評卷人三、選擇題（共20分，每題2分）1. 樹中所有結(jié)點的度數(shù)之和等于結(jié)點總數(shù)加_。A. 0 B. 1 C. -1 D. 22. 在一棵樹中，每個結(jié)點最多有_個直接前驅(qū)結(jié)點。A. 0 B. 1 C. 2 D. 任意多個3. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加_。A. 2 B. 1 C. 0 D. -14. 頂點個數(shù)為n的無向圖最多有_條邊。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)5. n個頂點的連通圖至少有_條邊。A. n-1 B. n C. n+1 D. 06. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。A. 3 B. 2 C. 1 D. 1/27. 對于順序存儲的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，為查找元素26，若采用順序查找，需要比較_次才能查找成功。A. 3 B. 4 C. 5 D. 68. 設(shè)哈希表長為14，哈希函數(shù)f（k）=k11，已知表中已有4個元素，關(guān)鍵字分別為15，38，61，84，存儲位置分別為4，5，6，7，其它存儲位置為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的存儲位置是_。A. 8 B. 3 C. 5 D. 99. 在對n個元素進行簡單選擇排序的過程中，需要進行_趟選擇和交換。A. n/2 B. n-1 C. n D. n+110. 在對n個元素進行快速排序的過程中，第一趟排序最多需要交換_對元素。A. n/2 B. n-1 C. n D. n+1得分評卷人四、應(yīng)用題（共30分，每題6分）1. 已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nk個度為k的結(jié)點，問該樹有多少個葉子結(jié)點？（6分）2. 對于下面兩個圖，求出：（1） 無向圖中每個頂點的度，有向圖中每個頂點的入度，出度和度。（2） 是否是連通圖/強連通圖，如果不是，畫出連通分量/強連通分量。（6分）01243403123. 分別畫出在線性表(a, b, c, d, e, f, g)中進行折半查找，以查關(guān)鍵字等于e、f和g的過程。（6分）4. 已知一組元素的關(guān)鍵字46,74,16,53,14,26,40,38,86,65,27,34，利用直接插入排序法，寫出每次向前面的有序表插入一個元素后的排列結(jié)果。（6分）5、將下圖轉(zhuǎn)換為二叉樹，對轉(zhuǎn)換后的二叉樹進行先序、中序、后序遍歷序列。（6分）ABCDEFGJ五、程序題（20分）1. 將下面算法填完整。（10分，每空2分）int Search_Bin(SSTable ST, KeyType key) /在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若找到，則返回該元素/在表中的位置，否則返回0 low=1;high=ST.length; while(low=high) mid=_; if(EQ(key, ST.elemmid.key) return _; else if(LT(key, ST.elemmid.key) high=_; else low=_; return _;2. 將下面算法填完整。（10分，每空2分）void InsertSort(SqList &L)/對順序表L作直接插入排序for(i=2;i=L.length