2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研题库
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
2． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
3． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
【答案】（1）（2）（3）（4）（5）
4． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
5．
【答案】5
=_____
6． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
7． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
8． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
9． 当两个栈共享一存储区时，栈利用一维数组当栈1空时
，
【答案】
为_____，栈2空时
，
表示，两栈顶指针为
则
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。 10．，设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：）则
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
的地址为
将
代入得33。
则
的地址为
的地址为_____。
若
二、判断题
11．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为
与待排序记录的初始排列状态无关。
若
则有：
（ ）
12．2，... ，n , 输出序列是栈的输入序列是1，
【答案】
【解析】出栈序列不一定满足比如1进栈，然后出栈，
13．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。
14．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
【答案】×
【解析】哈夫曼树不存在度数为1的结点。度数为2和0的结点数之差为1。
15．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
16．无环有向图才能进行拓扑排序。（ ）
【答案】√
【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
17．数组不适合作为任何二叉树的存储结构。（ ）
【答案】×
【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的（存储密度大）。
18．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
19．排序算法中的比较次数与初始元素序列的排列无关。（ ）
【答案】×
【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。
20．有n 个数顺序（依次）入栈，出栈序列有Cn 种，（ ）
【答案】
三、算法设计题
21．设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下：
//将满二叉树的后序序列转为前序序列，11、hl 、12、h2是序列初始和最后结点的下标。