2018年数据结构考研真题答案及解析（七）

本文提供2018年数据结构考研真题答案及解析，以下为具体内容

1、下列选项中，不能构成折半查找中关键字比较序列的是（  ）。

A、 500， 200， 450， 180

B、 500， 450， 200， 180

C、 180， 500， 200， 450

D、 180， 200， 500， 450

2、一棵有124个叶子结点的完全二叉树，最多有（ ）个结点。

A、247

B、248

C、249

D、250

3、具有n个关键字的m阶B树，应有（ ）个叶结点。

A、n+1

B、n-1

C、mn

D、nm/2

4、在一个单链表中，已知q所指结点为p所指结点的前驱结点，若在q和p之间插入结点s，则执行的操作是（ ）。

A、s→next=p→next; p→next=s;

B、p→next=s→next; s→next=p;

C、q→next=s; s→next=p;

D、p→next=s; s→next=q;

5、设有一个顺序共享栈，S[0…n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（ ）。

A、top2-top1=1

B、top1=top2

C、top1-top2=1

D、以上都不对

6、在下列排序方法中，（ ）方法可能出现这种情况：在最后一趟开始之前，所有元素都不在其最终应在的正确位置上。

A、快速排序

B、冒泡排序

C、堆排序

D、插入排序

7、下列哪一项不是数据结构的要素（ ）。

A、数据的逻辑结构

B、数据的存储结构

C、数据的运算

D、算法

8、采用邻接表存储的图，若邻接表中有奇数个边表结点，则该图一定是（ ）。

A、图中有奇数个结点

B、图中有偶数个结点

C、图为无向图

D、图为有向图

9、一个栈的入栈序列是1，2，3，4，则出栈次序不可能出现的是（ ）。

A、1，2，3，4

B、4，1，3，2

C、1，4，3，2

D、4，3，1，2

1、试题答案：A

试题解析：

【考点】本题考查折半查找。
【解析】折半查找判定树的本质是二叉排序树，二叉排序树或者为空树，或者为具有如下特性的树：① 若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；② 若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；③ 其左右子树也分别为二叉排序树。构造出A选项对应的折半查找路径如下：

检查上述各点，180在200的右子树上，但180<200，显然上述路径不符合二叉排序树的定义，因此A错误。
构造出B选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此B正确。
构造出C选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此C正确。
构造出D选项对应的折半查找路径如下：

检查上述各点,上述路径符合二叉排序树的定义，因此D正确。故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--完全二叉树--完全二叉树的性质。
【解析】在非空的二叉树当中，由度为0和2的结点数的关系n0=n2+1可知n2=123；总结点数n=n₀+n₁+n₂=247+n₁，其最大值为248（n₁的取值为1或0，当n₁=1时结点最多）。注意，由完全二叉树总结点数的奇偶性可以确定n₁的值，但不能根据n₀来确定n₁的值。故本题选B。

3、试题答案：A

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B-树--B-树的性质。
【解析】B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找，失败可能性有n+1种。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查单链表插入。
【解析】本题中在q和p之间插入结点s的示意图如下所示，由此可知选项C正确。故本题选C。

5、试题答案：A

试题解析：

【考点】本题考查判断共享栈满的条件。
【解析】在共享栈中，栈1和栈2的空间均向中间延伸，当栈1中入栈一个元素，指针top1向后移动一个位置后，若此时top1恰好与top2指向同一个位置，则说明该共享栈已满，即判断栈满的条件为top1+1=top2，即top2-top1=1。故本题选A。

6、试题答案：D

试题解析：

【考点】本题考查常见的排序算法的特点。
【解析】
A：快速排序进行一趟排序后，其选取的基准元素必定在其最终的正确位置上。
B：冒泡排序进行一趟排序后，一定会由一个最大（或最小）的元素在其最终的正位置上。
C：采用堆排序，每趟排序必定会有一个最大（或最小）元素在其最终位置上。
D：若整个序列逆序，采用插入排序，在最后一趟开始之前，所有元素都不在其最终应在的正确位置上。
综上所述，本题选D。

7、试题答案：D

试题解析：

【考点】本题考查数据结构的三要素。
【解析】数据结构的三要素包括数据逻辑结构、数据存储结构和数据的运算。
（1）数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的具体存储形式无关，是独立于计算机的。数据逻辑结构通常分为线性结构和非线性结构。
（2）数据的存储结构指的是数据结构在计算机中的表示，也称为物理结构，又称映像。数据存储结构依赖于计算机语言，它是用计算机语言实现的逻辑结构。数据的线性存储结构主要有：顺序存储、链式存储、索引存储、散列存储。
（3）数据的运算主要体现为运算的定义，以及运算的实现。运算的定义是针对数据逻辑结构的，它描述了运算所能实现的功能。运算的实现是针对数据存储结构的，它描述了运算的具体操作过程。
综上所述，算法不是数据结构的要素。故本题选D。

8、试题答案：D

试题解析：

【考点】本题考查邻接表。
【解析】n个结点e条边的无向图用邻接表存储，其中边结点个数为2e，即有偶数个边结点，因为一条边存储了两次。若邻接表中边结点个数为奇数，则该图不可能是无向图，那么只能是有向图。故本题选D。

9、试题答案：B

试题解析：

【考点】本题考查正确的出栈顺序。
【解析】一个栈的入栈序列是1，2，3，4，若4先出栈，则说明1、2、3均已依次入栈，接着出栈的元素只能是3、2、1。因此，一个栈的入栈序列是1，2，3，4，则出栈次序不可能出现的是4，1，3，2。故本题选B。