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

一、填空题

1． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；；O(1)；满足堆的性质

2． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何

置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素

成_____，若

【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边

3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

4． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

5． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则

＝i(i﹣l)/2＋j 。若i ＜j 。则

的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

二、单项选择题

6． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。

A.X 的双亲

B.X 的右子树中最左的结点

C.X 的左子树中最右的结点

D.X 的左子树中最右的叶结点

【答案】C

【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。

7． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）

A.O(2n)

B.O(n)

C.O(n2)

D.O(log2n )

【答案】C

2【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。

8． 下列关于UDP 协议的叙述中, 正确的是（ ）

Ⅰ提供无连接服务

Ⅱ提供复用/分用服务

Ⅲ通过差错校验, 保障可靠数据传输

A. 仅Ⅰ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】B

UDP 无连接创建, 提供多路复用服务。【解析】虽然有差错检验, 但是不能保证可靠数据传输,

所以Ⅲ错误。

9． 主机甲与主机乙之间已建立一个TCP 连接, 主机甲向主机乙发送了3个连续的TCP 段, 分别包含300字节、400字节和500字节的有效载荷, 第3个段的序号为900。若主机乙仅正确接收到第1和第3个段, 则主机乙发送给主机甲的确认序号是（ ）。

A.300

B.500

C.1200

D.1400

【答案】B

【解析】本题考查TCP 的确认机制, TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的序号为200, 这里主机乙仅正确接收了第1段和第3段, 这意味着第2段丢失, 需要超时重传, 因此主机乙发送给主机甲的确认序号, 也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号, 也就是500, 因此答案是B 。

10． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是（ ）

A.X 的父结点

B. 以Y 为根的子树的最左下结点

C.X 的左兄弟结点Y

D. 以Y 为根的子树的最右下结点

【答案】A

【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。

11．某CPU 主频为, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） A.

B.

C.

D.

【答案】C

【解析】采用4级流水线执行100条指令, 在执行过程中共用

CPU 的主频是, 也就是说每秒钟有

条指令/秒,

故答案为C 。

12．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。

A. 每次分区后，先处理较短的部分

B. 每次分区后，先处理较长的部分

C. 与算法每次分区后的处理顺序无关

D. 以上三者都不对

【答案】A

【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函

条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。 个时钟周期。流水线的吞吐率为