2017年中国海洋大学信息科学与工程学院912数据结构和软件工程之数据结构考研冲刺密押题
● 摘要
一、选择题
1． 对序
列
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
2． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
3． 下列选项中，用于设备和控制器（
A.PCI
B.USB
C.AGP
D.PCI-Express
【答案】B 用希尔排序方法排序，经一趟后序列变
为则该次采用的增量是（ ）。 ’接口）之间互连的接口标准是（ ）
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。
4． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps
C.
D.
【答案】D
【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到的时间用来刷新
1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：
5． 下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发）
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：
①结构相关，又称资源相关；
②数据相关；
③控制相关，又称指令相关，主要由转移指令引起。
6． 假定有4个整数用8位补码分别表示为
存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1×r2
B.r2×r3
C.r1×r4
D.r2×r4
【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有现在4个整数都是负数
，结果溢出，其余3个算式结果若将运算结果
都未超过127, 不发生溢出。
7． 在’体系结构中，直接为ICMP 提供服务的协议是（ ）。
A.PPP
B.IP
C.UDP
D.TCP
【答案】B 。
【解析】首先明确ICMP 是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层，在网络层上面，所以显然错误，而PPP 协议是广域网数据链路层协议，直接为网络层，也就是IP 层提供服务，ICMP 协议是封装在网络层，因此PPP 不能直接为ICMP 提供服务，ICMP 报文直接封装在IP 分组中，故答案是B 。
8． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为
度为
9． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.
B.
C.
D.
【答案】C
10．某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。
11．单级中断系统中，中断服务程序内的执行顺序是（ ）。
I 保护现场；II 开中断；III 关中断；IV 保存断点；V 中断事件处理；VI 恢复现场；VII 中断返回
【答案】A
【解析】程序中断有单级中断和多级中断之分，单级中断在CPU 执行中断服务程序的过程中不能被打断， 即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服 务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。
因为折半查找是查找效率最高的算法，它的事件复杂
相关内容
相关标签