2018年计算机专业综合考研真题答案及解析

本文提供2018年计算机专业综合考研真题答案及解析，以下为具体内容

1、什么是算法（ ）

A、 程序

B、 问题求解步骤的描述

C、 满足五个基本特性

D、 A和C

2、非空的单循环链表的头指针为head，尾指针为rear，则下列条件成立的是（ ）。

A、 rear- >next==head

B、 rear- >next->next==head

C、 rear->next==rear

D、 rear- >next->next==rear

3、对稀疏矩阵进行压缩存储的目的（ ）。

A、 便于进行矩阵的运算

B、 便于输入输出

C、 节省空间

D、 降低运算的时间复杂度

4、初始序列{25, 84, 21, 47, 15, 27, 68, 35, 20}，经过三次排序后，元素变化情况如下：20、15、21、25、47、27、68、35、8415、20、21、25、35、27、47、68、8415、20、21、25、27、35、47、68、84则采用的排序方法是（ ）。

A、 直接选择排序

B、 堆排序

C、 快速排序

D、 希尔排序

5、已知一个序列{13，18，24，35，47，50，62，83，90，114，115}，当二分查找值为90的元素时比较次数为（ ）

A、 1

B、 2

C、 3

D、 4

6、某栈的输入序列为a，b，c，d，e，则不可能是它的输出序列的为（ ）。

A、 dceab

B、 edcba

C、 decba

D、 abced

7、一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给作业的物理块数分别为3和4时，使用先进先出置换算法计算页面淘汰的缺页率分别为多少（ ）

A、 75%和83.3%

B、 75%和75%

C、 83.3%和83.3%

D、 83.3%和75%

8、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

A、存储结构

B、逻辑结构

C、算法

D、操作

9、若文件采用二级索引结构，每个物理块大小为1K，每个盘块指针占4个字节，则保存一个文件最多需要占用文件存储空间（ ）块。

A、 256

B、 257

C、 65536

D、 65793

1、试题答案：B

试题解析：

【考点】本题考查算法的定义
【解析】A. 程序不一定满足有穷性，如循环、操作系统等，而算法必须有穷。算法代表对问题求解步骤的描述，而程序则是算法在计算机上的特定实现。C. 它只是算法的必要条件，不能成为算法的定义。故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查非空单循环链表的指针
【解析】非空单循环链表如下可知，rear所指结点的next域指针指向头结点，故本题选A。

3、试题答案：C

试题解析：

【考点】本题考查稀疏矩阵压缩存储的目的
【解析】对矩阵进行压缩不能简化矩阵运算，对输入输出也不能提供便利，而降低运算的时间复杂度主要与算法有关，一般对矩阵压缩后其运算的复杂度会增加。故A、B、C错误。对稀疏矩阵进行压缩存储目的是节省存储空间。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查排序算法的比较
方法一：排序变化如下：
25，84，21，47，15，27，68，35，20；//初始序列
20，15，21， 25 ，47，27，68，35，84；//序列1
15， 20 ，21，25，35，27， 47 ，68，84；//序列2
15，20，21，25，27，35，47，68，84；//序列3
观察上述序列可知，初始序列变为序列1 是以25（序列的第一个元素）为基准值将初始序列分为大于25和小于25的两个部分。然后再分别对两个部分进行同样的操作，这样的排序也就是快速排序。故本题选C。
方法二：利用排除法。A. 直接选择排序主要是每一趟从待排序记录序列中选取一个关键字最小的记录，依次放在已排序记录序列的最后，直至全部记录排完为止。“20、15、21、25、47、27、68、35、84”序列中第一个关键字20不是最小记录，故A排除。B. 初始序列不满足堆的条件，故排除。D. 希尔排序是插入排序的升级版，本质是将数列按步长进行插入排序，这里没有步长，也没有插入，故排除D。通过排除法，本题选C。

5、试题答案：B

试题解析：

【考点】本题考查二分查找法
【解析】根据二分法查找法需要两次：(1)首先将90与表中间的元素50进行比较，由于90大于50，所以在线性表的后半部分查找。(2)第二次比较的元素是后半部分的中间元素，即90，这时两者相等，即查找成功。故本题选B

6、试题答案：A

试题解析：

【考点】本题考查栈的特点
【解析】栈的特点是后进先出。A. a比b先入栈，所以a不可能比b先出栈，即输出序列不可能为“ab”,故本题选A。B. abcde先入栈，然后依次出栈，正好是edcba。C. abcd先依次入栈，然后d出栈，e再入栈，e出栈，则可输出序列decba。D. abc依次入栈、出栈输出，d再入栈，接着e入栈、出栈，最后d出栈，则可输出序列abced。

7、试题答案：A

试题解析：

【考点】本题考查先进先出置换算法
【解析】使用先进先出算法时，当物理块为3时，缺页9次，缺页率为9/12= 75%；当物理块为4时，缺页10次，缺页率为10/12=83.3%。故本题选A。

8、试题答案：B

试题解析：

【考点】本题考查对逻辑结构的认识
【解析】逻辑结构指的就是数据之间的逻辑关系，它是理论上的东西，是虚拟的，所以它与数据元素本身的形式、内容、相对位置、个数无关。故本题选B。

9、试题答案：C

试题解析：

【考点】本题考查文件存储
【解析】因为是二级索引，所以假如第一级的索引有N个指向第二级索引的指针，而二级索引有N个指向第X块的指针，则最大的文件 = N * N * 1KB。 我们来看这个N为多少，因为每一块的地址占4 B，第一级索引是1KB，可以存下1K / 4 = 256个 指向二级索引的指针。同样的道理，二级所有也是最多有256个指向块的指针，那么256 * 256 * 1KB = 65536。故本题选C。