计算机专业（基础综合）模拟试卷102

计算机专业(基础综合)模拟试卷102

一、单选题(本题共40题，每题1.0分，共40分。)

1、假设n是描述问题规模的非负整数，下面程序片段的时间复杂度为()。void

fun(intn){inti,j»k；for(i=l;i<=n;i++)for(j=l;j<=n;j++){k=l；while(k<=n

k=5*k;}}

A、O(n2Iog2n)

O(nlog5n)

C、O(n-log5n)

D、O(n3)

标准答案：C

知识点解析：首先抓基本运算语句，即k=5*k：设其执行时间为T(n)。对于j每循

环一次，该语句的执行次数为m,有5msn,即mSlog5n。所以，

T(n)=Xni=IXnj=1m=m£ni=i\=mn2=n2log5n=0(n2log5n)

2、以下说法正确的是I.带头结点的循环双链表L为空的条件是：

L—prior==L&&L—next=L口.线性表的插入和删除总是伴随着大量数据的移动

m.只有删除静态链表的尾结点才不需要移动元素W.若线性表采用链式存储结

构，要求内存中可用存储单元的地址必须不连续

A仅

、I

B仅

、I、n

c仅

、、

DIm

、、n、in和w

标准答案：A

知识点解析：I：循环双链表为空时头结点如图所示。

图1-6空循环双链表可见当满足L—»prio=L&&L—>next=L时，双链

表为空，并且循环双链表与循环单链表一样，没有空指针域，所以I正确。n：

链表也是线性表，链表的插入和删除操作不需要大量的数据移动，所以n错误。

m：静态链表尽管使用的是数组存储方式，但是数据之间是靠指针(游标)相互关联

的，故不管是删除静态链表中的哪一个结点，都不需要移动元素，只需要修改指针

即可，所以田错误。IV：线性表采用链表存储，前驱和后继之间的联系需要依靠

由前驱指向后继的指针，而与前驱和后继在内存中的物理位置无关，因此对于整条

链表的存储，不需要划分一块连续的存储空间；但将链表中结点挨个连续存储在一

片空间中也耒尝不可。对于线性表的链式存储，连续或者不连续的存储空间都能满

足要求，所以W错误。

3、循环队列用数组存放其元素值，已知其头尾指针分别是fron【和

rear(且队尾指针rear指向队尾元素的下一个元素)，则当前队列中的元素个数是

()o

A、(rear-front+m)%m

B>(rcar-tront+l)%m

C、rear-front-1

D、rear-front

标准答案：A

知识点解析：因为是循环队列，所以应该分为rear>front和rearVfront两种情况来

讨论。(1)当rear〉front时，队列中元素个数为rear-fron【=(rear-front+m)%m因为0

Vrear-frontVm,所以rcar-ront+m与m取余后结果还是rear-fronto(2)当rcar<

front时，队列中元素个数为m-(front-rear)=rear-front+m=(rear-front+in)%m因为0V

rear-front+m<rn,所以rear-front+in与m取余后结果还是rear-front+mo综合⑴、

(2)可知，A选项正确。

4、下列关于二叉树的叙述中正确的是()。I.对于任何一棵二叉树，叶子结点数

都是度为2的结点数加1n.二义树的左右子树不可以任意地交换in.二义树只

适合使用链式结构存储，不可能用顺序结构存储iv.结点按层序编号的二叉树，

第i个结点的左孩子(假设存在)的编号为2i

A、仅I、n

B、仅口

c、仅口、w

D、仅n、in

标准答案：B

知识点解析：I：I的描述只有在非空二叉树的情况下才成立，所以考生在做这种

概念题目的时候一定要先想到这种特殊情况，所以I错误。n：二叉树的左右子

树是有顺序的，不能随意交换，所以口正确。m：一般的二叉树确实不能使用顺

序结构存储，但是完全二叉树和满二叉树一般都使用顺序结构存储，所以ni错误。

iv：该结论只对完全二义树才成立，所以w错误。综上所述，只有n正确。

5、若二叉树是由森林变换而来的，若森林中有n个非终端结点，则二叉树中无右

孩子的结点有()。

A、n-1

B、n

C、n+1

D、n+2

标准答案：C

知识点解析：由于森林中每一个非终端结点（根结点除外）的所有儿子在转换成二叉

树之后，只有一个儿子的右孩子为空，根结点中本身有一个在转化成二叉树后右孩

子为空，如图1-7所示，所以共有n+1个。

A、000,001,010,Oil,1

B、0000,0001,001,01,1

C、000,001,01,10,11

D、00,100,101,110,111

标准答案：D

知识点解析：赫夫曼树中只有度为0或2的结点，由D选项可以画出对应的二叉

树，如图1-8所示。图"D选项对应的二叉树由赫夫曼树的性质可知，树

中不应该含度为1的结点，因此D选项不可能。

7、在具有n个顶点的图G中，若最小生成树不唯一，贝心）。I.G的边数一定大

于n-1n.G的权值最小的边一定有多条HI.G的最小生成树代价不一定相等

A仅

、I

B仅

、I、n

c仅

、I、n

D仅

、

标准答案：A

知识点解析：最小生成两边的权值之和最小，若两棵树同时为最小生成树，那么它

们的边的权值之和一定相等，故in错误；既然最小生成树不唯一，并且最小生成树

的边都为n-l条，说明图G的边数一定会大于n-l,故I正确；最小生成树不唯

一，和G的权值最小的边的条数没有任何关系，故口错误。

8、图1-1中强连通分量的个数为（）。图有向图中的连通分量

A、2

B、3

C、4

D、5

标准答案：C

知识点解析：在有向图G中，如果两个顶点增、灯间有一条从盯到vj的有向路

径，同时还有一条从vj到环的有向路径，则称两个顶点强连通。如果有向图G的

每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强

连通分量。本题中可以看出v2、v3、v4同属于一个连通分量，另外vl、v5、v6各

自属于一个强连通分量，所以共有4个强连通分量。

9、在一棵二叉排序树上，查找关键字为35的结点，依次比较的关键字有可能是

()o

A、28,36,18,46,35

B、18,36,28,46,35

C、46,28,18,36,35

D、46,36,18,28,35

标准答案：D

知识点解析：可以根据选项画出查找路线上的结点，根据一叉排序树的规定来排除

不满足条件的选项。根据题目选项所得查找路线如图1-9所示。

28的右子树中出现了小于它的18,不满足二叉排序树规定，排除。B选项中36

的左子树中出现了大于它的46,不满足二叉排序树规定，排除。C选项中28的左

子树中出现了大于它的36,不满足二叉排序树规定，排除。补充：在关键字随机

分布的情况下，用二叉徘序树的方法进行查找，其查找长度相当于折半查找的时间

复杂度，即O（log2n）。平衡二叉树的查找效率最高，因为二叉树的查找效率取决于

二叉树的高度，对于结点个数相同的二叉树，平衡二叉树的高度最小。

10、排序趟数与序列的原始状态无关的排序方法是（）。I.直接插入排序D.简

单选择排序m.冒泡排序W.基数排序

A、仅I、m

B、仅I、U、IV

c、仅I、口、m

D、仅I、W

标准答案：B

知识点解析：直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为

n-l（n为元素数）。简单选择排序：每趟排序都是选出一个最小（或最大）的元素，所

以排序趟数固定为n-l（n为元素数）。交换类的排序：其趟数和原始序列状态有

关，所以冒泡排序与初始序列有关。基数排序：每趟排序都要进行“分配”和“收

集”，排序趟数固定为d（d为组成元素的关键字位数）。综上所述，I、H、W都是

无关的，所以选B。

11、下列关于外部排序说法正确的是（）。

A、内存与外设交换信息的时间只是外部排序总时间的一小部分

B、外部排序就是在外存上进行排序，无需内存参与

C、败者树是一棵完全二叉树

D、置换-选择排序得到的初始归并段长度一定相等

标准答案：C

知识点解析：A：影响外部排序时间的主要因素就是内存与外设交换信息的总次

数，所以A错误。B：外部排序也是在内存上进行排序，只不过需要分为多步而

己，所以B错误.C：从败者树的构建方式可知，败者树是一棵完全二叉树，所

以C正确。

12、、③、④和⑤的名称分别是

图1-2计算机硬件系统基本组成部件

()o

A、①控制器、②运算器、③存储器、④输入设备、⑤输出设备

B、①运算器、②控制器、③存储器、④输入设备、⑤输出设备

C、①运算器、②存储器、③控制器、④输入设备、⑤输出设备

D、①运算器、②控制器、③存储器、④输出设备、⑤输入设备

标准答案：B

知识点解析：图中实线框为CPU,而CPU包含五大部件中的运算器和控制器，排

除C选项。控制器为计算机提供工作统一的时钟及其发出各种控制命令来协调计

算机的各部件自动地工作，所以控制器应该与其他四大部件相连，可得①为运算

器，②为控制器。最后，根据数据的流向可以判断，④为输入设备，⑤为输出设

备。剩下③为存储器。

13、已知小写英文字母“a”的ASCII码值为61H,现字母“g”被存放在某个存储单元

中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是

()。

A、167H

B、E6H

C、67H

D、E7H

标准答案：D

知识点解析：由于“屋，的ASCII码值为61H,而“g”是第7个字母，所以可以得到

“g”的ASCII码值应为61H+6=67H=1100lllBo现在“g”的ASCII码值中有5个

“1”，按照偶校验的规见，应该在最高位上添加一个1,使得力”的个数为偶数个，

最后可得该存储单元中存放的十六进，制数为E7H(HI00111)o

14、页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小

为4KB,地址变换过程如图1-3所示，图中逻辑地址用十进制数表示。逻辑地址经

过变换后，十进制数物理地址a应为()。

控制寄存器逻辑地址

图1・3页式存储系统的逻辑地址变换过程

A、33220

B、8644

C、4548

D、2500

标准答案：A

知识点解析：本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统

管理中，逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页

面的大小为4KB,逻根地址8644除以4096,取整为2,取余为452。页号为2,

查页表得物理块号为8。因此，a的有效地址为8x4096+452=33220。

15、下列关于Cache和虚拟存储器的说法中，错误的有()。I.当Cache失效(即

不命中)时，处理器将会切换进程，以更新Cache中的内容U.当虚拟存储器失效

(如缺页)时，处理器将会切换进程，以更新主存中的内容HI.Cache和虚拟存储器

由硬件和OS共同实现，对应用程序员均是透明的虚拟存储器的容量等于主存

和辅存的容量之和

A、I、W

R、HI、IV

c、I、n、m

D、i、m、w

标准答案：D

知识点解析：Cache和虚拟存储器的原理是基于程序访问的局部性原理，但它们实

现的方法和作用均不相同。Cache失效与虚拟存储器失效的处理方法不同，Cache

完全由硬件实现，不涉及软件端；虚拟存储器由硬件和OS共同完成，缺页时才会

发出缺页中断，故I错误，II正确，ID错误。在虚拟存储器中，主存的内容只是辅

存的一部分，W错误。

16、在计算机体系结构中，CPU内部包括程序计数器(PC)、存储器数据寄存器

(MDR)、指令寄存器(IR)和存储器地址寄存器(MAR)等。若CPU要执行的指令为

MOVR0,#100(即将数值100传送到寄存器R0中)，则CPU首先要完成的操作是

()。

A、100—RO

B、100—MDR

C、PJMAR

D、PC—IR

标准答案：c

知识点解析：取指周期完成的微操作序列是公共的操作，与具体指令无关。CPU

首先需要取指令，取指令阶段的第一个操作就是将指令地址（PC中的内容）送往存

储器地址寄存器。题干中虽然给出了一条具体的指令“MOVR0,#100-,实际上

CPU首先要完成的操作是取指令，与具体指令没有关系。

17、某机器采用16位单字长指令，采用定长操作码，地址码为5位，现已定义60

条二地址指令，那么单地址指令最多有（）条。

A、4

B、32

C、128

D、256

标准答案：A

知识点解析：首先可以计算出操作码字段的长度为16-5-5=6。所以一共可以定义

26=64条指令，既然二地址指令占了60条，且是定长操作码，故单地址指令最多

可以有64-60=4条，所以选A°

18、在一条无条件跳转指令的指令周期内，程序计数器（PC）的值被修改了（）次。

（注：指令均为单字长指令，且按字寻址）

A、1

B、2

C、3

D、不能确定

标准答案：B

知识点解析，（1）取指周期结束后，PC的值自动加1（因为指令为单字长指令，且按

字寻址，故PC+1）。（2）在执行周期中，PC的值修改为要跳转到的地址。综上所

述，在一条无条件跳转指令的指令周期内，程序计数器（P。的值被修改了2次。

19、当有中断源发出请求时，CPU可执行相应的中断服务程序，以下可以提出中

断请求的是（）。I.外部事件D.CacheDI.浮点运算下溢H.浮点运算上溢

A、仅I、m

B、仅n、迎、iv

C、仅I、W

D、仅I、m、w

标准答案：C

知识点解析：I:外部事件是可以提出中断请求的，如可以通过敲击键盘来中止现

在正在运行的程序，这个就可以看作一个中断，所以I可以。n：Cache是属于存

储设备，不能提出中断请求，所以n不可以。m、IV：浮点运算下溢，可以当作

机器零处理，不需要中断来处理；而浮点运算上溢，必须中断来做相应的处理，所

以in不可以，w可以。

20、假定一个高速缓存(MI)和存储器(M2)的层次结构有以下性能。Ml：16KB,存

取时间为50ns；M2：1MB,存取时间为400ns。高速缓存块为8B,组大小为256

个字，采用组相联映射，高速缓存命中率h=0.95时的有效存储器存取时间是()。

A、50ns

B、60ns

C、70ns

D、80ns

标准答案：c

知识点谕析：平均存取时间是按照对不同的存储模块的存取时间进行加权平均而

得，即T=T]+(l-H)T2=50+(l-95%)x400=70ns。这里H是高速缓存块的命中率。本

题设置了很多干扰数据，平均存取时间与两个存储模块的存取时间以及高速缓存命

中率有关，在已知命中率的情况下，对于采用什么形式的映射和存储容量来说己经

不重要了；另外还有一点非常重要：对于以上公式的解读，可以这样来理解，无论

怎么存取，每次肯定是要访问高速缓存块的，这是一部分，另外还有一部分(1-H)

的概率要访问存储器：当然也可以分为命中时的存取时间HTi加上不命中时的存

取时间(1-H)(T[+T2)。

21、下面关于PCI总线的基描述中，错误的有()。I.PCI总线是一个与处理器性

能相关的高速外围总线n.PCI总线可对传输信息进行奇偶校验m.PCI设备一

定是主设备W.系统中允许有多条PCI总线

仅In

A、

仅nn

B、

仅nw

、

C仅

In

D、

标准答案：D

知识点解析：PCI总线与CPU及时钟频率都无关，故I错误；PCI总线支持即播即

用并且可对数据和地址进行奇偶校验，并且PCI总线采用猝发传送方式，故口正

确；主设备指获得总线控制权的设备，所以PCI设备不一定都是主设备，故HI错

误；系统中肯定允许有多条PCI总线，以此来提升计算机的效率，故W正确。

22、下列说法正确的是()。

A、在统一编址方式下，访问主存储器和访问I/O设备是通过不同的指令来区分

的

R、计算机的外围设备就是指输入和输出设备

C、中断隐指令属于程产控制型指令

D、在中断服务程序中，恢复现场之前需要关中断

标准答案：D

知识点解析：A：在统一编址方式下，访问主存储器和访问I/O设备是通过不同

的地址码来区分的；在独立编址方式下，访问主存储器和访问I/O设备是通过不

同的指令来区分的，所以A错误。B：除主机外的硬件装置统称为外围设备或外

部设备，包括输入、输出设备和外存储器，所以B错误。C：中断隐指令并不是

一条真正的指令，因此不可能把它预先编入程序中，只能在响应中断时由硬件直接

控制执行，它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断隐指

令不在指令系统中，不属于程序控制指令，所以C错误。

23、操作系统必须提供的功能是（）。

A、GUI

B、为进程提供系统调用命令

C、处理中断

D、编译源程序

标准答案：C

知识点解析：A错误，GUI是GraphicUserInterface（图形用户界面）的缩写。GUI是

为方便用户使用而出现的，实际上它的功能通过各种指令来实现，操作系统可以不

提供这个功能。B错误，对于系统调用来说，用户程序想要得到操作系统的服

务，必须使用系统调用（或机器提供的特定指令），但对于用户程序来说，当不要求

得到操作系统服务时，为其进程提供系统调用命令并不是必需的。D错误，编译

程序，对于操作系统来说一般是不提供这项功能的。对于各种源程序，通常都有相

应的编译程序或者编译数。C正确，中断是操作系统必须提供的功能，开机时程

序中的第一条指令就是一个Jump指令，指向一个中断处理程序的地址，进行开机

自检等一系列操作。

24、以下服务中，能发挥多线程系统的特长的是（），I.利用线程并发地执行矩

阵乘法运算口.Web服务器利用线程请求HTTP服务HI.键盘驱动程序为每一个

正在运行的应用配备一个线程，用来响应相应的键盘输入W.基于GUI的

debugg"用不同线程处理用户的输入、计算、跟踪等操作

A、I、m

B、ii、in

c、i、n>in

D、i、口、w

标准答案：D

知识点解析：在多线程操作系统中，通常一个进程中包括多个线程，每个线程都是

作为利用CPU的基本单位，是花费最小开销的实体。线程具有下述属性：（1）轻型

实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少，即能保证独立

运行的资源。它包含了一个线程ID、一个程序计数器、一个寄存器组和一个堆

栈。（2）独立调度和分派的基本单位。（3）可并发执行。（4）共享进程资源。在同一

进程中的各个线程，都可以共享该进程所拥有的资源，包括共享代码段、数据段以

及其他的操作系统资源（如打开的文件）等。多线程最大的优点就是并发执行。在4

个服务中，只有键盘操作是无法并发执行的，因为整个系统只有一个键盘，而且键

盘输入是人的操作，速度比较慢，完全可以使用一个线程来处理整个系统的键盘操

作，所以选择D。

25、现在有3个同时到达的作业JI、J2和J3,它们的执行时间分别为Tl、T2和

T3,且T1VT2VT3。如果该系统中有两个CPU,各自按照单道方式运行且采用短

作业优先算法，则平均周转时间是()。

A、(T1+T2+T3)/3

B、(2T1+T2+T3)/3

C、(T1+2T2+T3)/3

D、(211+12+13)/3或(T1+2T2+T3)/3

标准答案：B

知识点解析：JI、J2和J3同时在0时刻到达，按短作业优先算法，选择儿和J2执

行,则儿和J2等待时间为0。又因为T1VT2,所以J1先于J2完成，即在T2时

刻，释放CPU,J3开始，则J3的等待时间为T1。然后J2完成，最后J3完成。J1

周转时间为Tl。J2周转时间为T2。J3周转时间为T1+T3。所以平均周转时间为

(2T1+T2+T3)/3o周转时间=等待时间+运行时间=结束时间-到达时间

26、对计数型信号量S执行V操作后，下列选项错误的是()。I.当S.value<0

寸，唤醒一个阻塞队列进程口.只有当S.valueV(T寸，唤醒一个阻塞队列进程

HI.当S.valued)时，唤醒一个就绪队列进程W.只有当S.valueVO时，唤醒

一个就绪队列进程

A、n、皿

B、口、①、W

C、I、皿

D、I、皿、W

标准答案：B

知识点解析：I正确。当执行V操作后，S.value<o,说明了在执行V操作之前

S.valneVO(此时S.value的绝对值就是阻塞队列中进程的个数)，所以阻塞队列

必有进程在等到，所以需要唤醒一个阻塞队列的进程。口错误。由I的分析可

知，S.values。就会唤醒。因为可能在执行V操作前，只有一个进程在阻塞队

列，也就是说S.vatue=-l,执行V操作后，唤醒该阻塞进程，S.value=OoDI和

W错误。S.value的值却就绪队列中的进程没有此层关系，所以全错。综上所

述，本题选B。

27、设有8页的逻辑空间，每页有1024B,它们被映射到32块的物理存储区中。

那么逻辑地址的有效位是()，物理地址至少是()位。

A、10,12

B、10,15

C、13,15

D、13,12

标准答案：C

知识点解析：对于逻辑地址结构，因为8页-3页，所以表示页号的地址有3位，

乂因为每页有1024B=2i°B,所以页内偏移地址有10位。因此总共逻辑地址有13

位。对于物理地址结构，因为页面的大小和物理块的大小是一样的，所以每个物

理块也是1024B,而内存至少有32块物理块，所以内存大小至少是

32X1024B=215BO因此物理地址至少要15位，不然无法访问内存的所有区域。

28、某虚拟存储器的用户编程空间共32个页面，每页1KB,主存为。16KB。假定

某时刻用户页表中已调入主存的页面的虚页号和物理页号对照表为表1-1,则与表

表1-1页面映射表

虚页号物理页号

05

110

24

37

表十六进制虚地址

对应的物理地址

虚地址物理地址

0A5C(1)

IA5C(2)

1-2十六进制虚地址对应的物理地址为（）。----------

A、1E5C,2A5C

B、1E5C,缺页中断

C、125C,2A5C

D、125C,缺页中断

标准答案:D

知识点解析：每页1KB,默认字长为1B,那么页内地址需要10位，则剩下的6位

为虚页号。计算过程如表1-8所示。

表1・8十六进制虚地址及物理地址

上六进制废地址0A5CIA5C

二进制虚地址00001010010111000001101001011100

二进制虚页号000010000110

二选制物理页号000100燃页中断

二进制页内地址1001011100

二进制物理地址0001001001011100

上六进制物理地址125C

29、假定有一个请求分页存储管理系统，测得系统各相关设备的利用率如下：CPU

利用率为10%,磁盘交换区为99.7%,其他I/O设备为5%。试问：下面措施

中将可能改进CPU利用率的是（）。I.增大内存的容量D.增大磁盘交换区的容

量m.减少多道程序的道数W.增加多道程序的道数V.使用更快速的磁盘交换

区VI.使用更快速的CPU

A、i、口、m、iv

B、I、川

c、u、m、v

D、n.vi

标准答案：B

知识点解析：I正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因

而减少换入和换出过程，可提高CPU利用率。II错误。因为系统实际已处于频繁

的换入和换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量

无用。in正确。因为从给定的条件中可看出磁盘交换区的利用率为99.7%,说明

系统现在已经处于频繁的换入和换出过程中，可减少主存中的程序。W错误。系

统处于频繁的换入和换出过程中，再增加主存中的用户进程数，只能导致系统的换

入和换出更频繁，使性能更差。V错误。因为系统现在处于频繁的换入和换出过

程中，即使采用更快的磁盘交换区，其换入和换出频率也不会改变，因此采用V

的做法没用。VI错误。系统处于频繁的换入和换出过程中，CPU处于空闲状态，

利用率不高，提高CPU的速度无济于事。综上所述，本题选B。

30、DOS和Windows操作系统都支持FAT16文件系统，该文件系统中，一个文件

的物理结构（即该文件占磁盘上哪些块号，通常称块号为簇号）用文件分配表FAT

来表示，文件分配表FAT的每个表项占16位。如果某分区为FAT16磁盘文件系

统，每簇64扇区，扇区的大小为512B,则该分区最大可为,每个FAT表

占用存储空间是______o（）

A、1GB,8MB

B、1GB,16MB

C、2GB,8MB

D、2GB,16MB

标准答案：C

知识点解析：FAT16文件系统中，文件分配表FAT的每个表项占16位，那么就是

说每个分区最大可存放216个簇，乂每个簇为64x512bit=215B,则该分区最大可

存放216x215B=2GB。每个扇区需要占用一个表项，扇区数=216x64=222,那么

FAT表所需存储空间=222xl6bit=223B=8MB。

31、一个交叉存放信息的磁盘，信息存放方式如图1-4所示。每个磁道有8个扇

区，每个扇区512B,旋转速度为3000转/分。假定磁头已在读取信息的磁道上，

0扇区转到磁头下需要1/2转，且设备对应的控制器不能同时进行输入/输出，

在数据从控制器传送全内存的这段时间内，从磁头下通过的扇区数为2,问依次读

取一个磁道上所有的扇区的数据到内存平均传输速度为()。

图1-4磁盘中信息存放方式

A、57.IKB/s

B、67.IKB/s

C、77.1KB/s

D、87.IKB/s

标准答案：A

知识点解析：在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为

2。当数据从控制器传送至内存后，磁头开始读数据时，刚好转到目标扇区。所以

总时间为总时间=初始寻找0扇区时间+读扇区总时间+将扇区数据送入内存总时间

由题中条件可知，旋转速度为：3000r/min=50r/s,即20ms/r。读一个扇区需

要时间：20/8ms=2.5ms读一个扇区并将扇区数据送入内存需要时间：

2.5x3ms=7.5ms读出一个磁道上的所有扇区需要时间：20/

2ms+8x7.5ms=70ms=0.07s每磁道数据量为8x512B=4KB数据传输速度为4KB

/0.07s=57.1KB/s所以依次读出一个磁道上的所有扇区需要0.07s,其数据

传输速度为57.IKB/s。

32、假设T是从磁盘输入一块数据到缓冲区需要的时间，C是CPU对一块数据进

行处理的时间，而M是将一块数据从缓冲区传送到用户区的时•间。当一用户进程

要按顺序访问的方式处理大量数据时，请问在单缓冲和双缓冲的情况下，系统对一

块数据的处理时间分别是()。

A、inax(T,C)+M,max(T,M+C)

B、max!(T,M+C),max(T,C)+M

Cymax(T,M)+C,max(T,M+C)

D、max(T,M+C),max(T,M)+C

标准答案：A

知识点解析：单缓冲工作示意图和时序图如图1-11所示。从图中可以看出：数据

由I/O控制器到缓冲区和数据由缓冲区到工作区必须申行操作；同样，数据从缓

冲区到工作区和CPU从工作区中取出数据进行处理也需串行进行：但由于在顺序

访问时可采用预先读的方式，即CPU在处理一块数据(从工作区取数据)的同时可

从磁盘输入下一块数据，所以系统对一块数据的处理时间为max(T,C)+Mo

用户进程

处理（C）

工作区缓冲区I/O设备

T

a）单缓冲工作示意图

b）中堞冲时序曲

图1/1单辍冲工作示意图与时序图双缓冲的工作示意图和时

序图如图1・12所示。由此可见，数据由I/O控制器到双缓冲和数据由双缓冲区到

工作区可以并行工作，因此，系统对一块数据的处理时间为max（T,M+C）。

处理（C）

工作区

缓

冲

区

2

a）双城冲工作示意图

「（援冲1）可缓冲2）A爆冲D

Ia

:Mi;

b）双缓冲时序图

图1・12双缓冲工作示意图与时序图

33、计算机网络可分为通信子网和资源子网，下列属于通信子网的是（）。I.网

桥n.交换机ni.计算机软件w.路由器

A、I、口、IV

B、口、皿、IV

C、I、皿、W

D、I、口、W

标准答案：A

知识点解析：从计算机网络组成的角度来看，典型的计算机网络从逻辑功能上可以

分为两部分：资源子网和通信子网。资源子网：由主计算机系统、终端、终端控

制器、联网外部设备、各种软件资源与信息资源等组成。资源子网负责全网的数据

处理业务，负责向网络用户提供各种网络资源与网络服务。通信子网(包括物理

层、数据链路层、网络层)：由通信控制处理机、通信线路与其他通信设备组成，

完成网络数据传输、转发等通信处理任务。

34已知循环冗余码生成多项式G(X)=X5+X4+X+1,若信息位为10101100,则冗余

码是()。

A、01101

B、01100

C、1101

D、1100

标准答案：B

知识点解析:(1)确定生成多项式G(x户xS+x4+x+l,次数r=5,对应位串110011。

⑵在信息位串后补5个。即1010110000000,对应的多项式x『M(x)。(3)用模2不

借位除法，计算x「M(x)/G(x)的余数R(x),R(x)就是冗余码。具体用110011除

1010110000000余数为01100,冗余码是OHOOo

35、若子网掩码为255.255.0.0,则下列()IP与其他地址不在同一网络中？

A、172.25.15.200

B、172.25.16.15

C、172.25.25.200

D、172.35.16.15

标准答案：D

知识点解析：将子网掩码与IP地址按位与，得A、B、C各IP地址所在的网络号

为172.25.0.0：D中1P地址所在网络号为172・35.0.0,故D中的1P地址与其

他地址不在同一个网络中。一般对于这种求分别网络号是否一样的题目，只要抓住

IP地址从第几个字段开始不一样，然后开始将此字段按二进制展开，逐位与运

算，这种方法几乎在分析IP地址时都会用到。

36、在IPv6协议中，一个数据流可以由()进行标识。

A、源地址、目的地址和流名称

B、源地址、目的地址和流标号

C、源地址、端口号和流标号

D、MAC地址、端口号和流名称

标准答案：B

知识点解析：流就是Internet上从特定主机的源站到特定的目的站的单播或组播数

据分组，所经过的路径上的路由器都能保证指定的服务质量。头部中的源地址、目

的地址和流标号字段唯一地标识了一个流。

37、使用CIDR技术把4个网络100.100.0.0/18、100.100.64.0/18、

100.100.128.0/18.100.100.192.0/18汇聚成一个超网，得到的地址是

()。

A、100.100.0.0/16

B、100.100.0.0/18

C>100.100.128.0/18

D、100.100.64.0/18

标准答案：A

知识点解析：网络号中第几个字段不相同，就把第几个字段按二进制展开，结果如

下：100.100.00000000.0/18100.100.01000000.0/18

100.100.10000000.0/18100.100.11000000.0/18很明显从第三个字段的

第一位开始就已经不同，按照CIDR的规则，找到最大能涵盖这四个网络的网络

号，故超网的网络号是100.100.0.0/16o

38、A和B之间建立了TCP连接，A向B发送了一个报文段，其中序号字段

scq=300,确认号字段ACK=101,数据部分包含7个字节，那么在B对该报文的确

认报文段中（）。

A、seq=301,ACK=101

B、seq=301,ACK=108

C^seq=101,ACK=101

D、seq=101,ACK=307

标准答案：D

知识点解析：首先，B发送给A的报文中，seq的值应和A发送给B的报文中的

ACK值相同，即101；而ACK的值表示B期望下次收到A发出的报文段的第一个

字节的编号，应是300+7=307。

39、设某TCP的拥塞窗口的慢启动门限值初始为8（单位为报文段，且最大报文段

长度为1KR）,当拥塞窗口卜升到12时,网络会发生超时.按照以卜给出的条件.

第12次传输时，拥塞窗口的大小为（）。

A、5

B、6

C、7

D、8

标准答案：B

知识点解析：在慢启动和拥塞避免算法中，拥塞窗口初始值为1,窗口大小开始按

指数增长。当拥塞窗口大于慢启动门限后，停止使用慢启动算法，改用拥塞避免算

法。此时，慢启动的门限值初始为8,当拥塞窗口增大到8时改用拥塞避免算法，

窗口大小按线性增长，每次增长1个报文段。当增加到12时，出现超时，重新设

置门限值为6（12的一半），拥塞窗口再重新设为1,执行慢启动算法，到门限值为

6时执行拥塞避免算法。按照上面的算法，拥塞窗口的变化为I、2、4、8、9、

10、11、12、1、2、4、6、7、8、9…，从该序列可以看出，第12次传输时拥塞窗

口大小为6。

40、一台主机的域名是CS.zju.edu.cn,它位于DNS层次结构的第（）层（根结点

是第一层）。

A、3

B、4

C、5

D、6

标准答案：c

知识点解析：既然根结点是第一层，那么将域名从右往左拆开一共有4个，分别是

cn（第二层）、cdu（第三层）、zju（第四层）、cs（第五层），所以它位于DNS层次结构的

第5层。

二、综合应用题（本题共28题，每题7.0分，共28

分。）

41、有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设

G=（V,E）是一个具有n个顶点的带权连通无向图，T=（U,TE）是G的最小生成

树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的坡小

生成树T的步骤如下：（1）初始化U={u}。以u到其他顶点的所右边为候选边。（2）

重复以下步骤n-1次，使得其他n-1个顶点被加入到U中。从候选边中挑选权值最

小的边加入到TE,设该边在V-U中的顶点是v,将v加入U中。考查顶点v,将

v与V-U顶点集中的所有边作为新的候选边。若此方法求得的T是最小生成树，

请予以证明。若不能求得最小生成树，请举出反例。

标准答案：此方法不能求得最小生成树。例如，对于图7-1la所示的带权连通无向

图，按照上述方法从顶点0开始求得的结果为图7-11b所示的树，显然它不是最小

生成树，正确的最小生成树如图7-11c所示。在有些情况下，上述方法甚至无法求

得最小生成树。例如对于图7-Ud所示的带权连通无向图，从顶点0出发，找到顶

点1（边（0,1））,从顶点1出发，找到顶点3（边（1,3））,再从顶点3出发，找到顶

点0(边(3,0)),这样构成回路，就不能求得最小生成树了。

图7-11

知识点解析：暂无解析

已知由nJ个关键字组成的序列(K|,K2,Ke)是大顶堆，现在增加一个关键

字Kn，要求将关键字序列(Ki，K2，…，Kn-bKn)，重新调整为大顶堆。请完成

以下要求：

42、给出算法的基本设计思想。

标准答案：基本设计思想：从根结点的父母结点的标号[n/2]开始向上，对每个当

前结点和左右子树进行调整。最开始的时候要判断n是左结点还是右结点，之后的

情况一定是左右结点都有。每次把当前结点的标号除以2则得到当前结点的父母结

点的标号。

知识点解析：暂无解析

43、根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

标准答案：算法实现如下：#definen100；//宏定义n常量，由用户自定义结点

个数intK|n|;//关键字序列voidheap(){inti=n/2；//找到最后一个结点的

父母结点if(n%2==l)//当n是右结点时{if(K[i]VK[n=l]&&K[n.l]>

K[n])swap(K[n-i],K[i])；//sw叩0实现交换两个元素if(K[i]VK[n]&&K[n-l]V

K[n]}swap(K(n],K[i])；}else//当n是左结点{if(K[i]VK[n])swap(K[n],

K[i])；}i=i/2；while(i>0)//依次向上调整{if(K[i]<K[n-1]&&K[n-1]>

K[n])swap(K[n-l],K[i])；if(K[i]<K[n]&&K[n-1]<K[n])swap(K[n],K[i])；i=i/

2;I}

知识点解析：暂无解析

44、说明你所设计算法的时间复杂度。

标准答案：时间复杂度分析：在循环当中，我们可以看出每次都是对结点的父母结

点进行调整，因此操作次数正好是树的高度，时间复杂度为O(log2n)。

知识点解析：暂无解析

假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取

1000B的数据到主存缓冲区中，该I/O设备一旦启动即按50KB/s的数据传输率

向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时

钟周期，则以下4种方式下，在1000B的读取过程中，CPU用在该设备的I/O操

作上的时间分别为多少。占整个CPU时间的百分比分别是多少？

45、采用定时查询方式，每次处理一个字节，一次状态查询至少需要60个时钟周

期。

标准答案：主频为1GHz,所以时钟周期为1/lGHz=InSo因为每个字节的读取、

处理并存入内存缓冲区需要1000个时钟周期，所以，对于像程序查询和中断等用

软件实现输入/输出的方式，CPU为每个字节传送所用的时间至少为

1000xlns=1000ns=lpso在50kB/s的数据传输率下，设备每隔IB/50kB/

s=20RS=20000ns准备好一个字节，因而读取1000B的时间为lOOOx2O|4s=2Oms0定

时查询方式下的I/O过程如图7-12所示。用户可以设置每隔20000ns查询一次，

这样使得查询程序的开销达到最小，即第一次读取状态时就可能会发现就绪，然后

用1000个时钟周期进行相应处理，因此，对于每个字节的传送，CPU所用时钟周

期数为60+1000=1060。因此，在1000B的读取过程中，CPU用在该设备的I/O

操作_L的时间至少为1000xl060xlns=l.060ms,占整个CPU时间的百分比至少为

1.060/20=5.3%。

执行其他用户程序［矽丁丽

执行其他用户程序

有闻就绪20000

图7・12定时查询方式下的I/O过程

知识点解析：暂无解析

46、采用独占查询方式，每次处理一个字节，一次状态查询至少需要60个时钟周

期。

标准答案：独占查询方式下的I/O过程如图7-13所示。启动设备后，CPU就开始

查询，因为333x60+20=20000,所以第一个字节传送在第334次读取状态查询时检

测到就绪，随后用1000个时钟周期进行相应的处理，然后继续第二个字节的状态

查询，因为40+1000+316x60=20000,所以，第二个字节的传送在第316次读取状

态查询时检测到就绪，第一个和第二个字节的传送过程如图7-13a所示。每次检测

到就绪后，就进行相应的处理，然后周而复始地进行查询，因为(20000-1000)/

60=316.7,所以,第317次状态查询时发现就绪。因为1000+60x317-20000=20,

所以，每3B可多60个时钟周期，正好进行一次状态查询，因此，在剩下的998B

的读取过程中，前996B的传送正好用了996x20000个时钟周期，如图7/3b所

示。最后两个字节的传送过程如图7-13c所示，因为2x(1000+60x317-20000)=40,

此外，最后一个字节的处理还有1000个时钟周期，所以最后两个字节总的时间为

2x20000+40+1000=41040个时钟周期。综上所述，CPU用在该设备的I/O操作

上的总时间为1000x20000ns+1040x1ns=20.00104msi20ms,即在1000B的整个传

row।60*60*।60।60।fooo_160*~~~-i-ooo

、_/OUvU

-罩复始进行状态查询M绪j就绪

就绪20000设番完成20000设备完成

O最后两个字节的查询过程

图7/3独占查询方式下的I/O过程

知识点解析：暂无解析

47、采用中断I/O方式，外设每准备好一个字节发送一次中断请求。每次中断响

应需要2个时钟周期，中断服务程序的执行需要1200个时钟周期。

标准答案：中断方式下的I/O过程如图7-14所示。中断方式下，外设每准备好一

个字节请求一次中断，每次中断CPU所用时钟周期数为2+1200=1202,因此CPU

用在该设备的I/O操作上的时间为1000xl202xlns=l.202ms,占整个CPU时间

的百分比至少为1.202/20=6.01%。

1200।1200।

21执行我他用户程序执行其他用户程序

7

中断请求20000中断请求20000

图7-14中断方式下的I/O过程

知识点解析：暂无解析

48、采用周期挪用DMA方式，每挪用一次主存周期处理一个字节，一次DMA传

送完成1000B的传送，DMA初始化和后处理的时间为2000个时钟周期，CPU和

DMA之间没有访存冲突。

标准答案：DMA方式下，由于CPU和DMA没有访存冲突，所以不需考虑由于

DMA而影响到CPU执行其他程序。因此，传送1000BCPU所用的时钟周期数就

是2000,在I000B的读取过程中，CPU用在该设备的I/O操作上的时间为

2000x1ns=2ps,占整个CPU时间的百分比为2/(1000x20)=0.01%。

知识点解析：暂无解析

49、如果设备的速度提高到5MB/s,则上述4种方式中，哪些是不可行的?为什

么?对于可行的方式，计算出CPU在该设备I/O操作上所用的时间占整个CPU时

间的百分比。

标准答案：若设备数据芍输率为5MB/S,则外设传输1000B所用时间为1000B/

(5x106B/s)=200uso对于定时查询和独占查询方式，传送1000BCPU所用时间至

少为1000x(60+1000)x1ns=1060|is；对于中断方式，传送1000BCPU所用时间为

1000x(2+1200)xlns=l202|^So上述3种方式下，CPU所用的时间都比设备所用时

间长得多，即设备的传输比CPU的处理快得多，因而发生数据丢失。因此，这3

种方式都不能用于该设备的I/O操作。对于DMA方式，传送1000BCPU所用时

间为2000xins=2ns,占整个CPU时间的百分比为2/200=1%。这说明可以使用

DMA方式，不过由于外设传输速度加快，使得CPU频繁进行DMA预处理和后处

理，因而CPU的开销从0.01%上升到了1%。中断方式的计算，可以先求出Is

内该外设请求的中断次数为1/(IB/50kB)=50k,然后得到1s内CPU用于数据I

/O的时钟周期数为50kx(2+1200)=6.OlxIO7,因此在该设备传输过程中，CPU

用于该设备I/O操作的时间占整个CPU时间的百分比为6.OlxlO7/

1G=6.01%。

知识点解析：暂无解析

硬磁盘共有4个记录面，存储区域内半径为10cm,外半径为15.5cm,道密度为

60道/cm,外层位密度为600bit/cm,转速为6000r/min。问：

50、硬磁盘的磁道总数是多少？

标准答案：有效存储区域=15.5cm-10cm=5.5cm,道密度=60道/cm,因此每个

面60道/cmx5.5cm=330道,即有330个柱面,磁道总数=4x330道=1320道。

知识点解析：暂无解析

51、硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两

者之间有什么关系？

标准答案：外层磁道的长度为2兀R=2x3.14x15.5cm=97.34cm每道信息量

=600bit/cm^97.34cm=58404bit=7300.5B磁盘总容量=7300.5BX1320道

=9636660B(非格式化容量)磁盘在使用之前要对其执行格式化操作，要首先完成划

分磁道和扇区，设置文件目录区等。非格式化容量是指一个盘片上可以记录的二进

制位的总数量，而格式化容量通常是指用户可用空间的二进制位的总数量，前者比

后者要大，因为系统要管理磁盘会占用一定的存储空间，还要使用一个磁道用于同

步，扇区之间还有间隔和一些为保存检错纠错信息的空间，磁盘上往往还会留有一

些备份磁道。在谈到磁盘容量时，通常指的是格式化之后用户可用的磁盘容量。

知识点解析：暂无解析

52、将长度超过一个磁道容量的文件记录在同一个柱面上是否合理？

标准答案：如果长度超过一个磁道容量的文件，将它记录在同一个柱面上比较合

理，因为不需要重新寻找磁道，这样数据读/写速度快。

知识点解析•：暂无解析

53、采用定长数据块记录格式，直接寻址的最小单位是什么?寻址命令中磁盘地址

如何表示？

标准答案：采用定长数据块格式，直接寻址的最小单位是一个扇区，每个扇区记录

固定字节数目的信息，在定长记录的数据块中，活动头磁盘组的编址方式可用如下

硬盘号~柱面号磁头号~扇区号…山…*_「夕门、…,

格式：------------------------------------此地址格式表示最多可以接4

台硬盘，每台最多有8个记录面，每面最多可有128个磁道，每道最多可有16个

扇区。

知识点解析：暂无解析

54、假定每个扇区的容量512B,每个磁道有12个扇区，寻道的平均等待时间为

10.5ms,试计算读出磁盘一个扇区中数据的平均时间。

标准答案：读一个扇区中数据所用的