2018年北京市培养单位光电研究院863计算机学科综合(专业)之数据结构考研核心题库
● 摘要
一、填空题
1． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
2． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
3． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
4． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
5． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
6． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
7． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要
8． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
第 2 页，共 59 页 。
9． 阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。
本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
(3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
10．堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
二、判断题
11．2，n ，a 2，a n
若…，…，桟的输入序列是1，输出序列是a 1，
（ ）
【答案】 ×
【解析】出找序列不一定满足a 1＞a i+1... ＞a n ，比如1进栈，然后出找，a 1＝1。
12．堆是满二叉树。（ ）
【答案】×
【解析】堆的定义:
n 个关键字序列
①且
第 3 页，共 59 页 则有:。。 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :
②且
小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
因此并不能保证堆是满二叉树。
13．程序一定是算法。（ ）
【答案】 ×
【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，这时算法就是一个程序。
14．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
只要符合公式的内存块都是伙伴。
15．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路) 。
【答案】√
【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。
16．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
17．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
【答案】×
【解析】哈夫曼树不存在度数为1的结点。度数为2和0的结点数之差为1。
18．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
第 4 页，共 59 页