一、判斷題(每小題一分，共十分)

1 數據結構，數據元素，數據項在計算機中的映象（表示）分別稱為存儲結構，結點，數據域。 對
2 線性表的邏輯順序與存儲順序總是一致的。 錯
3 廣義表的表頭或是元素或是一個廣義表，而表尾總是一個廣義表。 對
4 拓撲排序是一種內部排序的算法。 錯
5 字符串是一種特殊的線性表，其特殊性體現在數據元素是一個字符。 對
6 若線索二叉樹有n個結點，則必有n+1條不空的指向樹中結點的線索。 錯
7 稀疏矩陣的壓縮存儲方法一般有三元組和十字鏈表兩種。 對
8 在AOE網中，一定有不止一條關鍵路徑。 錯
9 二維數組是其數據元素為線性表的線性表。 對
10 一個棧的輸入序列是12345，則輸出序列43512是可能的。 錯


二、單項選擇（每小題2分，共20分）
1 數據結構從邏輯上可以分成 線性和非線性 兩種結構。
2 哈希（Hash）法查找的基本思想是根據 關鍵字值 來決定記錄的存儲位置。
3 利用棧求表達式（（A-B）-C）-(D-(E-F)),操作數棧須有 4 項。
4 圖的廣度優先搜索算法類似于二叉樹的 按層 遍歷操作。
5 在所有排序方法中關鍵字比較次數與記錄初始排列次序有關的是 插入排序。
6 二維數組A的行下標從1到8，列下標從1到10，若每個元素占3個單元，則該數組按“以列序為主序”存放時，A[5][8]的起始位置是 180
7 表達式a*(b+c)-d的后綴表示（逆波蘭式）是 abc+*d－
8 在一個具有n個結點的單鏈表中查找，查找成功時需要平均計較 (n+1)/2 結點。
9 設Q[0……n-1]為循環隊列，front,rear分別為隊列的頭，尾，則隊列中的元素個數為 (rear-front+n) MOD n
10 在各種查找方法中，平均查找長度與結點個數無關的查找方法是 二叉樹查找

三 計算題（每小題6分，共30分）

1 一顆樹有N1個度為1的結點，N2個度為2的結點…………，Nm個度為m的結點，求：該樹中終端（葉）結點的個數N0
2 對長度為12的有序表進行折半查找，求查找成功與不成功時各平均比較次數。
3 已知一顆3階的B－樹中含有25個關鍵字，求該B－樹的最小高度和最大高度（不包含葉子層）
4 已知一棵平衡二叉樹的深度為6，求樹中最少可能的結點數和最多可能的結點數。
5 對n個結點的平衡二叉樹，請分別求出當二叉樹具有最小深度K和最大深度K時，第K層上的結點數。

四、綜合題 （每小題8分，共40分）

1 廣義表A＝((a),(b,(c,d,e)),()),請寫出其鏈式存儲結構。設鏈表中有兩類結點，表結點形式為 tag=1 hp tp ,其中指針hp和tp分別指向表頭
和表尾，元素（原子）結點形式為 tag＝0 元素值
2 對關鍵字序列（49，38，65，97，75，13，27，51，55，10）進行希爾排序。若排序三趟，各趟的增量分別為 d1=5 ,d2=3 ,d3=1 ，則請寫出每趟的結果及元素移動次數。
3 電文中使用字符a,b,c,d,e,f,他們出現的頻率為（4,7,5,2,9,8）,請畫出對應的編碼哈夫曼樹，并求出傳送電文的總長度。
4 已知一棵二叉樹的中序序列為DAJFBGICEHK，后序序列為DAFBJCIKHEG,請畫出該二叉樹，并使其成為先序線索樹。
5 對于加權圖
12
6
8 15 13
4 16
10 9 20 10
5
用克魯斯卡爾(Kruskal)方法構造最小生成樹，并寫出選邊的次序。

五、算法題 （1，2小題各13分，3，4小題各12分，共50分）1 設用二叉鏈表表示的二叉樹不空，其根指針為root，結點形式為：
lchild data rchild
請寫出將二叉樹中所有結點的左，右子樹相互交換的非遞歸算法。
2 利用兩個棧S1和S2來模擬一個隊列。若不存在棧溢出問題，則請寫出用棧的操作來實現隊列的插入和刪除的算法。
3 設計一個算法，在長度為n的（小頂）堆R[1………n]中刪除一個元素R[s]（s<=n）產生一個長度為n－1的(小頂)堆，并將r[s]存放于r[n]中。

4 假設循環單鏈表不空，且無表頭結點亦無表頭指針，指針p指向鏈表中某結點。請設計一個算法，將p所指節點的前驅結點變為p所指結點的后繼結點。

答案：

三、計算題（每小題6分，共30分）
m
1．n0=1 + ∑ ((i-1)*ni)
i=2
2．查找成功平均比較次數：37/12
查找不成功平均比較次數：49/13
3．最小高度：3 最大高度：4
4．最少結點數：20 最多結點數：63
5．最小深度時：n+1-2k-1 最大深度時：1

四、綜合題（每小題8分，共40分）