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

一、选择题

1． 栈和队的共同点是（ ）。

A. 都是先进后出

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。

2． 下列排序算法中，其中（ ）是稳定的。

A. 堆排序，起泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，起泡排序

【答案】D

3． 图中有关路径的定义正确的是（ ）。

A. 由顶点和相邻顶点构成的边所形成的序列

B. 由不同顶点所形成的序列

C. 由不同边所形成的序列

D. 上述定义都不是

【答案】A

【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列，路径上边的数目称为路径的长度。

4． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗

口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。

A.10KB

B.12KB

C.14KB

D.15KB

【答案】A

【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。

5． 下列二叉排序树中查找效率最高的是（ ）。

A. 平衡二叉树

B. 二叉查找树

C. 没有左子树的二叉排序树

D. 没有右子树的二叉排序树

【答案】A

【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。

6． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。

A. 建立在TCP 之上的控制连接

B. 建立在TCP 之上的数据连接

C. 建立在UDP 之上的控制连接

D. 建立在UDP 之上的数据连接

【答案】A

【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。

7． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。

【答案】B

【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为

8． 下列有关接口的叙述中错误的是：（ ）

A. 状态端口和控制端口可以合用同一寄存器 B. 接口中CPU 可访问寄存器，称为端口

端口 C. 采用独立编址方式时，

【答案】D

端口地址和主存地址可能相同 D. 采用统一编址方式时，CPU 不能用访存指令访问

【解析】采用统一编码方式，存储器和端口共用统一的地址空间，不需要专用的指令，任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误

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

A.X 的双亲

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

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

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

【答案】C

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

10．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。

I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC

A. 仅I 、II

B. 仅 I 、III

C. 仅 II 、III

D.I 、II 、III

【答案】B 。

【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。

二、填空题

11．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

12．VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

13．在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。