2018年武汉科技大学生物医学研究院856数据结构(C语言版)考研基础五套测试题
● 摘要
一、单项选择题
1． —组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A.(38，40，46，56，79，84)
B.(40，38，46，79，56，84)
C.(40，38，46，56，79，84)
D.(40，38，46，84，56，79)
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较:46比84小，不交换；
第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;
第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;
第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;
第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;
一次划分结束。
2． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）
A.2
B.3 C.4
D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误
对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误
对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确
3． 下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树
B. 二叉查找树
C. 没有左子树的二叉排序树
D. 没有右子树的二叉排序树
【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。
4． 一个非空广义表的表尾（ ）。
A. 不能是子表
B. 只能是子表
C. 只能是原子
D. 是原子或子表
【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
5． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
A.1
B.2
C.3
D.4
E.5
【答案】C
【解析】动态存储管理系统中有以下三种:首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
6． 假定基准程序A 在某计算机上的运行时间为100秒, 其中90秒为CPU 时间, 其余为若CPU 速度提高
A.55秒
B.60秒
C.65秒
D.70秒
时间。, 速度不变, 则运行基准程序A 所耗费的时间是（ ）。
【答案】D 。
CPU 速度提高50%, 即CPU 性能提高比为【解析】, 改进之后的CPU 运行时间秒。速度不变, 仍维持10秒, 所以运行基准程序A 所耗费的时间为70秒。
7． 静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
【解析】静态链表的一般结构为:struct static_list{ElemType data；int next；}
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
8． 某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机
A.
C.
D. 和和 B.{2, 3}和{1} 和
{1}
向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】
第一次交换机没有
这个数据报源MAC 地址的信息
所以只用从1端口转发。
的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了