2018年河北大学计算机科学与技术学院862数据结构(计)考研核心题库
● 摘要
一、单选题
1． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的
。 , 为1200MHz , 该机器的MIPS 为计算机的主频为
2． 已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
。
3． 某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息“＜netl ，16＞”，则能得出的结论是（ ）.
A.R2可以经过R1到达netl ，跳数为17
B.R2可以到达netl ，跳数为16
C.R1可以经过R2到达netl ，跳数为17
D.R1不能经过R2到达netl
【答案】D
【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，因此RIP 协议里规定16为路由不可达，答案为D.
4． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
A.O(1)
B.O(N)
C.O(N2) D.
【答案】B
【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。
5． 对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
D. 减少存储空间
【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
6． 下列选项中, 用于提高RAID 可靠性的措施有（ ）
Ⅰ. 磁盘镜像
Ⅱ. 条带化
Ⅲ. 奇偶校验
Ⅳ. 增加Cache 机制
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅰ、Ⅲ和Ⅳ
D. 仅Ⅱ、Ⅲ和Ⅳ
【答案】B
【解析】能够提高RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。
7． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
8． 在体系结构中, 直接为ICMP 提供服务的协议是（ ）。
A.PPP
B.IP
C.UDP
D.TCP
【答案】B 。
【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。
9． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）.
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是:如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询. 所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归. 正确选项为A.
10．元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
相关内容
相关标签