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

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

1、以下哪一个术语与数据的存储结构无关？（ ） 

A、栈

B、哈希表

C、线索树

D、双向链表

2、设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]可存放于B中（ ）

A、(i+3)*i/2

B、(i+1)*i/2

C、(2n-i+1)*i/2

D、(2n-i-1)*i/2

3、已知广义表LS=((a,b,c), (d,e,f))，运用head和tail函数取出LS中原子e的运算是（ ）

A、head(tail(head(tail(LS))

B、head(tail(LS))

C、head(tail(tail(head(LS))))

D、tail(head(LS))

4、若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指针rear指向队尾元素后的空单元，则当前队列中的元素个数为（ ）。

A、 (rear-front+m) % m

B、 rear-front + 1

C、 rear-front

D、 rear-front

5、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为（ ）。 

A、7

B、8

C、9

D、1

6、假设栈初始为空，将中缀表达式a/b-(c*d+e*f)/g转化为等价后缀表达式过程中，当扫描到f时，栈中的元素依次为（ ）。

A、 /-+*

B、 -(+*

C、 -(*+

D、 /-(*+*

7、某二叉树的先序和后序序列正好相反，则该二叉树一定是（ ）。 

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

8、既希望较快的查找又便于线性表动态变化的查找方法是（ ）。

A、顺序查找

B、折半查找

C、索引顺序查找

D、哈希法查找

9、已知一个线性表(38, 25, 74, 63, 52, 48), 假定采用散列函数h(key)=key%7计算散列地址，并将散列存储在散列表A[0,.....,6]中，若采用链地址法，求1号地址元素的个数( )。

A、0

B、1

C、2

D、3

10、 对序列{15,9,7,8,20,-1,4}进行排序，进行一趟后数据的排列变为{4,9,-1,8,20,7,15}，则采用的是( )排序。 

A、选择

B、 快速

C、 希尔

D、 起泡

1、试题答案：A

试题解析：

【考点】本题考查数据的存储结构
【解析】数据的存储结构指数据的逻辑结构在计算机中的表示（又称映像），主要包括数据元素本身的存储以及数据元素之间的关系表示。常见的存储结构有顺序存储、链式存储、索引存储、散列存储（又称哈希存储）等。哈希表属于散列存储，与数据结构有关。线索树属于链式结构，与存储结构有关。双向链表属于链式结构，与存储结构有关。栈是一种逻辑结构，它可以用顺序存储（顺序栈）也可以用链式存储（链栈）。故本题选择A。

2、试题答案：A

试题解析：

【考点】本题考查对称矩阵按行优先的压缩存储
【解析】对于压缩矩阵这类题，我们要明确的是要知道这个元素是第几个元素，而对应数组下标等于第几个元素-1。在对称矩阵的下三角部分中，若是按行优先存储，第一行有1个元素，第二行有2个元素，第i行有i个元素，所以位于第i行第j列的元素是第1+2+3+…+i-1+j=(i-1)*i/2+j个元素（前i-1共(i-1)*i/2个元素，第i行有j个元素）。这类题型需要特别注意矩阵的下标从0开始和从1开始的区别。本题给出的矩阵下标是从0开始的，所以A[i][i]在矩阵中位于第i+1行第i+1列，它是第1+2+3+…+i+1+(i+1)= .(i+3)*i/2+1个元素。由于数组下标是从0开始的，所以存放于数组B应该减1。故本题选A。

3、试题答案：A

试题解析：

【考点】本题考查广义表中关于tail和head的计算
【解析】实现步骤如下：tail(LS) = ((d,e,f))；head(tail(LS)) = (d,e,f)；tail(head(tail(LS))) = (e,f)；head(tail(head(tail(LS)))) = e。故本题选A。

4、试题答案：A

试题解析：

【考点】本题考查循环队列中元素的个数
【解析】计算队列的元素个数：(尾－头＋表长)%表长。
因为循环对列中，rear不一定比front大。如果rear<front，结果是rear-front+MaxSize；如果rear<front，结果是rear-front，为了用一个表达式同时表达两者，用(rear-front+MaxSize)%MaxSize。该公式为常见考点，记住即可。

5、试题答案：C

试题解析：

【考点】本题考查后缀表达式求值
【解析】后缀表达式求值过程中不需要考虑运算符的优先级，只需要对该表达式中的每一个元素进行判断。若为操作数则将其入栈，若为运算符则出栈前面的两个操作数并运算，然后将运算结果入栈，最终栈中的最后一个元素(栈顶元素)即为该表达式的运算结果。① 首先a、b、c依次入栈，碰到“-”时，b、c出栈，执行（b-c）操作后将运算结果压入栈中。② 碰到“/”时，a、出栈，执行（a/（b-c））操作后将运算结果压入栈中。碰到d、e时，直接将其入栈。③ 碰到“*”时d、e出栈，执行（d*e）操作后将运算结果压入栈中。④ 碰到“+”，（a/（b-c））、（d*e）出栈，执行（a/（b-c））+（d*e）结果为9。此时，可得到后缀表达式abc-/de*+的值为9，故本题选C。

6、试题答案：B

试题解析：

【考点】本题考查中缀表达式转后缀表达式的过程
【解析】① 碰到“a”输出加入后缀表达式。② 碰到”/”入栈。③ 碰到“b”输出加入后缀表达式。④ 碰到“-”，此时栈中有运算符“/”，其优先级大于“-”，故“/”出栈，再将“-”入栈。⑤ 遇到左括号入栈。⑥ 遇到“c”输出加入后缀表达式⑦遇到“*”，此时栈中元素依次是“-（”，直接入栈“*”。⑧ 遇到“d”输出加入后缀表达式。⑨ 遇到“+”，此时栈中元素依次是“-（ *”，由于栈顶元素“*”的优先级大于“+”，故“*”出栈，再将“+”入栈。⑩ 遇到“e”输出加入后缀表达式⑪遇到“*”，此时栈中元素依次是“-（ +”，由于栈顶“+”优先级小于“*”，则“*”直接入栈。⑫ 遇到“f”，此时栈中的元素依次是“-（ + *”。故本题选B。

7、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历
【解析】非空二叉树的先序和后序正好相反，说明“根左右”与“左右根”顺序相反。因此，树只有根结点，或者根结点只有左子树或右子树，以此类推，其子树有同样的性质，所以二叉树的高度一定等于其节点数。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查查找算法的辨析
【解析】A. 顺序查找的时间复杂度为O(n)，相较于索引查找的时间复杂度较大。B. 折半查找（又称二分查找）要求待查列表有序，且插入删除困难，故不适用于动态变化的线性表。其时间复杂度为O(log2(n))。C. 索引顺序查找（又称分块查找）是折半查找和顺序查找的一种改进方法，索引顺序查找由于只要求索引表是有序的，对块内节点没有排序要求（块内无序，块间有序），因此特别适合于节点动态变化的情况。时间复杂度为O(n)～O(log2n)。综合而言，希望较快的查找又便于线性动态变化的查找方法是索引顺序查找。D. 哈希查找在数据较多时可能会遇到哈希碰撞。故本题选C。

9、试题答案：A

试题解析：

【考点】本题考查链地址法
【解析】38%7=3；25%7=4,74%7=4；63%7=0；52%7=3；48%7=6，1号地址元素个数为0，故本题选A。

10、试题答案：C

试题解析：

【考点】本题考查排序算法辨析
【解析】A. 选择排序是每次选择未排序子列中最大（最小）的放到最后，显然4不是最值，所以A不对；B. 快速排序选取任意数据作为基轴，在经历一趟排序后，基轴左边的数均比基轴小，基轴右边的数均比基轴大，显然B不对。D. 冒泡排序是相邻两两比较，把最大的顶上去，显然边上两个元素不是最值，D不对。通过排除法，本题选择C。