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）