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)