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

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

1、一个栈的输入序列为1，2，3，. . .100，若输出序列的第一个元素是100，则输出的第30个元素是（ ）。

A、60

B、71

C、80

D、30

2、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。

A、n，e

B、e，n

C、2n，e

D、n，2e

3、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

4、一棵高度为k的满二叉树的结点总数是（ ）。

A、2^k-1

B、2^k

C、2^k-1

D、2k-1

5、设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。

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

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

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

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

6、在计算机的存储器中的表示时，物理地址和逻辑地址相同并且是连续的，称之为（ ）。

A、逻辑结构

B、顺序存储结构

C、链式存储结构

D、以上三种都不对

7、对有序单链表进行查找应选择（ ）查找法进行查找。

A、折半

B、分块

C、哈希

D、顺序

8、下列程序段的时间复杂度为（ ）。 

A、O(m*n*t)

B、O(m+n+t)

C、O(m+n*t)

D、O(m*t+n)

1、试题答案：B

试题解析：

【考点】本题考查栈正确的出栈元素。
【解析】若输出序列的而第一个元素是100，说明100前面的所有元素均已经入栈，栈中元素输出时按照99，98，97，…，1的顺序输出，所以输出的第30个元素是71。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查无向图的邻接表。
【解析】在邻接表中，图中的每个顶点建立了一个单链表，表头结点数即为图的顶点数。其中，每个单链表中的表结点表示依附于对应顶点的边，而在无向图中一条边连接两个顶点，即一条边存储了两次，所以表结点个数为2e。故本题选D。

3、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历。
【解析】非空二叉树的选序遍历序列和后序遍历序列正好相反，说明“根左右”和“左右根”顺序相反，因此树中只有根结点，或者根结点只有左子树或右子树，以此类推，其子树具有同样的性质，任意一个结点只有一个孩子，才能满足先序遍历序列和后序遍历序列正好相反。这样的二叉树应该是一个长链，满足条件高度等于结点数。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查满二叉树的性质。
【解析】在一棵高度为k的满二叉树中，第一层有1个结点，第二层有2个结点，第三层有4个结点，…，第k层有2^k-1个结点。利用等比数列公式求每层结点数之和，得1+2+4+…+2^k-1=2^k-1，一棵高度为k的满二叉树的结点总数2^k-1。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查单链表的删除操作。
【解析】在结点A和结点B插入结点x的示意图如下所示，由此易知选项B正确。故本题选B。

6、试题答案：B

试题解析：

【考点】本题考查顺序存储结构的特点。
【解析】选项A中，逻辑结构描述的是数据之间的逻辑关系。选项C中，链式存储结构是存储结构类型中的一种，该结构存储元素时地址可以是连续的，也可以是不连续的。选项D中，顺序存储结构也是存储结构类型中的一种，该结构把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，所以其物理地址和逻辑地址相同并且是连续的。故本题选B。

7、试题答案：D

试题解析：

【考点】本题考查折半查找的适用情况。
【解析】折半查找只适用于有序的顺序表。分块查找不适用于对单链表进行查找。哈希查找适用于散列存储的表。所以选项A、B、C错误。而顺序查找方法既适用于顺序表的查找，也适用于单链表的查找。故本题选D。

8、试题答案：A

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】本程序段主要耗时在于三层for循环，该三层for循环共执行m*n*t次，所以程序段的时间复杂度为O(m*n*t)。故本题选A。