2016年宁夏医科大学公共卫生与管理学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A. B. C. D.
【答案】B
【解析】因组与组之间已有序，故将个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
2． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4
=20MB/s。 字节信息, 则总线带宽是4B ÷
3． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
4． 假定有4个整数用8位补码分别表示为若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1xr2
B.r2xr3
C.r1xr4
D.r2xr4
【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有现在4个整数都是负数
，结果溢出，其余3个算式结果
都未超过127, 不发生溢出。
5． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
6． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
7． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 哈希函数选择不当
D. 解决冲突的算法选择不好
【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
8．
用户程序发出磁盘请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
9． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
【答案】A
10．—棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h B. C. D.
【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
二、填空题
11．无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
12．设有两个算法在同一机器上运行，其执行时闻分别为
_____。
【答案】15
【解析】当时，而，时，
13．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
14．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
15．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
16．组成串的数据元素只能是_____。
【答案】字符
要使前者快于后者，n 至少为