2018年杭州师范大学阿里巴巴商学院826计算机基础之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 假定有4个整数用8位补码分别表示为
放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。
A. B. C. D. 【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为数
,
, 在4个选项中, 只有
都未超过127, 不发生溢出
2． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n) B.O(n) C.O(n2) D.O(log2n ) 【答案】C
2
【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
3． 下列给出的指令系统特点中, 有利于实现指令流水线的是（ ）。
。若将运算结果存
。现在4个整数都是负
, 结果溢出, 其余3个算式结果
Ⅰ. 指令格式规整且长度一致 Ⅱ. 指令和数据按边界对齐存放
Ⅲ. 只有Load/Store指令才能对操作数进行存储访问 A. 仅Ⅰ、Ⅱ B. 仅Ⅱ、Ⅲ C. 仅Ⅰ、Ⅲ D. Ⅰ、Ⅱ、Ⅲ 【答案】D
【解析】特点Ⅰ和Ⅲ都是RISC 机的特征, 而特点Ⅱ则有利于指令和数据的存放, 所以以上三
个特点都有利于实现指令流水线。
4． 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 （ ）
A.27 B.46 C.54 D.56
【答案】B 【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为
5． 下列选项中, 不能改善磁盘设备性能的是（ ）。
A. 重排
请求次序
B. 在一个磁盘上设置多个分区 C. 预读和滞后写
D. 优化文件物理块的分布 【答案】B 。 【解析】
磁盘的一个瓶颈。“重排
性能主要是指其读写速度。相对而言,
磁盘的
性能是计算机性能提高
请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞
性能,
后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘
性能的提升没有什么帮助, 是不能改善磁
盘设备性能的, 故答案为B 。
6． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. B. C. D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时，全部时间下界为间下界为
0 。
7． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度 为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。
A.245Mbps B.979Mbps C.1958Mbps D.7834Mbps
【答案】D
【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到
的时间用来刷
新屏幕，故显存总带宽应加倍. 所以需要的显存总带宽至少约为:1600×l200×24×85×2＝7834Mbps.
8． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11 B.12 C.13 D.14
【答案】B
9． 程序段
与
对换；
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。 A.D(n) B.O(nlogn) C.O(n3) D.O(n2) 【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。
10．有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
两个操作完成后, 2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C
【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。