2021年计算机学科专业基础综合考研真题答案及解析

本文提供2021年计算机学科专业基础综合考研真题答案及解析，以下为具体内容

1、n个结点的线索二叉树上含有的线索数为（ ）。

A、2n

B、n-1

C、n+1

D、n

2、头指针为head的非空循环单链表的尾结点p满足（ ）。

A、

B、

C、p=NULL

D、p=head

3、表达式a*(b+c)-d的后缀表达式是（ ）。

A、abcd*+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

4、若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。

A、3，2，1

B、2，1，3

C、3，1，2

D、1，3，2

5、假设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后front指针的值为（ ）。

A、front=front-1

B、front=front+1

C、front=(front-1)%m

D、front=(front+1)%m

6、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A按以行序为主序存储，元素A[8,5]的起始地址与当A按以列序为主序存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、A[8,5]

B、A[3,10]

C、A[5,8]

D、A[0,9]

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

A、4

B、5

C、6

D、7

8、如果含n个顶点的图只形成一个环，则它共有（ ）棵生成树。

A、n

B、n-1

C、1

D、2

9、关键路径是指AOE（Activity On Edge）网中（ ）。

A、最长的回路

B、最短的回路

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

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

10、已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）

A、插入排序

B、冒泡排序

C、快速排序

D、归并排序

1、试题答案：C

试题解析：

n个结点的二叉树共有n-1条边，每个结点都有两个指针域，共有2*n个指针域，其中n-1条边则有n-1个非空指针域，因此空指针域有n+1个，每个空指针域对应一个线索，则线索数为n+1，故本题选C。

2、试题答案：A

试题解析：

本题是一个非空的单循环链表，因此p指向尾结点，对于A和B，p的next指向头结点，因此A正确而B错误。对于C，由于链表非空，因此p不等于NULL，因此C错误。对于D，p是尾指针，head是头指针，只有链表为空或者该链表不带头结点且只含一个结点时二者才相等，因此D错误。故本题选A。

3、试题答案：B

试题解析：

使用加括号的方法解决本题，步骤如下：
① 按照运算的先后顺序为表达式加上括号：((a*(b+c))-d)；
② 将括号内的运算符移动到对应的括号的外面：((a(bc)+)*d)-；
③ 将括号去掉后的后缀表达式：abc+*d-。故本题选B。

4、试题答案：C

试题解析：

对于C，栈是限定只能在表的一端进行插入和删除操作的线性表。在表中允许插入和删除的一端称为“栈顶”，不允许插入和删除的一端称为“栈底”。栈的操作具有“后进先出”的特性。因此当第一个出栈元素为3时，对应的出栈的序列仅有3，2，1。对于A，可以经过这样的栈操作得到该输出序列：push(3)、push(2)、push(1)、pop(3)、pop(2)、pop(1)；对于B，可以经过这样的栈操作得到该输出序列：push(1)、push(2)、pop(2)、pop(1)、push(3)、pop(3)；对于D，可以经过这样的栈操作得到该输出序列：push(1)、pop(1)、push(2)、push(3)、pop(3)、pop(2)。故本题选C。

5、试题答案：D

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。入队操作队尾指针应该更新为：rear=e;rear=(rear+1)%maxsize;。出队操作队首指针应该更新为：e=front; front=(front+1)%maxsize;。故本题选D。

6、试题答案：B

试题解析：

按行优先存储时，LOC(A[8,5])=LOC(A[0][0])+(8*10+4)*6=LOC(A[0][0])+84*6。
对于A，按列优先存储时，LOC(A[8,5])=LOC(A[0][0])+(4*9+8)*6=LOC(A[0][0])+44*6；
对于B，按列优先存储时，LOC(A[3,10])=LOC(A[0][0])+(9*9+3)*6=LOC(A[0][0])+84*6；
对于C，按列优先存储时，LOC(A[5,8])=LOC(A[0][0])+(7*9+5)*6= LOC(A[0][0])+68*6；
对于D，按列优先存储时，LOC(A[0,9])=LOC(A[0][0])+(8*9)*6=LOC(A[0][0])+72*6。故本题选B。

7、试题答案：C

试题解析：

8、试题答案：A

试题解析：

若含n个顶点的图只形成一个环，则该图有n条边，图的生成树中含有n条边中的任意n-1条边，因此共有n棵生成树，故本题选A。

9、试题答案：C

试题解析：

AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间，完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。故本题选C。

10、试题答案：B

试题解析：

对于A，插入排序的前两趟为：（35，51，93，24，13，68，56，42，77）；（51，35，93，24，13，68，56，42，77）。因此A错误。对于B，符合冒泡排序的前两趟，因此B正确。对于C，快速排序的每一趟都有一个基准，比基准小的在基准值的左边，比基准大的在基准右边。第一趟排序的基准为51，而题干所示的第一趟排序显然不符合快速排序的规律，因此C错误。对于D，第一趟归并排序是每两个数为一组的排序，因此第一趟排序为{35，51}，{24，93}，{13，68}，{42，56}，77，因此D错误。故本题选B。