2018年河南大学计算机与信息工程学院840专业基础课(数据结构、操作系统)之数据结构考研核心题库
● 摘要
一、单项选择题
1． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为
2字节，逻辑地址结构为:
逻辑地址空间大小为
（ ）.
A.64
B.128
C.256
D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为
采用二级页表，
一页可存放
个页面来保存页表项，故本题答案为B.
2． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
字节，页表项大小为2B ，字节，
故最少需要个页表项，本题中逻辑地址空间大小为页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是字节，页表项大小为
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的
。 计算机的主频为
, 为1200MHz , 该机器的MIPS 为。
3． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.
B. ; 产生软中断 C. ; 寄存器R0的内容取非 D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中
【答案】C
【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。
4． 循环队列A[0..m﹣1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
A.(rear﹣front ＋m)%m
B.rear ﹣front ＋1
C.rear ﹣front ﹣1
D.rear ﹣front
【答案】A
【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数＝(rear-front)；如果为负则元素的个数＝(rear-front+m)，所以统一的公式就是(rear-front+m)%m。
5． 某CPU 主频为, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令, 在执行过程中共用
CPU 的主频是, 也就是说每秒钟有
条指令/秒,
故答案为C 。
6． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。 个时钟周期。流水线的吞吐率为
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
7． 对同一待排序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是 （ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【答案】D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较, 折半插入排序仅减少了关键字间的比较次数, 而记录的移动次数不变。折半插入排序的时间复杂度仍为, 所以两者之间的不同只可能是元素之间的比较次数。
8． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。
9． 下列关于中断
A. 中断方式和DMA 方式比较的叙述中, 错误的是（ ） 方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断
送由硬件完成
D. 中断
设备
【答案】D
方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部