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

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

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

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

1． 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 void fun(int n){ int i，k； for(i=1；i<=n；i十十) for(j=1；j<=n；j十十){ k=1： while(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，即m≤log5n。所以：

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求值时，运算数栈OPND的大小至少为4。 例如求选项B的表达式(A—B)*C—D的过程如下表所示： 按照上述过程可知，选项B求值时，运算数栈OPND的大小至少为2。 类似地，选项C、D求值时，运算数栈OPND的大小至少为3、3。因此本题答案为B。

3． 已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。

A．dacb B．cadb C．dbca

D．以上答案都不对

正确答案：B

解析：输出受限的双端队列是指删除在一端进行，而插入允许在两端进行的队列。 分析选项A，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc，选项A为错误答案。 分析选项B，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。 分析选项C，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac，选项C为错误答案。

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

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

正确答案：C

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

5． 以下关于二叉排序树的说法正确的是( )。 I在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。 Ⅱ每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。 Ⅲ在二叉排序树中，新插入的关键字总是处于最底层。 Ⅳ在二叉排序树中，新结点总是作为叶子结点来插入的。 V二叉排序树的查找效率和二叉排序树的高度有关。

A． I、Ⅱ、Ⅳ、V B．Ⅱ、Ⅲ、Ⅳ C． I、Ⅲ、V D． I、Ⅳ、V

正确答案：D 解析：对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序.树的平均查找长度的值 不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和10g2n成正比。

6． 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的

值至少为( )。

A．n(n+1)／2 B．n2／2

C．(n—1)(n+1)／2 D。n(n—1)／2

正确答案：D

解析：简单无向图的邻接矩阵是对称的，且对角线元素均是0，故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式)： k=(n一1)+(n一2)+…+1+0=n2一(1+2+…+n)=n(n一1)／2。

7． 下面关于图的存储的叙述中，正确的是( )。

A．用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关

B．用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关

D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

正确答案：A

解析：邻接矩阵的空间复杂度为O(n2)，与边的个数无关。邻接表的空间复杂度为O(n+e)，与图中的结点个数和边的个数都有关。

8． 用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

A． B． C． D．

正确答案：D

解析：根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。 第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n； 第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为Llog2n」+1次，查找结束。

9． 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多

个位置，在查找成功的情况下，所探测的这些位置的键值( )。

A．一定都是同义词 B．一定都不是同义词 C．不一定都是同义词 D．都相同

正确答案：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，1 5，21，25，47，27，68，35，84 (3)1 5，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． 下图中计算机硬件系统基本组成部件①、②、③、④和⑤的名称是( )。 A．①控制器、②运算器、③存储器、④输入设备、⑤输出设备 B．①运算器、②控制器、③存储器、④输入设备、⑤输出设备 C．①运算器、②存储器、③控制器、④输入设备、⑤输出设备

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

正确答案：B

解析：本题图中所示为冯.诺依曼计算机硬件系统的五大基本部件，包括运算器、控制器、存储器、输入设备和输出设备五大基本部件。

13． 一7的八位二进制反码表示为( )。 A．00000111 B．10000111 C．11111000 D．11111001

正确答案：C

解析：A选项为+7，B选项为-7的原码，D选项为一7的补码。 14． 设数据码字为1001001 1，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。

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

正确答案：C

解析：如果仅考虑纠正1位错的情况，只要满足2k≥n+k+1就可以了(设校验位的位数为k，信息位的位数为n)。此题中因为n=8，所以k≥4。如果在纠正1位错的同时还要能发现2位错，则满足2k-1≥n+k+1。

15． 如果X为负数，则已知[X]补求[一X]补的方法是( )。 A．[X]补各值保持不变

B．[X]补符号位变反，其他各位不变

C．[X]补除符号位外，各位变反，末位加1 D．[X]补连同符号位一起各位变反，末位加1

正确答案：D 解析：[一X]补被称为[X]补的机器负数，由[X]补求[一X]补的过程称为对[X]补变补 (求补)，这是做减法运算时必须要完成的操作。

16． 下面是有关DRAM和SRAM存储器芯片的叙述： I DRAM芯片的集成度比SRAM高 Ⅱ DRAM芯片的成本比SRAM高 Ⅲ DRAM芯片的速度比SRAM快 Ⅳ DRAM芯片工作时需要刷新，SRAM芯片工作时不需要刷新 通常情况下，错误的是( )。

A．I和Ⅱ B．Ⅱ和Ⅲ C．Ⅲ和Ⅳ

D．I和Ⅳ

正确答案：B

解析：DRAM的集成度高于SRAM，SRAM的速度高于DRAM，可以推出DRAM的成本低于SRAM，SRAM芯片工作时不需要刷新，DRAM芯片工作时需要刷新。

17． 若想对某个寄存器中的某几位清零，可以使用的一条指令是( )。 A．AND B．OR C．NOT D．XOR

正确答案：A 解析：对某个寄存器中的某几位清零又称为按位清，将此寄存器的内容和一个特定 的源操作数做“与”运算，即可得到。

18． 设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为⊿t，采用常规标量流水线处理机。若连续执行10条指令，则共需时间是( )。

A．8⊿t B．10⊿t C．12⊿t D．14 ⊿t

正确答案：C

解析：具有3个功能段的流水线连续执行10条指令共需时间=3⊿t+9⊿t=12⊿t。

19． 某计算机的指令系统有1 01条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。

A．101 B．102 C．103 D．104

正确答案：B 解析：除去101条机器指令所对应的101个微程序外，至少还有一个取指微程序，所以至少有102个微程序。

20． 某总线有104根信号线，其中数据总线(DB)32根，若总线工作频率为33 MHz，则其理论最大传输率是( )。

A．33 MB／s B． MB／s C．132 MB／s

D．1 MB／s

正确答案：C

解析：在总线的104根信号线中，数据总线占32根，也就是4个字节，由于总线工作频率为33MHz，所以理论的最大数据传输率=4B×33MHz=132MB／s。

21． RGB8：8：8表示一帧彩色图像的颜色数是( )。 A．23 B．28 C．224 D．2512

正确答案：C

解析：RGB8:8:8是指红、绿、蓝3种颜色都各有8位，总共的颜色深度为24位，所以颜色数为224种。

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个优先级相同的并发进程P1和P2，它们的执行过程如下图所示，x、y和z是共享变量。假设，当前信号量s1=0，s2=0，进程运行结束后，x、y和z的值分别为( )。 进程P1 进程P2 …… …… y：=20； x：=10； y：=y+1； x：=x+1； y：=y+1； x：=x+1； z：=y+1； P(s1)； V(s1)； 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

解析：本题考查并发进程的特点，并结合信号量进行同步的原理。由于进程并发，所以，进程的执行具有不确定性，在P1、P2执行到第一个PV操作前，应该是相互无关的。现在考虑第一个对s1的PV操作，由于进程P2是P(s1)操作，所以，它必须等待P1执行完V(s1)操作以后才可继续运行，此时的xyz值分别为11，21，22，当进程P1执行完V (s1)以后便在P(s2)上阻塞，此时P2可以运行直到V(s2)，此时的xyz值分别为33，21，55，进程P1继续运行直到结束，最终的xyz值分别为33，76，55。在此需注意，xyz应该是共享变量，若是私有变量，则进程P1、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．4833 B．409636 C．475172 D．516132

正确答案：A 解析：本题考查段页式地址转换的计算。根据题目给出的条件，地址(1，8228)应该位于第二段，对应段号为1(段号从0开始计算)，因此找到第二段(即编号为1的段表)的页表，该段段长为3，可以看到有3个页面。8228按页分8228÷4096=2余36，因此应该在第三页，没有越界。第三页的页号为2(从0开始编址)，页号2对应的页框号为11 8，所以，物理地址为118×4096+36=4833 。

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

A．成正比 B．成反比 C．无关系 D．固定值

正确答案：C 解析：在分页存储管理系统中，页面的大小是由计算机系统的地址结构所决定的，一般由软硬件共同决定。对于某一种系统一般采用一种大小的页面(也有部分现代操作系统采用双页面系统的)。在确定地址结构时，若选择的页面较小，

一方面可使内碎片减小，并减少了内碎片的总空间，有利于提高内存利用率。另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外还会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但却又会使页内碎片增大。 由于内存的大小是固定的，所以无论页面是大是小，可以进入内存的作业大小也是固定的，最多不超过内存的大小。实际上，分页的大小并不影响进入内存作业的数量。从宏观上看，进入内存的页面内容是没有变化的。所以分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数并没有确定的关系。正确答案为C。

30． 某一个磁盘共有16个盘面，每个盘面上从外到内共有30000个磁道(或称30000个柱面)，每个磁道有250个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号(磁头号)、磁道号和扇区号均从0开始编号，那么，盘块号10025 78对应的盘面号、磁道号和扇区号是( )。

A．1，2500，78 B．10，250，78 C．2，250，1 61 D．0，4010，78

正确答案：C 解析：本题考查磁盘的结构。磁盘的存储是按照磁头(或盘面)，磁道(或柱面)和扇区三要素唯一确定的，但是，在具体的使用时，是将所有的可用存储块按一维编号来进行分配的，称为逻辑地址。由于多盘面的磁盘系统中所有的磁头装在同一个转动轴上，是同步一起移动的，所以选择高效的编址方式能够提高磁盘的读写时间。不同于按磁头、磁道、扇区的顺序编址，多盘组磁盘的编址首先是按磁道来编，从磁盘外边缘到磁盘中心从0开始编号，本题中是0到29999。确定了磁道，接下去随着磁盘的转动，所有磁头一起从某一起始点开始，寻找扇区，扇区的编号也是从0开始，本题中是0到249。找到扇区后再按磁头寻找，磁头从上到下从0开始编号，本题中是0到15。在了解了盘组磁盘的编址方式后，下面的计算就比较简单了。首先确定磁道，1002578÷(250×16)并下取整(即舍去小数部分)得250，得到磁道号，余下逻辑块编号的偏移量是25 78，接下去确定扇区号，2578÷16并下取整得161，得到扇区号，余下逻辑块编号的偏移量是2，此号便是磁头号了，所以，其对应的三要素单位为2，250，161。

31． 现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有相同的文件名。那么，实现该功能的主要方法是( )。

A．重名翻译机构 B．建立索引表 C．建立指针

D．建立树形目录结构

正确答案：D 解析：本题考查文件系统重名问题的解决。树形目录的引入将文件重名的问题得到解决。树形文件目录是多级目录，最初的目录称为根目录，其余目录称为子目录。每一个目录下可以存放不同的文件，相同文件名的文件(可能内容是不

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

32． 设备管理中，设备映射表(DMT)的作用是( )。 A．管理物理设备 B．管理逻辑设备 C．实现输入／输出

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

正确答案：D

解析：本题考查设备管理中重要的数据结构的作用。既然是映射关系，必定有源和目标，能说明存在这关系的只有D选项。

33． 在OSI参考模型中，实现系统间二进制信息块的正确传输，为上一层提供可靠、无错误的数据信息的协议层是( )。

A．物理层 B．数据链路层 C．网络层 D．传输层

正确答案：B

解析：本题主要考查OSI参考模型各个层次的作用，这里二进制信息块其实就是数据链路层所封装的数据帧，传输层虽然也提供可靠的数据传输，但不能保证系统间直接的二进制信息块的可靠性，因此答案是B。

34． 光纤分为单模光纤和多模光纤，这两种光纤的区别是( )。 A．单模光纤的数据速率比多模光纤低 B．多模光纤比单模光纤传输距离更远 C．单模光纤比多模光纤的价格更便宜 D．多模光纤比单模光纤的纤芯直径粗

正确答案：D

解析：本题考查物理层介质，单模光纤芯径小(10mm左右)，仅允许一个模式传输，色散小，工作在长波长(1 310nm和1550nm)，与光器件的耦合相对困难，而多模光纤芯径大(62．5mm或50mm)，允许上百个模式传输，色散大，工作在850nm或1310nm。与光器件的耦合相对容易，也就是主要区别在于直径的粗细，两者在数据传输速率，传输距离和价格方面并没有太大的区别，因此答案是D。

35． 使用HDLC时，位串011111110111110进行位填充后的位模式是( )。 A．011101110101110110 B．0111101110111110 C．1.1111110111e+014 D．1.1111011011e+015

正确答案：D

解析：本题考查零比特填充，为了避免其它字段中出现“011 11 10”，产生误解，HDLC采用零比特填充技术，即在发送时，除标志字段外，如果连续发现5个“1”，则在其后自动插入一个”0”。接收方收到连续5个“1”后，如果其后为“0”，则自动将该“0”位删除，如果其后为“1”，则继续检查下一位，如果为“0”，则为标志位，为“1”则出错。即： 核心点就是只要出现连续的5个0之后，添加一个0，因此位串011111 11011111 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)=a1 xm-1+a2xm-2+a3xm-3+……+am，选择一个r次多项式G(x)作为生成多项式，再按下面步骤生成校验串： (1)在信息位串后补r个0，对应的多项式为xrM(x)， (2)用模2又不借位除法，计算xrM(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+x4+1，r=4 xrM(x)=x10+x8+x4→10100010000 计算R(x)=xrM(x)／G(x)的过程如下： R(x)为1101，因此R(x)=xrM(x)／G(x)=x3+x2+1，T(x)=xrM(x)／G(x)+R(x)=x10+x8+x4+x3+x2+1，也就是1010001(信息位串)1101(校验位串)，因此答案为B。

38． 关于因特网中的主机和路由器，以下说法正确的是( )。 I．主机通常需要实现TCP协议 Ⅱ．路由器必须实现TCP协议 Ⅲ．主机必须实现IP协议 Ⅳ．路由器必须实现IP协议

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

正确答案：C

解析：主要考查网络设备与参考模型的关系，主机作为终端设备，需要实现整个五层协议，而路由器作为网络层设备，仅实现物理层，数据链路层和网络层三个层次的协议，这里TCP是传输层协议，路由器不需要管理传输层的内容，仅完成网络层的数据包传输，选项Ⅱ排除，因此答案为C。

39． 下面包含在TCP头中而不包含在UDP头中的信息是( )。 A．目标端口号 B．序号

C．源端口号 D．校验号

正确答案：B

解析：本题主要考查TCP报文段和UDP报文段结构，TCP数据报和UDP数据报都包含目标端口、源端口、校验号。但是由于UDP是不可靠的传输，故数据报不需要编号，所以不会有序号这一字段，而TCP是可靠的传输，故需要设置序号这一字段，答案是B。

40． DNS服务器在名称解析过程中正确的查询顺序是( )。

A．本地缓存记录→区域记录→转发域名服务器→根域名服务器 B．区域记录→本地缓存记录→转发域名服务器→根域名服务器 C．本地缓存记录→区域记录→根域名服务器→转发域名服务器 D．区域记录→本地缓存记录→根域名服务器→转发域名服务器

正确答案：C

解析：本题考查DNS域名解析的工作过程，具体步骤如下： (1)客户机提交域名解析请求，并将该请求发送给本地的域名服务器； (2)当本地的域名服务器收到请求后，就先查询本地的缓存。如果有查询的DNS信息记录，则直接返回查询的结果。如果没有该记录，本地域名服务器就把请求发给根域名服务器； (3)根域名服务器再返回给本地域名服务器一个所查询域的顶级域名服务器的地址； (4)本地服务器再向返回的域名服务器发送请求； (5)接收到该查询请求的域名服务器查询其缓存和记录，如果有相关信息则返回本地域名服务器查询结果，否则通知本地域名服务器下级的域名服务器的地址； (6)本地域名服务器将查询请求发送给下级的域名服务器的地址，直到获取查询结果； (7)本地域名服务器将返回的结果保存到缓存，并且将结果返回给客户机，完成解析过程。 因此本题答案是C。

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

41． 已知加权有向图G如下，回答下列问题： (1)画出该有向图G的邻接矩阵； (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

正确答案：(1)有向图G的邻接矩阵 (2)

解析：本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk-stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是： (1)设置两个顶点的集合S和T=V—S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。 (2)初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点b>路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点b>到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。 (3)此过程不断重复，直到集合T的顶点全部加入到S中为止。

42． 已知数组A[1……n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想； (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释； (3)说明你所设计算法的时间复杂度和空间复杂度。

正确答案：(1)算法的基本设计思想如解析所述。 (2)用C语言算法描述如下： void Adjust(int A[]){ ／／调整数组A，使得A的左边为负整数，

右边为正整数 int i=1，j=n，temp； while(i<j){while(A[i]<0&&i<j)i++； ／／A[i]为负整数时，i增1while(A[j]>0&&i<j)j--； ／／A[j]为正整数时，j减1if(i<j){ temp=A[i]；A[i]=A[j]；A[j]=temp； ／／A[i]为正整数、A[j]为负整数时，交换 i++： j--；} } } (3)算法的时间复杂度为0(n)；算法的空间复杂度为O(1)。

解析：本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组末端查找负整数，找到后进行交换，直到上、下界相遇。 具体做法是：设置两个指示器i和j，其中i=1，j=n；当A[i]为正整数，A[j]为负整数时，A[i]和A[j]交换；否则，A[i]为负整数时，则i++；A[j]为正整数时，则j--。这样， 可使算法的时间复杂度为O(n)。

43． 设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，设当前指令的地址码部分为001AH，正在执行的指令所在地址为1F05H，变址寄存器中的内容为23A0H。 (1)当执行取数指令时，如为变址寻址方式，则取出的数为多少? (2)如为间接寻址，取出的数为多少? (3)当执行转移指令时，转移地址为多少? 已知存储器的部分地址及相应内容，见下表。

正确答案：(1)变址寻址时，操作数S=((Rx)+A)=(23AOH+001AH)=(23BAH)=1 748 H。 (2)间接寻址时，操作数S=((A))=((001 AH))=(23AOH)=2600 H。 (3)

转移指令使用相对寻址，转移地址=(PC)+A=1F05 H+001 AH=1F1FH。 因为在本题中没有指出指令的长度，故此题未考虑PC值的更新。

解析：前两个小题涉及数据寻址，其最终目的是寻找操作数，第3小题涉及指令寻址，其目的是寻找下一条将要执行的指令地址。

44． 四位运算器框图如下图所示，ALU为算术逻辑单元，A和B为三选一多路开关，预先已通过多路开关A的SW门向寄存器R1，R2送入数据如下：R1=0101，R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下： (1)R1(A)+R2(B)→BR(显示结果1010)； (2)R2(A)+R1(B)→BR(显示结果1111)； (3)R1(A)+R1(B)→BR(显示结果1010)； (4)R2(A)+R2(B)→BR(显示结果1111)； (5)R2(A)+BR(B)→BR(显示结果1111)； (6)R1(A)+BR(B)→BR(显示结果1010)； 试分析运算器的故障位置与故障性质(“1”故障还是“0”故障)，说明理由。

正确答案：运算器的故障位置在多路开关B，其输出始终为R1的值。 (1)R1(A)+R2(B)＝1010，输出结果错； (2)R2(A)+R1(B)＝11 11，结果正确，说明R2(A)，R1(B)无错； (3)R1(A)+R1(B)＝1010，结果正确，说明R1(A)，R1(B)无错。由此可断定ALU和BR无错； (4)R2(A)+R2(B)＝11 11。结果错。由于R2(A)正确，且R2(A)＝1010，本应R2 (B)一101 0，但此时推知R2(B)＝0101，显然，多路开关B有问题； (5)R2(A)+BR(B)=11 11，结果错。由于R2(A)＝1010，BR(B)＝11 11，但现在推知BR(B)＝0101，证明开关B输出有错； (6)R1(A)+BR(B)＝1010，结果错。由于R1(A)＝0101，本应BR(B)＝11 11，但现在推知BR(B)＝0101，再次证明开关B出错。 综上所述，多路开关B输出有错。故障性质：多路开关B输出始终为0101。这有两种可能：一是控制信号BS0，BS1始终为01，故始终选中寄存器R1；二是多路开关B电平输出始终处于在0101上。

解析：根据已知的6步运算过程一步一步地分析，可知运算器的故障位置在多路开关B。

45． 在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统中有二个进程P0、P1已经就绪，进程P0首先获得处理机运行，调度算法为先来先服务，进程P0、P1的运行要求是这样的：P0：计算100ms，打印信息200ms，继续计算1 00ms，打印信息200ms，结束。P1：计算100ms，输入数据150ms，继续计算200ms，结束。 请用甘特图画出它们的运行轨迹，并说明： 进程P0、P1在运行时有无等待?若有，请指出时间区间。 计算处理机的利用率。

正确答案：根据题意，画出甘特图如下： 从运行的时序甘特图上可以看出：处理机在200ms到300ms之间是空闲的。因此，处理机的利用率可以计算出为：(200+300)÷600=83．3%。 进程P0运行过程中无等待现象，进程P1有等待现象，等待区间为350—400ms之间。

解析：本题考查进程调度的过程。解决这类题目的关键在于画出进程运行的时序图，若用条形来表示这种时序图就称为甘特图，然后再对其进行分析。绘图和分析过程中要注意题目适用的调度算法，先来先服务最简单，按先来后到的次

序进行调度，被调度的进程一般会占有处理机运行直到自己主动放弃；短进程优先算法在选取调度的进程时需要知道进程的预计执行时间，根据进程表里填写的进程预计执行时间，选取最短的进程调度其运行；高优先级优先的调度算法是根据进程表内赋予的优先级来调度，当然，优先级的确定可以有各种方法，可以在创建时确定，也可以根据程序的紧急程度确定，还可以根据收费多少确定，所以优先级的确定有许多灵活性，现行大部分操作系统均会采用高优先级优先的调度算法；时间片轮转的调度算法是由硬件时钟确定每一个进程占用处理机的时间的，进程按先来先服务排队，调度器调度进程队列中最先的进程运行，若分配的时间未到进程就主动放弃处理机，则会引起下一次调度，若分配的时间到，则不管进程是否运行完成，必须立即强制地出让处理机。在以上描述的各种调度算法既可以单独使用，也可以组合使用。不管采用什么算法，能否抢先是另一个调度的非常重要的因素，为适应不同用户的需求，也为改善计算机的性能，现代许多操作系统均采用抢先式调度算法，抢先式调度不能单独实施，一定是与上述各种调度算法相结合。处理机的调度相对较复杂，而IO的调度就简单了，为保证安全，一般IO设备是不能抢夺的，一旦分配，则一定是使用到进程主动放弃。

46． 某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节计址，每页的大小为1024字节。 (1)计算下列逻辑地址转换为物理地址，并说明为什么? 0793，1197，2099，3320，41 88，5332 (2)假设程序要访问第2页，页面置换算法为改进的Clock算法，请问该淘汰哪页?页表如何修改?上述地址的转换结果是否改变?变成多少?

正确答案：(1)根据题意，计算逻辑地址的页号和页内偏移量，合成物理地址如下表。 (2)第2页不在内存，产生缺页中断，根据改进的C1ock算法，第3页为没被引用和没修改的页面，故淘汰。新页面进入，页表修改如下： 因为页面2调入是为了使用，所以页面2的引用位必须改为1。地址转换变为如下表：

解析：本题考查逻辑地址到物理地址的转换，同时混合有缺页问题，页面置换问题，置换算法的应用等。根据题意，每页1024字节，地址又是按字节编址，因此，所有地址均可以转换为页号和页内偏移量。地址转换过程一般先将逻辑页号取出，然后查找页表，得到页框号，将页框号与页内偏移量相加，即可获得物理地址，若取不到页框号，那么，该页不在内存，于是产生缺页中断，开始请求调页，若内存有足够的物理页面，那么可以再分配一个新的页面，若没有页面了，就必须在现有的页面之中找到一个页，将新的页与之置换，这个页可以是系统中的任意一页，也可以是本进程中的一页，若是系统中的一页，则这种置换方式称为全局置换，若是本进程的页面，则称为局部置换。置换时为尽可能地减少缺页中断次数，可以有多种算法来应用，本题使用的是改进的Clock算法，这种算法必须使用页表中的引用位和修改位，由这2位组成4种级别，没被引用和没修改的页面最先淘汰，没引用但修改了的页面其次，再者淘汰引用了但是没修改的页面，最后淘汰既引用又修改的页面，当页面的引用位和修改位相同时，随机淘汰一页。解答如下。

47． 如果下表是路由器R1的路由表，仔细分析各个表项的特点，并回答

如下问题。 (1)给出m0和m1所在的网络号，以及可连接的最大主机数目。 (2)给出接口m0，m1和m2的合理的IP地址。 (3)试给出网络的拓扑。

正确答案：(1)m0和m1所在的网络号分别是145．23．128．0／20和202．14．17．192／26，可连接的最大主机数目分别是4094和62个。 (2)接口m0，m1和m2的合理的IP地址分别是145．23．129．65、202．14．17．200和130．56．12．5。 (3)如下图所示

解析：本题考查路由表的构建和原理，本题要从路由表出发，反推网络的拓扑的情况，因此首先要仔细分析路由表的每一个表项，首先第一个条目，涉及到接口m0所连接的网络，这里目的地址是145．23．129．7，掩码是255．255．1 92．0，即255．255．1100 0000．0，目的地址129转换为二进制1000 0．001，因此所连接的网络是145．23．128．0／20，主机位占有12位，因此最大主机数目是212一2=4094，因此接口m0只要取属于这个网络的任何地址都是可以的，但必须不能是145．23．129．7，这里无妨假定取145．23．129．65。同理，针对m1所连接的网络，这里目的地址是202．14．1 7．193，掩码是255．255．25 5．224，即255．255．255．11 10 0000，目的地之中最后一个字节193转换为二进制是1100 00001，因此接口m1所连接的网络是202．14．1 7．192／26，主机位占有6位，因此最大主机数目是26一2=62，因此接口mO只要取属于这个网络的任何地址都是可以的，但必须不能是202．14．17．193，这里无妨取202．14．17．200。最后一个表项是默认路由，仅给出了下一跳的地址，或者是一个网络，或许是ppp，因此只能假定m2的接口地址是130．56．1 2．5，这样这个路由器的基本情况就知道了，m0和m1分别连接两个网络，m2连接因特网，拓扑图就容易给出了。