哈尔滨工业大学
一. 名词分析（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<t<n )。若再有 aj2 > ai ( j2 < j1 ),aj2 与
at (j2 < t <= n )。如在挑选第一大元过程中，与 a1 交换的
元素有 k ( k >= 0 )个，依次为 aj1,aj2,…,ajk,
