2021年操作系统考研真题答案及解析（三）

本文提供2021年操作系统考研真题答案及解析，以下为具体内容

1、创建—个包含n个结点的有序单链表的时间复杂度为（ ）。

A、O(1)

B、O(n)

C、O(n²)

D、O(nlog₂n)

2、在双向链表存储结构中，在p指针所指向的结点后插入q指针所指向的新结点，其修改指针的操作为（ ）。

A、p->next = q； q->prior = p； p->next->prior = q；q->next = q；

B、p->next = q； p=>next->prior = q； q->prior = p；q->next = p->next；

C、q->prior = p； q->next = p->next； p->next = q；p->next->prior = q；

D、q->prior = p； q->next = p->next； p->next->prior = q；p->next = q；

3、已知一算术表达式的中缀形式为A + B/C-D*E，其后缀形式为（ ）。

A、 ABC/ + DE* -

B、 ABC + /DP-

C、 ABC/ + DE-*

D、 ABC + /DE-*

4、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为 2的结点，10个度为1的结点，则树T的叶子结点个数是（ ）。

A、41

B、82

C、113

D、122

5、线性表L在（ ）情况下适用于使用链式结构实现。

A、需经常修改L中的结点值

B、需不断对L进行删除、插入

C、L中含有大量的结点

D、L中结点结构复杂

1、试题答案：C

试题解析：

【考点】本题考查单链表创建的时间复杂度。
【解析】创建—个包含n个结点的有序单链表可以看作是对n个数进行直接插入排序，时间复杂度为O(n²)。故本题选C。

2、试题答案：D

试题解析：

【考点】本题考查双向链表的删除操作。
【解析】在双向链表存储结构中，在p指针所指向的结点后插入q指针所指向新结点的示意图如下所示，其中① q->prior = p，② q->next = p->next，③ p->next->prior = q，④ p->next = q。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查中缀表达式转后缀表达式。由此知，本题选A。
【解析】中缀形式为A + B/C-D*E转后缀表达式的过程如下所示：
（1）先按照运算符的优先级对中缀表达式加括号，变成（（A +（B/C））-（D*E））。
（2）将运算符移到括号的后面，变成（（A（BC）/）+（DE）*）-。
（3）去掉括号，得到ABC/ + DE* -。

4、试题答案：B

试题解析：

【考点】本题考查求树中对应度数的结点个数。
【解析】在树中，结点总数=总度数+1。本题给的是一颗度为4的树，则有n0+n1+n2+n3+n4=n1+2*n2+3*n3+4*n4+1，由已知n4=20，n3=10，n2=1，n1=10，解得n0=82，即树T的叶子结点个数是82。故本题选B。

5、试题答案：B

试题解析：

【考点】本题考查链表的优点。
【解析】链表中，所有结点通过指针相连，删除或插入元素时只需要修改指针指向即可，所以线性表在需要不断对表中的元素进行插入、删除的情况下适用于链式结构。故本题选B。