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

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

1、下列数据中，（ ）是非线性数据结构。

A、栈

B、队列

C、完全二叉树

D、堆

2、以下属于逻辑结构的是（ ）。

A、顺序表

B、哈希表

C、有序表

D、单链表

3、在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节约时间。

A、单链表

B、仅有头指针的单循环链表

C、双向链表

D、仅有尾指针的单循环链表

4、对（ ）中序遍历必将得到一个树中结点的非递减有序遍历。

A、AVL树

B、扩充二叉树

C、散方树

D、最小堆

5、设散列表H[11]，散列函数是H（key）=key mod 11，用关键字序列{24，34，35，39，46}建立散列表，采用二次探查法解决冲突，则46在散列表中的下标为（ ）。

A、-2

B、2

C、6

D、9

6、二叉树是非线性数据结构，所以（ ）。

A、它不能用顺序存储结构存储

B、它不能用链式存储结构存储

C、顺序存储结构和链式存储结构都能存储

D、顺序存储结构和链式存储结构都不能存储

7、以下关于图的说法，不正确的是（ ）。

A、无向图中的极大连通子图称为连通分量

B、连通图的广度优先搜索中一般要采用队列来暂存刚访问的节点

C、图的深度优先搜索一般采用栈暂存刚访问过的顶点

D、有向图的遍历不可采用广度优先搜索方法

8、在下列存储形式中（ ）是树的直接存储形式。

A、双亲表示法

B、三重链表表示法

C、孩子兄弟表示法

D、多重链表表示法

9、下列排序算法中，经过一趟排序后不一定能确定待排序元素的最终位置的算法是（ ）。

A、直接插入排序

B、冒泡排序

C、快速排序

D、简单选择排序

10、下面关于哈希查找的说法，不正确的是（ ）。

A、采用链地址法处理冲突时，查找一个元素的时间是相同的

B、采用链地址法处理冲突时，若插入规定总是在链首，则插入任何一个元素的时间是相同的。

C、用链地址法处理冲突，不会引起二次聚集现象

D、用链地址法处理冲突，适合表长不确定的情况

1、试题答案：C

试题解析：

线性结构是一个有序数据元素的集合，其特点是数据元素之间存在一对一的线性关系。栈和队列是线性数据结构，堆也可以看作是线性结构，一般存储在数组中。而完全二叉树根结点与子结点存在一对多的关系，一定是非线性结构。故本题选C。

2、试题答案：C

试题解析：

数据的存储结构：顺序存储、链式存储、索引存储、哈希存储。顺序表属于顺序存储，哈希表属于哈希存储，单链表属于链式存储，所以顺序表、哈希表和单链表都不是逻辑结构。有序表属于逻辑结构，且是线性结构，既可以顺序存储结构存储，也可以用链式存储结构存储。故本题选C。

3、试题答案：D

试题解析：

单链表、仅有头指针的单循环链表和双链表查找最后一个元素时，都需要遍历整个链表，而仅有尾指针的单循环链表在O(1)的时间复杂度内就可以找到最后一个结点和第一个结点，便于在最后一个元素之后插入一个元素和删除第一个元素。故本题选D。

4、试题答案：A

试题解析：

AVL树即平衡二叉树，一般是基于二叉排序树的，而二叉排序树中任意一个结点满足条件“左孩子值<该结点值<右孩子值”，所以中序遍历二叉排序得到的是一个非递减有序遍历。故本题选A。

5、试题答案：D

试题解析：

关键字与其散列函数值对应如下：

24、34、35、39未发生冲突，可以直接存储散列表中；46与35发生冲突，采用二次探测法解决冲突：（2+1²）%11=3，（2-1²）%11=1，（2+2²）%11=6，（2-2²+11）%11=9，由此将46存入散列地址为9的位置。构造的散列表如下：

6、试题答案：C

试题解析：

二叉树既可以采用顺序存储，也可以采用链式存储。二叉树的顺序存储是用一组连续的存储单元存放二叉树中的结点，一般适合存储完全二叉树和满二叉树。二叉树的链式存储结构是指用链表来表示一棵二叉树。故本题选C。

7、试题答案：D

试题解析：

有向图的遍历既可以使用深度优先搜索方法，也可以采用广度优先搜索方法，所以选项D中说法错误。故本题选D。

8、试题答案：C

试题解析：

孩子兄弟表示法是树的直接存储形式。在孩子兄弟表示法中，每个节点除了指向其第一个子节点的指针外，还有指向其右兄弟节点的指针，这种存储方式可以方便地遍历树的所有节点。而双亲表示法、三重链表表示法和多重链表表示法，都是树的间接存储形式。故本题选C。

9、试题答案：A

试题解析：

如果整个序列逆序，采用直接插入排序只有最后一趟排序完成后，所有的元素才位于最终的位置上。在此之前，任何一个元素都没有被确定其最终位置。故本题选A。

10、试题答案：A

试题解析：

采用链地址法处理冲突时，查找一个元素的时间不一定相同。例如两个同义词位于同一个链表中的不同位置，查找这两个元素进行关键字比较的次数不同，所消耗的时间不同。故本题选A。