1、安徽大學20 0620 07學年第2學期數據結構與算法考試試卷（A卷）得 分（時間120分鐘）題號.*四五.六七總分得分院/系專業姓名學號一、選擇題（每小題2分，共20分）L1、數據結構中，與所使用的計算機無關的是數據的結構。2、A.存儲結構 B.物理結構C.邏輯結構 D.物理和存儲結構循環鏈表的主要優點是oA.不再需要頭指針了 B.已知某個結點的位置后，能很容易找到它的直接前驅結點C.在進行刪除操作后，能保證鏈表不斷開D.從表中任一結點出發都能遍歷整個鏈表3、棧和隊列都是OA.順序存儲的線性結構C.限制存取點的線性結構B. 鏈式存儲的非線性結構D.限制存取點的非線性結構4、串的長度是指A.串

2、中所含不同字母的個數C. 串中所含字符的個數B.串中所含不同字符的個數D.串中所含非空格字符的個數5、若某二叉樹的先序和中序遍歷序列分別為ABCD、ACDB,則該二叉樹的后序遍歷序列為A. DBCAB. ADCBC. DCBAD.CDBA6、有n個葉子結點的哈夫曼樹,其結點總數為A. 2n-lB. 2nC. 2n+lD.不確定。7、無向圖的鄰接矩陣一定是OA.對角矩陣 B.稀疏矩陣C.三角矩陣D.對稱矩陣8、以下序列中符合堆的定義。A. (2, 40, 20, 25, 30) B. (2, 20, 40, 25, 30) C. (40, 25, 2, 30, 20) D. (40, 25, 2

3、, 20, 30)9、下列排序方法中屬于不穩定排序方法的是A.直接插入排序B.冒泡排序C.快速排序D.歸并排序10、設有一個用線性探測法解決沖突得到的散列表（或哈希表）如下圖所示，散列函數為H（k）二k% 11,若 要查找元素14,探查的次數為oA. 5B. 9（第一題，第10小題圖）C. 3D. 60123456789101325801617614二、填空題（每小題2分，共20分）1、一個“好”的算法要考慮以下標準：正確性、可讀性、和高效率與低存儲量需求。2、對于二維數組a0.4,0.5,設每個元素占1個存儲單元，且以行為主序存儲，則元素a2, 3相對于數組空間起始地址的偏移量是o3、若一棵

4、完全二叉樹共有101個結點，則該二叉樹的葉子結點個數是o4、在一棵三叉樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為個。5、適用于折半查找的表的存儲方式及元素排列要求為o6、設順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均 查找長度為o7、采用遍歷二叉排序樹，可以得到一個關鍵字的有序序列。8、以數據集2, 5, 7, 8, 9為權值構造一棵哈夫曼樹，則其帶權路徑長度WPL為。9、求圖的最小生成樹的兩種算法中，其中算法適合于求

5、稀疏圖的最小生成樹。10、圖的深度優先搜索遍歷類似于樹的遍歷。三、判斷題（每小題1分，共10分）1、順序表結構適宜于進行順序存取，而鏈表則適宜于進行隨機存取。2、兩個棧共享一片連續內存空間時，為提高內存利用效率，減少溢出機會, 這片內存空間的兩端。（）應把兩個棧的棧底分別設在3、棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。4、空串是由空格構成的串。5、6、折半查找法的查找速度一定比順序查找法快。7、二叉樹是度為2的有序樹。KMP算法的特點是在模式匹配過程中指示主串的指針不會變小或回溯。8、9、完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。迪杰斯特拉（Dijkstra）算法是按照路

6、徑長度逐步遞減的次序產生最短路徑的方法。10、有e條邊的無向圖，在鄰接表中有e個結點。四、應用題(每小題10分，共30分)1、設 F=T1, T2, T32、已知待排序的序列為(12, 2, 16, 30,28, 10, 16, 20, 6, 18),試完成：(1) 根據以上序列，建立堆排序的初始堆(要求先輸出最大值)，請畫出主要過程和最后堆的結果圖;(2) 輸出最大值后，如何得到次大值，請畫出主要過程及相應的結果圖。3、對如下所示的連通圖，試分別用普里姆(Prim)算法和克魯斯卡爾(Kruskar)算法構造其最小生成樹，并 給出其構造過程。(第四題，第3小題圖)五、算法設計題（每小題10分，共20分）1、試設計算法，對帶頭結點的單鏈表實現就地逆置，即利用原單鏈表中的結點的存儲單元，將鏈表L逆置為：Lai 一壬其中，單鏈表及結點定義如下: typedef struct LNode ElemType data；struct LNode *next；LNode, *LinkList；2、假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點（注意不設頭指針,如下圖所示），試編寫相應的入隊列算法void EnQueue（Queue *Q, QElemType e