2017年武汉科技大学生物医学研究院856数据结构(C语言版)考研导师圈点必考题汇编
● 摘要
一、选择题
1． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
2． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1”
原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码
为“11111101”，即
3． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDM AC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
4． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深
则z 的机器数为（ ）
，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）
过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
5． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
6． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
7． 主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A.500
B.700
C.800
D.1000
【答案】D
【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和
500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200+300+500=1000。
8． 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）
A.
B.
C.
D.
【答案】D
【解析】根据广度优先遍历的定义，可知选项A 、B 、C 都为广度优先遍历，而选项D 是深度优先遍历而不是广度优先遍历，故答案为D 。
9． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
10．将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N-1
C.2N
D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为
其后缀形式为（ ）。
11．已知一算术表达式的中缀表达式为
【答案】D
【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。