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

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

1、将长度分别为n（n>0）和n2+n 的两条升序单链表合并成长度为n2+2n 的降序单链表，则最坏时间复杂度是（ ）。

A、O(n)

B、O(n²)

C、O(n²+n)

D、O(n³)

2、字母a，b，c，d，e，f，g依次入栈（stack），最后全部出栈。出栈和入栈可以交替进行，但连续出栈的操作次数不得超过上次连续入栈的次数，除最后的出栈操作外。比如：入栈、出栈、入栈、入栈、入栈、出栈、出栈、入栈…的顺序满足条件，但入栈、入栈、出栈、入栈、入栈、出栈、出栈、出栈…有误。下面的出栈顺序哪些有误（ ）。I.a，c，f，e，g，d，bII.b，e，d，f，g，c，aIII.c，b，d，a，f，e，gIV.a，b，d，c，f，g，eV.d，c，e，b，g，f，a

A、I，II和V

B、仅III

C、II和IV

D、III和V

3、顺序队列最多可记录n个元素。如果只通过比较front和rear指针的位置来判断元素的数量以及队列是否为空，则顺序队列的数组长度至少是（ ）。

A、n+1

B、2n

C、n

D、nlogn

4、初始为空的二叉检索树BST里依次插入值为17，8，12，29，11，13，6，19的结点。删除值为8的结点后得到的 BST，其前序遍历结点的值序列是（ ）。I.17，6，12，11，13，29，19II.17，13，6，12，11，29，19III.17，11，6，12，13，29，19IV.17，12，6，11，13，29，19

A、仅I

B、II或III

C、I或III

D、I，II或IV

5、Huffman 编码树中所有节点（含叶节点）的权重分别为：0.05，0.15，0.18，0.2，0.26，0.36，0.38，0.62，1.0。则该Huffman 编码的平均编码长度是（ ）。

A、3.2

B、2.8

C、3.4

D、3.6

6、对如下无向图进行广度优先遍历，结点序列错误的是（ ）。

A、a，b，d，c，f，e

B、b，a，c，f，d，e

C、d，a，e，c，f，b

D、d，a，b，e，c，f

7、使用Dijkstra算法计算如下有向带权图中从源结点b到达各结点的最短路径，则求得最短路径的结点（b除外）依次是（ ）。

A、c，a，d，e，f

B、c，a，e，f，d

C、c，e，a，d，f

D、a，c，e，f，d

8、最大堆中最大的元素在第1层（设根为第1层），则第二大和第三大的元素所在的位置是（ ）。

A、都在第2层

B、第二大元素在第2层、第三大在第3层

C、第二大元素在第2层、第三大在第2或第3层

D、都不确定

9、对已排好序的序列进行排序，最坏时间复杂度为O(n)的排序算法有（ ）。I.选择排序II.快速排序III.插入排序IV.堆排序V.合并排序I.选择排序

A、仅IV

B、II和III

C、I和V

D、仅III

1、试题答案：B

试题解析：

使用头插法将两个链表合并，最坏情况下，两条升序单链表中的元素大小交错存在，此时遍历长度为合并后的降序单链表的长度，时间复杂度为O(n²)。故本题选B。

2、试题答案：D

试题解析：

第一个操作中栈的运行过程是入栈、出栈、入栈、入栈、出栈、入栈、入栈、入栈、出栈、出栈、入栈、出栈、出栈、出栈，符合要求；第二个操作中栈的运行过程是入栈、入栈、出栈、入栈、入栈、入栈、出栈、出栈、入栈、出栈、入栈、出栈、出栈、出栈，符合要求；第三个操作中栈的运行过程是入栈、入栈、入栈、出栈、出栈、入栈、出栈、出栈、入栈、入栈、出栈、出栈、入栈、出栈，不符合要求；第四个操作中栈的运行过程是入栈、出栈、入栈、出栈、入栈、入栈、出栈、出栈、入栈、入栈、出栈、入栈、出栈、出栈，符合要求；第五个操作中栈的运行过程是入栈、入栈、入栈、入栈、出栈、出栈、入栈、出栈、出栈、入栈、入栈、出栈、出栈、出栈，不符合要求。故本题选D。

3、试题答案：A

试题解析：

循环队列通过等式front==rear无法判断队列空间是“空”还是“满”，因此可以选择少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）”作为队列呈“满”状态的标志。故本题选A。

4、试题答案：C

试题解析：

依次插入结点后，二叉排序树如下图所示。

由于8所在结点的左子树和右子树均不空，删除值为8的结点后得到的二叉排序树有两种可能。如下图所示。

故本题选C。

5、试题答案：A

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2（结点数量）=n1+2n2+1（边数量+1）。由于哈夫曼树不存在度为1的结点，因此有5个叶子节点，分别为0.05，0.15，0.18，0.26，0.36。构造的哈夫曼树如下图所示。

因此平均编码长度=0.05×4+0.15×4+0.18×3+0.26×3+0.36×3=3.2。故本题选A。

6、试题答案：D

试题解析：

图的广度优先遍历的算法思想：假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。选项D并没有完全访问完d结点的邻接点，就访问了结点b。故本题选D。

7、试题答案：A

试题解析：

对题中邻接矩阵应用Dijkstra算法求从顶点b到其他各顶点之间的最短路径的过程如下表所示。

故本题选A。

8、试题答案：D

试题解析：

大根堆的含义是完全二叉树中所有非终端结点的值均不小于其左、右子树。因此第二大和第三大的元素所在的位置均不确定。故本题选D。

9、试题答案：D

试题解析：

根据不同排序的算法思想可知，只有插入排序在已排好序的序列进行排序时，仅需要遍历序列，每次均将元素插入到新序列的末尾，时间复杂度为O(n)，其他排序算法的时间复杂度均大于O(n)。故本题选D。