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

一、填空题

1． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

2． 对n 个记录的表

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。

3． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

4． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【答案】

表

平均查找次数为。

5． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】

6． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

【解析】折半查找时每个的次数如表所示: 进行简单选择排序，所需进行的关键字间的比较次数为_____。

二、单项选择题

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

A.MIPS

B.CPI

C.IPC

D.MFLOPS

【答案】D

【解析】MFLOPS(Million Floating-point Operations per Second)表示每秒执行多少百万次浮点运算, 用来描述计算机的浮点运算速度, 适用于衡量处理机的性能。

MIPS(Million Instructions per Second) 表示每秒执行多少百万条指令。对于一个给定的程序, MIPS 定义为

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

CPI(Cycles per Instruction) 就是每条指令执行所用的时钟周期数。由于不同指令的功能不同, 造成指令执行时间不同, 也即指令执行所用的时钟数不同, 所以CPI 是一个平均值。

IPC(Instructions per Cycle)每个时钟周期执行的指令数。

8． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT(往返时间) 时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。

A.7KB

B.8KB

C.9KB

D.16KB

【答案】C

【解析】回顾TCP 流量控制和拥塞控制(慢启动) 的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2＝8, 故三次成功后为8，以后为线性增长，故为8＋1＝9, 答案为C 。

9． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. A.

B. C. D.

【答案】B

【解析】平衡二叉树是指左右子树高度差(平衡因子) 的绝对值不超过1的二叉树.A 项中根结

B 项中每个结点的平衡因子的绝对值均不超过1；C 项中根结点的平衡因子是；点的平衡因子是2；

D 项中根结点的平衡因子是3.

10．—组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A.(38，40，46，56，79，84)

B.(40，38，46，79，56，84)

C.(40，38，46，56，79，84)

D.(40，38，46，84，56，79)

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:46比84小，不交换；

第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;

第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;

第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;

第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;

一次划分结束。