2018年复旦大学软件学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
2． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。
【答案】算法如下:
在二叉树t 中査找结点值等于x 的结
点
结束
统计以t 为根结点的子树的叶结点数
n0
第 2 页，共 39 页
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
. 叶结点
输出并计数
结束
:
3． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
4． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
在b 数组中起始下标为
”，1，
k)
b 中连续的相等元素构成的子序列称为平台。试设计算法，
第 3 页，共 39 页
5． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 ，则编号 求各顶点的入度 二、应用题 6． 设与记录 对应的关键字分别是 。如果存在 和 使得j 且 成立，试证明经过一趟起泡后，一定有记录与进行交换。 【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在 ，又因 之前且 ，则 ，故 ，即说明和 是反序；设对于 和 之前全部记录: (其 中包括) 中关键字最大为 ，故经过起泡排序前i-2次比较后， 必定交换。 的关键字一定为 和Rf 为反序，由此可知 7． 请回答下列关于图(Graph)的一些问题: (1)有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？ (2)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？ (3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 【答案】⑴最多有n(n－1) 条边；最少有n 条边。 (2)有有 个矩阵元素；不一定是稀疏矩阵(稀疏矩阵的定义是非零元素个数远小于该矩阵元 素个数，且分布无规律) (3)使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果 第 4 页，共 39 页
相关内容
相关标签