2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库
● 摘要
目录
2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库（一） ... 2 2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库（二） ... 8 2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库（三） . 15 2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库（四） . 21 2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研核心题库（五） . 27
一、算法设计题
1． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
2． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
3． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。
【答案】算法如下:
中关键字分二路分别按序插入到辅助向量
前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分
二路插入排序的算法
辅助存储
插人后部
折半査找插入位置
移动元素
插入有序位置
插入前部
移动元素
将序列复制回去
4． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。
5． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
【答案】(1)递归算法如下:
递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值
(2)非递归算法如下:
递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值
S 是二叉排序树结点指针的栈，容量足够大
沿右分支向下
去左分支
算法结束
二、应用题
6． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下:
(1)对该算术表达式(二叉树) 进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值。
(2)递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+、－、*、/等) 进行求值。