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

1、试题答案：C

试题解析：

外层for循环的执行次数为logn，内层for循环的执行次数为n，因此题中程序段的时间复杂度为O(nlogn)。故本题选C。

2、试题答案：D

试题解析：

选项A的单链表和选项B的单循环链表在末尾插入结点和删除尾结点时均需要遍历链表，时间复杂度为O(n)。选项C的带尾指针的单循环链表在末尾插入结点的时间复杂度为O(1)，删除尾结点时需要获取尾结点的前驱结点，时间复杂度为O(n)。选项D的带头结点的双循环链表在末尾插入结点和删除尾结点的时间复杂度为O(1)。故本题选D。

3、试题答案：B

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表。当元素d开头输出时，此时栈顶元素往下分别为c，b，a。目前还有一个元素e未进栈，因此e可以在输出c之前进栈、c已输出b还未输出时进栈、c和b已输出a还未输出时进栈、栈中元素全部输出后进栈。因此出栈序列有decba，dceba，dcbea和dcbae。故本题选B。

4、试题答案：B

试题解析：

5、试题答案：C

试题解析：

根据中序和后序遍历的结果确定二叉树的过程如下图所示。此后根据先序遍历的算法思想可获得先序遍历序列。

故本题选C。

6、试题答案：C

试题解析：

在有向图G中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。当G是一个环时，此时G是强连通图且含有边的数目最少为n。故本题选C。

7、试题答案：D

试题解析：

图的深度优先遍历的算法思想是：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。因此得到的遍历序列有：

故本题选D。

8、试题答案：B

试题解析：

含有n个顶点的无向图中的每个顶点均可与剩下n-1个顶点相连，因此最多有n(n-1)/2条边。在无向图的邻接表中，每个边均要被存储两次，因此最多有n(n-1)个边结点。故本题选B。

9、试题答案：C

试题解析：

折半查找的具体过程如下表所示。故本题选C。

10、试题答案：C

试题解析：

快速排序的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。整个快速排序结束后的排序结果是2，3，4，5，6，7，9。2趟快速排序后，需至少有两个以上元素位于最终所在的位置上，选项C中有且仅有一个元素9位于最终所在的位置上。故本题选C。