2018年复旦大学基础医学院754生物医工综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。
【答案】算法如下:
//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾
//申请结点空间
//将s 结点链入队尾
//rear指向新队尾
//rear是带头结点的循环链队列的尾指针
//本算法执行出队操作，成功输出队头元素；否则给出出错信息
//s指向队头元素
//队头元素出队
//空队列
2． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下:
按递减次序输出二叉排序树结点的值
是元素为二叉树结点指针的栈，容量足够大
沿右子树向下
结束
3． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 4． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。 【答案】算法如下: //设整数序列存于数组a 中，共有n 个，本算法求解其最大值 5． 编写算法，求二叉树的宽度。 【答案】算法如下: 求二叉树bt 的最大宽度 空二叉树宽度为 Q 是队列，元素为二叉树结点指针，容量 足够大 front 为队头指针，rear 为队尾指针 last 为同层最右结点在队列中的位置 ，则编号 求各顶点的入度 temp 记当前层宽度，maxw 记最大宽度 根结点入队 同层元素数加 1 左子女入队 右子女入队 一层结束 指向下层最右元素 更新当前最大宽度 二、应用题 6． 对给定文件(28，07，39，10，65，14，61，17，50，21) 选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。 【答案】快速排序的思想如下:首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴(或支点) ，凡其关键字不大干枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列割成两部分: 和 和，且 进行快速排序。快速排序在记录有序时蜕变为起泡排序， 对应的关键字分别是 。如果存在 和 使得j 且 将分 然后再递归地将初始序列:21移动:39移动:17移动:65移动:14移动: 7． 设与记录 可用“三者取中”法改善其性能，避免最坏情况的出现。 成立，试证明经过一趟起泡后，一定有记录与进行交换。 【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在 ，又因 之前且 ，则 ，故 ，即说明和是反序；设对于 和 之前全部记录: (其 中包括) 中关键字最大为，故经过起泡排序前i-2次比较后， 必定交换。 的关键字一定为 和Rf 为反序，由此可知
相关内容
相关标签