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

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

1、以下与数据的存储结构无关的术语是（ ）。

A、循环队列

B、链表

C、哈希表

D、栈

2、用DFS遍历有向无环图，并在算法退栈返回时打印相应的顶点，则输出顶点序列是（ ）。

A、逆拓扑有序

B、拓扑有序

C、无序的

D、有序的

3、用6棵节点数均为5的树所组成的森林转化的二叉树中，根节点的右子树上一定有（ ）个节点。

A、30

B、6

C、5

D、25

4、在线性表的存储结构中，能实现随机存储的是（ ）。

A、单链表

B、双链表

C、循环链表

D、顺序表

5、具有65个节点的完全二叉树，其深度为（ ）（根在第一层）。

A、8

B、7

C、6

D、5

6、如果只考虑有序的情形，那么具有7个节点不同形态的二叉树共有（ ）。

A、132

B、154

C、429

D、前三者均不正确

7、在一棵含有n个关键字的m阶B树进行查找，读盘数至多为（ ）。

A、log₂n

B、1+1og₂n

C、1+1og_⌈m/2⌉(n+1)/2

D、1+1og_⌈n/2⌉(m+1)/2

1、试题答案：D

试题解析：

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的存储结构/物理结构--存储结构/物理结构的分类。
【解析】循环队列属于顺序存储结构，链表属于链式存储结构，哈希表属于散列存储结构。而栈属于逻辑结构，与存储结构无关。它既可以用链式结构存储，也可以用顺序结构存储。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的深度优先遍历/搜索--图的深度优先遍历/搜索的应用。
【解析】在使用 DFS 遍历有向无环图时，算法退栈返回的顺序是逆拓扑序列的顺序，因为先访问的节点会后退栈，后访问的节点会先退栈，所以最后退栈的节点一定是入度为 0 的节点，而这些节点一定是在DAG 的拓扑序列的末尾。故本题选A。

3、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--森林转换为二叉树。
【解析】森林转换成二叉树的过程：先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树为空，则把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当做第一棵二叉树根的右子树，将第三棵树对应的二叉树当做第二棵二叉树根的右子树……以此类推，即可将森林转换为二叉树。由此知，除了第一棵树，其余的五棵树均作为了第一棵树的右孩子部分。那么根节点的右子树上一定有5*5=25个结点。故本题选D。

4、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构。
【解析】链表中所有结点的存储位置不一定是连续的，所以想要访问其中的某一结点时只能从头遍历整个链表，无法实现随机存储的特点。而顺序表中元素的存储空间是连续的，所以能实现随机存储。故本题选D。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--完全二叉树--完全二叉树的性质。
【解析】一棵高度为h的满二叉树共有2^h-1个结点。而2⁶-1<65<2⁷-1，说明具有65个节点的完全二叉树的深度为7。故本题选B。

6、试题答案：C

试题解析：

7、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B-树--B-树的性质。
【解析】一棵包含n个关键字（n>=1）阶数为m的B-树的最大高度hmax=log_⌈m/2⌉((n+1)/)+1，最小高度hmin=log_m(n+1)。而对一棵B树进行查找的最多不会超过B树的高度，所以读盘数至多为log_⌈m/2⌉((n+1)/2)+1。故本题选C。