东北大学96年数据结构考题

东北大学96考研题

一、（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树，处理时每次只能读一个结点到内存。要求：

① 计算出由图中结构用计算机查找到关键字（35）的记录并将其删掉，需进行

多少次读/写才能完成？

② 画出删除关键字为（35）和关键字为（50）的记录后的三阶B树。

二、（10分）知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结

点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 三、（12分）线性表(a1,a2,a3…an)中元素递增有序且按顺序存于计算机内。要求设计一算法

完成：

（1） 用最少的时间在表中查找数值为的元素。 （2） 若找到将其与后继元素位置交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。 四、（12分）设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列

法散列0——10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表在等概率查找情况下查找成功的平均查找长度是多少？ 五、（10分）设为t一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树

中每个结点的左右孩子位置交换。 六、（14分）设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设

计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。 七、（15分）设t是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递

归的算法，把一个地址为x的新结点插到t树中，已知地址为y的结点有侧作为结点y的右孩子，并把插入后的二叉树仍为后序线索二叉树。

本文来源：https://www.bwwdw.com/article/nm3x.html