东北大学 1996 年考研题 一、（25 分）每小题 5 分 1.根据下图完成： （1）画出该图的十字链表存储结构图。 （2）写出其拓扑排序的输出序列。 （3）写出图的强连通分量（支）。 （4）写出到的所有路径及简单路径。 2.给定 8 个权值集合（2，5，3，10，4，7，9，18）画出含有 8 个叶子结点的最佳三叉归并树，并计算出 3.已知含有 8 个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 --- 2 3 --- 5 --- 7 8 中根序遍历 3 --- 4 1 --- 7 8 6 后根序遍历 --- 4 2 --- 6 5 1 4.根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入 （1）构造一棵完全二叉树； （2）画出整理好的一棵堆树； （3）画出一棵输出一个排序记录后的二叉树； （4）画出重新调整好的堆树。 5.下图给出的是一棵三阶 B 树，处理时每次只能读一个结点到内存。要求： （1）计算出由图中结构用计算机查找到关键字（35）的记录并将其删掉，需进行多少次读/写才能完成？ （2）画出删除关键字为（35）和关键字为（50）的记录后的三阶 B 树。 二、已知 L1、L2 分别为两循环单链表的头结点指针，m,n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。（10 分） 三、线性表(a1,a2,a3…an)中元素递增有序且按顺序存于计算机内。要求设计一算法完成（12 分）： 1.用最少的时间在表中查找数值为的元素。 2.若找到将其与后继元素位置交换。 3.若找不到将其插入表中并使表中元素仍递增有序。 四、设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列 0——10 的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表在等概率查找情况下查找成功的平均查找长度是多少？（12 分） 五、设为 t 一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。（10 分） 六、设 L 为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。（14 分） 七、设 t 是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为 x 的新结点插到 t 树中，已知...
