2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编（一）.... 2 2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编（二）.... 9 2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编（三）.. 15 2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编（四）.. 21 2017年湖南师范大学数学与计算机科学学院865数据结构考研导师圈点必考题汇编（五）.. 28
一、填空题
1． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
2． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
3．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
4． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
5． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
6． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
7． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
8． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
9． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）链表未到尾就一直进行
（2）
将当前结点作为头结点后的第一元素结点插入
10．应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
〔始顶点号，终顶点号，权值）
（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在〈limits •h>中
//图的顶点数，应由用户定义
//用二维数组作为邻接矩阵表示
//生成树的边结点
//边的起点与终点
//边上的权值
//最小生成树定义
//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点
//初始化最小生成树
T
//依次求MST 的候选边
//遍历当前候选边集合
//选具有最小权值的候选边
//图不连通，出错处理
//修改候选边集合
【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图
，是N
上最小生成树边的集合。算法从属于
为止。
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
相关内容
相关标签