计算机统考模拟题及答案.docx

计算机统考模拟题及答案.docx

《计算机统考模拟题及答案.docx》由会员分享，可在线阅读，更多相关《计算机统考模拟题及答案.docx（13页珍藏版）》请在冰点文库上搜索。

计算机统考模拟题及答案

2009年计算机统考试题

一﹑单项选择题：

1~40小题，每小题2分，共80分。

在每小题给出的四个选项中，请选出一项最符合题目要求的。

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

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

2一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是______。

A．不确定          B．n-i+1          C．i           D．n-i

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

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.成本低

C．容量大D.灵活性好

12数据发生溢出的根本原因是_______。

A．数据的位数有限

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

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

D．数据运算中的错误

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

A．增大主存容量B.增大辅存容量

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条B．3条

C．2+D．2n+2

21以下叙述错误的是______。

A．产生中断请求信号后，一般由硬件和中断屏蔽字完成中断的裁决和中断源识别

B．在多级中断中，CPU本身也有优先级

C．软中断是由程序员安排的指令（称为软中断指令和陷阱指令）引起的

D．DMA比通道具有更强的独立处理数据输入输出的功能。

22磁盘设备适宜于连接到______通道。

A．字节多路通道或数据组多路通道

B．字节多路通道或选择通道

C．数组多路通道或选择通道

D．任一种

23分时操作系统的主要目标是 ______。

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．dB．d+1                C．d+2   D．2d+1

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

A．帧同步功能     B．电路管理功能

C．差错控制功能     D．流量控制功能

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

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

37HDLC是一种_________协议。

A．面向比特的同步链路控制        B．面向字节数的异步链路控制

C．面向字符的同步链路控制        D．面向比特的异步链路控制

38下面关于网桥的说法中不正确的是_______。

A．网桥工作在数据链路层，对网络进行分段，并将整个物理网络连接成一个逻辑网络。

B．网桥可以通过对数据进行过滤，有效地组织广播数据

C．网桥可以连接数据链路层协议不同的局域网

D．网桥要处理器接收到的数据，增加了传播时延

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

_______

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

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

C．当一个路由器发现自己的一条直接相邻链路断开时，没能将这个变化报告给其他路由器

D．慢收敛导致路由器接受了无效的路由信息

40PING使用了哪个协议？

_______

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 求信息码01101110的海明校验码，画出能指出2位出错和纠正一位出错位的海明校验逻辑。

（15分）

4 什么叫页式虚拟存储器？

什么叫页表？

说明工作原理。

（6分）

5 有一个虚拟存储系统,分配给某个进程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 什么是AND信号量?

试利用AND信号量写出生产者－消费者问题的解法。

（9分）

7 在数据传输速率为50kb/s的卫星信道上发送长度为1kb的帧。

假设确认总是由数据帧捎带。

帧头很短，帧序号的长度为3比特。

对于下列三种协议可以取得的最大利用率是多少？

（假设卫星信道端到端的单向传播延迟时间为270ms）

（1） （3分）停止等待协议；

（2） （3分）后退N滑动窗口协议；

（3） （3分）选择重发滑动窗口协议。

参考答案

一．选择题 

1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

B 

C 

D 

B 

C 

B 

A 

D 

A 

B 

11 

12 

13 

14 

15 

16 

17 

18 

19 

20 

C 

D 

D 

C 

D 

C 

A 

A 

D 

B 

21 

22 

23 

24 

25 

26 

27 

28 

29 

30 

D 

A 

D 

D 

C 

A 

C 

B 

A 

A 

31 

32 

33 

34 

35 

36 

37 

38 

39 

40 

B 

A 

B 

B 

C 

A 

D 

D 

C 

A 

选择题部分答案解析：

1.此题考察各数据结构的特点。

栈的特点是先进后出。

队列的特点是先进先出。

树的特点是节点的前驱只能有一个的数据结构。

图是最复杂的数据结构，它是前驱和后继都可以有多个的网状结构。

2.元素abcdefg依次进入栈，bdcfeag依次出队，那么他们在栈中操作顺序依次为：

a入栈、b入栈、b出栈、c入栈、d入栈、d出栈、c出栈、e入栈、f入栈、f出栈、e出栈、a出栈、g入栈、g出栈。

这其间栈中数据最多有3个。

3.一看第一个遍历出来的元素是3，所以后序遍历

4.平衡二叉树，又称AVL树。

它或者是一棵空树，或者是具有下列性质的二叉树：

它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

5.第6层有8个叶节点，说明这个完全二叉树最多共7层，所以树的节点数为：

1+2+4+8+16+32+48=111。

8.B树是一种多叉平衡查找树。

一棵m阶的B树，或为空树，或为满足下列特性的m叉树：

　　①树中每个结点至多有m棵子树；

　　②若根结点不是叶子结点，则它至少有两棵子树；

　　③除根之外的所有非叶子结点至少有「m/2]棵子树；

　　④所有的非叶子结点中包含卞列数据信息

　　　（n，A0，K1，A1，K2，A2，…，Kn，An）

　　其中：

Ki（i=1，2，…，n）为关键字，且Ki

Ai（i=0，1，…，n）

　　⑤所有的叶子结点都出现在同一层次上，并且不带信息（可以看作县外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

9.堆调整算法的应用

10.解此题必须熟知各种排序方法的步骤。

11.考察CPU区分指令和数据的方法：

取指令和取数据发生在指令的不同阶段。

13.熟悉浮点运算过程

14.熟悉组相联映射的方式。

组相联的映象规则：

（1）主存和Cache按同样大小划分成块。

（2）主存和Cache按同样大小划分成组。

　　（3）主存容量是缓存容量的整数倍，将主存空间按缓冲区的大小分成区，主存中每一区的组数与缓存的组数相同。

　　（4）当主存的数据调入缓存时，主存与缓存的组号应相等，也就是各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放，即从主存的组到Cache的组之间采用直接映象方式；在两个对应的组内部采用全相联映象方式。

15.需要ROM片数：

4K*8/2K*8=2，需要RAM片数：

60K*8/4K*4=30.

16.相对寻址：

以当前程序计数器pc的内容为基址，加上指令给出的一字节补码数（偏移量）形成新的pc值的寻址方式称为相对寻址。

17.精简指令集的特点：

统一指令编码（例如，所有指令中的op-code永远位于同样的位位置、等长指令），可快速解译；

　　泛用的缓存器，所有缓存器可用于所有内容，以及编译器设计的单纯化（不过缓存器中区分了整数和浮点数）；

　　单纯的寻址模式（复杂寻址模式以简单计算指令序列取代）；

　　硬件中支持少数数据型别（例如，一些CISC计算机中存有处理字节字符串的指令。

这在RISC计算机中不太可能出现）。

RISC设计上同时也有哈佛内存模块特色，凡指令流和数据流在概念上分开；这意味着更改代码存在的内存地址对处理器执行过的指令没有影响（因为CPU有着独立的指令和数据缓存），至少在特殊的同步指令发出前。

在另一面，这允许指令缓存和数据缓存同时被访问，通常能改进运行效率。

18.时钟周期以最大的流水段为准

19.硬布线控制器是早期设计计算机的一种方法。

硬布线控制器是将控制部件做成产生专门固定时序控制信号的逻辑电路，产生各种控制信号，因而又称为组合逻辑控制器。

这种逻辑电路以使用最少元件和取得最高操作速度为设计目标，因为该逻辑电路由门电路和触发器构成的复杂树型网络，所以称为硬布线控制器。

微程序控制的基本思想，就是仿照通常的解题程序的方法，把操作控制信号编成所谓的“微指令”，存放到一个只读存储器里．当机器运行时，一条又一条地读出这些微指令，从而产生全机所需要的各种操作控制信号，使相应部件执行所规定的操作

20.10M/2*4=20MB/S

21.（1000-50）/1000=95%

25.K的最小值是4，当K为4是，每个进程若占用2台打印机，则发生死锁。

27.段号占8位，则段内地址24位。

也就是2^24位，即2^21字节。

29.SCAN调度算法就是电梯调度算法，顾名思义就是如果开始时磁头往外就一直要到最外面，然后再返回向里（磁头编号一般是最外面为0号往里增加），就像电梯若往下则一直要下到最底层才会再上升一样。

32.无论有多少物理设备都要映射为逻辑设备使用。

这些设备在程序员看来是没有差别的。

33.传输层和应用层都是端到端的。

自下而上次一个端到端的是传输层。

35.在后退N协议式ARQ中，接收方应以正确的顺序把沙鸥到的报文递交到主机。

发送方在不等待确认就连续发送许多帧的情况下，有可能发了N个帧以后，才发现尚未收到对前面帧的确认信息，也许某个帧在传输过程中出错了。

接收方因这一帧出错，查出后不会交给本地主机，对后面再发送来的N个帧也可能均不接收而丢弃。

换句话说，接收方只能按顺序接收。

36.以太网交换机工作在物理层，所以进行交换决策时使用的是物理地址。

38.主机乙发送给主机甲的确认序列号是期待接收到的数据的序列号

39.拥塞控制是指节制沿着一条通路的分组流以保持网络部件免于变得过量拥挤所采用的控制规程。

二．综合应用题

41.该方法求得的路径不一定是最短路径。

例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。

42.

（1）算法基本思想如下：

从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。

当遍历到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。

（2）详细实现步骤：

增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当前遍历的节点，指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头节点。

用整型变量i表示当前遍历了多少节点，当i>k时，指针p随着每次遍历，也向前移动一个节点。

当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。

（3）算法描述：

IntLocateElement（linklistlist,intk）

{

P1=list->link;

P=list;

i=1;

while（P1）

{

P1=P1->link;

i++;

if（i>k）p=p->next;//如果i>k,则p也往后移

}

if（p==list）return0;//说明链表没有k个结点

else

{

printf（“%d\n“,p->data）;

return1;

}

}

43.

（1）在中断方式下，每32位（4B）被中断一次，故每秒中断

0.5MB/4B=0.5×106/4=12.5×104次

要注意的是，这里是数据传输率，所以1MB=106B。

因为中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间，且执行每条指令平均需5个时钟周期，所以，1秒内用于中断的时钟周期数为

（18+2）×5×12.5×104=12.5×106

（2）在DMA方式下，每秒进行DMA操作

5MB/5000B=5×106/5000=1×103次因为DMA预处理和后处理的总开销为500个时钟周期，所以1秒钟之内用于DMA操作的时钟周期数为

500×1×103=5×105

故在DMA方式下，占整个CPU时间的百分比是

（（5×105）/（500×106））×100%=0.1%

44.指令执行阶段每个节拍的功能和有效控制信号如下所示

时钟

功能

有效控制信号

C5

MAR←（R1）

PCout,MARin

C6

MDR←M（MAR）

MemR,MDRinE

C7

A←（R0）

R0out,Ain

C8

AC←（MDR）+（A）

MDRout,Addr,ACin

C9

MDR←（AC）

ACout,MDRin

C10

M（MAR）←MDR

MDRoutE,MemW

45.定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。

程序如下：

Vars1=0,s2=0,empty=N,mutex=1;

Parbegin

P1:

begin

X=produce（）;/*生成一个数*/

P（empty）;/*判断缓冲区是否有空单元*/

P（mutex）;/*缓冲区是否被占用*/

Put（）;

Ifx%2==0

V（s2）;/*如果是偶数，向P3发出信号*/

else

V（s1）;/*如果是奇数，向P2发出信号*/

V（mutex）;/*使用完缓冲区，释放*/

end.

P2:

begin

P（s1）;/*收到P1发来的信号，已产生一个奇数*/

P（mutex）;/*缓冲区是否被占用*/

Getodd（）;

Countodd（）:

=countodd（）+1;

V（mutex）;/*释放缓冲区*/

V（empty）;/*向P1发信号，多出一个空单元*/

end.

P3:

begin

P（s2）/*收到P1发来的信号，已产生一个偶数*/

P（mutex）;/*缓冲区是否被占用*/

Geteven（）;

Counteven（）:

=counteven（）+1;

V（mutex）;/*释放缓冲区*/

V（empty）;/*向P1发信号，多出一个空单元*/

end.

Parend.

46.

（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。

页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位