2018年郑州大学联合培养单位黄淮学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
第 2 页，共 39 页
和是两个序列首、尾
结束:
3． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。
【答案】算法如下:
//采用三元组表方式存储，按列序实现矩阵的转置
//行数、列数和非零元素个数
//设置N 中第一个非零元素从下标1开始存储
//按列，共
//在//转置
//三元组表上实现矩阵的快速转置的算法
//矩阵M 每一列非零元初始化为零
//求矩阵M 每一列的非
零元个数
//第1列第一个非零元在转置后的三元组中下标是
1
//求
第j 列第一个非零元在
中的序号
列
个元素中查找
//求转置矩阵N 的三元组表
//同列下一非零元
素位置
第 3 页，共 39 页
4． 对给定关键字序号j(1 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 5． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为 。 【答案】算法如下: 用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值 n 为偶数时 r 最小值 ("最大值) ； 二、应用题 6． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时, 若有空座位, 则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下: 第 4 页，共 39 页
相关内容
相关标签