2017年华南农业大学数学与信息学院854数据结构与计算机组成原理之数据结构考研冲刺密押题
● 摘要
一、选择题
1． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的该机器的
2． —个栈的入栈序列为的个数是（ ）
A.n-3
B.n-2
C.n-1
D. 无法确定
【答案】C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
3． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。
I .增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象
A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III
第 2 页，共 57 页 计算机的主频为 其出栈序列是若，则为1200MHz ，则可能取值
【答案】D
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
4． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
5． 以下说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n 下，复杂度的算法在时间上总是优于复杂度的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A. （1）
B. （1）, （2）
C. （1）, （4）
D. （3）
【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
6． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1
B. 仅2
C. 仅 1，2
第 3 页，共 57 页
D. 仅 2, 3
【答案】C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
7． 下列选项中，描述浮点数操作速度指标的是（ ）。
A.MIPS
B.CPI
C.IPC
D.MFLOPS
【答案】D
【解析】表示每秒执行多少百万次浮点
. 表示每秒执行多少百万条指令。对于一个给定的程序，
MIPS 定义为
这里所说的指令一般是指加、减运算这类短指令。
就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，
造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。
每个时钟周期执行的指令数。
8． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ） A. B. C. D.
【答案】D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
9． 某磁盘的转速为10, 000转/分，平均寻道时间是磁盘传输速率是
为读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms
B.9.4ms
C.12ms
D.12.4ms
第 4 页，共 57 页 运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。
磁盘控制器延迟