本文档由标准美女(标准王国)整理,仅作学习交流使用。如文档存在缺页、字迹模糊、乱码等情况,请大家通过论坛消息与我联系。 上海交通大学一九九九年硕士生入学考试
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
试题序号:19 试题名称:数据结构及程序设计技术说明:试卷共十题,第1-5题只需写出实现算法的函数或过程即可,不必写出整个程序,只准使用pascal或C编写(类 pascal和类C均可),必须写清楚算法设计思想及所用的数据结构,对程序要加以适当的注解,程序应有良好的结构,不得使用goto语句,第6-10题直接写出答案即可。1、ﻩ假设有两个按元素值递增有序排列的线性表A和B,2、ﻩ均以单链表作存储结构,3、ﻩ请编写算法将表A和表B归并成一个按元素非递减有序(允许值相同4、)排列的线性表C,5、ﻩ并要求利用原表(即表A和表B)的结点空间存放表C。(12分)6、利用两个栈S1和S2模拟一个队列,7、写出入队和出队的算法(可用栈的基本操作)。(12分)8、试以二叉链表作存储结构,9、ﻩ编写按层次顺序遍历二叉树的算法。(12分)10、已知一棵二叉树的先序遍历和中序遍历序列分别在于两个一维数组中,11、试编写算法建立二叉树的二叉链表。(12分)12、写出从哈希13、ﻩ表中删除关键字为K的一个记录的算法,14、设哈希15、函数为h,解决冲突的方法为链地址法。(12分)16、ﻩ考虑下图:(12分)1)从顶点A出发,2)求它的深度优先生成树。3)ﻩ从顶点E出发,4)求它的广度优先生成树。5)根据普里姆(Prim)算法,6)求它的最小生成树。 5 A2 B 6 4 D 1C 3 E5 3 G 1 F17、试求按关键字序列(12,18、ﻩ1,19、4,20、3,21、ﻩ7,22、8,23、10,24、2)插入生成的二叉排序树和平衡二叉树。(7分)25、ﻩ给出一组关键字T=(12,26、2,27、ﻩ16,28、30,29、ﻩ8,30、28,31、ﻩ4,32、ﻩ10,33、ﻩ20,34、6,35、ﻩ18),36、ﻩ写出用下列算法从小到大排序时第一趟结束时的序列:(9分)1)ﻩ希2? 尔排序(第一趟排序的增量为5)3)快速排序(选第一个记录为枢轴(分隔))4?ﻩ链接基数排序(基数为10)37、判别序列(12,38、ﻩ70,39、33,40、65,41、ﻩ24,42、56,43、ﻩ48,44、92,45、86,46、ﻩ33)是否为堆,47、如果不48、是,49?则把它调整为堆。试给出堆排序方法在平均时间性能、最坏情况下的时间性能和辅助存储量,50、ﻩ并与快速排序方法在以上三方面进行比较。(8分)51、ﻩ给出一组关键字T=(12,52、2,53、16,54、30,55、ﻩ8,56、28,57、ﻩ4,58、10,59、20,60、ﻩ6,61、ﻩ18),62、ﻩ设内存工作区可容纳4个记录,63、ﻩ写出用置换-64、ﻩ选择排序得到的全部初始归并段。(4分)来源:上海教育热线202.120.8.177雅舍考研之路yasee.net/ky精品文档