2018年青岛理工大学计算机工程学院818数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
2． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.
【答案】A
【解析】寄存器个数
指令编址方式如下所示:
16位补码取值范围为 , 所以偏移量取值范围为
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
第 2 页，共 49 页 偏移量有32-8-4-4=16位
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
4． 某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。
5． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】
折半查找法在查找不成功时和给定值进行比较的关键字个数最多为
题中, n=16, 故比较次数最多为5。
6． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的, 在本总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，
第 3 页，共 49 页
可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
7． 若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）
A.x+y
B.-x+y
C.x-y
D.-x-y
【答案】C
答:8位定点补码能表示的数的范围为:-128~127
A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出
8． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
9． 下列选项中, 用于设备和控制器(
A.PCI
B.USB
C.AGP D.
【答案】B 接口) 之间互连的接口标准是（ ）
【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。
10．下列选项中，降低进程优先级的合理时机是（ ）.
A. 进程的时间片用完
第 4 页，共 49 页
相关内容
相关标签