2018年温州医科大学眼视光学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。
【答案】算法如下:
//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称
//i记下结点个数，s 是字符栈
//P是链表的工作指针，指向待处理的当前元素
//链表前一半元素入栈
//恢复最后的i 值
//若n 是奇数，后移过中心结点
//测试
是否中心对称
//链表中心对称
//链表不中心对称
//算法结束
2． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
3． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
4． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
5． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
当前叶结点链入双链表
树中的所有叶结点链成带头结点的双链表
二、应用题
6． 若森林共有n 个结点和b 条边(b 【答案】森林的n 个结点开始可看作是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n －b 棵树。 7． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B ，数据Cache 采用直接映射方式. 现有两个功能相同的程序A 和B ，其伪代码如下所示:程序A :程序B :
相关内容
相关标签