当前位置：问答库＞考研试题

一、填空题

1． 中缀式

运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

2． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称

增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

3． 在循环队列中，队列长度为n ，存储位置从0到，

【答案】 编号，以rear 指示实际的队尾元素，现对应的前缀式为_____，若则后缀式的要在此队列中插入一个新元素，新元素的位置是（ ）。

4． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

5． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

6． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

7． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以

达到整个序列有序。

8． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

9． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

10．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

二、判断题

11．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。

12．取线性表的第i 个元素的时间同i 的大小有关。（ ） 【答案】

【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。

13．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）

【答案】×

【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。

14．B-树中所有结点的平衡因子都为零。（ ）

【答案】√

【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。

15．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）

【答案】

【解析】队列是一种先入先出型结构，而栈才是先进后出的线性结构。

16．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易増加闲置空间的碎片。

（ ）

【答案】√

【解析】最佳适配法：将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。

17．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】

【解析】数据的逻辑结构是指数据元素之间的逻辑关系。

18．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）

【答案】√

，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，

所以顺序是一致的。

19．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）

【答案】√

【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之间的关系。

20．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）

【答案】×

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

三、算法设计题

21．已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。

（1）编写用前序遍历树中每个结点的非递归算法；

（2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。

【答案】（1）算法如下: