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