上海交通大学一九九九年硕士生入学考试试题 试题序号:19 试题名称:数据结构及程序设计技术 说明:试卷共十题,第1-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)算法,求它的最小生成树。 3 7、试求按关键字序列(12,1,4,3,7,8,10,2)插入生成的二叉排 序树和平衡二叉树。(7分) 8、给出一组关键字T=(12,2,16,30,8,28,4,10,20,6, 18),写出用下列算法从小到大排序时第一趟结束时的序列:(9分) 1)希尔排序(第一趟排序的增量为5) 2)快速排序(选第一个记录为枢轴(分隔)) 3)链接基数排序(基数为10) 9、判别序列(12,70,33,65,24,56,48,92,86,33) 是否为堆,如果不是,则把它调整为堆。试给出堆排序方法在平均时间性能、 最坏情况下的时间性能和辅助存储量,并与快速排序方法在以上三方面进行比 较。(8分)
上海交通大学一九九九年硕士生入学考试试题 试题序号：19 试题名称：数据结构及程序设计技术 说明：试卷共十题，第 1-5 题只需写出实现算法的函数或过程即可，不必写出整个程 序，只准使用 pascal 或 C 编写（类 pascal 和类 C 均可），必须写清楚算法设计思想 及所用的数据结构，对程序要加以适当的注解，程序应有良好的结构，不得使用 goto 语句，第 6-10 题直接写出答案即可。 １、假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构， 请编写算法将表 A 和表 B 归并成一个按元素非递减有序（允许值相同）排列的 线性表 C，并要求利用原表（即表 A 和表 B）的结点空间存放表 C。（12 分） ２、利用两个栈 S1 和 S2 模拟一个队列，写出入队和出队的算法（可用栈的基本操 作）。（12 分） ３、试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。（12 分） ４、已知一棵二叉树的先序遍历和中序遍历序列分别在于两个一维数组中，试编写算 法建立二叉树的二叉链表。（12 分） ５、写出从哈希表中删除关键字为Ｋ的一个记录的算法，设哈希函数为 h,解决冲突的 方法为链地址法。（１２分） ６、考虑下图：（１２分） １） 从顶点Ａ出发，求它的深度优先生成树。 ２） 从顶点Ｅ出发，求它的广度优先生成树。 ３） 根据普里姆（Ｐrim）算法，求它的最小生成树。 5 A 2 Ｂ ６ ４ Ｄ １ C ３ E 5 3 Ｇ １ Ｆ ７、试求按关键字序列（１２，１，４，３，７，８，１０，２）插入生成的二叉排 序树和平衡二叉树。（７分） ８、给出一组关键字Ｔ＝（１２，２，１６，３０，８，２８，４，１０，２０，６， １８），写出用下列算法从小到大排序时第一趟结束时的序列：（９分） １） 希 尔排序（第一趟排序的增量为５） ２） 快速排序（选第一个记录为枢轴（分隔）） ３） 链接基数排序（基数为１０） ９、判别序列（１２，７０，３３，６５，２４，５６，４８，９２，８６，３３） 是否为堆，如果不是， 则把它调整为堆。试给出堆排序方法在平均时间性能、 最坏情况下的时间性能和辅助存储量，并与快速排序方法在以上三方面进行比 较。（８分）
10、给出一组关键字T=(12,2,16,30,8,28,4,10,20, 6,18),设内存工作区可容纳4个记录,写出用置换一选择排序得到的全部 初始归并段。(4分)
１０、给出一组关键字Ｔ＝（１２，２，１６，３０，８，２８，４，１０，２０， ６，１８），设内存工作区可容纳４个记录，写出用置换－选择排序得到的全部 初始归并段。（４分）