一 判斷題(每小題一分，共十分)
1 數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)項在計算機中的映象（表示）分別稱為存儲結(jié)構(gòu)，結(jié)點，數(shù)據(jù)域。         對
2 線性表的邏輯順序與存儲順序總是一致的。       錯
3 廣義表的表頭或是元素或是一個廣義表，而表尾總是一個廣義表。     對
4 拓撲排序是一種內(nèi)部排序的算法。       錯
5 字符串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素是一個字符。    對
6 若線索二叉樹有n個結(jié)點，則必有n+1條不空的指向樹中結(jié)點的線索。  錯
7 稀疏矩陣的壓縮存儲方法一般有三元組和十字鏈表兩種。    對
8 在AOE網(wǎng)中，一定有不止一條關(guān)鍵路徑。    錯
9 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。         對
10 一個棧的輸入序列是12345，則輸出序列43512是可能的。       錯
 
 
二 單項選擇（每小題2分，共20分）
 
1 數(shù)據(jù)結(jié)構(gòu)從邏輯上可以分成 線性和非線性 兩種結(jié)構(gòu)。
2 哈希（Hash）法查找的基本思想是根據(jù) 關(guān)鍵字值 來決定記錄的存儲位置。
3 利用棧求表達式（（A-B）-C）-(D-(E-F)),操作數(shù)棧須有 4 項。
4 圖的廣度優(yōu)先搜索算法類似于二叉樹的 按層 遍歷操作。
5 在所有排序方法中關(guān)鍵字比較次數(shù)與記錄初始排列次序有關(guān)的是 插入排序。
6 二維數(shù)組A的行下標從1到8，列下標從1到10，若每個元素占3個單元，則該數(shù)組按“以列序為主序”存放時，A[5][8]的起始位置是  180
7 表達式a*(b+c)-d的后綴表示（逆波蘭式）是 abc+*d－
8 在一個具有n個結(jié)點的單鏈表中查找，查找成功時需要平均計較 (n+1)/2 結(jié)點。
9 設(shè)Q[0……n-1]為循環(huán)隊列，front,rear分別為隊列的頭，尾，則隊列中的元素個數(shù)為 (rear-front+n) MOD n
10 在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找方法是 二叉樹查找
 
三 計算題（每小題6分，共30分）
1 一顆樹有N1個度為1的結(jié)點，N2個度為2的結(jié)點…………，Nm個度為m的結(jié)點，求：該樹中終端（葉）結(jié)點的個數(shù)N0
2 對長度為12的有序表進行折半查找，求查找成功與不成功時各平均比較次數(shù)。
3 已知一顆3階的B－樹中含有25個關(guān)鍵字，求該B－樹的最小高度和最大高度（不包含葉子層）
4 已知一棵平衡二叉樹的深度為6，求樹中最少可能的結(jié)點數(shù)和最多可能的結(jié)點數(shù)。
5 對n個結(jié)點的平衡二叉樹，請分別求出當二叉樹具有最小深度K和最大深度K時，第K層上的結(jié)點數(shù)。
 
四 綜合題 （每小題8分，共40分）
1 廣義表A＝((a),(b,(c,d,e)),()),請寫出其鏈式存儲結(jié)構(gòu)。設(shè)鏈表中有兩類結(jié)點，表結(jié)點形式為   tag=1 hp  tp  ,其中指針hp和tp分別指向表頭
和表尾，元素（原子）結(jié)點形式為 tag＝0   元素值   
2 對關(guān)鍵字序列（49，38，65，97，75，13，27，51，55，10）進行希爾排序。若排序三趟，各趟的增量分別為 d1=5 ,d2=3 ,d3=1 ，則請寫出每趟的結(jié)果及元素移動次數(shù)。
3 電文中使用字符a,b,c,d,e,f,他們出現(xiàn)的頻率為（4,7,5,2,9,8）,請畫出對應(yīng)的編碼哈夫曼樹，并求出傳送電文的總長度。
4 已知一棵二叉樹的中序序列為DAJFBGICEHK，后序序列為DAFBJCIKHEG,請畫出該二叉樹，并使其成為先序線索樹。
5 對于加權(quán)圖
                       12
          6                                   
                8        15            13
           4                   16                               
      10        9          20           10
                      5
用克魯斯卡爾(Kruskal)方法構(gòu)造最小生成樹，并寫出選邊的次序。
 
五 算法題 （1，2小題各13分，3，4小題各12分，共50分）
1 設(shè)用二叉鏈表表示的二叉樹不空，其根指針為root，結(jié)點形式為：
lchild   data  rchild  
請寫出將二叉樹中所有結(jié)點的左，右子樹相互交換的非遞歸算法。
2 利用兩個棧S1和S2來模擬一個隊列。若不存在棧溢出問題，則請寫出用棧的操作來實現(xiàn)隊列的插入和刪除的算法。
3 設(shè)計一個算法，在長度為n的（小頂）堆R[1………n]中刪除一個元素R[s]（s<=n）產(chǎn)生一個長度為n－1的(小頂)堆，并將R[s]存放于R[n]中。
4 假設(shè)循環(huán)單鏈表不空，且無表頭結(jié)點亦無表頭指針，指針p指向鏈表中某結(jié)點。請設(shè)計一個算法，將p所指節(jié)點的前驅(qū)結(jié)點變?yōu)閜所指結(jié)點的后繼結(jié)點。
 
答案：
三、計算題（每小題6分，共30分）
          m
1．n0=1 + ∑ ((i-1)*ni)
         i=2
2．查找成功平均比較次數(shù)：37/12
查找不成功平均比較次數(shù)：49/13
3．最小高度：3      最大高度：4
4．最少結(jié)點數(shù)：20   最多結(jié)點數(shù)：63
5．最小深度時：n+1-2k-1    最大深度時：1
 
四、綜合題（每小題8分，共40分）
 
1      
1      
1   Λ

1．A 
1 Λ Λ

1   Λ
1      

       
1   Λ

 
 
0 d  
  0 a
0 c  
0 b  
    

 
2．第1趟：13  27  51  55  10  49  38  65  97  76  移動5次
   第2趟：13  10  49  38  27  51  55  65  97  76  移動3次
   第3趟：10  13  27  38  49  51  55  65  76  97  移動5次
 
 
 
 
 
 
 
3．                                  電文總度：87
        0        1                                                    
                                                                   
  0       1     0       1                                                   
                                                                            
                       0   1                                                    
                                                        
                                                                                      
                        0        1
                     
 4．