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

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

1、从表中任一结点出发都能扫描整个表的是（ ）。

A、静态链表

B、单链表

C、顺序表

D、循环链表

2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A、顺序表

B、双链表

C、带头结点的双循环链表

D、单循环链表

3、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。

A、6

B、4

C、3

D、2

4、中缀表达式A-(B+C/D)*E的后缀形式是（ ）。

A、AB-C+D/E*

B、ABC+D/-E*

C、ABCD/E*+-

D、ABCD/+B*-

5、若用单链表来表示队列，则应该选用（ ）。

A、带尾指针的非循环链表

B、带尾指针的循环链表

C、带头指针的非循环链表

D、带头指针的循环链表

6、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉树中共有（ ）个结点。

A、2n

B、n+1

C、2n-1

D、2n+1

7、将有关二叉树的概念推广到完全二叉树，则一棵有244个结点的完全二叉树的高度是（ ）。

A、5

B、6

C、7

D、8

8、连通分量是（ ）极大连通子图。

A、无向图

B、有向图

C、树

D、图

9、无向图的邻接矩阵是一个（ ）。

A、对称矩阵

B、零矩阵

C、上三角矩阵

D、对角矩阵

1、试题答案：D

试题解析：

本题考查循环链表的特点。
对循环链表来说，其最后一个结点有指向头结点的指针，所以从表中任一结点出发都能通过前后操作而扫描整个循环链表。故本题选D。

2、试题答案：A

试题解析：

本题考查顺序表与链表的特点。
对于顺序表，直接通过下标就可以存取任一指定序号的元素和在最后进行插入和删除运算，时间复杂度为O(1)。而对于链表，需要从表头遍历整个链表来找到指定序号的元素以及最后一个元素的位置，相较于顺序表花费时间更长。故本题选A。

3、试题答案：C

试题解析：

本题考查栈的出栈入栈操作。
首先e1、e2依次入栈，此时栈中有2个元素，随即e2出栈后依次执行入队、出队操作。接着e3、e4依次入栈，此时栈中有3个元素，随即e4、e3出栈后依次执行入队、出队操作。然后e5、e6依次入栈，此时栈中有3个元素，随即e6、e5、e1出栈后依次执行入队、出队操作。最终元素出队顺序是是e2、e4、e3、e6、e5、e1。分析整个过程可知，栈中同时最多会存放3个与元素，所以栈S的容量至少应该是3。故本题选C。

4、试题答案：D

试题解析：

本题考查中缀表达式转后缀表达式。
① 从左至右依次扫描整个中缀表达式，遇到“A”直接输出加入后缀表达式。② 遇到“-”则入栈。③ 遇到“（”入栈，遇到“B”直接加入后缀表达式。④ 遇到“+”，此时栈顶的元素为“（”，所以将“+”入栈。⑤ 遇到“C”直接加入后缀表达式，遇到“/”，此时栈顶元素为“+”，其优先级不大于“/”，所以将“/”入栈。⑥ 遇到“D”直接加入后缀表达式，遇到“）”，则将栈中元素“/”、“+”依次出栈加入后缀表达式，直至出栈元素为“（”时停止元素出栈操作。遇到“*”，此时栈顶元素为“-”，其优先级不大于“*”，所以将“*”入栈。⑦ 遇到“E”直接加入后缀表达式。⑧ 此时整个中缀表达式已经完全扫描一遍，随即将栈中所有元素“*”、“-”依次出栈并加入后缀表达式，最终得到中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+B*-。故本题选D。

5、试题答案：B

试题解析：

本题考查链队的实现。
构造队列需要满足方便在队头出队、队尾入队的操作，而带尾指针的循环链表方便找到尾结点进行入队操作。同时，循环队列的尾结点的next指针域指向头结点，所以很方便找到头结点进行出队操作。故本题选B。

6、试题答案：C

试题解析：

本题考查二叉树的性质。
在二叉树中，n0=n2+1。题干给出n0=n，可知n2=n-1。又因为该二叉树只有度为0和度为2的结点，所以这棵二叉树的总结点个数为n0+n2=n+(n-1)=2n-1。故本题选C。

7、试题答案：D

试题解析：

本题考查完全二叉树的性质。
一颗高度为h的满二叉树，其结点总数为2h-1。本题假设完全二叉树的高度为h，则由2h-1-1<=244<=2h-1，由此解得h=8。故本题选D。

8、试题答案：A

试题解析：

本题考查连通分量的定义。
无向图G的极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。故本题选A。

9、试题答案：A

试题解析：

本题考查无向图邻接矩阵的特点。
无向图中，若存在顶点a到顶点b的边，必定存在顶点b到顶点a的边，所以无向图的邻接矩阵一定是个对称举证。故本题选A。