2017年中国人民公安大学安全工程823计算机学科专业基础综合[专业硕士]之数据结构考研题库
● 摘要
一、填空题
1． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
2． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。 【答案】
3． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
5． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
6． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
7． 设有两个算法在同一机器上运行，其执行时闻分别为
_____。
【答案】15
【解析】当
时，而
，时， 要使前者快于后者，n 至少为
8． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
9． 二进制地址为011011110000，大小为【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为当大小为16时，起始地址为
：
10．在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
和其伙伴块的起始地址计算公 和块的伙伴地址分别为：_____
二、判断题
11．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是
12．取线性表的第i 个元素的时间同i 的大小有关。（ ） 【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
13．
快速排序和归并排序在最坏情况下的比较次数都是（ ）
【答案】×
【解析】快速排序最坏的情况下比较次数是
14．两个长度不相同的串有可能相等。（ ） 【答案】
（ ）。
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
15．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ） 【答案】
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
16．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
【答案】×
【解析】哈夫曼树不存在度数为1的结点。度数为2和0的结点数之差为1。
17．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 【答案】
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
18．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
19．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
20．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
21．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。