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

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

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

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

while(i<=n)i=i*2：

A、O(log2n)

B、O(n)

C、O(nlog2n)

D、O(n2)

标准答案：A

知识点解析：这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)

的结果。关键在于分析出while语句执行的次数。由于循环体中，i=i*2,所以循环

执行的次数是Iog2。，由此可见，算法的时间复杂度不是由问题规模n直接决定，

而是log2n0

2、下列关于栈和队列说法中，正确的是()。

A、消除递归不一定需要使用栈

B、对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也

一定相同

C、通常使用队列来处理函数或过程调用

D、队列和栈是操作受限的线性表，只允许在表的两端进行运算

标准答案：A

知识点解析：使用栈可以模拟递归的过程以此来消除递归，但对于单向递归和尾递

归而言，可以用迭代的方式来消除递归，所以选项A正确；不同的进栈和出栈组

合操作，会产生许多不同的输出序列，所以选项B错误；通常使用栈来处理函数

或过程调用，选项C错误；队列和栈都是操作受限的线性表，但只有队列允许在

表的两端进行运算，而戌只允许在栈顶方向进行操作。

3、已知栈的输入序列为1,2,3,…，n,输出序列为pi，p2，P3，…，Pn»若

Pl=3,则P2的值为O。

A、一定是2

B、一定是1

C、可能是I

D、可能是2

标准答案：D

知识点解析：当第一个出栈元素为3时，1,2一定压在栈内，下一个出栈的元素

可能是2,不可能是1。当然如果4,5…进栈，第一个出栈的元素也可能不是2。

4、下列关于二叉树的说法中，正确的是（）。

A、度为2的有序树就是二叉树

B、含有n个结点的二叉树，其高度为［log2nHi

C、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点

D、在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得的二叉排序

树与删除前原二叉排序对相同

标准答案：C

知识点解析：二叉树是有序树，但是度为2的有序树却不是二叉树，所以选项A

错误：选项B当且仅当完全二叉树时才有意义，对于任意一棵二叉树高度可能为

Uog2n］+I=n；根据完全二叉树的定义，选项C正确；在二叉排序树上删除结点时

可能会调整部分结点的位置，而插入时一定是插在叶子结点的位置，故先删除再插

人结果可能就不再一样了，所以选项D错误。

5、含有n个结点的三叉树的最小高度是（）。

A^n

B、［n/3］

C、［log3nn］+l

D、［log3（2n+l）］

标准答案：D

知识点解析：设含有n个结点的三叉树的最小高度为h（为完全三叉树时高度最

小），第h层至少有一个结点,至多有3勤个结点，则有：l+31+32+...+3h-

2l+32+...+3h-2+3h-1BP：（3h-1-l）/2h-l）/2^：3环〈2叶仁3人也就是：h<

log3（2n+l）+l,hKog3（2n+l）而h只能是正整数，则h=［log3（2n+l）］,所以，含有n

个结点的三叉树的最小高度是［log3（2n+l）］o

6、某二叉树的先序遍历序列为LJKLMNO,中序遍历序列为JLKINMO,则后序遍

历序列是（）o

A、JLKMNOI

B、LKNJOMI

C、LKJNOMI

D、LKNOJMI

标准答案：C

知识点解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍

历序列。

7、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为Nl,N2和

N3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A、NI

B、NI+N2

C、N3

D、N2+N3

标准答案：D

知识点解析：由森林转生的二叉树中，根结点即为第一棵树的根结点。根结点的左

子树是由第一棵树中除了根结点以外其余结点组成的；根结点的右子树是由森林中

除第一棵树外其他树转爽来的。

8、以下关于图的说法正确的是（）。I图G的生成树是该图的一个极小连通子图

n生成树中最长路径的起点和终点的度均为1m对任意一个图，从某个顶点

出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

A、I、n

B、口、DI

C、I、皿

D、仅有n

标准答案：D

知识点解析：说法I是错误的，图G的生成树是该图的一个极小连通子图，但必

须包含全部顶点。说法II是正确的，可用反证法证明。设Vl，V2，…Vk是生成树

的一条最长路径，其中，V］为起点，为终点，若vk的度为2,取vk的另一个邻

接点V,由于生成树中元回路。所以，V在最长路径上，显然Vl，V2，…，Vk，V

的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点

VI的度不能大于1,只能为1。说法HI是错误的，只有连通图从某个顶点出发进行

一次遍历，可访问图的所有顶点。

9、已知有向图G=（V,A）,其中V={a,b,c,d,e},A={<a,b>,<a,c>,

<d,c>><d,e>,<b,e>,<c,e>）,对该图进行拓扑排序，下面序列中

不是拓扑排序的是（）。

A^a,d,c,b,e

B、d,a,b,c,e

C、a,b,d,c,e

D^a,b,c,d,e

标准答案：D

知识点解析：对AOV网进行拓扑排序的方法和步骤是：（1）从AOV网中选择一个

没有前驱的顶点（该顶点的入度为0）,并且输出它；（2）从网中删去该顶点，并且删

去从该顶点发出的全部有向边；（3）重复上述两步，直到剩余的网中不再存在没有

前驱的顶点为止。本题按照拓扑排序方法对该图进行拓扑排序使可得到结果。

10、序列（8,9,10,4,5,6,20,1,2）,只能是以下哪种排序方法两趟排序后

的结果是（）。

A、选择排序

B、冒泡排序

C、插入排序

D、堆排序

标准答案：C

知识点解析：本题主要考查各种排序的手工排序过程。执行两趟选择排序后，结果

应该是(1，2,……)。执行两趟冒泡排序后(假设扫描是从前向后)，结果应该是

(……，10,20)o执行两趟堆排序后，若采用大根堆，则结果应该是(……，10,

20)；若采用小根堆，则结果应该是(……,2,1)0执行两趟插入排序后，待排序序

列前3个关键码有序。

11、对关键码序列(23,17,72,60,25,8,68,71,52)进行堆排序，输出两个

最小关键码后的剩余堆是()。

A、(23,72,60,25,68,71,52)

B、(23,25,52,60,71,72,68)

C、(71,25,23,52,60,72,68)

D、(23,25,68,52,60,72,71)

标准答案：D

知识点解析：本题主要考杳堆排序过程。筛选法初始建堆为(8,17,23,52,25,

72,68,71,60),输出8重建堆(17,25,23,52,60,72,68,71),输出17重

建堆为(23,25,68,52,60,72,71)。

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

图］.1

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

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

C、应运算器、②存储器、⑥控制器、④输入设备、既输出设备

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

标准答案：B

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

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

13、31的八位二进制反码表示为()。

A、11111

B、1.00111e+007

C、l.lle+007

D、l.lle+007

标准答案：C

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

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

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

A、2

B、3

C、4

D、5

标准答案：C

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

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

错的同时还要能发现2位错，则满足21?」加+1<+1。事实上，题中给出的具体数据

对结果没有任何影响，真正有影响的是数据的位数。

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高DDRAM芯片的成本比SRAM高DIDRAM芯片的速度比SRAM快

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

的是（）。

A、I和H

B、II和HI

C、HI和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个子部件完成，每个子部件的工作周期均为

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

A^8AI

B、lOAt

C、12At

D、14At

标准答案：D

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

=3At+lI△t=14Ato

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

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

A、101

B、102

C、103

D、104

标准答案：A

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

程序，所以至少有：101个微程序。

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

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

A、3.3MB/s

B、64MB/s

C、132MB/s

D、164MB/s

标准答案：C

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

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

So

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

A、23

B、28

D、2512

标准答案：C

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

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

22、关于程序中断方式和DMA方式的叙述中错误的是（）。I若同时接到DMA请

求和中断请求，CPU优先响应DMA请求II程序中断需要保护现场，DMA方式

不需要保护现场HI程序中断方式的中断请求是为了报告CPU数据的传输结束，而

DMA方式的中断请求完全是为了传送数据W中断方式和DMA方式中，快速［/0

设备更适合采用中断方式传递数据

A、U、IV

B、口、m、IV

c、m、w

D、i、m、w

标准答案：c

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

方式。在这两种控制方式下，CPU和I/O设备可以并行正作。DMA方式的中断

请求是为了报告CPU数据的传输结束。中断方式需要执行中断服务程序，并且完

成一次程序中断还需要许多辅助操作，所以它主要适用于中、低速外设。

23、构造操作系统的主要结构模式是（）。I整体式结构n层次式结构HI微内核（客

户/服务器）结构W对称式结构

A、I和m

B、II和W

c、I、n和in

D、口、in和w

标准答案：c

知识点解析：操作系统是一种大型的、复杂的系统软件，为了合理地使用操作系

统，必须分析、了解并掌握其结构。在操作系统的发展过程中，出现了多种操作系

统结构，整体式结构是早期操作系统设计中所采用的方法，即首先确定操作系统的

总体功能，然后将总功能分解为若干个子功能，实现每个子功能的程序称为模块。

层次式结构力求使模块向调用的无序性变为有序性。因此层次式结构最内层是裸

机，裸机的外层是操作系统的第一层，以后每增加一层软件就是在原虚拟机上的又

一次扩充，又成为一个新的虚拟机。微内核（客户/服务器）结构的操作系统适宜于

应用在网络环境下分布式处理的计算环境中。内核只提供了一个很小的功能集合。

除内核部分外，操作系统所有的其他部分被分成若干个相对独立的进程，每一个进

程实现一组服务，称为服务进程。这些服务进程可以提供各种系统功能、文件系统

服务以及网络服务等。对称式结构在操作系统结构设计中是不存在的。

24、某系统正在执行〉U)时间和I/O时间

进程计算时间I/O时间

P190%10%

P250%50%

P315%85%

比例如表1-1所列。为提高系统资源利

用率，合理的进程优先级设置应为

A、B1>F2>P3

B、P3>P2>P1

C、P2>P1=P3

D、P1>P2=P3

标准答案：B

知识点露析：本题考查考生对调度算法的实际应用。不同的调度算法具有不同属

性，可能对某些进程有特殊偏好。例如短进程优先算法就会特别眷顾短进程，长进

程就会被忽视。这与设计操作系统时需要保证系统的公平性相悖，所以，为了选择

合适的算法，必须分析各个算法的属性。调度的基本准则包括：尽可能让昂贵的处

理机处于繁忙中；单位时间内所完成进程的数量尽量多；要LL周转时间尽可能地

少；后备时间越短越好；等待时间越短越好；响应时间越短越好。本题中，由于进

程的CPU时间和I/OE寸间不同，I/O越繁忙，表示其状态由执行到阻塞的变化

越多，为此，公平起见，给予较高的优先级，同时也避免CPU繁忙的进程独占处

理机。考察本题，调度的公平性是最重要的。若将P1的优先级设为最高，那么很

有可能其会长期占用处理机，造成其他进程的饥饿，所以，从公平性考虑，需要均

衡配置处理机的时间。

25、一个支持并发的操作系统在运行过程中，调度模块会不断地选择新进程投入运

行.在非抢先式操作系统中,下面不是引起操作系统重新选择新进程的直接原因是

()。

A、分配的时间片用完

B、运行着的进程要等待某一信号到来

C、正在运行的进程出错

D、有新进程进入就绪队列

标准答案：D

知识点解析：本题考查进程调度的时机。在所列出的四个选项中，A、B和C的情

况一旦发生，处理机空闲，操作系统必须立即调度其他进程，而D选项有新的进

程进入就绪状态，如果操作系统采用的是抢先式调度，则立即激活调度模块，进行

进程调度，进程调度的结果可能引起进程切换，也可能维持当前进程运行而不切

换；而当操作系统采用非抢先式调度方式时，当新进程进入就绪状态，若此时处理

机正在忙于处理当前运行进程的请求，则不会激活调度模块。这里需要了解进程调

度的细节问题。

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

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

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

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

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

标准答案：C

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

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

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

临界区是不允许其他进程访问的。其他进程若要访问，必定会在临界区的"锁''上阻

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

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

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

A、存取控制列表

B、用户权限保护

C、程序状态保护

D、界地址保护

标准答案：D

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

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

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

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

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

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

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

28、某简单分页式存储管理中,逻辑地址空间分页为每页1KR.对应相应的物理

块。设主存总容量为256KB,描述主存分配情况如表1—2所列（0表示未分配，1

*1-2

起始页号位示图

011111111111)1111

161011100000111000

321111111111111.........

表示已分配）。此时，操作系统创

建了一个新进程，大小为2.5KB,按首先分配低址空间的策略，那么，分配给该

进程的页面的页号分别是（）。

A、17、21和22

B、21、22和23

C、23、24和25

D、29、30和31

标准答案：A

知识点解析：本题考查简单页式地址分配和转换的计算。根据题目给出的条件，进

程的大小为2.5KB,它所需要占用的空间为3页，对应3个物理块。按题意是从

地址的低址部分开始分配。因此，查看位示图，看到从低到高别别是17、21和22

空闲，则进行分配。若考虑程序运行的优化，则希望这3页装入内存时放到一起，

则21〜25以及29〜31均可以使用，而29〜31的分配更加有利，可以使得内存效

率更高，硬件使用更均衡。由于页式分配的特点，虽然页面的分配可以离散化，理

论上可以分配在内存中的任何地方，但是从内存使用的效率和均衡，以及对于代码

优化，快表更新和减少转移引起的缺页中断等方面考虑，尽量集中分配对整个系统

还是更加有利的。本题并不考查这一点，所以按最简单的算法去分配即可。

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

（）。

A、成正比

B、成反比

C、无关系

D、固定值

标准答案：C

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

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

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

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

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

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

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

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

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

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

数关系并没有确定的关系。正确答案为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。确定了磁道，

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

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

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

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

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

取整得161,得到扇区号，余下逻辑块编号的偏移量是2,此号便是磁头号了，所

以，其对应的三要素单位为2,250,161o

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

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

A、重名翻译机构

B、建立索引表

C、建立指针

D、建立多级树形目录结构

标准答案：D

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

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

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

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

32、设备管理中，能够用空间换取时间的技术是（），

A、SPOOLing

B、虚拟存储技术

C、覆盖与交换技术

D、通道技术

标准答案：A

知识点解析：本题考查SPOOLing系统的功能，SPOOLing技术，即同时联机外围

操作技术，乂称假脱机技术，是指在多道程序环境下，利用多道程序中的一道或两

道程序来模拟脱机输入输出中的外围控制机的功能，以达至『脱机''输入输出的目

的，即在联机的条件下，将数据从输入设备传送到磁盘，或从磁盘传送到输出设

备。因此它一方面解决了低速设备与高速设备之间的链接，解放了高速设备被频繁

中断的不足，另一个方面通过它可以将一台独占的物理设备虚拟为多台逻辑设备，

故，事实上它是以空间（磁盘上的存储块）换取了时间（低速配高速以及解决了同时访

问问题）。虚拟存储技术和覆盖与交换技术是为了扩充存储的容量，并不能改善时

间响应速度；而通道技术提高设备的并发度，即提高了数据交换的速度，它并不占

用更多的空间。

33、关于OSI参考模型和TCP/IP模型在网络层提供的服务，正确的说法是（）。

A、0SI模型在网络层仅提供面向连接服务

B、TCP/IP模型在网络层提供无连接服务

C、OSI模型在网络层仅提供无连接服务

D、TCP/IP模型在网络层提供无连接和面向连接服务

标准答案：B

知识点解析：本题考查OSI参考模型和TCP/IP模型的层次功能比较，重点是网

络层所提供的服务，也就是网络层的功能。在OSI参考模型中，网络层提供无连

接和面向连接的两种服务方式，而TCP/IP模型在传输层提供了面向连接和面向

无连接两种服务。在网络层仅提供无连接的服务方式，选项A,C仅阐述了OSI模

型网络层所提供服务的一个方面，选项D则给TCP/IP模型的网络层多增加了面

向连接服务，因此答案是B。

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

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

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

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

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

标准答案：D

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

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

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

作在850nm或1310n与光器件的耦合相对容易，也就是主要区别在于直径的

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

Do

35、使用HDLC时,位串011111H0111110进行位填充后的位模式是O。

A、1.110lle+016

B、1.11101e+014

C、1.11111e+014

D、l.lllle+015

标准答案：D

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

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

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

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

位,为“1”则出错。即：发送方：除标志位外，连续发现5个“1”后自动插入“0”。

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

其后为“0”，则自动去掉该

（如果为“0”，

接收方：连续发现5个“1"后1甘1ali..皿5K士代

其后为1，则检查下一位《则为标志位.

'为“1”出错•经过填

充后是01111101101111100,特别注意即使5个1后面是0,也是需要再添加一个

0的，因此答案为D。

36、在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过

一段时间，发送窗口的后沿的变化情况可能是()。I原地不动n向前移动HI向后

移动

A、I、m

B、I、口

c、u、m

D、都有可能

标准答案：B

知识点解析：本题考查滑动窗口机制的工作原理，注意发送窗口的后沿的变化情况

只能有两种：⑴原地不动(没有收到新的确认)；(2)向前移动(收到了新的确认)。

发送窗口不可能向后移动，因为不可能撤销掉已收到的确认帧，因此答案是B。

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

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

A、1011

B、1101

C、1110

D、1100

标准答案：B

知识点解析：本题考查CRC校验的计算方法。设信息位串为a%2a3……am,则信

息编码多项式为M(x尸a】xm/+a2xm-2+a3xm-3+……+四选择一个r次多项式G[x)作

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

式为X『M(x)；(2)用模2又不借位除法，计算X「M(K)/G(X)的余数R(x)。R(x)就是

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

本题中该字符串为1010001,G(X)=X4+X?+X+1，因此M(X)=X6+X4+L

r=4x「M(x)=xi°+x8+x4T10100010000计算R(x)=xrM(x)/G(x)的过程如下:

1001111

loin/ioioooioooo"

10111

11010

10111

noio

10111

noio

10】ll

noio

10111

1101R(x)为1101,SiltR(x)=xrM(x)/G(x)=x3+x2+l,T(x)=xrM(x)/

G（x）+R（x）=x,0+x8+x4+x3+x2+l,也就是1010001（信息位串）1101（校验位串），因此

答案为B。

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

TCP协议II路由器必须实现TCP协议m主机必须实现IP协议H路由器必须实现

IP协议

A、I、II和出

B、I、II和W

c、I、ni和w

D、口、in和w

标准答案：c

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

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

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

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

39、下面包含在TCP头中而不包含在UDP头中的信息是（）o

A、目标端口号

B、序号

C、源端口号

D、校验号

标准答案：B

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

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

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

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

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

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

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

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

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

标准答案：C

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

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

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

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

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

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

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

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

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

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

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

41、将任意给定的序列1,2,…，n指定为一棵树的先根遍历序列；同时任意给定

这n个数值（1,2,n）的一个排列pi，P2…Pn为这棵树的后根遍历序列。⑴根

据这样的先根遍历序列和后根遍历序列，是否都可以得到一棵树?如果能够，清简

述理由（不要求形式化证明）。如果不能，请给出一个简单反例。（2）如果能得到

树，所得到的树是否唯一?如果能够，请简述理由（不要求形式化证明）。如果不

能，请给出一个简单反例。

标准答案：（1）不一定能得到一棵树。反例（给出任何一个正确的反例即可）：反例

1：对于先根遍历序列｛1,2,3,4）,后根遍历序列｛1,3,2,4｝这种情况，就无

法得到一棵树。反例2：对于先根遍历序列｛1,2,3,4）,后根遍历序列（4,2,

3,1｝这种情况，也不能得到一棵树。理由（题目并不要求说明理由，如果说清了

理由而没有给出反例，也可以得分）：理由一：若一棵树的先根遍历序列为｛1,

2,3,4）,则1必为树根，该树的后根遍历序列中“1”一定在最后，故根据最后数

字不为“1”的后根序列与先根序列［1,2,3,4）就无法得到一棵树v理由二：一棵

树可以转换成一棵没有右子树的二叉树，反之亦然。所以，对于n个结点的树，可

以等价地考虑相应的除去根结点（即1）以外的（n-1）个结点的二叉树问题。在这旦

2,3,…，n就是相应的二叉树的先序遍历序列pi，pz，…pn-i就是相应二叉树的

中序遍历序列。对于n个结点的树，可以等价地考虑相应的n-I个结点的二叉树问

题。该问题转换为：指定2,3,…，n这n-1个数为一棵二叉树先序遍历序列；同

时Pl，P2，…Pn-I（其中pi，P2，…Pn-1，为2,3,…，n这n-1个数值的一个排列）

为这棵树的二叉树中序遍历序列。是否都可以得到一棵二叉树？可以证明：对于一

棵先序遍历序列为1,2,n的二叉树，在中序遍历时其被涉及的顺序也就是进

入运行栈的顺序就是1,2,n,其中中序遍历顺序，则是一种可能的出栈顺

序。有可能从初始输入序列1,2,n,利用一个栈得到输出序列pi，

P2，…Pn（Pl，P2，…Pn是।，2,…，n的一种排列）的充分必要条件是：不存在这

样的i,j,k,满足iVjVk同时pjVpkVpi。因此,先根序列1,2,n和后根

序列Pl，P2,…Pn-l，1能够得到一棵树的充分必要条件是不存在下标i，j，k,满

足iVjVk同时pjVpkVpi。（2汝11（1）所述，不一定能得到一棵树。但是如果所给出

的序列合法，就能够得到一棵树，而且得到的树是唯一的。所谓合法序列是指：

先根遍历序列为1,2,...»n,后根遍历序列为pi，P2，…，Pn，那么只有当

Pn=l时,，而日在pi，P2........Pn-1中不存在这样的i，j，k,满足iVjVk同时pjV

Pk<Pi。（不要求考生说明什么是合法的）理由一：一棵树可以转换成一棵没有右子

树的二叉树，反之亦然。所以，对于n个结点的树，可以等价地考虑相应的除去根

结点（即1）以外的（n-1）个结点的二叉树问题。在这里2,3,…，n就是相应二叉树

的先序遍历序列pi，P2,…，Pn-1就是相应二叉树的中序遍历序列——二叉树先序

序列为DLR,二叉树中序序列为LDR,因此可以定位二叉树的根，然后定位出二

叉树的左右子树并对左右子树做类似的递归处理，故所的二叉树是唯一的。因此相

应的树也是唯一的。理由二：对于合法的序列：先根序列为1,2,…，n,后根序

列为pi，P2,…，Pn-l，首先可以确定树根为1。其子树形成的森林的先根序列为

2,...»n,后根序列为pi，p2»...»pn-b这些森林被分成m(mK))个不相交的集

合Ti，T2,…，Tm,而且这些集合的每一个又都是树;在先根序列中按照

T2,Tm的结点顺序出现，在后根序列中也按照T1，T2,…，Tm的结点顺序

出现(但是对应的每个集Ti中，结点出现的顺序不同)。因此可以找到每棵子树的

结点集合，然后进行递归处理，最终只能得到棵确定的树。

知识点解析：暂无解析

42、设有一个双向链表h,每个结点中除有prior、data和next共3个域外，还有一

个访问频度域freq,在链表被起用之前，每个结点中的freq域的值均被初始化为

零。每当进行LocateNode(h,x)运算时，令元素值为x的结点中freq域的值加1,

并调整表中结点的次序，使其按访问频度的递减序列排序，以便使频繁访问的结点

总是靠近表头。试写一符合上述要求的LocateNode运算的算法。

标准答案：算法如下：intLocaieNode(DuLlnkList&h,臼emTypex){DuLinkLisl

p=h->next,q：while(p!=NULL&&p->data!=x)p=p->next：//找data域值为

x的结点*pif(p=NULL>//未找到这样的结点return。：clse{//找到这样的结

点*pp->freq++；//频度增1q=q->prior；//*q为*p前驱结点if(q!=h){//

若*p为第一个数据结点，则不移动while(q!=h&&q->freqVp->freq)//找到*q

结点，®q->frcq>=p->frcqq=q->prior；p->prior->ncxt=p->next；//先删除

*p结点if(p->nexl!=NULL>p->nexl・>prior=p->prior；p->next=q->next；//

您*p结点ifi入到*q结点之后if(q->next!二NULL)q->next->prior=p：q->

ncxt=p；p->prior=q；}return1；)}

知识点解析：暂无解析

43、问：下列正EE754单精度浮点数所表示的十进制数分别是多少？(1)10111101

010000000000000000000000(2)01010101011000000000000000000000(3)1100

0001111100000000000000000000(4)00111010100000000000000000000000

(5)00000000000000000000000000000000

标准答案：(1)符号位为1,表示这是一个负数。阶码字段=O1I11O1OB=122D,阶码

真值=122-127=5,尾数字段二10000000000000000000000B。所以十进制数值

为：-(1.I)2X2-5=0.046875C(2)符号位为0,表示这是一个正数。阶码字段

=10101010B=170D,阶码真值二170-127=43,尾数字段二1100000000000000000

0000Bo十进制数值为：(1.11)2X243=1.539xioq表示为4位有效数字形式)。

(3)符号位为1,表示这是一个负数。阶码字段=10000011B=131D,阶码真值

127=4,尾数字段=11100000000000000000000。十进制数值为：・(1.111)2x24=

30(4)符号位为0,表示这是一个正数。阶码字段=0U10101B=117D,阶码真值

=117-127=-10,尾数字段-0000000000000000000()000。十进制数值为：

,O

（I.O）2X2-=O.0009766（表示为4位有效数字形式）。（5）由于符号位为0,阶码字

段和尾数字段均为全0,所以它表示机器零。

知识点解析：暂无解析

44、某机主存容量为1MB,两路组相连方式（每组仅有两块）的Cache容量为

64KB,每个数据块为256字节。CPU要顺序访问的地址为20124H、58100

60140H和60138H等4个主存字节单元中的数。已知访问开始前第2组（组号为1）

的地址阵列内容如表5-3所列，Cache采用LRU。替换策略。说明Cache的结构

（即分多少组、组内分多少块），给出主存及Cache的地址格式。上述4个数能否直

接从Cache中读取，若能，请给出实际访问的Cache地址。第4个数访问结束时，

as-3

00100《二进制）

010］】《二进制）

图的内容如何变化。

标准答案：Cache分为128组，组内分成2块，主存和Cache的地址格式如图5—3

的地址写出二进制，可以发现:20124H=00100000000100100100B,组号为1,是

第2组的块，根据第44题图可知，现在Cache内有这个块，第1次访问命中，实

际访问的Cache地址为0124H。58100H=01011000000100000000B,组号为1,

是第2组的块，现在Cache内有这个块。第2次访问命中，实际访问的Cache地址

为0100H。60140H=01100000000101000000B,组号为1,是第2组的块,但

Cache中没有这个块，第3次访问不命中，根据LRU算法，替换掉第0块位置上

»5-5

00】100（二迸制）

101011（二进总）

的数据块，变化后的地址阵列如表5—5所列。

60138H=01100000000100111000B,组号为1,是第2组的块,与上一个地址处于

同一个块，此时这个块已调入Cache中，所以第4次访问命中，实际访问的Cache

地址为0138H。第4个数访问结束时，地址阵列的内容与刚才相同。

知识点解析：暂无解析

45、在某勘探队计算中心的大型计算机系统中，某台大型机可供用户使用的内存空

间为1000MB,系统连接有绘图机1台，打印机2台。某天该系统接到了作业任务

如下表5—4所列：

衰5-4作业情况

作业号到达时间演计运行时间颈计所II内存使用笈图机使用打印机

1810025分150MB11

28,2020分300MB01

38,2010分600MB10

48|3030分200MB01

58,3515分100MB11

大型机的内存采用可变分区的动态分配方式，且使用最先适应算法，作业装入内存

以后不能移动。设备分配采用静态分配算法，为提高效率，仅当作业创建到内存后

才申请。其中，作业调度采用短作业优先的算法，进入内存后的进程调度采用先来

先服务的算法。忽略系统调度的开销。请问：（1）作业调度选中作业的序列是什么？

⑵各个作业的周转时间是多少?平均周转时间又是多少？（3）当天上午作业的每小时

的吞吐量是多少？（4）全部执行完成后的时间是几点。

标准答案：（1）作业调度的序列为：作业1,作业3,作业4,作业2,作业5。（2）

作业的周转时间见下表5—7

衰5-7作业的周转时间

作业等待时间运行时间周转时间

作业1025分25分

作业2