上海交通大学一九九九年硕士生入学考试试题

    试题序号：19（答案清写在答题纸上）

    试题名称：数据结构及程序设计技术

    说明：试卷共十题。第I－5题只需写出实现算法的函数或过程即可。不必写出整个程序，只准使用Pascal或C编写（类Pascal和类C也可），必须写清楚算法设计思想及所用的数据结构，对程序要加以适当的注解，程序应有良好的结构，不得使用GOTO语句。第6－10题直接写出答案即可。

    1．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素值非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。（12’）

    2．利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。（12’）

    3．试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。（12’）

    4．已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中；试编写算法建立该二叉树的二叉链表。（12’）

    5．写出从哈希表中删除关键字为K的一个记录的算法。设哈希函数为h，解决冲突的方法为链地址法。（12’）

    6.考虑下图：（12’）

    1）从顶点A出发，求它的深度优先生成树。

    2）从顶点E出发，求它的广度优先生成树。

    3）根据普里姆（Prim）算法，求它的最小生成树。

    7．试求按关键字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树和平衡二叉树。（7’）