2017年北京市培养单位软件研究所863计算机学科综合(专业)之数据结构考研题库
● 摘要
一、填空题
1． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
2． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
3． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】
【解析】叶子节点的左右孩子都不存在。
4． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
5． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
6． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
7． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
8． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）
而快速排序算法需要比较的次数达到最大，时间复杂度为
9． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
10．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称
增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
二、判断题
11．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】√
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
12．数据元素是数据的最小单位。（ ） 【答案】
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
13．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，且ri 在rj 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
14．堆是满二叉树。（ ）
【答案】×
【解析】堆的定义：
n 个关键字序列
且
且 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆；
大根堆：满足第②种情况的堆。
因此并不能保证堆是满二叉树。
15．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
16．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
17．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
18．直接访问文件也能顺序访问，只是一般效率不高。（ ）
【答案】×
【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。
19．二元查找树的任何结点的左右子树都是二元查找树。（ ）
【答案】√
【解析】二元查找树也称作二元排序树。二元查找树的性质：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。
20．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】√
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
三、算法设计题
21．编程：假设以数组存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初
，插入（enqueue ）和删除（dequeue ）兀素的操作。 始化（initqueue ）
【答案】定义队列：