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