哈爾濱工程大學(xué)2003年考研數(shù)據(jù)結(jié)構(gòu)真題

1、一 判斷題(每小題一分，共十分)1 數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)項在計算機中的映象（表示）分別稱為存儲結(jié)構(gòu)，結(jié)點，數(shù)據(jù)域。         對2 線性表的邏輯順序與存儲順序總是一致的。       錯3 廣義表的表頭或是元素或是一個廣義表，而表尾總是一個廣義表。     對4 拓?fù)渑判蚴且环N內(nèi)部排序的算法。       錯5 字符串是一種特殊的線性表，其特殊性體

2、現(xiàn)在數(shù)據(jù)元素是一個字符。    對6 若線索二叉樹有n個結(jié)點，則必有n+1條不空的指向樹中結(jié)點的線索。  錯7 稀疏矩陣的壓縮存儲方法一般有三元組和十字鏈表兩種。    對8 在AOE網(wǎng)中，一定有不止一條關(guān)鍵路徑。    錯9 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。         對10 一個棧的輸入序列是12345，則輸出序列43512是可能的。     

3、0; 錯  二 單項選擇（每小題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的行下標(biāo)從1到8，列下標(biāo)從1到10，若每個元素占3個單元，則該數(shù)組按“以列序為主序”存放時，A58的起始位置是  1807 表達式a*(b+c)-d的后綴表示（逆

4、波蘭式）是 abc+*d8 在一個具有n個結(jié)點的單鏈表中查找，查找成功時需要平均計較 (n+1)/2 結(jié)點。9 設(shè)Q0n-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樹的最小高

5、度和最大高度（不包含葉子層）4 已知一棵平衡二叉樹的深度為6，求樹中最少可能的結(jié)點數(shù)和最多可能的結(jié)點數(shù)。5 對n個結(jié)點的平衡二叉樹，請分別求出當(dāng)二叉樹具有最小深度K和最大深度K時，第K層上的結(jié)點數(shù)。 四 綜合題 （每小題8分，共40分）1 廣義表A(a),(b,(c,d,e),(),請寫出其鏈?zhǔn)酱鎯Y(jié)構(gòu)。設(shè)鏈表中有兩類結(jié)點，表結(jié)點形式為   tag=1 hp  tp  ,其中指針hp和tp分別指向表頭和表尾，元素（原子）結(jié)點形式為 tag0   元素值    2 對關(guān)鍵字序列（49，38，65，

6、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)圖               

7、;         12          6                                

8、                    8        15            13           4  &

9、#160;                16                                  

10、60;   10        9          20           10                   

11、0;  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的（小頂）堆R1n中刪除一個元素Rs（s<=n）產(chǎn)生一個長度為n1的(小

12、頂)堆，并將Rs存放于Rn中。4 假設(shè)循環(huán)單鏈表不空，且無表頭結(jié)點亦無表頭指針，指針p指向鏈表中某結(jié)點。請設(shè)計一個算法，將p所指節(jié)點的前驅(qū)結(jié)點變?yōu)閜所指結(jié)點的后繼結(jié)點。 答案：三、計算題（每小題6分，共30分）          m1n0=1 + (i-1)*ni)         i=22查找成功平均比較次數(shù)：37/12查找不成功平均比較次數(shù)：49/133最小高度：3      最大高度：4