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

一、填空题

1． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

2． 在单链表中设置头结点的作用是_____。

【答案】方便运算

3． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

4． 中缀式运算结果为_____。

【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

5． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。

6． 组成串的数据元素只能是_____。

【答案】字符

7． 线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

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

【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

对应的前缀式为_____，若则后缀式的

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素

平均需要移动元素的个数是_____。

9． 设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

10．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）链表未到尾就一直进行

（2）

将当前结点作为头结点后的第一元素结点插入

二、选择题

11．—次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）

A. 并行传输 B 串行传输 C. 突发 D. 同步 【答案】C

【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式 12． 若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）

A.X 的父结点

B. 以Y 为根的子树的最左下结点 C.X 的左兄弟结点Y

D. 以Y 为根的子树的最右下结点 【答案】A

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

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

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

A. 仅I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】B 。

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

14．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。

A.b ，a , c , d ，e B.d ，b , a , c ，e C.d ，b , c , a ，e D.e ，c ，b , a ，d

【答案】C

【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。

假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：

选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL

15．主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。

A.1000 B.2000 C.3000 D.4000 【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，=2000字节，于是此时发送方的发送窗口为min{4000, 2000）由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节，正确选项为A 。