2018年北京市培养单位材料科学与光电技术学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
2． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
第 2 页，共 37 页
b 中连续的相等元素构成的子序列称为平台。试设计算法，
在b 数组中起始下标为”，1，
k)
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
3． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中，删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)
释放空间
沿链表继续査找
4． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 第 3 页，共 37 页 ，则编号 求各顶点的入度 记录结点的逆序序号 5． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。 【答案】算法如下: 层次遍历二叉树，并统计度为1的结点的个数 统计度为1的结点的个数 是以二叉树结点指针为元素的队列 出队，访问结点 度为1的 结点 非空左子女入队 非空右子女入队 返回度为1的结点的个数 二、应用题 第 4 页，共 37 页
相关内容
相关标签