2018年宁波大学信息科学与工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
2． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
3． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
(1)下面所示的序列中哪些是合法的？
A.
B.
C.
D.
(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。
【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:
//判断字符数组A 中的输入输出序列是否是合法序列。
//i为下标
//j和k 分别为I 和字母O 的个数
//入栈次数增
1
//不论A[i]是’I'或’〇' ，指针i 均后移
//算法结束
4． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。
【答案】算法如下:
//本算法将无符号十进制整数m 转换为十六进制整数
本算法的递归描述如下:
//本算法将无符号十进制整数m 转换为十六进制整数
5． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间