哈尔滨工业大学
一. 名词分析(15分)
1.广义表 2.最小生成树 3.散列表 4.堆 5.随机文件
二. 试分别画出具有3个结点的树和3个结点的二元树的所有不同形态(同构的算一个)。(6分)
三. 本题给出一个子程序的框图，如图2，试填完完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表F1，F2，F3中的相同整数。假定调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。(15分)
data link
f a1a2 a2 …… an nil
图1
(注：在图2中的框图中：found和exit均为布尔型的变量，可取值为true和false。Val是整型变量，用来存放F1，F2，F3中无相同的整数found 的值为false，否则found的值为true。F1^.link
表示访问found结点的link域)。
四 假设一株二元树，按其后根顺序的结点排序
为：
H，I，D，J，E，B，F，G，C，A
而按中根顺序的结点排序为：
H，D，I，B，E，J，A，C，F，G
(1) 试画出这株二元树。(7分)
(2) 画出它的线索二元树。(7分)
五 已知集合S={7，3，4，6，19，14，16，9，22，11}，
试按照自左而右的顺序依次取出S中的每个元素，逐
步建立一株对应于S的二元查找树。试画出所得到的
二元查找树(不要求给算法)。(8分)
六 本题给出的是将数组a的元素a1,a3…,an从大到小排序
的子程序的框图，如图3，填空完善此算法框图。该子
程序采用改进的选择排序方法，该方法基本于以下思想：
在选择第一大元过程中：a1与aj ( j = n , n – 1…,2)逐
个比较，若发现aj1>a1,则aj1与a1交换，交换后新的aj1
有性质aj1>= at ( j1 ai ( j2 < j1 ),aj2与
at (j2 < t <= n )。如在挑选第一大元过程中，与a1交换的
元素有k ( k >= 0 )个，依次为aj1,aj2,…,ajk, | 
