2019年数据结构考研真题答案及解析

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

1、在存储数据时，通常不仅要存储各数据元素的值，而且要存储（）。

A、 数据的操作方法

B、 数据元素的类型

C、 数据元素之间的关系

D、 数据的存取方法

2、长度分别为m和n的升序顺序表，若将它们合并为一个长度为m+n的升序顺序表，则最坏情况下算法执行的比较次数为（ ）。

A、 m+n-1

B、 mXn

C、 min（m，n）

D、 max（m，n）

3、四个元素1，2，3，4 依次进栈，允许进栈、退栈操作交替进行，则（ ）不可能是其出栈序列。

A、 1，2，3，4

B、 4，1，3，2

C、 1，4，3，2

D、 4，3，2，1

5、已知广义表L（（a，b），（c，d）），Tail是取表尾操作。广义表运算式Tail（L）的操作结果是（ ）。

A、 （c，d）

B、 c，d

C、 （（c，d））

D、 d

6、具有10个叶结点的二叉树中有（ ）个度为 2的结点。

A、 8

B、 9

C、 10

D、 11

7、设某无向图有n个顶点和e条边，则该图的邻接表中有（）个边结点。

A、 n

B、 e

C、 n+e

D、 2e

8、若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图（）。

A、 含有多个出度为0的结点

B、 是个强连通图

C、 含有多个入度为0的顶点

D、 必然有环

9、当采用分块查找时，数据的组织方式的特点是（ ）。

A、 数据分成若干块，每块内数据必须有序，块间也必须有序

B、 数据分成若干块，每块内数据必须有序，但块间不必有序

C、 数据分成若干块，每块内数据不必有序，但块间必须有序

D、 数据分成若干块，每块内数据不必有序，块间也不必有序

10、简单选择排序算法中，关键字的总比较次数为（ ）。

A、

B、

C、

D、

1、试题答案：C

试题解析：

【考点】本题考查数据结构的定义
【解析】数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。而存储结构存储“数据元素”的映像以及“关系”的映像。而数据的操作方法或存取方法，属于数据结构的运算，不需要存储，因此A、D错误。数据元素的类型是数据的标记，数据在实际存储时在存储空间中没有存储类型。因此B错误。故本题选C。

2、试题答案：A

试题解析：

【考点】本题考查顺序表的合并
【解析】两个有序表合并时，最坏情况下，两个表的各个元素需要依次进行比较，其比较次数为两个表的长度和-1。例如L1={1，3，5，7}，L2={2，4，6}。合并两个表时，1和2比较，1加入到L中；2和3比较，2加入到L中；3和4比较，3加入到L中；4和5比较，4加入到L中；5和6比较，5加入到L中；6好人7比较，6加入到L中；7加入到L中。上述过程一共比较了6次，因此最坏情况下的比较次数为m+n-1。在最好情况下，仅需要将较短表的全部元素和较长表的首元素进行比较，比较次数为min（m，n）。例如L1={1，2，3}，L2={4，5，6，7}，此时，1、2、3分别和4比较，之后L2直接全部添加到L中。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查栈的基本操作
【解析】对于A，执行操作push（1）、pop（1） 、push（2）、pop（2） 、push（3）、pop（3） 、push（4）、pop（4）可得到A选项的出栈序列。对于B，若第一个出栈元素为4，说明1、2、3已经在4之前入栈且之前并无出栈元素，此时1应当为第1个入栈最后一个出栈，其出栈序列1不可能在3、2前面，因此B选项是不可能的出栈序列。对于C，执行操作push（1）、pop（1） 、push（2）、push（3）、push（4）、pop（4）、pop（3）、pop（2）可得C选项的出栈序列。对于D，执行操作push（1）、push（2）、push（3）、push（4）、pop（4）、pop（3）、pop（2）、pop（1）可得D选项的出栈序列。故本题选B。

5、试题答案：C

试题解析：

【考点】本题考查广义表的基本操作
【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。在本题中，Head（L）= （a，b），Tail（L）= （（c，d））。取尾操作包含一个括号是因为表尾是一个广义表，故本题选C。

6、试题答案：B

试题解析：

【考点】本题考查二叉树的性质
【解析】根据二叉树的性质：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。其证明过程为：设n1为二叉树中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，所以其结点总数为n=n0+n1+n2。二叉树中，除根结点以外，其余结点均有一个分支进入，设分支总数为B，则有n=B+1。由于这些分支是由度为1或者度为2的结点射出的，所以有B=n1+2*n2。带入B=n-1可得，n0+n1+n2-1=n1+2*n2，即n0=n2+1。带入本题，n0=10，因此n2=9，故本题选B。

7、试题答案：D

试题解析：

【考点】本题考查无向图的邻接表存储
【解析】邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。在无向图中，每个边连接两个顶点，因此边两端的顶点会在链表中各出现一次，因此边结点的个数是边数的两倍。故本题选D。

8、试题答案：D

试题解析：

【考点】本题考查拓扑序列
【解析】对于A，含有多个出度为0的结点不会影响拓扑排序，C同理。对于B，强连通图是指有向图的任意两个顶点之间都存在路径，因此强连通图是一个有环图，但有环图不一定是强连通图，有环图无拓扑序列。因此，若一个有向图无拓扑结构，仅能判断该图存在环，但不一定是强连通图。故本题选D。

9、试题答案：C

试题解析：

【考点】本题考查分块查找
【解析】分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。 分块查找要求把一个数据分为若干块，每一块里面的元素可以是无序的，但是块与块之间的元素需要是有序的。故本题选C。

10、试题答案：C

试题解析：

【考点】本题考查简单选择排序
【解析】简单选择排序是一种简单直观的排序算法。它在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。比较次数与关键字的初始状态无关，总的比较次数N=（n-1）+（n-2）+...+1=n*（n-1）/2，即比较次数为O（n^2），故本题选C。