2016年操作系统考研真题答案及解析

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

1、下列程序段的时间复杂度是（ ）。sum=0;for(i=0;i<n;i*=2)     for(j=0;j<n;j++)         sum++;

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n²)

2、若某链表最常用的操作是在末尾插入结点和删除尾结点，则该链表最节省时间的存储方式是（ ）。

A、单链表

B、单循环链表

C、带尾指针的单循环链表

D、带头结点的双循环链表

3、元素数a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可以停留、可出栈，直到所有元素出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（ ）。

A、3

B、4

C、5

D、6

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

A、41

B、82

C、113

D、122

5、已知某二叉树的前序遍历序列为 ABCDEFGH，中序遍历序列为CBEDFAGH，则后序遍历序列为（ ）。

A、HGFEDACB

B、GHEDFCBA

C、CEFDBHGA

D、HGAFDEBC

6、某有向图G是具有10个顶点的强连通图，则G含有边的数目至少是（ ）。

A、45

B、90

C、10

D、9

7、

A、2

B、3

C、4

D、5

8、某无向图G有n个顶点，则G的邻接表中的边结点最多有（ ）。

A、n²

B、n(n-1)

C、n(n+1)

D、n(n-1)/2

9、折半查找有序表（2，5，7，10，14，15，18，23，35，41，52）查找关键字14需做的比较次数为（ ）。

A、2

B、3

C、4

D、5

10、下列选项中，不可能是快速排序第2趟排序结果的是（ ）。

A、2，3，5，4，6，7，9

B、2，7，5，6，4，3，9

C、3，2，5，4，7，6，9

D、4，2，3，5，7，6，9