2017年武汉科技大学计算机科学与技术学院856数据结构(C语言版)考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列二叉排序树中，满足平衡二叉树定义的是（ ）。
【答案】B
【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A 项中根结点的平衡因子是2; B 项中每个结点的平衡因子的绝对值均不超过1; C 项中根结点的平衡因子是-2; D 项中根结点的平衡因子是3。
2． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。
A.1000 B.2000 C.3000 D.4000 【答案】A
【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，=2000字节，于是此时发送方的发送窗口为min{4000, 2000）由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节，正确选项为A 。
3． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1 B.n C.n+1 D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需
要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
4． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
5． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点 C.X 的左子树中最右的结点 D.X 的左子树中最右的叶结点 【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
6． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是复杂度也是
所需要的辅助存储为
仅仅表示的是一个量级，
比如
所需要的辅助存储为和
的量级都为
虽然堆排序的时间
之所以说快排
看似堆排序比快速排序的性能好，
但是需要注意
最好，是在综合考虑的情况下。
7． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
8． 下列寄存器中，汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器（MAR ） B. 程序计数器（PC ）
C. 存储器数据寄存器（MDR ） D. 指令寄存器（IR ） 【答案】B
【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。
9． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。
10．已知序列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。