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

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

1、对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。在p指针所指向的结点之后插入s指针所指结点的操作应为（ ）。

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

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

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

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

2、由abc，3个结点可以构造出多少种不同的二叉树？（ ）

A、2

B、3

C、4

D、5

3、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。

A、BA+141

B、BA+180

C、BA+222

D、BA+225

4、一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。

A、2 3 1

B、3 2 1

C、3 1 2

D、1 2 3

5、下述编码中哪一个不是前缀码（ ）。

A、（00，01，10，11）

B、（0，1，00，11）

C、（0，10，110，111）

D、（1，01，000，001）

6、当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[1..n]中时，数组中第i个结点的左孩子为（ ）。

A、A[2i]（2i=<n）

B、A[2i+1]（2i+1=<n）

C、A[i/2]

D、无法确定

7、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。

A、O(n)

B、O(e)

C、O(n+e)

D、O(n*e)

8、串的长度是指（ ）。

A、串中所含不同字母的个数

B、串中所含字符的个数

C、串中所含不同字符的个数

D、串中所含非空格字符的个数

9、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

A、rear=rear+1

B、rear=(rear+1)mod(m-1)

C、rear=(rear+1)mod m

D、rear=(rear+1)mod(m+1)

10、关键路径是事件结点网络中（ ）。

A、从源点到汇点的最长路径

B、从源点到汇点的最短路径

C、最长回路

D、最短回路

1、试题答案：D

试题解析：

对于A、B、C选项，p->next=s这一步执行后p指针指向的原有的后继结点会丢失，D选项执行步骤正确，其操作如下图所示：

故本题选D。

2、试题答案：D

试题解析：

画出不同形态的二叉树如下：

故本题选D。

3、试题答案：B

试题解析：

LOC( A[5,8])=BA+[(8-1)*8+(5-1)]*3=BA+180，故本题选B。

4、试题答案：C

试题解析：

栈具有“后进先出”的特性。对于A，经过这样的操作后可得该输出序列：push(1)、push(2)、pop(2)、push(3)、pop(3)、pop(1)；对于B，经过这样的操作后可得该输出序列：push(1)、push(2)、push(3)、pop(3)、pop(2)、pop(1)；对于D，经过这样的操作后可得该输出序列：push(1)、pop(1)、push(2)、pop(2)、push(3)、pop(3)；对于C，若3是第一个出栈元素，则对应的出栈序列只有3、2、1这一种，故本题选C。

5、试题答案：B

试题解析：

在哈夫曼编码每个编码都不会其他编码的前缀，在B选项中0是00的前缀，1是11的前缀，因此B不是前缀码，其余选项均为前缀编码，故本题选B。

6、试题答案：A

试题解析：

当完全二叉树顺序存储在一维结构中时，从上到下从左往右从1开始编号，结点i的左孩子为2*i，右孩子为2*i+1，双亲结点为i/2。若结点从0开始编号，结点R[i]的双亲结点的下标为(i-1)/2；结点R[i]若存在左孩子，其下标为2*i+1；若存在右孩子，其下标为2*i+2。故本题选A。

7、试题答案：C

试题解析：

本题要求删除与某个顶点相关的所有弧，即删除当前结点的出度边和入度边，需要遍历所有顶点和所有边一次，将与Vi相关的所有结点删除，故本题选C。

8、试题答案：B

试题解析：

串是由零个或多个字符组成的有限序列，串中字符的数目称为串的长度。零个字符的串称为空串，故本题选B。

9、试题答案：D

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在循环队列中，入队操作仅改变尾指针，尾指针加1，出栈操作仅改变头指针，头指针加1。而本题中数组的最大空间为m+1，故本题选D。

10、试题答案：A

试题解析：

AOE网是表示活动的网，是一个带权的有向无环图，完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。故本题选A。