当前位置：问答库＞考研试题

一、选择题

1． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程中元素之间进行的比较次数是（ ）。

A.1 B.2 C.4 D.5

【答案】B

【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆， （2）为插入18后， （3）比较10与18, 交换后，

（4）比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。

2． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D

【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归度一致。例如：待排序列{48，62，35，77，55，14，35，98）

调用过程的二叉树如下图所示。

在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

3． 数据链路层采用选择重传协议（SR ）传输数据，发送方已发送了0H3号数据倾，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（ ）。

A.1 B.2 C.3 D.4

【答案】B

【解析】在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认，要特别注意其与GBN 协议的区别。本题收到1号帧的确认，说明1号帧正确接收，0和2号帧依次超时，因此必须重传，然而3号帧尚未超时，是否正确接收未知，故不用重传，因此必须重传0和2号帧，答案是B 。

4． 计算机硬件能直接执行的只有（ ）。

A. 符号语言 B. 机器语言

C. 机器语言和汇编语言 D. 汇编语言 【答案】B

5． 已知循环队列存储在一维数组rear 的值分别是（ ）。

A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1

中，且队列非空时front 和rear 分别指向队头元素和

队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执

行

n ，则初始时front 的值为0、rear 的值为n-1。

6． 下列选项中，描述浮点数操作速度指标的是（ ）。

A.MIPS B.CPI C.IPC

D.MFLOPS 【答案】D

【解析】

表示每秒执行多少百万次浮点运算，

MIPS 表示每秒执行多少百万条指令。对于一个给定的程序，

定义为

这里所说的指令一般是指加、减运算这类短指令。

就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，造

成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。

每个时钟周期执行的指令数。

7． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

A. B. C. D. 【答案】A

【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是 ，则有语句设其执行时间为T （n ）

8． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）。

I. 父子关系 II. 兄弟关系

III.u 的父结点与v 的父结点是兄弟关系

用来描述计算机的浮点运算速度，适用于衡量处理机的性能。