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

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

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

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

fun(intn){inti»k；fbr(i=1；i<=n；iH--b)for(j=l；j<=n；jH--H){k=l：

whilc(k<=n)k=5*k：)}

A、O(n2log2n)

B、O(nlog5n)

C>O(n2log5n)

D、O(n3)

标准答案：c

知识点解析：基本运算语句是k=5*k,设其执行时间为T(n)。对于j每循环一次，

该语句的执行次数为m,有：5m<n,即mSlog5n。所以：

■_■•■

1mn：22

T(n)=XA"=mXX==nlog5n=0(nlogsn)

f•i

•*

2、利用栈求表达式的值时，设立运算数栈OPND。假设OPND只有两个存储单

元，在下列表达式中，不发生溢出的是()。

A、A—B*(C—D)

B、(A—B)*C—D

C、(A—B*C)—D

D、(A—B)*(C—D)

标准答案：B

知识之解析：利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及进行后

缀表达式求值这两步操作可以和在一起进行，需要设立运算符栈OPTR和运算数

栈OPND两个栈。例如求选项A的表达式A—B*(C—D)的过程如下表所示：

求A-B・（C-D）衰达式值的过程

当前字符运算符枝（）PTR运算数梗OPND说明

AA

——A

B—AB

•一■AB

(一•(AB

C•(ABC

—_•(一ABC：

D—•(-ABCD

一■

)ABTt执行C-D运算•令Ti-C-D

—AT,执行B•「运算,令T?=B・Ti

T,执行ATi运算•令T严A-Ti

按照上述过程可知，选项A求值时，运算数栈。PND的大小至少为4。例如求选

项B的表达式（A—B）*C—D的过程如下表所示：

求（A-B）-C-D表达式值的过程

当前字符运算符枝OPTR运算数枝OPND说明

((

A(A

—(-A

B(-AB

)Ti执行A-B运算•令Ti=A-B

.T1

CT,C

——Ti执行T,・C运H・令Ti-Ti・C

D—T,D

T,执行TLD运算•令TLTLD

按照上述过程可知，选项B求值时，运算数栈OPND的大小至少为2。类似地，

选项C、D求值时，运算数栈OPND的大小至少为3、3。因此本题答案为B。

3、已知输入序列为abed,经过输出受限的双端队列后，能得到的输出序列是（）。

A^dacb

B、cadb

C、dbea

D、以上答案都不对

标准答案：B

知识点解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进

行的队列。分析选项A,输入序列为abed,输出序列为dacb,由输出受限性质可

知以da开头的结果只有dabc,选项A为错误答案。分析选项B,输入序列为

abed,输出序列为cadb,其输入输出顺序为：先在输出端输入a,然后在非输出端

输入b,这时队列中的序列为ba,再在输出端输入c,这时队列中的序列为bac；

输出c,再输出a；再在输出端输入d,这时队列中的序列为bd；输出d,再输出

bo最后得到输出序列为cadb。分析选项C,输入序列为abed,输出序列为

dbea,由输出受限性质可知以db开头的结果只有dbac,选项C为错误答案。

4、一个具有1025个结点的二叉树的高h为（）。

A、11

B、10

C、11至1025之间

D、10至1024之间

标准答案：C

知识点解析：一棵二叉树每层只有1个结点，则具有1025个结点的二叉树的最大

高度为1025o一个具有1025个结点的完全二叉树的高度为11。这一个具有1025

个结点的二叉树的高h为11至1025之间。

5、以下关于二叉排序树的说法正确的是（）。I在二叉排序树中，每个结点的关键

字都比左孩子关键字大，比右孩子关键字小。n每个结点的关键字都比左孩子关

键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。in在二叉排序树

中，新插入的关键字总是处于最底层。w在二叉排序树中，新结点总是作为吐子

结点来插入的。v二又排序树的查找效率和二义排序树的高度有关。

A、I、n、W、v

B、口、皿、IV

C、I、m、V

D、I、W、V

标准答案：D

知识点解析：对于二又徘序树，左子树上所有记录的关键字均小于根记录的关键

字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子

的关键字进行比较。在二叉排序树中，新插入的关键字总是作为叶子结点来插入

的，但是叶子结点不一定总是处于最底层。对于每一棵特定的二义排序树，均可

按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造

所得的不同形态的各棵二叉排序.树的平均查找长度的值不同，甚至可能差别很

大。最好的情况是二义徘序树的形态和折半查找的判定树相同，其平均查找长度和

10g2n成正比。

6、简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个

结点，其邻接矩阵为A[l..n,1.,n],且压缩存储在B[l..k],则k的值至

少为（）。

标准答案：c

知识点露析：采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地

址。

10、如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排

序算法中最快的是()。

A、归并排序

B、希尔排序

C、快速排序

D、基数排序

标准答案：D

知识点解析：按照所有中国人的生日(月、日)排序，一方面待排序记录个数n是非

常大的，另一方面关键字所含的排序码为2,且一个排序码基数为12,另一个为

31,都是较小的常数值，采用基数排序可以在O(n)内完成排序过程。

11、用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序

时，元素序列的变化情况如下：(1)25,84,21,47,15,27,68,35,20(2)20,

15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84(4)1

5,20,21,25,27,35,47,68,84则采用的排序方法是()“

A、选择排序

B、希尔排序

C、二路归并排序

D、快速排序

标准答案：D

知识点解析：本题主要考查各种排序的手工排序过程。选择排序在每趟结束后可

以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位

置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递增，

直到最后的一个有序的完整序列：希尔排序也是形成部分有序的序列：快速排序以

某个元素为界将大于它和小于它的关键字划分为两个子序列，再将该元素放在中

间。观察题中的元素排序过程，可知是快速排序。

12、下图中计算机硬件系统基本组成部件①、②、③、④和⑤的名称是()。

CPU

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

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

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

D、①运算器、4）控制器、⑤存储器、④输出设备、回输入设备

标准答案：B

知识点解析：本题图中所示为冯.诺依曼计算机硬件系统的五大基本部件，包括运

算器、控制器、存储器、输入设备和输出设备五大基本部件。

13、一7的八位二进制反码表示为（）。

A、00000111

B、10000111

C、11111000

D、11111001

标准答案：C

知识点解析：A选项为+7,B选项为-7的原码，D选项为一7的补码。

14、设数据码字为10010011,采用海明码进行校验，若仅考虑纠正一位错，则必

须加入的（冗余）位数是（）。

A、2

B、3

C、4

D、5

标准答案：C

知识点解析：如果仅考虑纠正1位错的情况，只要满足2株n+k+1就可以了（设校验

位的位数为k,信息位的位数为n）。此题中因为n=8,所以k%。如果在纠正1位

错的同时还要能发现2位错，则满足2k-,>n+k+U

15、如果X为负数，则已知［X］补求［一X］补的方法是（）。

A、［X］补各值保持不变

B、［X］补符号位变反，其他各位不变

C、［X］补除符号位外，各位变反，末位加1

D、［X］补连同符号位一起各位变反，末位加1

标准答案：D

知识点解析：［・X］补被称为［X］补的机器负数,由［X］补求［-X］补的过程称为对［X］补

变补（求补），这是做减法运算时必须要完成的操作，

16、下面是有关DRAM和SRAM存储器芯片的叙述：IDRAM芯片的集成度比

SRAM高HDRAM芯片的成本比SRAM高IEDRAM芯片的速度比SRAM快IV

DRAM芯片工作时需要刷新，SRAM芯片工作时不需要刷新通常情况下，错误的

是（）。

A、I和口

B、nflm

c、c和w

D、I和W

标准答案：B

知识点解析：DRAM的集成度高于SRAM,SRAM的速度高于DRAM,可以推出

DRAM的成本低于SRAM,SRAM芯片工作时不需要刷新，DRAM芯片工作时需

要刷新。

17、若想对某个寄存器中的某几位清零，可以使用的一条指令是（）。

A、AND

B、OR

C、NOT

D、XOR

标准答案：A

知识点解析：对某个寄存器中的某几位清零又称为按位清，将此寄存器的内容和一

个特定的源操作数做“与”运算，即可得到。

18、设指令由取指、分听、执行3个子部件完成，每个子部件的工作周期均为4,

采用常规标量流水线处理机。若连续执行10条指令，则共需时间是（）。

A、8一

B、lOJt

C>12/t

D、14/1

标准答案：C

知识点解析：具有3个功能段的流水线连续执行10条指令共需时间

=3，l+9/l=12/t。

19、某计算机的指令系统中共有101条不同的指令，采用微程序控制方式时，控

制存储器中具有的微程序数目至少是（）。

A、101

B、102

C、103

D、104

标准答案：B

知识点解析：除去101条机器指令所对应的101个微程序外，至少还有一个取指微

程序，所以至少有102个微程序。

20、某总线有104根信号线，其中数据总线（DB）32根，若总线工作频率为33

MHz,则其理论最大传输率是（）。

A、33MB/s

B、64MB/s

C、132MB/s

D、164MB/s

标准答案：C

知识点解析：在总线的104根信号线中，数据总线占32根，也就是4个字节，由

于总线工作频率为33MHz,所以理论的最大数据传输率=4Bx33MHz=132MB/s。

21、RGB8：8：8表示一-帧彩色图像的颜色数是（）。

A、23

B、28

C、224

D、2512

标准答案：C

知识点解析：RGB8:8:8是指红、绿、蓝3种颜色都各有8位，总共的颜色深度为

24位，所以颜色数为2%种。

22、关于在I/O设备与主机间交换数据的叙述中，错误的是（）。

A、中断方式下，CPU需要执行程序来实现数据传送任务

B、中断方式和DMA方式下，CPU与I/O设备都可并行工作

C、中断方式和DMA方式中，快速I/O设备更适合采用中断方式传递数据

D、若同时接到DMA请求和中断请求，CPU优先响应DMA请求

标准答案：c

知识点露析：中断和DMA方式是I/O设备与主机间交换数据常采用的传送挖制

方式，在这两种控制方式下，CPU和I/O设备可以并行工作，由于中断方式需要

执行中断服务程序，并且完成一次程序中断还需要许多辅助操作，所以它主要适用

于中、低速外设。

23、交互式操作系统中为了能使多个用户同时与系统进行交互，最关键的问题是

（）。

A、计算机要有足够快的运行速度

B、能快速进行内外存之间的信息交换

C、系统能够及时接收多个用户的输入

D、一段时间内所有用户的程序都能运行

标准答案：C

知识点解析：交互式操作系统有时又称为分时操作系统，它将时间分成一个个的片

段，轮流分给每个用户，用户将分到的时间片段用于本进程的运行。交互式系统强

调交互，所以，对用户的输入及时响应就显得非常重要，而分时方式最能够及时地

响应用户的请求，因为分时系统能够频繁地给多个用户分配时间。因此如何保证操

作系统能及时地接收多个用户的输入就成了交互式操作系统设计的目标，也是交互

式系统需要解决的关键问题。

24、有.2个优先级相同的并发进程Pl和P2,它们的执行过程如下图所示，x、y和

z是共享变量。假设，当前信号量sl=O,s2=0,进程运行结束后，x、y和z的值分

别为()。进程P1进程P2...............y：=20；x：=10；y：=y+l；x：=x+l；y：

=y+l；x：=x+l；z：=y+l；P(sl)；V(sl)；x：=x+y；P(s2)；z：=x+z；y：

=z+y；V(s2)；

A、33,42,22

B、11,42,33

C>33,76,55

D、33,76,33

标准答案：c

知识点解析：本题考查并发进程的特点，并结合信号量进行同步的原理。由于进程

并发，所以，进程的执行具有不确定性，在Pl、P2执行到第一个PV操作前，应

该是相互无关的。现在考虑第一个对si的PV操作，由于进程P2是P(sl)操作，所

以，它必须等待P1执行完V(sl)操作以后才可继续运行，此时的xyz值分别为

11,21,22,当进程P1执行完V(sl)以后便在P(s2)上阻塞，此时P2可以运行直

到V(s2),此时的xyz值分别为33,21,55,进程P1继续运行直到结束，最终的

xyz值分别为33,76,55。在此需注意，xyz应该是共享变量，若是私有变量，则

进程PI、P2就各自独立对xyz操作。

25、临界区是指并发进程访问共享变量段的()。

A、管理信息

B、信息存储

C、数据

D、代码程序

标准答案：D

知识点解析：本题考查对临界区的理解。所谓临界区，并不是指临界资源，临界资

源是指共享的数据、代码或硬件设备等，面临界区是指访问这些临界资源的那段代

码程序，例如PV操作，加减锁等。操作系统中对临界区的访问关心的就是临界区

的操作过程，具体对临界资源作何操作是应用程序的事，操作系统并不关心。

26、一个正在访问临界资源的进程由于申请等待10操作而被中断时，它是()。

A、可以允许其它进程进入与该进程相关的临界区

B、不允许其它进程进入任何临界区

C、可以允许其它进程抢占处理机，但不得进入该进程的临界区

D、不允许任何进程抢占处理机

标准答案：c

知识点解析：进程进入临界区必须满足互斥条件，当进程进入临界区但是尚未离开

时就被迫进入阻塞是可以的，系统中经常有这样的情形。在此状态下，只要其它进

程在运行过程中不寻求进入该进程的临界区，就应该允许其运行。该进程所锁定的

临界区是不允许其它进程访问的，其它进程若要访问，必定会在临界区的“锁”上阻

寒，期待该进程下次运行时可以离开并将临界区交给它。所以正确选项为C。

27、在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于

该方法，进行内存保护的措施是（）。

A、存取控制列表

B、用户权限保护

C、程序状态保护

D、界地址保护

标准答案：D

知识点解析：本题考查分区保护的主要措施。在分区分配内存管理方法中，最常采

用的方法是界地址保护法和基址、限长寄存器保护法。界地址保护法将每一个进程

在内存中的物理位置的上界和下界值存放到上下界地址寄存器中，进程的每一条指

令或数据的物理地址均与这两个上下界寄存器比较，一旦低于下界寄存器或大于上

界寄存器均发生越界中断，从而起到保护作用。基址、限长寄存器保护法是上述方

法的改进。将进程的逻辑地址与限长寄存器比较，一旦越界就发出中断，从而保护

内存。基址寄存器主要是用来进行逻辑地址到物理地址的转换。

28、段页式存储管理中，某个进程的段表和页表如下图所示，页的大小为4096B,

现有逻辑地址（1，8228）,其对应的物理地址是（）。

A、483364

B、409636

C、475172

D、516132

标准答案：A

知识点解析：本题考查段页式地址转换的计算。根据题目给出的条件，地址（1,

8228）应该位于第二段，对应段号为1（段号从0开始计算），因此找到第二段（即编

号为1的段表）的页表，该段段长为3,可以看到有3个页面。8228按页分

8228X096=2余36,因此应该在第三页，没有越界。第三页的页号为2（从0开始

编址），页号2对应的页框号为118,所以，物理地址为118x4096+36=483364。

29、分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数是（）。

A、成正比

B、成反比

C、无关系

D、固定值

标准答案：c

知识点.析：在分页存储管理系统中，页面的大小是由计算机系统的地址结构所决

定的，i般由软硬件共同决定。对于某一种系统一般采用i种大小的页面（也有部

分现代操作系统采用双页面系统的）。在确定地址结构时，若选择的页面较小，

方面可使内碎片减小，并减少了内碎片的总空间，有利于提高内存利用率。另一方

面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外还

会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进

换出效率，但却又会使页内碎片增大。由于内存的大小是固定的，所以无论页面

是大是小，可以进入内存的作业大小也是固定的，最多不超过内存的大小。实际

上，分页的大小并不影响进入内存作业的数量。从宏观上看，进入内存的页面内容

是没有变化的。所以分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中

断次数并没有确定的关系。正确答案为C。

30、某一个磁盘共有16个盘面，每个盘面上从外到内共有30000个磁道（或称

30000个柱面），每个磁道有250个扇区。假定存储信息时以一个扇区作为一个存储

块，盘面号（磁头号）、磁道号和扇区号均从。开始编号，那么，盘块号1002578对

应的盘面号、磁道号和扇区号是（）。

A、1,2500,78

B、10,250,78

C、2,250,161

D、0,4010,78

标准答案：C

知识点解析：本题考查磁盘的结构。磁盘的存储是按照磁头（或盘面），磁道（或柱

面）和扇区三要素唯一确定的，但是，在具体的使用时，是将所有的可用存储块按

一维编号来进行分配的，称为逻辑地址。由于多盘面的磁盘系统中所有的磁头装在

同一个转动轴上，是同步一起移动的，所以选择高效的编址方式能够提高磁盘的读

写时间。不同于按磁头、磁道、扇区的顺序编址，多盘组磁盘的编址首先是按磁道

来编，从磁盘外边缘到磁盘中心从。开始编号，本题中是。到29999。确定了磁

道，接下去随着磁盘的转动，所有磁头一起从某一起始点开始，寻找扇区，扇区的

编号也是从0开始，本题中是。到249。找到扇区后再按磁头寻找，磁头从上到下

从0开始编号，本题中是0到15。在了解了盘组磁盘的编址方式后，下面的计算

就比较简单了。首先确定磁道，1002578;（250x16）并下取整（即舍去小数部分）得

250,得到磁道号，余下逻辑块编号的偏移量是2578,接下去确定扇区号，

2578引6并下取整得161,得到扇区号，余下逻辑块编号的偏移量是2,此号便是

磁头号了，所以，其对应的三要素单位为2,250,161o

31、现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有

相同的文件名。那么，实现该功能的主要方法是（），

A、重名翻译机构

B、建立索引表

C、建立指针

D、建立树形目录结构

标准答案：D

知识点解析：本题考查文件系统重名问题的解决。树形目录的引入将文件重名的问

题得到解决。树形文件目录是多级目录，最初的目录称为根目录，其余目录称为子

目录。每一个目录下可以存放不同的文件，相同文件名的文件（可能内容是不同

的），可以存放在不同的目录下，从而解决了文件重名问题。

32、设备管理中，设备映射表（DMT）的作用是（）。

A、管理物理设备

B、管理逻辑设备

C、实现输入/输出

D、建立逻辑设备与物理设备的对应关系

标准答案：D

知识点解析•：本题考查没备管理中重要的数据结构的作用。既然是映射关系，必定

有源和目标，能说明存在这关系的只有D选项。

33、在OSI参考模型中，实现系统间二进制信息块的正确传输，为上一层提供可

靠、无错误的数据信息的协议层是（）。

A、物理层

B,数据链路层

C、网络层

D、传输层

标准答案：B

知识点解析：本题主要考查OSI参考模型各个层次的作用，这里二进制信息块其

实就是数据链路层所封装的数据帧，传输层虽然也提供可靠的数据传输，但不能保

证系统间直接的二进制信息块的可靠性，因此答案是Bo

34、光纤分为单模光纤和多模光纤，这两种光纤的区别是（）。

A、单模光纤的数据速率比多模光纤低

B、多模光纤比单模光纤传输距离更远

C、单模光纤比多模光纤的价格更便宜

D、多模光纤比单模光纤的纤芯直径粗

标准答案：D

知识点解析：本题考查物理层介质，单模光纤芯径小（10mm左右），仅允许一个模

式传输,色散小，工作在长波长（1310nm和1550nm）,与光器件的耦合相对困难,

而多模光纤芯径大（62.5mm或50mm）,允许上百个模式传输，色散大，工作在

850nm或l310nm。与光器件的耦合相对容易，也就是主要区别在于直径的粗细，

两者在数据传输速率，芍输距离和价格方面并没有太大的区别，因此答案是D。

35、使用HDLC时,位串011111110111110进行位填充后的位模式是（）。

A、011101110101110110

B、0111101110111110

C、1.1111110111e+014

D、l.llllOHOlle+015

标准答案：D

知识点解析：本题考查零比特填充，为了避免其它字段中出现“0111110”，产生误

解，HDLC采用零比特填充技术，即在发送时，除标志字段外，如果连续发现5个

“1”，则在其后自动插入一个“0”。接收方收到连续5个“1”后，如果其后为“0”，则

自动将该“0”位删除，如果其后为“1”，则继续检查下一位，如果为“0”，则为标志

位，为"1”则出错。即：

(发送方：除标志位外•连续发现5个“1”后自动插入“0”.

其后为“0。则自动去掉该“0工

接收方：连续发现5个“1”后《如果为“0”,则为标志位.

其后为“1。则检查F一位

为“】”出错。

核心点就是只要出现连续的5个0之后，添加一个0,因此位串01111111011111

0,经过填充后是01111101101111100,因此答案为D。

36、以太网交换机转发数据包时所依据的是()。

A、IP地址

B、MAC地址

C、LLC地址

D、PORT、地址

标准答案：B

知识点解析•：本题考查交换机的工作原理，注意本题前提是以太网交换机，因此属

于数据链路层的范畴，故可以排除选项A和D,因为IP地址属于网络层，而

PORT地址，即端口地址属于传输层，这里要明确以太网中MAC和LLC的功能，

LLC子层负责向其上层提供服务，MAC子层的主要功能包括数据帧的封装/卸

装，帧的寻址和识别，喊的接收与发送，链路的管理，帧的差错控制等，因此，交

换机在转发数据包时所依据的是MAC地址，答案是B。

37、CRC校验是目前常用的检错方式。如果采用的多项式为G(X)=X4+X+1,那么

对于要传的信息串1101011011的CRC校验码是()。

A、1011

B、1101

C、：1110

D、1100

标准答案：B

知识点解析：本题考查CRC校验的计算方法，设信息位率为ala2a3….am,则信

息编码多项式为M(x)=alxm-l+a2xm-2+a3xm.3+……十2由，选择一个「次多项式G(x)

作为生成多项式，再按卜面步骤生成校验串：(1)在信息位串后补r个0,对应的多

项式为x「M(x),(2)用模2又不借位除法,计算为M(x)/G(x)的余数R(x),R(x)就

是校验位串对应的多项式。设要发送的码字多项式为T(x),则：T(x)=xrM(x)+R(x)

本题中该字符串为1010001,G(X)=X4+X2+X+1,因此M(X)=X6+X'+1,『4

xrM(x)=x,0+x8+x4->10100010000计算R(x户x「M(x)/G(x)的过程如下：

1001111

10111710100010000

10111

11010

10111

11010

10111

11010

10111

11010

10111

1101R(x)为1101,因此R(X)=X/M(X)/G(X)=X3+X2+1,

T(x)=xrM(x)/G(X)+R(X)=X,0+X8+X4+X3+X2+1,也就是1010001(信息位串)1101(校验

位串)，因此答案为B。

38、关于因特网中的主矶和路由器，以下说法正确的是()。I.主机通常需要实现

TCP协议口.路由器必须实现TCP协议HI.主机必须实现IP协议W.路由器必

须实现IP协议

A、I、n和山

B、I、n和w

c、cc和w

D、口、m和w

标准答案：c

知识点解析•：主要考查网络设备与参考模型的关系，主机作为终端设备，需要实现

整个五层协议，而路由器作为网络层设备，仅实现物理层，数据链路层和网络层三

个层次的协议，这里TCP是传输层协议，路由器不需要管理传输层的内容，仅完

成网络层的数据包传输，选项n排除，因此答案为C。

39、下面包含在TCP头中而不包含在UDP头中的信息是()。

A、目标端口号

B、序号

C、源端口号

D、校验号

标准答案：B

知识点解析：本题主要考查TCP报文段和UDP报文段结构，TCP数据报和UDP

数据报都包含目标端口、源端口、校验号。但是由于UDP是不可靠的传输，故数

据报不需要编号，所以不会有序号这一字段，面TCP是可靠的传输，故需要设置

序号这一字段，答案是B。

40、DNS服务器在名称解析过程中正确的查询顺序是（）。

A、本地缓存记录一区域记录-转发域名服务器一根域名服务器

B、区域记录一本地缓存记录一＞转发域名服务器一＞根域名服务器

C、本地缓存记录T区域记录T根域名服务器T转发域名服务器

D、区域记录T本地缓存记录一根域名服务器一转发域名服务器

标准答案：C

知识点解析：本题考查DNS域名解析的工作过程，具体步骤如下：（1）客户机提交

域名解析请求，并将该请求发送给本地的域名服务器；（2）当本地的域名服务器收

到请求后，就先查询本地的缓存。如果有查询的DNS信息记录，则直接返回查询

的结果。如果没有该记录，本地域名服务器就把请求发给根域名服务器；（3）杈域

名服务器再返回给本地域名服务器一个所查询域的顶级域名服务器的地址；（4）本

地服务器再向返回的域名服务器发送请求；（5）接收到该查询请求的域名服务器查

询其缓存和记录，如果有相关信息则返回本地域名服务器查询结果，否则通知本地

域名服务器下级的域名服务器的地址；（6）本地域名服务器将查询请求发送给下级

的域名服务器的地址，直到获取查询结果；（7）本地域名服务器将返P1的结果保存

到缓存，并且将结果返回给客户机，完成解析过程。因此本题答案是C。

二、综合应用题（本题共7题，每题7.0分，共7分。）

41、已知加权有向图G如下，回答下列问题:

画出该有向图G的邻接矩阵；（2）试利用Dijkstra算法求G中从顶点a到其他各顶

点间的最短路径，并给出求解过程。

*0015212OOOOOO-

OO8OOOO6OOOO

OOOOOOOO84OO

OOOOOOOOOOOO3

OOOOOOOOOO89

OOOO858OO10

OO4OOOO8OOOO

标准答案：（1）有向图G的邻接矩阵(2)

bede1CS

15l12

k-l<a«c)

(a.b)(a«c)(a.d)

IS12106

32

(a.b)<«.d>(a«c*e)<a»c»D

15111016

k-3(U・e)

(a.b)(a.c.f(d)

IS11IS

k-4

(a.b)(a»c«(«d)(a.c«f.R)

ISH

k-5

(a.b)(a»c(f.d.R)

15

k—6(«»(•(>«.d.g.b)

(a.b)

知识点解析：本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特

拉（Dijk.slra）算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的

基本思想是：（1）设置两个顶点的集合5和1二丫一S,集合S中存放已找到最短路

径的顶点，集合T存放当前还未找到最短路径的顶点。（2）初始状态时，集合S中

只包含源点vo,然后不断从集合T中选取到顶点b＞路径长度最短的顶点u加入到

集合S中，集合S每加入一个新的顶点u,都要修改顶点b＞到集合T中剩余顶点

的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度

值与顶点”的最短路径长度值加上u到该顶点的路径长度值中的较小值。（3）此过程

不断重复，直到集合T的顶点全部加入到S中为止。

42、已知数组A[1……n]的元素类型为整型ini,设计一个时间和空间上尽可能高效

的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整

数。不要求对这些元素徘序。（1）给出算法的基本设计思想；（2）根据设计思想，采

用C或C++或JAVA语言表述算法，关键之处给出注释；（3）说明你所设计算法的

时间复杂度和空间复杂度。

标准答案：(1)算法的基本设计思想如解析所述。(2)用C语言算法描述如下：void

Adjust(intA[]){//调整数组A,使得A的左边为负整数，右边为正整数面i=l,

j=n,temp；while(iO&&i

知识点解析：本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基

本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组

末端查找负整数，找到后进行交换，直到上、下界相遇。具体做法是：设置两个

指示器i和j,其中i=l,j=n；当A[i]为正整数,AU]为负整数时,A[i]和A[j]交

换；否则，A[i]为负整数时，则i++；A[j]为正整数时，则j-。这样，可使算法的

时间复杂度为0(n)。

43、设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，设当前指令的地址

码部分为001AH,正在执行的指令所在地址为1F05H,变址寄存器中的内容为

23A0H。(1)当执行取数指令时，如为变址寻址方式，则取出的数为多少？(2)如为

间接寻址，取出的数为多少？(3)当执行转移指令时，转移地址为多少？已知存储器

地址内容

001AH23AOH

1F05H24OOH

1FIFH2500H

23A0H2600H

23BAH1748H

的部分地址及相应内容，见下表。

标准答案：⑴变址寻址时，操作数S=((Rx)+A)=(23AOH+001AH)=(23BAH)=l748

Ho(2)间接寻址时，操作数S=((A))=((001AH))=(23AOH)=2600H。⑶转移指令

使用相对寻址，转移地址=(PC)+A=1FO5H+OOIAH=1F1FH。因为在本题中没有指

出指令的长度，故此题未考虑PC值的更新。

知识点解析：前两个小题涉及数据寻址，其最终目的是寻找操作数，第3小题涉及

指令寻址，其目的是寻找下一条将要执行的指令地址。

44、四位运算器框图如下图所示，ALU为算术逻辑单元，A和B为三选一多路开

关，预先已通过多路开关A的SW门向寄存器R|,R2送入数据如下：Ri=0101,

R2=1010O寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下：

AS.

AS,

(1)R|(A)+R2(B)-BR(显示结果1010)；(2)R2(A)+R|(B)TBR(显示结果1111)；

(3)R](A)+R1(B)-BR(显示结果1010)；(4)R2(A)+R?(B)―BR(显示结果1111)；

(5)R2(A)+BR(B)TBR(显示结果1111)；(6)R](A)+BR(B)—BR(显示结果1010)；试

分析运算器的故障位置与故障性质(力”故障还是“0”故障)，说明理由。

标准答案：运算器的故障位置在多路开关B,其输出始终为Ri的值。

(l)Rl(A)+R2(B)=1010,输出结果错;(2)R2(A)+R1(B)=1I11,结果正确，说明

R2(A),R1(B)无错;(3)Ri(A)+R|(B)=1010,结果正确，说明Ri(A),R|(B)无错。

由此可断定ALU和BR无错；(4)R2(A)+R2(B)=111U结果错。由于R2(A)正

确，且R2(A)=I010,本应R2(B)—1010,但此时推知R2(B)=0101,显然，多路

开关B有问题；(5)R2(A)+BR(B)=1111,结果错。由于R2(A)=1010,BR(B)=11

11,但现在推知BR(B)=0101,证明开关B输出有错；(6)Ri(A)+BR(B)=1010,

结果错。由于Rl(A)=0101,本应BR(B)=1111,但现在推知BR(B)=0】01,再次

证明开关B出错。综上所述，多路开关B输出有错。故障性质：多路开关B输出

始终为0101。这有两种可能：一是控制信号BSo,BSi始终为01,故始终选中寄

存器R]；二是多路开关B电平输出始终处于在0101上。

知识点解析：根据已知的6步运算过程一步一步地分析，可知运算器的故障位置在

多路开关B。

45、在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统

中有二个进程PO、P1已经就绪，进程P0首先获得处理机运行，调度算法为先来

先服务，进程PO、P1的运行要求是这样的:P0：计算100ms,打印信息200ms,

继续计算100ms,打印信息200ms,结束。PI：计算100ms,输入数据150ms,继

续计算200ms,结束。请用甘特图画出它们的运行轨迹，并说明：进程P0、P1在

运行时有无等待?若有，请指出时间区间。计算处理机的利用率。

标准答案：根据题意，画出甘特图如下：

处理机■QBWEiasalPl结束

打印机idle结束

输入设符idle1Plidle结束

ISO|20012501300350J400

时间50100450|500|550|600ms

从运行的时序甘特图上可以看出：处理机在200ms到300ms之间是空闲的。因

此，处理机的利用率可以计算出为：（200+300）:600=83.3%。进程P0运行过程中

无等待现象，进程P1有等待现象，等待区间为35100ms之间。

知识点解析：本题考查进程调度的过程。解决这类题目的关键在于画出进程运行的

时序图，若用条形来表示这种时序图就称为甘特图，然后再对其进行分析。绘图和

分析过程中要注意题目适用的调度算法，先来先服务最简单，按先来后到的次序进

行调度，被调度的进程一般会占有处理机运行直到自己主动放弃；短进程优先算法

在选取调度的进程时需要知道进程的预计执行时间，根据进程表里填写的进程预计

执行时间，选取最短的进程调度其运行；高优先级优先的调度算法是根据进程表内

赋予的优先级来调度，当然，优先级的确定可以有各种方法，可以在创建时确定，

也可以根据程序的紧急程度确定，还可以根据收费多少确定，所以优先级的确定有

许多灵活性，现行大部分操作系统均会采用高优先级优先的调度算法；时间片轮转

的调度算法是由硬件时钟确定每一个进程占用处理机的时间的，进程按先来先服务

排队，调度器调度进程队列中最先的进程运行，若分配的时间未到进程就主动放弃

处理机，则会引起下一次调度，若分配的时间到，则不管进程是否运行完成，必须

立即强制地出让处理机。在以上描述的各种调度算法既可以单独使用，也可以组合

使用。不管采用什么算法，能否抢先是另一个调度的非常重要的因素，为适应不问

用户的需求，也为改善计算机的性能，现代许多操作系统均采用抢先式调度算法，

抢先式调度不能单独实施，一定是与上述各种调度算法相结合。处理机的调度相对

较复杂，而IO的调度就简单了，为保证安全，一般10设备是不能抢夺的，一旦

分配，则一定是使用到进程主动放弃。

46、某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个

进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0,并且所有

的地址均按字节计址，每页的大小为1024字节。

逻馔页号存在位引用位修改位页假号

01109

11113

2000——■

31001

4000——

51015

(1)计算下列逻辑地址转

换为物理地址，并说明为H么？0793,1197,2099,3320,4188,5332(2)假设程

序要访问第2页，页面置换算法为改进的Clock算法，请问该淘汰哪页?页表如何

修改?上述地址的转换结果是否改变?变成多少?

标准答案：(1)根据题意，计算逻辑地址的页号和页内偏移量，合成物理地址如下

迎新地址逻辑页号页内偏移国贞根号物理地址

0793079344889

119711733324S

2099251••••接页中断

3320324811272

4188492——缺货中蜥

5332521255332

表。(2)第2页不在

内存，产生缺页中断，艰据改进的Clock算法，第3页为没被引用和没修改的页

面，故淘汰。新页面进入，页表修改如下:

亚辑页号存在位引用位修改位页依号

0110<

11113

20—10-10———♦]调入