2017年烟台大学计算机与控制工程学院846数据结构考研仿真模拟题
● 摘要
一、选择题
1． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率
II. 优化数据通路结构
III. 对程序进行编译优化
A. 仅I 和II
B. 仅I 和III
C. 仅II 和III
D.I 、II 和III
【答案】D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。
2． 下列选项中，用于设备和控制器（
A.PCI
B.USB
C.AGP
D.PCI-Express
【答案】B ’接口）之间互连的接口标准是（ ）
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。
3． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
4． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。
5． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一
6． 下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断
，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
7． 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）
A.00110110
B.10101101
C.01010010
D.11000101
【答案】A
【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。
8． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU
速度提高
A.55秒
B.60秒
C.65秒
D.70秒
【答案】D 。
CPU 速度提高【解析】
秒。即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。 速度不变，则运行基准程序A 所耗费的时间是（ ）。 时
9． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
【解析】指令流水线不会断流，预取过来的都是指令
10．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7
B.24，10，5 和24，12，7
C.24，10，10和24，14，11
D.24，10，10和 24，14，6
【答案】D
相关内容
相关标签