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

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

1、计算算法的时间复杂度是属于一种（  ）。

A、 事前统计的方法

B、 事前分析估算的方法

C、 事后统计的方法

D、 事后分析估算的方法

2、若有n个结点的线性表（a1，a2， ...，an） 以顺序方式存储，则算法的时间复杂度是O（1）的操作是（  ）。

A、 访问第i个结点（1≤i≤n） 和第i个结点的直接前驱（2≤i≤n）

B、 在第i个结点后插入一个新结点（1≤i≤n）

C、 删除第i个结点（1≤i≤n）

D、 以上都不对

3、双向循环链表的结点中有两个指针域，next和prior，分别指向前驱及后继，设p指向链表中的一个结点，s指向一待插入结点，现要求在p后插入s，则正确的插入为（ ）。

A、 p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B、 s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

C、 p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;

D、 s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

4、链栈与顺序栈相比，有一个比较明显的优点是（ ）。

A、 插入操作更加方便

B、 删除操作更加方便

C、 通常不会出现栈满的情况

D、 不会出现栈空的情况

5、串是一种特殊的线性表，其特殊性体现在（）。

A、 可以顺序存储

B、 可以链接存储

C、 数据元素可以是多个字符

D、 数据元素是一个字符

6、稀疏矩阵一般的压缩存储方法有两种，即(  )。

A、 二维数组和三维数组

B、 三元组顺序表和散列表

C、 散列表和十字链表

D、 三元组顺序表和十字链表

7、一棵高度为h的完全二叉树至少有(  )个结点。

A、 2^h-1

B、 2^h-1-1

C、 2^h-1

D、 2^h

8、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的(  )倍。

A、 1/2

B、 1

C、 2

D、 4

9、针对下述结论，正确答案是（ ）。① 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。② 对大小均为 n的有序表和无序表分别进行顺序查找，在等概率查找情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。

A、 ①②都正确

B、 ①②都不正确

C、 只有①正确

D、 只有②正确

10、假设对已经正序的n个关键字序列用直接插入排序法、简单选择排序法和一般的快速排序法对其排序，这些算法的时间复杂度依次应为（ ）。

A、 O（n），O（n²），O（n²）

B、 O（n²），O（n²），O（n²）

C、 O（n），O（n），O（n）

D、 O（n），O（n²），O（nlog₂n）

1、试题答案：B

试题解析：

【考点】本题考查算法时间复杂度的属性。
【解析】算法效率的度量方法主要有两种，一种是事后统计法，一种是事前分析估算法。A和D不属于算法效率的度量方法。事后统计法是指计算机计时器对不同的算法编写的程序运行时间的计算。这种方法在编写好算法的基础上计算该算法花费的时间。而事前分析估算的方法是在计算机程序编写前对算法的运行时间进行估算。而时间复杂度就是事前估算法，时间复杂度能够估算出当输入的规模不断增大时算法的增长规律，故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查顺序表操作的时间复杂度。
【解析】顺序表是一种随机存储结构，因此顺序表的访问操作的时间复杂度为O（1）。而顺序表的插入和删除操作均需要移动元素，插入一个元素平均要移动的元素个数为n/2，删除一个元素平均要移动的元素个数为（n-1）/2，因此插入和删除结点的时间复杂度均为O（n），故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查双向循环链表的插入操作。
【解析】针对A，若p->next=s在p->next->prior=s和s->next=p->next之前操作，那么会导致p->next被s覆盖，从而导致p->next的丢失，C和D同理，存在的问题均为p->next指针指向的结点丢失。而B选项正确，其执行的步骤如下图所示：

故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查顺序栈和链栈的特点。
【解析】不管是顺序栈还是链栈，其本质还是栈，栈是特性是只能在栈顶进行插入和删除，其时间复杂度均为O（1），因此A和B错误。顺序栈采用顺序存储结构，会受到最大容量空间的限制，而链栈采用指针结构，因此适用于无法预估栈的最大空间的情况，因此C正确。对于D，不管是链栈还是顺序栈均可以出现栈空的情况，故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查串的定义。
【解析】串的存储结构既可以是顺序存储也可以是链式存储，因此A和B错误。串的定义为：串是由零个或多个字符组成的有序序列，一般记为s=”a₀a₁a₂…a_n-1”（n>=0），因此D错误，故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查稀疏矩阵的压缩存储。
【解析】稀疏矩阵是指矩阵中非零元素<=50%，且分布无规律。在存储稀疏矩阵时，仅存储非零元素即可。存储非零元素的行坐标、列坐标、元素值。其存储方法有两种，分别为三元组顺序表和十字链表。三元组顺序表存储方法的每个元素有三个域，分别为i、j、k，代表非零元素的行号、列号、值。十字链表的每一行是一个链表，代表行坐标，每一个列是一个链表代表列坐标。故本题选D。

7、试题答案：C

试题解析：

【考点】本题考查完全二叉树的性质。
【解析】根据二叉树的性质，在二叉树的第i层上至多有2^i-1个结点（i>=1）。高度为h的完全二叉树从第1层到底h-1层是一个满二叉树，因此每层的结点个数为2^i-1个，当高度为h-1层时，结点个数为2⁰+2¹+2²+……+2^h-2=2^h-1-1。题干要求至少有多少个结点个数，则第h层需要有一个结点，总的结点数为2^h-1，故本题选C。

8、试题答案：B

试题解析：

【考点】本题考查有向图的度。
【解析】有向图的入度是指有向图中某点作为图中弧的终点的次数之和，而有向图的出度是指有向图中某点作为图中弧的起点的次数之和。在有向图中，一条弧两端连接两个顶点，其中一个顶点必为弧的起点，另一条必为弧的终点，因此有向图的入度=出度=边数，故本题选B。

9、试题答案：A

试题解析：

【考点】本题考查查找的长度计算。
【解析】分块查找首先查找分块，之后在分块内采用顺序查找或折半查找的方法查找元素。分块的大小与表中元素个数有关，块内查找与每块元素个数有关，因此①正确。无序表或有序表采用顺序查找时，成功查找的平均查找长度均为(n+1)/2，无序表的失败查找长度为n+1，而有序表<n+1，因此②正确。故本题选A。

10、试题答案：A

试题解析：

【考点】本题考查排序算法的时间复杂度。
【解析】直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。当初始序列正序时，直接插入排序仅需要一趟扫描即可完成排序，此时时间复杂度为O（n）。一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换。其比较次数与序列的初始状态无关，因此时间复杂度为O（n²）。快速排序是把序列分块，若序列已经基本有序，则选取第一个数为枢纽时，第一块前面没有数，第二块是除了第一个数以外的所有值，每次分块仅减少一个值。分块的时间复杂度是O（n），分了n次块，时间复杂度是O（n²）。故本题选A。