考研数据结构在线题库每日一练（五十九）

本文提供考研数据结构在线题库每日一练，以下为具体内容

1、在长度为n顺序实现的线性表的第i（1≤i≤n）个位置之前插入一个元素，需要后移（ ）个元素。

A、0

B、i

C、1

D、n-i+1

2、六个元素按6，5，4，3，2，1的顺序进栈，下列哪个出栈序列是错误的（ ）。

A、5 4 3 6 1 2

B、4 5 3 1 2 6

C、3 4 6 5 2 1

D、2 3 4 1 5 6

3、若采用递归方式对顺序表进行快速排序，关于递归次数的描述正确的是（ ）。

A、递归次数与初始数据的排列次序无关

B、递归次数与每次划分后得到的分区的处理次序无关

C、每次划分后先处理较长的分区可减少递归次数

D、每次划分后先处理较短的分区可减少递归次数

4、已知一棵二叉树的前序序列为ABDCE，则它可能的中序序列是（ ）。

A、BACDE

B、CBADE

C、BDAEC

D、BEACD

5、已知一棵二叉树的前序序列为ABDGCEFH，中序序列为DGBAECHF，则其后序序列为（ ）。

A、BDGCEFHA

B、GDBECFHA

C、BDGAECHF

D、GDBEHFCA

1、试题答案：D

试题解析：

顺序表第i个位置之前插入一个元素，则第i至第n的元素均需要向后移动一位，因此需要后移的元素总数为n-i+1，故本题选D。

2、试题答案：C

试题解析：

对于A，可以经过这样的操作得到该出栈序列：push(6)，push(5)，pop(5)，push(4)，pop(4)，push(3)，pop(3)，pop(6)，push(2)，push(1)，pop(1)，pop(2)；对于B，可以经过这样的操作得到该出栈序列：push(6)，push(5)，push(4)，pop(4)，pop(5)，push(3)，pop(3)，push(2)，push(1)，pop(1)，pop(2)，pop(6)；对于C，6在5之前进栈，则5应当在6之前出栈，因此C错误；对于D，可以经过这样的操作得到该出栈序列：push(6)，push(5)，push(4)，push(3)，push(2)，pop(2)，pop(3)，pop(4)，push(1)，pop(1)，pop(5)，pop(6)；故本题选C。

3、试题答案：B

试题解析：

在对顺序表进行快速排序时，每次划分都会将待排序区间分为两个子区间，并将一个元素放置到它最终的位置。递归次数取决于划分出来的子区间的个数，而与每次划分后得到的分区的处理次序无关，因为最终排序的结果只与子区间的大小关系有关，而不涉及子区间之间的相对位置。故本题选B。

4、试题答案：A;C

试题解析：

前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。中序遍历二叉树先遍历左子树，再访问根结点，最后遍历右子树。A选项和C选项符合树的遍历规则，因此AC正确。B选项和D选项不符合树的遍历规则，因此BD错误。故本题选AC。

5、试题答案：D

试题解析：

根据二叉树的前序序列和中序序列可以唯一的构造一棵二叉树，画出这棵二叉树如下：

由上述二叉树得出树的后序遍历序列为：GDBEHFCA。故本题选D。