2016年西北师范大学物理与电子工程学院955数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 计算机硬件能够直接执行的是（ ）。
I .机器语言程序A. 仅
B. 仅
C. 仅
D.
答:A 汇编语言程序硬件描述语言程序
【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言，但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。
2． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1
B.2
C.3
D.4
答:C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
3． 某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息
B.R2可以到达netl ，跳数为16
C.R1可以经过R2到达netl , 跳数为17
D.R1不能经过R2到达netl
答:D
【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，
第 2 页，共 43 页 则能得出的结论是（ ）。 A.R2可以经过R1到达netl ，跳数为17
因此RIP 协议里规定16为路由不可达，答案为D 。
4． 已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （
A.i=l，j=0
B.i=5，j=0
C.i=5，j=2
D.i=6，j=2
答:C
【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决定的，即t 的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2。
5． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）
I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用
A. 仅 I 、II
B .仅 I 、III
C. 仅II 、III
D. I、II 和III
答:B
【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。
6． 假定有4个整数用8位补码分别表示为若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1xr2
B.r2xr3
C.r1xr4
D.r2xr4
答:B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有
都未超过127, 不发生溢出。
7． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
第 3 页，共 43 页 ，i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ））。 现在4个整数都是负数
，结果溢出，其余3个算式结果
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
答:D
【解析】多级页表避免了把所有的页表一直保存在内存中
8． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
答:D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。
9． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
答:B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：
（1）e 进找后出栈，出梭序列为decba 。
（2）c 出找，e 进找后出栈，出找序列为dceba 。
（3）cb 出找，e 进找后出栈，出找序列为dcbea 。
（4）cba 出找，e 进找后出找，出找序列为dcbae 。
10．以太网交换机进行转发决策时使用的PDU 地址是（ ）。
A. 目的物理地址
B. 目的IP 地址
第 4 页，共 43 页
相关内容
相关标签