育路教育網(wǎng)，權(quán)威招生服務(wù)平臺

哈爾濱工業(yè)大學1999年數(shù)據(jù)結(jié)構(gòu)考研試題

來源：時間：2007-06-06 14:34:58

一. 名詞分析（15分）
1.廣義表 2.最小生成樹 3.散列表 4.堆 5.隨機文件
二. 試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二元樹的所有不同形態(tài)（同構(gòu)的算一個）。（6分）
三. 本題給出一個子程序的框圖，如圖2，試填完完善此算法框圖。該子程序用來尋找第一個均出現(xiàn)在三個整數(shù)單向鏈表F1，F(xiàn)2，F(xiàn)3中的相同整數(shù)。假定調(diào)用該子程序前，這三個整數(shù)鏈表已按從小到大的次序排序，單向鏈表的形式如下圖1的例子所示。（15分）

（注：在圖2中的框圖中：found和exit均為布爾型的變量，可取值為true和false。Val是整型變量，用來存放F1，F(xiàn)2，F(xiàn)3中無相同的整數(shù)found 的值為false，否則found的值為true。F1^.link
表示訪問found結(jié)點的link域）。
四假設(shè)一株二元樹，按其后根順序的結(jié)點排序
為：
H，I，D，J，E，B，F(xiàn)，G，C，A
而按中根順序的結(jié)點排序為：
H，D，I，B，E，J，A，C，F(xiàn)，G
（1）試畫出這株二元樹。（7分）
（2）畫出它的線索二元樹。（7分）
五已知集合S={7，3，4，6，19，14，16，9，22，11}，
試按照自左而右的順序依次取出S中的每個元素，逐
步建立一株對應(yīng)于S的二元查找樹。試畫出所得到的
二元查找樹（不要求給算法）。（8分）
六本題給出的是將數(shù)組a的元素a1,a3…,an從大到小排序
的子程序的框圖，如圖3，填空完善此算法框圖。該子
程序采用改進的選擇排序方法，該方法基本于以下思想：
在選擇第一大元過程中：a1與aj ( j = n , n – 1…,2)逐
個比較，若發(fā)現(xiàn)aj1>a1,則aj1與a1交換，交換后新的aj1
有性質(zhì)aj1>= at ( j1<t<n )。若再有aj2 > ai ( j2 < j1 ),aj2與
at (j2 < t <= n )。如在挑選第一大元過程中，與a1交換的
元素有k ( k >= 0 )個，依次為aj1,aj2,…,ajk,

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。