计算机统考模拟题(海文辅导班)

海文专业课模拟试卷

2010年计算机研究生全国统一考试冲刺模拟题（一）

一﹑单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出

一项最符合题目要求的。

1

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用______存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是______。 A．不确定 B．n-i+1 C．i D．n-i

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。

2 3

A．13 B．33 C．18 D．40

4 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二

叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 5 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。 A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)? D． ?n/(m-1)?-1 E．?(n+1)/(m+1)?-1 6 用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。 A．5 B．6 C．8 D．9 7 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A．O(n) B．O(n＋e) C．O(n*n) D．O(n*n*n) 8 当采用分快查找时，数据的组织方式为 ( )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索

引块

C．数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D．数据分成若干块，每块（除最后一块外）中数据个数需相同

9 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A．快速排序 B．堆排序 C．归并排序 D．直接插入排序

10 在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。 A．?n/2? B．?n/2? -1 C．1 D．?n/2? +2

11 硬件和软件实现在逻辑功能上是一样的，但硬件的优势在于_______。

A．速度快

B.成本低 D.灵活性好

C．容量大 12 数据发生溢出的根本原因是_______。

A．数据的位数有限

B．数据运算中将符号位的进位丢弃 C．数据运算中将符号位的借位丢弃

D．数据运算中的错误

13 在页式虚拟存储器中，为了提高主存的命中率，可以采取的措施是______。

A．增大主存容量

B.增大辅存容量

信息咨询： 010-82487377 13701202290

1

选择海文选择成功

C．增大Cache容量 D.将LRU替换算法改为FIFO 14 下列关于存储器的描述，正确的是______。

A．CPU访问时间由存储器容量决定 B．ROM和RAM在存储器中是统一编址的 C．ROM中任一单元可随机访问

D．DRAM是破坏性读出，因此需要读后重写

15 在相对寻址方式中，若指令中地址码为X，则操作数的地址为______。

A．X

B（PC）+X

C．X+段基址 D.变址寄存器+X 16 指令系统中采用不同寻址方式的目的主要是______。

A．可直接访问内存

B．提供扩展操作码并降低指令译码难度 C．实现存储程序和程序控制

D．缩短指令长度，扩大寻址空间，提高编程灵活性。

17 在总线结构的CPU中，各个部件连接到总线上，其中（在某一时间）______。

A．只有一个部件可以向总线发送信息，并且只有一个部件能从总线上接收消息 B．只有一个部件可以向总线发送消息，但可有多个部件能同时从总线上接收消息 C．可以有一个以上部件向总线上发送消息，但只有一个可以从总线上接收消息

D．可以有一个以上部件向总线上发送消息，并且可由多个部件同时从总线上接收消息

18 微程序执行的顺序控制问题，实际上是如何确定下一条微指令的地址问题。通常采用的一种方法是断

定方式，其基本思想是______。

A．用程序计数器PC来产生后继微指令地址 B．用微程序计数器? PC来产生后继微指令地址

C．通过微程序顺序控制字段或由设计者指定的判断字段控制产生后继微指令地址 D．通过指令中指定的一个专门字段来控制产生一个后继微程序地址 19 在各种异步通信握手方式中，速度最快的是______。

A．全互锁 B．半互锁

C．非互锁 D．与互锁性无关

20 为了对n个设备使用总线的请求进行裁决，在链式查询方式中需要使用______条控制线。

A．n条

2 B．3条

n?D．2n+2 C．2+ ? ?log?21 以下叙述错误的是______。

A．产生中断请求信号后，一般由硬件和中断屏蔽字完成中断的裁决和中断源识别 B．在多级中断中，CPU本身也有优先级

C．软中断是由程序员安排的指令（称为软中断指令和陷阱指令）引起的 D．DMA比通道具有更强的独立处理数据输入输出的功能。 22 磁盘设备适宜于连接到______通道。

A．字节多路通道或数据组多路通道 B．字节多路通道或选择通道 C．数组多路通道或选择通道 D．任一种 23 分时操作系统的主要目标是 ______。

http://www.vipkaoyan.com

2

海文专业课模拟试卷

A．提高计算机系统的实时性 B．提高计算机系统的利用率

C．提高软件的运行速度 D．提高计算机系统的交互性

24 并行技术可使系统的各种硬件资源尽量并行工作,这样的程序执行环境具有独立性,随机性和 ______。 A．封闭性 B．多发性 C．顺序性 D．资源共享性

25 假设就绪进程中有10个进程,系统将时间片设为200ms,CPU进行进程切换要花费10ms，则系统开销

所占的比率为______。

A．1% B．5% C．10% D．20%

26 在操作系统中,对信号量S的v原语操作定义中,进程从相应等待队列中出列并进入就绪队列中的条件

是______。 A．s<=0 B．s=0 C．s<0 D．s≠0 27 系统抖动是指______。

A．使用机器时，屏幕闪烁的现象

B．系统盘有问题，至使系统不稳定的现象

C．由于内存分配不当，偶然造成内存不够的现象

D．被调出的页面又立刻被调入形成的频繁调入调出现象 28 下列哪一种属于操作系统中以空间换取时间的技术______。

A．SPOLLing技术 B．虚拟存储技术 C．覆盖和交换技术 D．通道技术 29 在文件系统中,下列关于当前目录(工作目录)的叙述中,不正确的是______。

A．提高文件目录的检索速度 B．减少启动硬盘次数 C．利用全路径查找文件 D．当前目录可以改变 30 下列那种磁盘调度算法只考虑了公平性？______

A．先来先服务 B．最短寻道时间优先 C．先来先服务和扫描 D．前3个都是

31 系统为了管理文件,设置了专门的数据结构文件控制块(FCB),FCB是在执行下列哪一个系统调用时建

立的? ______

A．create B．open C．read D．write 32 在下列叙述中正确的是 ______。

A．在设备I/O中引入缓冲技术的目的是为了节省内存

B．指令中的地址结构和外存容量是决定虚存作业地址空间的两个因素 C．处于阻塞状态的进程被唤醒后,可直接进入运行状态 D．在虚拟页式管理中,FIFO置换算法的内存利用率是较高的 33 波特率等于

A．每秒传输的比特

B．每秒钟可能发生的信号变化的次数 C．每秒传输的周期数 D．每秒传输的字节数

34 一种编码的检错能力和纠错能力取决于它的海明距离。为了检测出d个比特错，需要使用海明距离为

_______的编码。 A．d

A．帧同步功能 C．差错控制功能

B．d+1 C．d+2

B．电路管理功能 D．流量控制功能

D．2d+1

35 下列不属于数据链路层功能的是_______。

36 IEEE802.11MAC层具有多种功能，其中分布式协调功能采用的是_______协议

A ．CSMA/CA B ．CSMA/CB C． CSMA/CC D． CSMA/CD

信息咨询： 010-82487377 13701202290

3

选择海文选择成功

37 HDLC是一种_________协议。

A．面向比特的同步链路控制 B．面向字节数的异步链路控制 C．面向字符的同步链路控制 D．面向比特的异步链路控制 38 下面关于网桥的说法中不正确的是_______。

A．网桥工作在数据链路层，对网络进行分段，并将整个物理网络连接成一个逻辑网络。 B．网桥可以通过对数据进行过滤，有效地组织广播数据 C．网桥可以连接数据链路层协议不同的局域网 D．网桥要处理器接收到的数据，增加了传播时延

39 在距离矢量路由选择协议中，下列哪项最可能导致路由回路(rooting loop)问题？_______

A．由于网络带宽的限制，某些路由更新数据包被丢弃

B．由于路由器不知道整个网络的拓扑结构信息，当收到一个路由更新时，又将该更新信息发回向自

己发送该路由信息的路由器

C．当一个路由器发现自己的一条直接相邻链路断开时，没能将这个变化报告给其他路由器 D．慢收敛导致路由器接受了无效的路由信息 40 PING使用了哪个协议？_______

A．ICMP

B．TCP C．UDP D．HTTP

二﹑综合应用题：41~47小题，共70分

1 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按

下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。（15分）

2 图的D_搜索类似与BFS,不同之处在于使用栈代替BFS中的队列 ,入出队列的操作改为入出栈的操作，

即当一个顶点的所有邻接点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表做存储结构,写一个D_搜索算法（10分） 3 4 5

求信息码01101110的海明校验码，画出能指出2位出错和纠正一位出错位的海明校验逻辑。（15分） 什么叫页式虚拟存储器？什么叫页表？说明工作原理。（6分）

有一个虚拟存储系统,分配给某个进程3页内存,开始时内存为空,页面访问序列如下:6,5,4,3,2,1,5,4,3,6,5,4,3,2,1,6,5.

(1) （2分）采用先进先出页面置换算法,缺页次数为多少? (2) （2分）采用最近最少使用页面置换算法,缺页次数为多少? (3) （2分）采用最佳页面置换算法,缺页次数为多少? 6 7

什么是AND信号量?试利用AND信号量写出生产者－消费者问题的解法。（9分）

在数据传输速率为50kb/s的卫星信道上发送长度为1kb的帧。假设确认总是由数据帧捎带。帧头很短，帧序号的长度为3比特。对于下列三种协议可以取得的最大利用率是多少？（假设卫星信道端到端的单向传播延迟时间为270ms） (1) （3分）停止等待协议； (2) （3分）后退N滑动窗口协议； (3) （3分）选择重发滑动窗口协议。

http://www.vipkaoyan.com

4

海文专业课模拟试卷

2010年计算机研究生全国统一考试冲刺模拟题（二）

一﹑单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出

一项最符合题目要求的。

41 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A．单链表

B．单循环链表

C．带尾指针的单循环链表

D．带头结点的双循环链表

42 下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便

D．可方便地用于各种逻辑结构的存储表示

43 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删

除操作时( )。

A．仅修改队头指针 B．仅修改队尾指针

C．队头、队尾指针都要修改

D．队头,队尾指针都可能要修改

44 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8

45 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。 A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆 46 （ ）的遍历仍需要栈的支持.

A．前序线索树 B．中序线索树 C．后序线索树

47 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 48 下列关于AOE网的叙述中，不正确的是（ ）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成

具有12个关键字的有序表，折半查找的平均查找长度（ ） A．3.1 B．4 C．2.5 D．5 m阶B-树是一棵( ) A．m叉排序树

B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树

下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A．快速排序 B．shell排序 C．堆排序 D．冒泡排序

下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) A．选择排序法 B．插入排序法 C．快速排序法 D．堆积排序法

信息咨询： 010-82487377 13701202290

5

49 50

51 52

海文专业课模拟试卷

A．多为交叉存储器主要解决扩充容量问题。 B．Cache的功能全由硬件完成。

C．Cache与主存统一编址，即主存空间的某一部分属于Cache D．―主存－外存‖的存储层次是为了弥补主存速度不足。

93 在Cache更新策略中，在Cache命中时把数据同时写入Cache和主存的策略是______。

A．写直达

B.写回法 D.不按写分配法

C．按写分配法

94 为了缩短指令中某个地址码的位数，有效的方法是采用______寻址。

A．立即数 B．寄存器 C．直接 D．变址 95 一条指令有16位，在读取这条指令后，PC的值为______。

A．3000 B．3001 C．3002 96 以下错误的是______。

A．在指令编码中，编码效率最高的是直接表示法

B．在各种微地址的形成方式中，计数器方式需要的顺序控制字段较短 C．在各种微地址的形成方式中，断定方式需要的顺序控制字段较短 D．汇编语言依然与计算机的结构特征相关 97 控制存储器用来存放______。

A．机器指令和数据

B．微程序和数据 D．微程序

C．机器指令和微程序 A．启动外设

B．存放CPU给外设的操作命令 C．存放CPU给接口的操作命令 D．存放外设给CPU的操作命令

99 为了对n个设备使用总线的请求进行裁决，在独立请求方式中需要使用______条控制线。

??A．n条 B．3条 C．2+ ?log n ? D．2n+2

2 D．3016

98 在总线接口中，命令寄存器的作用是______。

100 以下叙述中错误的是______。

A．中断服务程序一般是操作系统模块 B．中断向量方法可以提高判断中断源的速度 C．中段向量就是中断服务程序的入口地址 D．DMA方式的接口中包含程序中断内容 101 单独编址法进行输入输出操作的指令是______。

A．控制指令 B．运算指令 C．访存指令 D．输入输出指令 102 中断向量是______。

A．子程序入口地址 B．中断服务程序入口地址 C．没有服务程序入口地址的地址 D．设备地址 103 UNIX操作系统区别于WINDOWS95的主要特点是______。

A．具有多用户分时功能 B．提供图形用户界面 C．文件系统采用多级目录结构 D．提供字符用户界面

信息咨询： 010-82487377 13701202290

11

选择海文选择成功

104 一个进程可以包含多个线程,下列哪一向不是这些线程独立拥有的资源? ______。

A．线程控制快 B．内存空间 C．处理器 D．系统运行栈

105 进程在其生命周期期间,在三种基本状态之间相互转换.下列哪一种进程状态转换是不会发生

的?______

A．从运行态到等待态 B．从等待态到运行态 C．从就绪态到运行态 D．从运行态到就绪态

106 在使用基于优先数的，不可抢占进程调度算法的系统中，不会引起进程切换的事件是______。

A．进程运行完成 B．进程运行过程中变为等待状态 C．时间片刻 D．有一个优先级高的进程就绪 107 下列哪些问题没有包含互斥关系? ______

A．哲学家就餐问题 B．司机售票员问题 C．飞机订票问题 D．读者写者问题

108 若页的大小为4K，则地址转换机制将逻辑地址0转换成相应的物理地址______。

A．8192 B．4096 C．2048 D．1024

109 在虚拟页式存储管理方案中，下面那种页面置换算法会产生异常现象？______

A．先进先出页面置换算法 B．最近最少使用页面置换算法 C．最不经常使用页面置换算法 D．最佳页面置换算法 110 在页式存储管理中，系统提供一对硬件寄存器，他们是______。

A．基址寄存器和限长寄存器

B．页表始址寄存器 和页表长度寄存器 C．上界寄存器和下界寄存器

D．直接地址寄存器 和间接地址寄存器 111 位示图可用于______。

A．文件目录的查找 B．磁盘空间的管理 C．内存空间的共享 D．实现文件的保护和保密

112 特权指令是操作系统中只能在管态下执行的指令,而下列哪一条指令不是特权指令？______

A．输入输出 B．置中断屏蔽 C．P、V操作 D．置程序状态字 113 在OSI参考模型的7层结构中，实现帧同步功能的是_______。

A．物理层 C．网络层

B．数据链路层 D．传输层

114 在下列传输介质中，哪一种错误率最低?

A．同轴电缆 B．光缆 C．微波 D．双绞线

115 一种编码的检错能力和纠错能力取决于它的海明距离。为了纠正d个比特错，需要使用海明距离为

_______的编码。

A．d B．d+1 C．d+2 A．只有数据链路层存在流量控制

B．不只是数据链路层存在流量控制，不过各层的流量控制对象都一样 C．不只是数据链路层存在流量控制，但是各层的流量控制对象都不一样

D．2d+1

116 流量控制是数据链路层的基本功能之一，有关流量控制下列说法正确的是_______。

http://www.vipkaoyan.com

12

海文专业课模拟试卷

D．以上都不对

117 假设数据链路层采用go-back-N的方式进行差错控制，发送方已经发送了编号为0～7的帧，当计时器

超时而1号帧的确认没有返回，发送方需要重发的帧数为_______。 A．1

B．2 C．6

D．7

118 局域网的协议结构一般不包括_____。

A．网络层 C．物理层

B．数据链路层 D．媒体访问控制层

119 下列哪项不属于路由选择协议的功能？_______。

A．获得网络拓扑结构的信息 B．选择到达每个目的网络的最优途径 C．构建路由表

D．发现下一跳的物理地址

120 在下列关于UDP的陈述中，哪一句是正确的? A．UDP使用TCP传输协议 B．给出数据的按序投递 C．不允许多路复用

D．运行主动的流控机制 E．都不正确

二﹑综合应用题：41~47小题，共70分

1 Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U V.-U 请看下边的无向加权图，按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分）

信息咨询： 010-82487377 13701202290

13

选择海文选择成功

2

有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

(1) (3分)给出适用于计数排序的数据表定义;

(2) (6分)使用Pascal或C语言编写实现计数排序的算法； (3) (3分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么? 3

某计算机的字长为16位，存储器按字编址，访存指令格式为16位，其中5位操作码，

3位寻址方式字段，分别表示立即寻址、直接寻址、间接寻址、变址寻址和相对寻址5种，8位地址码字段。设PC和Rx分别为程序计数器和变址寄存器。问：

(1) (2分)该格式能定义多少种指令？ (2) (3分)各种寻址方式的寻址范围是多少？

(3) (6分)写出各种寻址方式的有效地址EA的计算式。 4

某计算机的虚拟存储系统有40位虚拟地址，32位实际地址，虚页为1M（220）。假设 (1) (2分)计算页表大小。 (2) (2分)计算页面大小。

(3) (6分)画出该虚拟存储系统的虚实地址转换逻辑图（包括虚地址、实地址、页表、页 表寄存器及相互关系）。 5 6

什么是抖动? 产生抖动的原因是什么?（6分） 有一文件系统如图所示：

有效位、保护位、修改位和使用位共用去4位（valid、protection、dirty、wu），所有虚页都在使用。

http://www.vipkaoyan.com

14

海文专业课模拟试卷

图中，方框表示目录文件，圆表示普通文件。根目录常驻内存，目录文件中组织成连接文件，不设文件控制块，普通文件组织成索引文件，目录文件指示下级文件名及其磁盘地址（各占2个字节，共4个字节），若下级文件是目录文件，指示其第一个磁盘块地址，若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级目录文件中的次序在图中为自左向右。每个磁盘块512字节，与普通文件的一页等长。

普通文件的文件控制块组织如下：

其中每个磁盘地址占5个字节，前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第12个地址指示二级索引表地址，二级索引表中每个地址表示一个一级索引表地址；第13个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地址。问

(1) (2分)一个普通文件最多可有多少个文件页？ (2) (2分)若要读文件J中某一页，最多启动磁盘多少次？ (3) (2分)若要读文件W中某一页，最好启动磁盘多少次？

(4) (3分)就上一问而言，为最大限度减少启动磁盘次数，可采用什么办法？此时最多磁盘启动多少次？ 7

无限局域网的MAC有哪些特点?为什么在无线局中不能使用CSMA/CD协议而必须使

用CSMA/CA协议？结合隐藏站问题和暴露站问题说明RTS帧和CTS帧的作用。

信息咨询： 010-82487377 13701202290

15

选择海文选择成功

2010年计算机研究生全国统一考试冲刺模拟题（一）答案

一、BBBDC,ABBCD,AACCB,DBCCB,DCDDB,ADACA,ABBBB,AABDA 二、（1） 散列地址 关键字 0 1 4 2 3 12 4 49 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 比较次数 1 1 1 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

（2）ASLsucc =11/8 ASLunsucc=19/11

值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11

1. D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未

遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0)

// 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。 { int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1,i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1,i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0)

{s[++top]=i; visited[i]=1; printf( \ while (top>0)

{i=s[top--]; //退栈

p=g[i].firstarc; //取第一个邻接点

while (p!=null) //处理顶点的所有邻接点

{j=p->adjvex;

if (visited[j]==0) //未访问的邻接点访问并入栈。

{visited[j]=1; printf( \ p=p->next; } //下一个邻接点

}//while(top>0)

} //if

http://www.vipkaoyan.com

16

海文专业课模拟试卷

}//D_BFS

2. 求信息码01101110的海明校验码。

分析1：

①确定海明校验位的位数。

设r为海明校验位的位数，则整个码字的位数应满足不等式：k+r ≤2-1

设r=3，则2-1=7，n=8+3=11,不等式不满足；设r=4，则2-1=15，n=8+4=12，不等式满足。所以r最小取4。

②确定校验位的位置。

位号（1～12）为2的权值的那些位，即：20，21，22，23的位置作为校验位，记做P1、P2、P3、P4，余下的为有效信息位。即：

12 11 10 9

8

7 6

5 4 3

2 1

D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1

3

4

r

③分组：有4个校验位，将12位分成4组，第i组由校验位号之和等于i的那些校验位所校验，如下表所示，如：第11位D6由P1（位号为1）、P2（位号为2）、P4（位号为8）所校验，因为1+2+8=11。

4位校验位的分组

12 D7 0 第一 组（P1） 第二 组（P2） 第三√ 组（P3） 第四√ 组（P4） 11 D6 1 √ √ √ 10 D5 1 √ √ 9 D4 0 √ √ 8 P4 √ 7 D3 1 √ √ √ 6 D2 1 √ √ 5 D1 1 √ √ 4 P3 √ 3 D0 0 √ √ 2 P2 √ 1 P1 √ ④校验位的形成。

P1=第一组中的所有位(P1外)同=D6?D4?D3?D1?D0=1?0?1?1?0=1 P2=第一组中的所有位(P2外)同=D6?D5?D3?D2?D0=1?1?1?1?0=0 P3=第一组中的所有位(P3外)同=D7?D3?D2?D1=0?1?1?1=1 P4=第一组中的所有位(P4外)同=D7?D6?D5?D4=0?1?1?0=0 P5=D7?D6?D5?D4?D3?D2?D1?D0?P1?P2?P3?P4 =0?1?1?0?1?1?1?0?1?0?1?0=1

答案1：信息码01101110的海明校验码为：1011011110110。 校验原理

分析2：在接收端分别求G1、G2、G3、G4、G5。 G1=P1?D6?D4?D3?D1?D0 G2=P2?D6?D5?D3?D2?D0

信息咨询： 010-82487377 13701202290

17

为了能检测两个错误，增加一位校验位P5，放在最高位。

选择海文选择成功

G3=P3?D7?D3?D2?D1 G4=P4?D7?D6?D5?D4

G5=P5?D7?D6?D5?D4?D3?D2?D1?D0?P1?P2?P3?P4

当G5=1时有一位数，由G4G3G2G1的二进制编码指出出错位号。例如G4G3G2G1=1001说明第9位出当G5=0时无错或有偶数个错（两个错的可能性比较大）；当G4G3G2G1=0000时，接收的数无错，否

错，将其取反，即可纠错。

则有两个错。 答案：能找出两个错误并能纠正一位出错位的海明校验逻辑电路如下图所示

3. 页式虚拟存储器把虚拟存储空间（逻辑空间）和主存空间（物理空间）等分成固定大小的页面，虚存

和实存间交换数据是以页面为单位进行的，每个虚拟页面可以装入主存中任一个物理页面。如果页面

大小为4KB，则页内地址共12位，虚拟空间的虚拟地址，去掉页内地址，就是页面地址，简称页号，即虚拟地址（逻辑地址）的高位地址。

给定一个虚拟地址（逻辑地址），从虚拟存储器中取出该单元的数据的过程是：首先必须查页表，进行虚实地址转换。页表中存放着各逻辑页面调入主页时的对应物理页号，如果所读逻辑页面已调入主存，可按页表给出该逻辑页面装入主存的物理页号作为访问主存的高位地址，再把逻辑地址的页内地址作为物理页面的页内地址（被访问主存单元的低位地址），二者合起来构成主存的物理地址。如果虚拟访问的页面还为调入主存，则必须先将磁盘中该页调入主存一个空闲页面中，并在页表中填入有关物理页号。然后根据主存地址访问主存单元，即可达到访问对应虚拟地址对应单元的目的。 4. (1):17次

(2):17次 (3)11次

5. 为解决并行所带来的死锁问题，在wait操作中引入AND条件，其基本思想是将进程在整个运行过程

中所需要的所有临界资源，一次性地全部分配给进程，用完后一次性释放.解决生产者－消费者问题可

描述如下:

var mutex,empty,full: semaphore:=1,n,0; buffer: array[0,...,n-1] of item; in,out: integer:=0,0; begin

parbegin

producer: begin

http://www.vipkaoyan.com

18

海文专业课模拟试卷

repeat . .

produce an item in nextp; .

.

wait(empty);

wait(s1,s2,s3,...,sn); //s1,s2,...,sn为执行生产者进程除empty外其余的条件 wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full);

signal(s1,s2,s3,...,sn); until false; end

consumer: begin repeat

wait(full);

wait(k1,k2,k3,...,kn); //k1,k2,...,kn为执行消费者进程除full外其余的条件 wait(mutex);

nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty);

signal(k1,k2,k3,...,kn); consume the item in nextc; until false; end parend end

6. 已知数据帧的长度为1kb，卫星通信信道的数据传输速率为50kb/s,因此发送一帧的时间 为1/50=0.02(s)。另外，卫星信道的单向传播延时为270ms=0.27s。

（1）在停止等待协议中，发送方首先用0.02s发送一个帧，然后等待确认。该帧经过0.27s后到达接收方，接收方立即用0.02s发送一个数据帧，其中捎带了对所接受的帧的确认，该数据帧经过另外0.27s之后到达发送方。于是，发送周期为(0.02+0.27+0.02+0.27)=0.58(s)。其中用于发送数据的时间为0.02s。因此，可以取得的信道最大利用率=0.02/0.58，约为3.4％。

（2）在后退N滑动窗口协议中，由于帧序号的长度为3比特，发送窗口大小的最大值=23-1=7，也就是在一个发送周期内发送方可以连续发送7帧。后退N协议的发送周期与停止等待协议的发送周期相同，也为0.58s。因此，可以取得的信道最大利用率=7×0.02/0.58,约为24.1％。

（3）在选择重发滑动窗口协议中，由于帧序号的长度为3比特，发送窗口大小的最大值=23-1=4，也就是在一个发送周期内发送方可以连续发送4帧。选择重发协议的发送周期与停止等待协议的发送周期相同，也为0.58s。因此可以取得的信道最大利用率=4×0.02/0.58，约为13.8％。

信息咨询： 010-82487377 13701202290

19

选择海文选择成功

2010年计算机研究生全国统一考试冲刺模拟题（二）答案

7. 上三角矩阵第一行有n个元素，第i-1行有n-（i-1）+1个元素，第一行到第i-1行是等腰梯形，而第

i行上第j个元素（即aij）是第i行上第j-i+1个元素，故元素Aij在一维数组中的存储位置（下标k）

为：

k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1

2

进一步整理可得k=（n+1/2）i-i/2+j-n，

则得f1（i）=（n+1/2）i-i2/2，f2（j）=j，c=-n。 8. （1）递归算法

void DecPrint(BSTree t）

//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 { if（t）

{DecPrint(t->rchild)；

if（!t->lchild && t->rchild）printf(t->data：4） DecPrint(t->lchild）； }

}//DecPrint

（2）非递归算法 void DecPrint(BSTree t）

// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 { BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0； while（t || top>0）

{while（t）

{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；

if（!t->lchild && t->rchild）printf(t->data：4)； t=t->lchild； // 去左分枝 }//if

}//while }//算法结束

9. 16K?1位的芯片有14条地址线，行地址线、列地址线各7条，行数和列数各等于27=128

条。用它来构成32K?8的存储器需要32/16?8=16片。一个刷新周期执行的刷新操作数等于行数（128），所占用的时间=128?50ns=6400ns=6.4 ?s.两次刷新之间的时间间隔=1ms/128=7.8 ?s（分布式刷新，相邻两行的刷新时间间隔）。

10. （1）当使用正常的中断屏蔽码时，处理机响应各中断源的中断请求的先后次序是根据

优先级从高到低的级别排列的，分别是1级、2级、3级4级和5级。实际处理的顺序也是这个顺序。

（2）当使用改编后的屏蔽码时，处理机响应各中断源的中断请求的先后依序依然是1级、2级、3级、4级和5级。但是由于中断屏蔽寄存器的设置，故改变了中断处理的顺序，变成4级、5级、3级、2级和1级。

http://www.vipkaoyan.com

20

海文专业课模拟试卷

（3）按照改变后的中断屏蔽码，当D1、D2、D3、D4和D5这5个中断源同时请求中断时，处理机响应中断源的中断请求和实际运行中断服务程序过程如下图所示。图中时间轴向下，箭头表示处理过程，没有箭头的垂直线表示响应的过程。

原程序 1级 2级

11. #define CHAIR 6

semaphore customers = 0; semaphore barbers = 0; semaphore S = 1; int waiting = 0; void barber() {while(T) {

P(customers); P(S);

waiting = waiting – 1; V(barbers); V(S); 理发…… } }

void customer() {

P(S);

if(wait < CHAIR) {

waiting = waiting + 1; V(customers); V(S);

P(barbers);

信息咨询： 010-82487377 13701202290

21

3级 4级 5级

选择海文选择成功

坐下等待；

} else {

V(S); }

}

12. 相似处：

13. 信号和中断都采用了相同的异步通信方式；

14. 当检测出有信号或中断请求时，都是暂停正在执行的程序而转去执行相应的处理程序； 两者都是在处理完毕后返回到原来的断点； 对信号或中断都可进行屏蔽； 差异处：

中断有优先级，而信号没有优先级，即所有信号都是平等的；

信号处理程序是在用户态下运行的，而中断处理程序则是在核心态下运行的； 中断响应是及时的，而信号响应通常都有较大的时间延迟.

15. 已知路由器C测得到自己的另连接路由器B、D和E的时延分别等于6、3和5.在收到 来自D的矢量(16,12,6,0,9,10)后，路由器C的路由表如图(一)所示。

路由器C的路由表(一) 站点 A B C 下一跳 D B — 度量 19 6 — 站点 D E F 路由器C的路由表(二) 站点 A B C 下一跳 E B — 度量 12 6 — 站点 D E F 路由器C的路由表(三) 站点 A B C 下一跳 B B — 度量 11 6 — 站点 D E F 下一跳 D E B 度量 3 5 8 下一跳 D E E 度量 3 5 9 下一跳 D E D 度量 3 5 13 自E的矢量(7,6,3,9,0,4)后，路由器C的路由表如下图(二)

在收到来自B的矢量(5,0,8,12,6,2)后，路由器C的路由表如图(三)所示。

http://www.vipkaoyan.com

22

海文专业课模拟试卷

2010年计算机研究生全国统一考试冲刺模拟题（三）答案

16. Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 ① 2 3 ① 3 ① 3 ④ 1 ② 2 ④ 2 ④ 2 ④ 4 ④ 4 ⑤ 1 ⑤ 2 ⑤ 2 ⑥ 4 ⑦ 3 {1,2,4,3,5,6,7,8} {} {1,2,4,3,5,6,7} {8} {1,2,4,3,5,6} {7,8} {1,2,4,3,5} {6,7,8} {1,2,4,3} {5,6,7,8} {1,2,4} {3,5,6,7,8} {1,2} {3,4,5,6,7,8} 4 5 6 7 8 U {1} V-U {2,3,4,5,6,7,8} 17. typedef struct

{ int key; datatype info}RecType

void CountSort(RecType a[],b[],int n) //计数排序算法，将a中记录排序放入b中 { for(i=0;i

if(a[j].key

b[cnt]=a[i]; }

}//Count_Sort

(3) 对于有n个记录的表，关键码比较n次。

(4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间；而这种方法比较次数是n2，且需要另一数组空间。

信息咨询： 010-82487377 13701202290

23

2

选择海文选择成功

[算法讨论]因题目要求―针对表中的每个记录，扫描待排序的表一趟‖，所以比较次数是n2次。若限制―对任意两个记录之间应该只进行一次比较‖，则可把以上算法中的比较语句改为：

for(i=0;i

if(a[i].key

18. 答：（1）5位操作码可表示25=32种不同的指令。

（2）立即数寻址方式只能访问唯一的一个数据；

直接寻址方式用地址码表示存储器地址，8位地址码可以有28=256个数据字；

间接寻址方式用地址码表示地址的存储位置，存储器中16位的地址可以有2=64K种数据地址； 变址寻址方式用地址码表示地址的偏移量，地址在寄存器中，16位变址寄存器和8位偏移量的寻址范围是216+18；

相对寻址方式的寻址范围是PC值附近的字，8位地址偏移量可对PC附近的256个数据字进行寻址。 （3）设地址码位A，各寻址方式的有效地址表达式如下： 立即数寻址：EA=PC 直接寻址：EA=A 间接寻址：EA=（A） 变址地址：EA=Rx+A 相对地址：EA=PC+A

19. 因为虚拟存储系统有40位虚拟地址，32位实际地址，虚页为1M（220），所以主存地址格式为：

31

20 19

0

16

物理页号（12位） 虚拟地址格式为：

39

页内地址（20位） 20 19 0

虚页面号（20位） 页内地址（20位） http://www.vipkaoyan.com

24

海文专业课模拟试卷

（1）页表的字长=物理页号位数12+有效位、保护位、修改位和使用位共4位=16位。页表的单元数=1M（220）。

所以页表大小=1M×16。 （2）页面大小=1M（2）。

（3）虚实地址转换示意图如下图所示。

20. 抖动(Thrashing)就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调

出一页程序或数据送磁盘的对换区中，如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的时间，我们称这种现象为\抖动\

产生抖动的原因是由于CPU的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导致CPU的利用率下降，而系统的调度程序又会为了提高CPU利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于\抖动\状态.

21. （1）10＋256＋256×256＋256×256×256

（2）7次 （3）6次

20

（4）将w链接到根目录最左端 5次

22. 无线局域网设计了独特的MAC层。MAC层在物理层的上面，包括有两个子

信息咨询： 010-82487377 13701202290

25

选择海文选择成功

层，分别是分布协调功能DCF子层和点协调功能PCF子层。通过协调功能来确定在基本服务集BSS中的移动站发送数据或者接收数据的时间。为了避免碰撞，规定所有的站在完成发送后，必须再等待一段时间才能发送下一帧。

CSMA/CD协议不能用于无线局域网，，主要有下列原因：第一，CSMA/CD协议要求一个站点在发送本站数据的同时还必须不间断地检测信道，以便发现是否有其他的站也在发送数据，这样才能实现―碰撞检测‖的功能，但是在无线局域网的设备中要实现这种功能花费太大；第二，即使能够实现碰撞检测的功能，且当发送数据的时候检测到信道是空闲的，在接收端仍然有可能发生碰撞，表明碰撞检测对于无线局域网没有发挥作用；第三，无线信道还由于传输条件特殊，造成信号强度的动态范围非常大，是发送站无法使用碰撞检测的方法确定是否发生了碰撞。所以，无线局域网不能使用CSMA/CD，而只能使用改进的CSMA/AD协议。

隐蔽站问题：当A和C都检测不到 无线信号时，以为B是空的，向B发送

数据，结果B同时收到A和C发送的数 据，发生碰撞，这就是隐蔽站问题。使用 与帧后，B处在A的传输范围，可以收 到A发送的RTS，当请求允许后，B将会 向其他站点发送CTS。当C收到B的 CTS后，在A和B通信的时间内就不能

发送数据，保证了A和B的正常通信。

暴露站问题：当站B向A发送数据， 而C又想和D通信时，由于C检测到了 媒体上有信号，于是不能向D发送数据。 这就是暴力站问题。使用RTS和CTS

帧后，在A和B通信的时间内C能收到B的RTS，但是收不到A的CTS，所以C可以发送自己的数据给D也不会干扰B。

可以看到通过使用RTS和CTS较好的解决了隐藏站和暴露站的问题。

B C D ·· ·

A B C

· · ·

A · http://www.vipkaoyan.com

26

本文来源：https://www.bwwdw.com/article/l5tg.html