2018年中南民族大学计算机科学学院842数据结构考研核心题库
● 摘要
一、填空题
1． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
2． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
第 2 页，共 50 页
中
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
的边为止。
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
5． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
7． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
8． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
第 3 页，共 50 页
是连通图
，
，v ，
直到
，开始，重复执行下述操作:在所有u 属于
加入集合
，同时将并入
属于E 中找一条代价最小的边
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
9． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
:_____:
{_____)
(_____、
:_____；_____；p ＝u ；
【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中 (2)p!＝NULL //当链表尚未到尾，p 为工作指针
(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针 (4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中
(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针
10．一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
二、单项选择题
11．主机甲与主机乙之间使用后退N 帧协议(GBN)传输数据, 甲的发送窗口尺寸为1000, 数据帧长为1000字节, 信道宽带为100Mbps , 乙每收到一个数据帧立即利用一个短帧(忽略其传输延迟) 进行确认, 若甲乙之间的单向传播延迟是50ms , 则甲可以达到的最大平均数据传输速率约为（ ）
A.10Mbps B.20Mbps C.80Mbps D.100Mbps 【答案】C 【解析】
12．二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
第 4 页，共 50 页