2016年沈阳理工大学信息科学与工程学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B.
C.
D.
答:B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是
法运算的时间。
因此，
当时
，
当
即fact （n
）的时间复杂度为
2． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU
速度提高
A.55秒
B.60秒
C.65秒
D.70秒
答:D 。
CPU 速度提高【解析】即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间秒。速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。
3． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
其中O （1）为乘则
，
时
，时速度不变，则运行基准程序A 所耗费的时间是（ ）。
D.-3
答:B
；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1”
原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码
为“11111101”，即
4． 为支持 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
答:A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
5． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
答:A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
6． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP ±也址
D. 根据IP 地址查询域名
答:A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
7． 分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
答:A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
8． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
答:A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需趟排序，也即时间复杂度仍为而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时
；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，
比较的时间复杂度由 降至
9． 折半查找的时间复杂性为（ ）。
答:D
【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂 度为
10． 对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
答:D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
而记录的移动次数不变。折半插入排序的时间复杂度仍为
所以两者之间的不同只可能是元素之间的比较次数。
二、填空题
相关内容
相关标签