2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
目录
2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题（一） ... 2 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题（二） . 10 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题（三） . 16 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题（四） . 23 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研仿真模拟五套题（五） . 30
第 1 页，共 37 页
一、算法设计题
1． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
2． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
第 2 页，共 37 页
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
本句的有无不影响査找结果
3． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败
//检査参数及置换后的长度的合法性
//若S 串被替换的子串长度小于t 串长度，则S 串部分右移
//S串中被替换子串的长度小于t 串的长度
//将t 串复制到S 串的适当位置
//算法结束
//本算法是串的置换操作，将串S 中所有非空串t 相等且不重叠的子串用V 代替
//判断S 是否有和t 相等的子串
//串S 中包含和t 相等的子串
//creat操作是将串常量(此处为空串) 赋值给
temp
//求串t 和s 的长度
//用串v 替换t 形成部
分结果
//将串s 中串后的部分形成新的s 串
//求串s 的长度
//在新s 串中再找串t 的位置
//将串temp 和剩余的串s 连接后再赋值给s
}//if结束
第 3 页，共 37 页
//算法结束
4． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下:
在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回
确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情
况
返回第一邻接点，
和
中必有一个等于
i
取第一个边结点
5． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
其中n 表示随后输入英语单
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
第 4 页，共 37 页