计算机专业(基础综合)模拟试卷146(题后含答案及解析)

计算机专业（基础综合）模拟试卷146 (题后含答案及解析)

题型有：1. 单项选择题 2. 综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1． 此程序的复杂度为( )。 for(int i=0；i<n；i++) for(int j=m；j>0；j--) A[i][j]=i+j；

A．O(m2) B．O(n2) C．O(m*n2) D．O(m+n)

正确答案：C

解析：内层循环语句最多执行次数为m*n。

2． 一个具有1025个结点的二叉树的高h为( )。 A．11 B．10

C．11至1025之间 D．10至1024之间

正确答案：C

解析：一棵二叉树每层只有1个结点，则具有1025个结点的二叉树的最大高度为1025。一个具有1025个结点的完全二叉树的高度为11。这一个具有1025个结点的二叉树的高h为11至1025之间。

3． 构造操作系统的主要结构模式是( )。Ⅰ整体式结构 Ⅱ层次式结构 Ⅲ微内核(客户／服务器)结构 Ⅳ对称式结构

A．I和Ⅲ B．Ⅱ和Ⅳ

C．Ⅰ、Ⅱ和Ⅲ D．Ⅱ、Ⅲ和Ⅳ

正确答案：C 解析：操作系统是一种大型的、复杂的系统软件，为了合理地使用操作系统，必须分析、了解并掌握其结构。在操作系统的发展过程中，出现了多种操作系统结构，整体式结构是早期操作系统设计中所采用的方法，即首先确定操作系统的总体功能，然后将总功能分解为若干个子功能，实现每个子功能的程序称为模块。层次式结构力求使模块问调用的无序性变为有序性。因此层次式结构最内层是裸机，裸机的外层是操作系统的第一层，以后每增加一层软件就是在原虚拟机上的又一次扩充，又成为一个新的虚拟机。微内核(客户／服务器)结构的操作系统适

宜于应用在网络环境下分布式处理的计算环境中。内核只提供了一个很小的功能集合。除内核部分外，操作系统所有的其他部分被分成若干个相对的进程，每一个进程实现一组服务，称为服务进程。这些服务进程可以提供各种系统功能、文件系统服务以及网络服务等。对称式结构在操作系统结构设计中是不存在的。

4． 在基址寻址方式中，若基址寄存器BR的内容为2D3 CH，形式地址A的内容为53 H，则有效地址EA为( )。

A．53H B．2D3CH C．2D8FH D．803CH

正确答案：C

解析：基址寻址方式下，EA=(BR)+A，结合题中条件，EA=(BR)+A=2D3C16+5316=2D8F16，选C。

5． 假设栈的容量为3，入栈的序列为1、2、3、4、5，则出栈的序列可能为( )。Ⅰ．5、4、3、2、1Ⅱ．1、5、4、3、2Ⅲ．3、2、1、5、4Ⅳ．4、3、2、1、5

A．Ⅰ、Ⅲ B．只有Ⅲ C．Ⅱ、Ⅲ D．只有Ⅳ

正确答案：B

解析：此题有一个陷阱，因为没有按照常规的思路出题。这种题型在2009年的真题第2题中反着考过一次，是给出一个入栈和出栈的序列（通过出队序列可以知道出栈的序列），要求考生算出栈的容量。首先，由于栈的容量只有3，很明显4和5不能第一个出来，所以先排除I和Ⅳ；再看Ⅱ，1入栈，l出栈，然后只有2、3、4、5同时入栈，5才能第二个出栈，所以要实现这种出栈序列，栈的容量至少要为4，与题意矛盾，故只有Ⅲ才是可能的出栈序列。

6． 设CPU与I／O设备以中断方式进行数据传送。当CPU响应中断时，该I／O设备接口控制器送给CPU的中断向量表(中断向量表存放中断向量)的指针是0800H，0800H单元中的值为1200H，则该I／O设备的中断服务程序在主存中的入口地址为( )。

A．0800H B．0801H C．1200H D．1201H

正确答案：C 解析：首先需要明白中断向量就是中断服务程序的入口地址，所以需要找到指定的中断向量。中断向量是保存在中断向量表中的，而0800H是中断向量表

的地址，所以0800H的内容即是中断向量。

7． 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是( )。

A．11 B．10 C．9 D．8

正确答案：B

解析：n个结点的无向图中，边数e≤n(n-1)／2，将e=36代入，有n≥9，现已知无向图非连通，则n=10。

8． 下面的地址中，属于单播地址的是( )。 A．10．3．2．255/24 B．172．31．129．255/18 C．192．168．24．59/30 D．224．100．57．211

正确答案：B 解析：A选项：10.3.2.255/24所表示的子网掩码是11111111 11111111 11111111 00000000，即后8位为主机号，很明显主机号全为1，所以10.3.2.255/24是子网10.3.2.0的一个广播地址。B选项：与A选项类似，可以得到主机号为00000111111111。由此可知，172.31.129.25 5/18是一个单播IP地址。C选项：与A选项类似，可以得到主机号为11。由此可知，192.168.24.59/30属于子网192.168.24.56的一个广播地址。D选项：224.100.57.211为D类IP地址，即组播地址。

9． 进程从运行状态转换为就绪状态的可能原因是( )。 A．被调度程序选中占用处理机 B．等待某一事件

C．等待的事件已经发生 D．时间片用完

正确答案：D 解析：就绪状态是指一个进程获得了除处理机以外的一切资源，当得到调度时，就由就绪状态转换为运行状态；运行状态就是一个进程在处理机上正在运行。当处于运行状态的进程在运行过程中所分配的时间片用完，则会被强制撤离处理机，以便调度其它进程运行。由于原先运行的进程是非自愿地离开运行状态，所以没有其它的事件相关，只有继续在就绪队列中等候下一次的调度，所以D是正确的。A的情形是由就绪状态转换为运行状态；B的情形是由运行状态转换为阻塞状态；C的情形是由阻塞状态转换为就绪状态，均不正确，正确答案应选D。本题主要考察学生对进程状态以及相互转换的关系，难度也并不高，改变一下问题的问法，ABC三个答案均会有可能。

10． 已知10个数据元素为(，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为( )。

A．2 B．3 C．4 D．5

正确答案：B

解析：参考二叉排序树的建立。将这10个元素按照依次插入结点的方法生成一棵二叉排序树后，62位于这棵二叉排序树的第三层，查找值为62的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的深度。

11． 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一元素，其存储地址为1，每个元素占一个地址空间，则a8,5的地址是( )。

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

正确答案：B

解析：这里数组下标从1开始，只存储其下三角形元素，在a8,5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7／2=2 8个元素，在第8行中，a8,5的前面有4个元素，所以，a8，5前有28+4=32个元素，其地址为33。

12． 若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有树的数目是( )。

A．k B．n C．n-k D．n+k

正确答案：C 解析：因为一棵具有n个顶点的树有n一1条边，因此设题目中的森林有m棵树，每棵树具有顶点数为Vi(1≤i≤m)，则V1+V2+…Vm=N及(V1一1)+(V2一1)+…(Vm一1)=K，所以n=m+k。

13． 一台装有Linux系统的主机，只有两个账号root和guest，下面关于“Linux是一个多用户、多任务的操作系统”的理解中，正确的有( )。 Ⅰ．该主机允许root和guest同时登录，因为LinUX系统支持多用户 Ⅱ．该主机不允许root和guest同时登录，因为Linux系统最多只能有一个活跃用户

Ⅲ．该主机允许多个客户端通过root账号登录，因为Linux系统支持多任务 Ⅳ．该主机不允许多个客户端通过同一账号登录，因为Linux用户只能有一个活跃客户端

A．Ⅰ和Ⅲ B．Ⅰ和Ⅳ C．Ⅱ和Ⅲ D．Ⅱ和Ⅳ

正确答案：A

解析：这里的“账号”等价于“用户”。 Ⅰ正确很容易理解，支持多用户，肯定就是支持同时登录。 Ⅲ正确，多个客户端通过同一账号登录，这些个客户端其实运行的只是一个进程。Linux支持多任务的系统，所以肯定是可以的。 知识点扩展： Linux是一个多用户、多任务的操作系统，考生应该了解单用户多任务和多用户多任务的概念。 (1)Linux的单用户、多任务。 例如，以beinan登录系统，进入系统后，要打开gedit来写文档，但在写文档的过程中，感觉少点音乐，所以又打开xmms来点音乐；当然听点音乐还不行，MSN还得打开，想知道几个朋友现在正在做什么。这样，在用beinan用户登录时，执行了gedit、xmms以及msn等，还有输入法fcitx。这样说来就有点简单了，一个beinan用户，为了完成工作，执行了几个任务；当然beinan这个用户，其他的人还能以远程登录过来，也能做其他的工作。 (2)Linux的多用户、多任务。 有时可能是很多用户同时用同一个系统，但并非所有的用户都一定要做同一件事，所以这就有多用户、多任务。 例如，LinuxSir．org服务器，上面有FTP用户、系统管理员、Web用户、常规普通用户等，在同一时刻，可能有人正在访问论坛；有人可能在上传软件包管理子站，如luma或Yuking在管理他们的主页系统和FTP；与此同时，可能还会有系统管理员在维护系统；浏览主页用的是nobodv用户，大家都用同一个，而上传软件包用的是FTP用户；管理员对系统的维护或查看，可能用的是普通账号或超级权限root账号；不同用户所具有的权限也不同，要完成不同的任务就需要不同的用户，也可以说不同的用户，可能完成的工作也不一样。 值得注意的是，多用户、多任务并不是大家同时挤到一起在一台机器的键盘和显示器前来操作机器，多用户可能通过远程登录来进行，比如对服务器的远程控制，只要有用户权限任何人都是可以上去操作或访问的。

14． 磁盘和磁带是两种存储介质，他们的特点是( )。 A．二者都是顺序执行的 B．二者都是随机存取的

C．磁盘是顺序存取的，磁带是随机存取的 D．磁带是顺序存取的，磁盘是随机存取的

正确答案：D

解析：本题主要考查磁盘和磁带的工作方式的区别。

15． 关于ICMP协议的说法正确的是( )。Ⅰ．ICMP消息的传输是可靠的Ⅱ．ICMP被封装在IP数据报的数据部分Ⅲ．ICMP可用来进行拥塞控制

A．仅Ⅰ B．Ⅰ和Ⅱ C．Ⅱ和Ⅲ D．Ⅰ和Ⅲ

正确答案：C

解析：Ⅰ：由于IP层提供的是无连接不可靠的服务，所以ICMP消息的传输是不可靠的，故Ⅰ错误。 Ⅱ：ICMP报文整个被作为IP分组的数据部分，所以Ⅱ正确。 Ⅲ：主机在发送数据报时，经常会由于各种原因发送错误，比如路由器拥塞丢弃了或者传输过程中出现错误丢弃了，如果检测出错误的路由器或主机都能把这些错误报告通过一些控制消息告诉发送数据的主机那就好了，那么发送数据的主机就可根据ICMP报文确定发生错误的类型，并确定如何才能更好地重发失败的数据报。比如ICMP报文发过来的是改变路由，那么主机就不能继续按照这个路由线路发送了，需要用另外一条路由线路发送数据，所以Ⅲ正确。 注1：ICMP报文包含的不仅是出错类型，而且还要包含出错IP数据报的数据部分的前8个字节。因为前8个字节包含了TCP和UDP报文首部巾的TCP或UDP端口号，这样源主机可更好地和用户进程(用户进程需要IP地址和端口号才能唯一确定)联系起来，因为发送数据的是某个主机中的某个进程而不足主机本身，这样才算是真正找到了发送数据源。 注2：常用的ping命令使用了回送请求报文，以探测目标主机是否可达；如果在IP数据报传送过程中，发现生命周期字段为零，则路由器发出超时报文。

16． 若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式最节省时间的是 ( )。

A．单链表 B．双链表

C．单循环链表 D．顺序表

正确答案：D

解析：线性表中常用的操作是取第i个元素，所以应选择随机存取结构，即顺序表，同时在顺序表中查找第i个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便，双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。

17． 下列程序段的时间复杂度是( )。 int i，j； for(i=m+l；i<=m+n；i++){ A[0]=A[i]； for(j=i-1；A[j]>A[i]；j--){ A[j+1]=A[j]； } }

A．O(m2) B．O(n2) C．O(m*n) D．O(m+n)

正确答案：C

解析：时间复杂度由m，n共同决定，最坏情况F的时间复杂度为O(mn)。

18． 将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较次数是( )。

A．1 B．n-1 C．n D．2n

正确答案：C

解析：假设有两个有序表A和B都递增有序，当有序表A所有元素均小于B的元素时，只需将A的所有元素与B的第一个元素比较即可，其比较n次。

19． “总线忙”信号由( )建立。 A．获得总线控制权的设备 B．发出“总线请求”的设备 C．总线控制器 D．CPU

正确答案：A

解析：在总线控制机制中，准备使用总线的设备向总线控制器发出“总线请求”由总线控制器进行裁决。如果经裁决允许该设备使用总线，就由总线控制器向该设备发出一个“总线允许”信号。该设备接收到此信号后，发出一个“总线忙”信号用来通知其他设备总线已被占用。当该设备使用完总线时，将“总线忙”信号撤销，释放总线。因此“总线忙”信号是由获得总线控制权的设备建立的。

20． 在UNIX系统中，将一个文件卷复制到另一个磁盘上。只复制文件数据，包括目录之后( )。

A．文件数据能够被访问 B．文件目录能够被访问

C．文件数据和目录都能被访问 D．文件数据和目录都不能访问

正确答案：D

解析：UNIx系统中每个文件卷需要经过安装后才能使用。所以只复制文件数据，包括目录后，是都不能访问的。即使物理介质本身在工作，但若其上的文件卷没有安装好，系统也无法存取其中的信息。uNIx需要安装文件卷后才可以被访问。

21． 某计算机采用微程序控制，微指令字中操作控制字段共12位，下列说法正确的是( )。 Ⅰ．若采用直接控制，则此时一条微指令最多可同时启动1 2个微操作 Ⅱ．若采用字段直接编码控制，并要求一条微指令需同时启动3个微操作，则微指令字中的操作控制字段应分6段 Ⅲ．若采用字段直接编码控制，并要求一条微指令需同时启动3个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含45个微操作命令

A．仅Ⅰ、Ⅱ B．仅Ⅰ、Ⅲ C．仅Ⅱ、Ⅲ D．Ⅰ、Ⅱ和Ⅲ

正确答案：B

解析：对于Ⅰ选项：如果12个微操作都相容的话，最多可以同时启动12个微操作，故Ⅰ正确。对于Ⅱ选项：首先，如果要同时启动3个微操作，那么这3个微操作必须是相容的，所以要将控制字段分为3段，也就是每段占4位，故Ⅱ错误。对于Ⅲ选项：由Ⅱ的分析可知，由于每段占4位，每个字段可表示15种状态(保留一个状态表示不发微命令)，那么一共就可以表示45个状态，故Ⅲ正确。

22． 无向图G有16条边，有3个度为4的顶点，4个度为3的顶点，其余顶点的度均小于3，则G至少有( )个顶点。

A．10 B．11 C．12 D．13

正确答案：B 解析：度的定义指的是进入一个顶点的边数和从该顶点出去的边数之和。我们可以根据这个关系来求解此题。由于题目已经告诉度为4的顶点有3个，度为3的顶点有4个，其余的顶点的度均小于3，而已知有16条边，则总的度数应为16×2=32。所以要求最小的顶点个数，我们应当尽量增加每个顶点的度数，这里将剩下的结点的度数全部看成2，设结点数为x，则3×4+4×3+(x-3-4)×2≥32，解得x至少为11。

23． 若循环队列以数组Q[0．．m一1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear＝(rear＋1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。

A．rear—length

B．(rear—lengh＋m)MOD m

C．(1＋rear＋m—length)MOD m D．m—length

正确答案：C

解析：按照循环队列的定义，因为元素移动按照rear＝(rear＋1)MOD m进行，则当数组Q[m＝1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear—length＋1＋m)MOD m。

24． TCP的通信双方，有一方发送了带有FIN标志的数据段后表示( )。 A．将断开通信双方的TCP连接

B．单方面释放连接，表示本方已经无数据发送，但是可以接收对方的数据

C．中止数据发送，双方都不能发送数据 D．连接被重新建立

正确答案：B 解析：FIN位用来释放一个连接，它表示本方已经没有数据要传输了。然而，在关闭一个连接之后，对方还可以继续发送数据，所以还有可能接收到数据。

25． 有n个叶子结点的哈夫曼树的结点总数为( )。 A．不确定 B．2n C．2n+1 D．2n-1

正确答案：D

解析：在哈夫曼树中，由计算公式可得，结点总数为2n一1，所以选D。

26． 8086的堆栈采取向下生长的方式，在压入时的操作是( )。 A．SP先减，再压入数据 B．先压入数据，SP再减 C．SP先加，再压入数据 D．先压入数据，SP再加

正确答案：A

解析：8086微处理器中所谓的向下生长堆栈就是自底向上生成的堆栈(即栈底地址大于栈顶地址)，栈指针始终指向栈顶的满单元。

27． 下列关于强连通图的说法中，正确的是( )。 Ⅰ．n个顶点构成的强连通图至少有n条边 Ⅱ．强连通图是任何顶点到其他所有顶点都有边 Ⅲ．完全有向图一定是强连通图

A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ

正确答案：C

解析：Ⅰ：强连通图是相对于有向图而言的，即在有向图G中，任何两个顶点都存在路径。所以最少的情况应该是n个顶点构成一个首尾相连的环，共有n条边，故Ⅰ正确。 Ⅱ：这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。有向图中顶点A和B之间存在边，不能说明A和B是互相连通的，所以说正确的表述应该是：强连通图是任何顶点到其他所有顶点都有路径，故Ⅱ错误。 Ⅲ：完全有向图肯定是任何顶点到其他所有顶点都有路径，故Ⅲ正确。

28． 假设初始为空的散列表的地址空间为(0…10)，散列函数为H(key)=key

mod 11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是( )。

A．4 B．5 C．6 D．8

正确答案：C

解析： 首先通过散列函数H(key)=key mod 11的计算得知，37、95、27、14分别插入到散列表中的4、7、5、3的位置。而48 mod 11=4，但是此时4已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置4的下一个地址，直到此地址为空，发现6为空则插入，故选C选项。 补充：如果此题改为使用平方探测法，则又应该选择哪一个选项? 提示：平方探测法的原理是设发生冲突的地址为d，则平方探测法的探测序列为d+12，d一12，d+22，d一22，…位置4不空时，下一个探测的位置应该为5，发现又不空，则下一个探测的位置应该是3，发现又不空。接着再探测位置8，发现为空，将元素插入，故选D选项。 平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

29． 传输一幅分辨率为0×480，6．5万色的照片(图像)，假设采用数据传输速度为56kb／s，大约需要的时间是( )。

A．34．82s B．42．86s C．85．71s D．87．77s

正确答案：C

解析：照片(图像)的颜色数为65536色，意味着颜色深度为16位，则一幅图占据的存储空间为0×480×16＝4915200位。又因为用数据传输速度为56Kb／s，则有传输时间＝491 5200／(56×1024．)≈85．71s[归纳总结]图片存储的内容就是一幅像点信息，在单色显示时，每个点只用一位二进制代码来表示，在彩色显示时，每个点需要由若干位代码来表示。颜色深度与颜色数的对应关系为： 颜色深度＝log2颜色数 所以图片的容量不仅与分辨率有关，还与颜色数有关。分辨率越高，颜色数越多，图片所占的容量就越大。[解题技巧]首先计算出每幅图的存储空间，然后除以数据传输率，就可以得出传输一幅图的时间。

30． 下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个 Ⅳ．高度为h的完全二叉树最少有2h个结点

A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ、Ⅳ C．仅Ⅰ、Ⅲ、Ⅳ

D．仅Ⅰ、Ⅱ、Ⅲ

正确答案：D

解析：Ⅰ：二叉树叶子结点的个数比度为2的结点的个数多1，故I正确。 总结：这个性质在选择题中常有体现，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少?我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加1，即n+1个。 这个性质还可以扩展，即在一棵度为m的树中，度为1的结点数为n1，度为2的结点数为n2……度为m的结点数为nm，则叶子结点数n0=1+n2+2n3+…+(m-1)nm。推导过程如下： 总结点=-n0+n1+n2+n3+…+nm ① 总分支数=1×n1+2×n2+…+m×nm(度为m的结点引出m条分支) ② 总分支数=总结点数-1 ③ 将式①和式②代入式③并化简得n0=1+n2+2n3+…+(m-1)nm Ⅱ：最少结点的情况应该是除根结点层只有1个结点外，其余4层都有2个结点，因此结点总数为2×(5-1)+1=9。如图6-4所示，故Ⅱ正确。 Ⅲ：由二叉树的性质可知：n0=n2+1，且完全二叉树度为1的结点个数要么为0，要么为1。又因为二叉树的总结点个数n=n0+n1+n2。将n0=n2+1代入，可得n=2n0+n1-1；由于n=1001，得到2n0=1002+n1。 ①当n1=1时，无解。 ②当n1=0时，可解得n0=501 故Ⅲ正确。 Ⅳ：高度为h的完全二叉树中，第1层～第h-1层构成一个高度为h-1的满二叉树，结点个数为2h-1-1。第h层至少有一个结点，所以最少的结点个数=(2h-1-1)+1=2h-1，故Ⅳ错误。

31． 设有一个n阶三对角线矩阵A[n][n]，现把它的三条对角线上的非零元素按行存放到一个一维数组B口中，A[1][1]存放到B[1]中（假定不用O下标），那么B[k]存放的元素的行号是( )。

A．[(k+1)/3] B．[(k+1)/3] C．[(k+2)/3] D．[(k+2)/3]

正确答案：B

解析：这种题目最好采用特殊值法，推导过程可能比较繁琐，见表6—3。

32． 若用一个大小为6的数组来实现循环队列，且当前rear和f．ront的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和Iront的值分别是( )。

A．1和5 B．2和4 C．4和2 D．5和1

正确答案：B

解析：出队1个元素后，front=(front+1)％MAXQSIZE，front的值是4；入队两个元素后，rear=(rear+2)％MAXQSIZE，rear的值是2。

33． 若一个信号量的初值为3，经过多次PV操作以后当前值为－1，此表示等待进入临界区的进程数是( )。

A．1 B．2 C．3 D．4

正确答案：A 34． 某计算机采用页式存储管理，内存中现有1000个页表项，CPIJ的cache中可以存放N个页表项，该系统中，CP[J内存访问的时间为100ns，对cache访问的时间是5ns，如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高于( )。

A．850 B．858 C．923 D．842

正确答案：A

解析：本题考查cache与页式存储管理结合下的时间计算。根据题意，页式寻址方式的过程是这样的：当执行到一个逻辑地址时，MMU首先将页号分离，将得到的页号与cache中的多个页表项比较(同时进行)，若页表项命中，则取出页表项与页内地址相加，形成指令或数据的物理地址，花费5ns，据此地址，然后到内存中取得对应的指令或数据，送到CPU中执行或计算。若不能在cache命中，那么cPu会启动cache更新程序，将新的页表项从内存复制到cache，花费100ns，然后，重复上述地址转换过程，又花去5ns，得到物理地址，再去内存取指令或数据。根据题意，要求得到页框号，也就是物理地址的过程小于20ns，那么设，cache的命中率为x，列关系式：5*x＋(1一x)*(5＋100)＝20解得x为85％。因此，装入cache的页表项应大于1000*85％＝850项，这样可以保证获得页框号的时间小于20ns。 本题若问，一个指令双字的执行时间是多少时，需要考虑的事情就比较复杂。例如系统的字长是否是32位，32位的系统执行一个双字的时间是1次寻址，16位系统就需要2次寻址。8位系统的就需要4次寻址。另外，采用什么内存管理机制，页式和段式都是执行1次指令寻址需要访问内存2次，段页式需要3次。还要看cache的容量多大，指令是否在cache中等，所以，内存管理中寻址时间的计算与CPU结构和cache的运行模式息息相关，考生应结合计算机组成原理，妥善解决此类问题。

35． 下列关于操作系统结构说法中，正确的是( )。 Ⅰ．当前广泛使用的Windows XP操作系统，采用的是分层式OS结构 Ⅱ．模块化的OS结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易 Ⅲ．由于微内核结构能有效支持多处理机运行，故非常合适于分布式系统环境 Ⅳ．采用微内核结构设计和实现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等

A．仅Ⅰ、Ⅱ B．仅Ⅰ、Ⅲ C．仅Ⅲ

D．仅Ⅲ、Ⅳ

正确答案：C

解析：Ⅰ错误，当前比较流行的、能支持多处理机运行的OS，几乎全部都采用微内核结构，包括Windows XP。 Ⅱ错误，模块化OS结构原则是：分解和模块化。Ⅱ中描述的是分层式结构设计的基本原则。 Ⅲ正确。 Ⅳ错误，微内核结构将操作系统的很多服务移动到内核以外(如文件系统)。且服务之间使用进程间通信机制进行信息交换，这种通过进程间通信机制进行信息交换影响了系统的效率，所以微内核结构设计并不会使系统更高效。由于内核的内服务变少了，且一般来说内核的服务越少肯定越稳定。

36． 循环队列用数组A[0…m—1]存放其元素值，头尾指针分别为front和rear，front指向队头元素，rear指向队尾元素的下一个元素，其移动按数组下标增大的方向进行(rear!=m—1时)，则当前队列中的元素个数是( )。

A．(rear—front+m)％m B．(rear—front+1)％m C．real一front一1 D．rear—front

正确答案：A

解析：考查循环队列的性质。分rear＞front和rear＜front两种情况讨论： ①当rear＞front时，队列中元素个数为rear—front=(rear—front+m)％m ②当rear＜front时，队列中元素个数为m一(front—rear)=(rear—front+m)％m 综合①、②可知，选项A正确。

37． 单处理机系统中，可并行的是( )。Ⅰ进程与进程 Ⅱ处理机与设备 Ⅲ处理机与通道 Ⅳ设备与设备

A．Ⅰ、Ⅱ和Ⅲ B．Ⅰ、Ⅱ和Ⅳ C．Ⅰ、Ⅲ和Ⅳ D．Ⅱ、Ⅲ和Ⅳ

正确答案：D

解析：进程和进程是不能并行的，因为只有一个CPU。

38． 图8一1是一棵( )。 A．4阶B一树 B．4阶B+树 C．3阶B一树 D．3阶B+树

正确答案：A

解析：首先很明显不是B+树，因为B+树的叶子结点本身依关键字的大小自小而大顺序链接，故排除B、D选项。另外，B一树有一个性质为：m阶B一树的结点关键字数量最多为m一1个，但是图8—1中有个结点有3个关键字，也就是说此B一树不可能是3阶，故选A选项。

39． 设有一个二维数组A[m][n]在存储中按行优先存放（数组的每一个元素占一个空间），假设A[0][0]存放位置在780clo)，A[4][6]存放位置在1146(10)．则A[6][20]在( )位置(其中(10)表明用十进制数表示）。

A．1342(10) B．1336(10) C．1338(10) D．1340(10)

正确答案：D

解析：由Loc(4，6)=Loc(0，0)+(4×n+6)×1=780+(4×n+6)=1146，n=(1146—780—6)/4=90，则可计算Loc(6， 20)=Loc(0， 0)+(6×90+20)×1=780+560=1340。

40． 不需要抢占的进程调度算法是( )。 A．最早截至时间优先 B．时间片轮转 C．最短时间优先

D．最短剩余时间优先

正确答案：C

解析：最短时间优先算法以进程本次所需CPU时间的长短作为调度的依据来选择进程投入运行，一旦进程获得处理机后就不可被抢占直到本进程执行完毕。而其他3种进程调度算法都是基于抢占的调度算法，当前获得处理机的进程可能被刚进来的进程抢占处理机。故选C。

综合应用题41-47小题，共70分。

下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控制信号，例中yi表示y寄存器的输入控制信号，R1o为寄存器R1的输出控制信号，未标字符的线为直通线，不受控制。

41． “ADDR2，R0”指令完成(R0)+(R2)→R0的功能操作，画出其指令周期流程图，假设该指令的地址已放入PC中。并列出相应的微操作控制信号序列。

正确答案：

42． 若将“取指周期”缩短为一个CPU周期，请先画出修改数据通路，后画出指令周期流程图。

正确答案：[*]

43． 在(2)的基础上，将“执行周期”也缩短为一个CPu周期，先修改运算器数据通路，后画出指令周期流程图。此时加法指令速度比(1)提高几倍?

正确答案：[*]

完成以下各小题。

44． 什么是Belady现象?为什么会产生这种现象?

正确答案：如果某种换页算法，在增加页框数之后反而可能导致更多缺页，这种反常情形称为Belady现象。

45． 页面置换算法FIFO为什么会出现Belady现象?简述理由。

正确答案：FIFO换页策略将最早换人页框的页面换出，而不考虑该页面是否最近使用过，这违背了局部性原理。当页框数较大时，由于包含的页面更多，历史记录更全面，就有可能使最近频繁使用但较早进入页框的页面被换出，从而出现Belady异常。

46． 页面置换算法LRU为什么不会出现Belady现象?简述理由。

正确答案：LRU换页策略将最近最长时间未使用的页面换出，符合局部性原理。当页框数较大时，最近最长未使用的情况更全面，因此缺页数不会增加。

假定A和B是试图在一个以太网上发送的两个站。每个站都有一个稳定的帧的队列准备发送，A的帧编号是A1，A2和A3等，B的帧编号是B1，B2和B3等。再假定指数后退的基本单元时间是T=51．2微秒。现在A和B同时尝试发送1号帧，碰撞，并且刚好分别选择了0×T和1×T的退避时间，也就是说，A赢得了这一次竞争，发送A1，B需要等待。在这次传送结束时，B尝试再发送B1．而A则尝试发送A2。这一轮的首次尝试产生碰撞，此时，A的退避时间从0×T和1×T中选择，而B则从0×T，…，3×T中选择。

47． 给出A赢得第2次退避竞争的概率。

正确答案：A可以选择KA=0或1；B可以选择KB=0，1，2，3。如果(KA，

KB)选择(0，1)，(0，2)，(0，3)，(1，2)，(1，3)中的一个组合，那么将是A赢得这第2次竞争，其概率是5／8。

48． 假定A已赢得了第2次退避竞争。A在成功发送A2后，接着尝试发送A3。当B再次尝试发送B1时，A和B再次碰撞。给出A赢得这第3次退避竞争的概率。

正确答案：现在A是在一次成功发送之后，可以选择KA=0或1；KB是在它的第3次碰撞之后，可能的选择是0，1，2，…，7。如果KA=0，那么KB中有7种选择使得A赢；如果KA=1，那么KB中有6种选择使得A赢。所以A赢得这第3次竞争的概率是13／16。

49． 给出A赢得所有其余后退竞争的概率的合理下限值。

正确答案：A赢得第2次竞争的概率=5／8>1／2A赢得第3次竞争的概率=13／16>3／4类似地，A赢得第4次竞争的概率>7／8一般地，A赢得第i次竞争的概率>(1—1／2i一1)因此，假定A已经赢得第1至第3次竞争，那么A赢得所有其余的后退竞争的概率将不低于：(1—1／8)×(1一1／16)×(1一1／32)×(1一1／)×…≈1—1／8—1／16—1／32—1／一…=6／8=3／4