2016年北京林业大学信息学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU 执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A. B. C. D. 答:C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
2． 一个C 语言程序在一台32位机器上运行。程序中定义了3个变量x 、Y 和z ，其中x 和z 为int 型，Y 为short 型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x 、Y 和z 的值分别是（ ）。
A.x=0000007FH, Y=FFF9H, z=00000076H B.x=0000007FH, Y=FFF9H, z=FFFF0076H C.x=0000007FH, Y=FFF7H, z=FFFF0076H D.x=0000007FH, Y=FFF7H, z=00000076H 答:D
【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x 的补码是0000007FH , Y 的补码是FFFFFFF7H , 所以x+Y=00000076H。
3． 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，
把一个磁盘块读人缓冲区的时间为传送到用户区的时间是
CPU 对一块数据进行分析的时间为
构下，读人并分析完该文件的时间分别是（ ）。
A. B. C. D. 答:B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU 对数据的分
条指令/秒 条指令/秒 条指令/秒 条指令/秒
个时钟周期。
CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
将缓冲区的数据
，在单缓冲区和双缓冲区结
析与从用户区读数据也是需要互斥操作，但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU 会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间
）
处理最后一块数据的时
间
当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，
对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU 的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间=（磁盘写入缓冲区时间）
读出最后一块数据时间+CPU分析最后一块数据时间=
4． 数据链路层采用后退N 帧（GBN ）协议，发送方已经发送了编号为0〜7的倾。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。
A.2 B.3 C.4 D.5 答:C
【解析】后退N 帧协议，即GO-BACK-N 策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N 个帧后，若发现该N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N 帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6, 7号帧，共4帧。因此答案为C 项。
5． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串 B. 树 C. 广义表 D. 栈 答:C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
6． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1 B.1、0 C.1、2
D.2、0 答:B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
7． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8 答:B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
淘汰：3。
8． 当字符序列
A.4个 B.5个 C.3个 D.6个
图
答:C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果此总共有3种结果。
若首字符为则只有一种结果
因
作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是
相关内容
相关标签