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

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

1、链表不具有的特点是（  ）。

A、插入、删除不需要移动元素

B、可随机访问任一元素

C、不必事先估计存储空间

D、所需空间与线性长度成正比

2、在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是（ ）。

A、G中有弧<v_i，v_j>

B、G中有一条从v_i到v_j的路径

C、G中没有弧<v_i，v_j>

D、G中有一条从v_j到v_i的路径

3、二叉搜索树中，最小元素的左子树（ ），它的右子树（ ）。

A、一定为空，不一定为空

B、不一定为空，一定不为空

C、一定不为空，不一定为空

D、不一定为空，不一定为空

4、设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R，头指针F指向队首元素的前一个位置，尾指针R指向队尾元素，则此循环队列中的元素个数（ ）。

A、R-F

B、F-R

C、（R -F+M）%M

D、（F-R+M）%M

5、设高度为h的二叉树上，只有度为0和度为2的结点，则这一类二叉树中所包含的结点数至少为（ ）。

A、h-1

B、h

C、2h-1

D、2h

6、（ ）的先序遍历和后序遍历序列正好相反。

A、所有结点的左子树都为空的二叉树

B、所有结点的右子树都为空的二叉树

C、3个结点的二叉树

D、6个结点的二叉树

7、查找效率最高的二叉搜索树是（ ）。

A、所有结点的左子树都为空的二叉搜索树

B、所有结点的右子树都为空的二叉搜索树

C、 AVL二叉搜索树

D、没有左子树的二叉搜索树

8、下面叙述中，不正确的是（ ）。

A、B-树中所有的失败结点处于同一层

B、B-树中根结点至少有2个孩子

C、B-树中所有结点至少有⌈m/2⌉个孩子

D、一棵m叉搜索树中最多有（m^h-1）个元素

9、以下排序算法中，一趟排序后所有元素的最终位置暂不能确定的算法是（ ）。

A、直接插入排序

B、快速排序

C、冒泡排序

D、简单选择排序

10、倒排文件的主要优点是（ ）。

A、便于进行插入和删除运算

B、便于进行文件的合并

C、能大大提高次关键字的查找速度

D、能大大节省存储空间

1、试题答案：B

试题解析：

【考点】本题考查链式存储的特点。
【解析】线性表有两种存储结构，一种是顺序结构，一种是链式结构。链表属于链式结构。对于A，链表的插入和删除仅需修改指针不需要移动元素，A是链表的特点。对于B，顺序存储结构是一种随机存取的结构，而链式存储结构非随机存取结构，链表访问某元素需要从头指针开始，B不是链表的特点而是顺序存储的特点。对于C，链表不必事先估计存储空间，其存储单元不必连续，C是链表的特点。链表每个结点都需要开辟存储空间，因此所需空间与线性长度成正比，D是链表的特点。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查数据结构--图--有向无环图--拓扑排序--拓扑排序算法--拓扑排序算法的思想。
【解析】若图G中存在一条从v_j到v_i的路径，说明v_j是v_i的前驱，则要把v_j消去以后才能消去v_i，从而拓扑序列中必然先输出v_j，再输出v_i，这显然与题意矛盾。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树--二叉排序树的性质。
【解析】二叉搜索树中，任意结点满足特性“左孩子结点值<该结点值<右孩子结点值”。若某一元素的左子树不为空，则说明还有比它更小的元素，所以最小元素的左子树一定为空。而最小元素的右子树是比它大的元素，可以为空也可以不为空。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查数据结构--栈和队列--队列--队列的应用--循环队列。
【解析】在循环队列中，头指针F指向队首元素的前一个位置，尾指针R指向队尾元素。因为牺牲了一个存储单元用于判断队满，所以rear-front的绝对值即表示队列中元素的个数。为了保证R-F为正数 ，用(R-F+Maxsize)mod Maxsize表示循环队列中元素个数。本题中maxsize=M，所以当前队列中元素数是（R-F+M）%M。故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--二叉树的性质。
【解析】高度为h的二叉树上，只有度为0和度为2的结点，该树结点最少的情况是除了第一层以外，剩余的h-1层中，每一层都有两个结点，那么共有2(h-1)+1=2h-1个结点。故本题选C。

6、试题答案：A;B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--遍历二叉树。
【解析】先序遍历和后序遍历分别遵循“根左右”、“左右根”的遍历原则。若先序遍历过程是“根左”，后序遍历过程是“左根”，这样的二叉树中所有结点的右子树都为空，此时两者的遍历结果相反。亦或是，若先序遍历过程是“根右”，后序遍历过程是“右根”，这样的二叉树中所有结点的左子树都为空，此时两者的遍历结果也相反。故本题选A和B。

7、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树。
【解析】二叉搜索树的查找效率和与这棵树的高度有关，高度越低，查找效率越高。而AVL二叉搜索树相较于其它选项中的二叉搜索树而言，在结点总数相同的情况下，其高度更低，所以查找效率最高的二叉搜索树是AVL二叉搜索树。故本题选C。

8、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B-树--B-树的性质。
【解析】B-树中，除了根结点之外，所有非叶子结点最少有⌈m/2⌉个孩子，并非所有结点至少有⌈m/2⌉个孩子，所以选项C中说法错误。故本题选C。

9、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--内部排序算法的综合比较。
【解析】若整个序列逆序，采用直接插入排序后，直到最后一趟排序完成前，所有元素的最终位置都暂时不能确定。快速排序一趟后，其基准元素的最终位置可以确定。冒泡排序或者是简单选择排序一趟后，整个序列中的最大或最小元素的最终位置可以确定。因此，直接插入排序一趟排序后所有元素的最终位置暂不能确定。故本题选A。

10、试题答案：C

试题解析：

【考点】本题考查数据结构--文件--多关键字文件--倒排文件--倒排文件的特点。
【解析】倒排文件能够大大提高次关键字的查找速度。倒排文件是指根据单词或者词组创建的索引表，记录了每个单词或词组出现的位置，可以快速定位包含某个单词或词组的文档。因此，倒排文件可以帮助加快文本检索的速度，提高检索的准确性。相比于选项A、B、D，倒排文件的主要优点并不在于插入和删除运算、文件的合并以及节省存储空间。故本题选C。