一、选择题（2 分/题）

1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据一次写入该缓冲取，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是______。

A.栈 B.队列 C.树 D.图

解答：B 。先入先出，显然是队列。

2.设栈 S 和队列 Q 的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b ，d，c，f，e，a，g，则栈 S 的容量至少是____.

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

解答：C 。出队顺序可看作出栈顺序。a，b入栈（容量为 2 ），b出栈；c，d入栈（容量为 3 ），d出栈，c出栈；e、f入栈（容量为 3 ），f 出栈，e 出栈，a 出栈；g 入栈（容量为 1 ），g出栈。故 S 的容量至少是 3。

3.给定二叉树如图所示。设 N 代表二叉树的根，L代表根结点的左子树，R 代表根节点的右子树。若遍历后的节点序列是 3，1，7，5，6，2，4，则其遍历方式是_____。

A.LRN B.NRL C.RLN D.RNL

解答：D 。第一个节点是 3 ，必定先 R 。第二个节点是 1 ，N 是第二个。所以是 RNL。

4.下列二叉排序树中，满足平衡二叉树的定义的是______。

A. B. C. D.

解答：B。二叉排序树——空二叉树或者二叉树上任一节点的值小于其右子树上任一节点的值并且大于左子树上任一节点的值。平衡二叉树——空二叉树或者二叉树上任一节点的左右子树高度差不大于1。

5.已知一棵完全二叉树的第六层（设根为第一层）有八个叶节点，则该完全二叉树的节点数量最多为____。

A.39 B.52 C.111 D.119

解答：C。完全二叉树。深度为 h 的二叉树，除第 h 层外，其他各层的节点个数都达到最大个数，且第 h 层所有节点都集中在最左边。题目中第六层有八个叶子节点，所以最多有七层，且第六层最多只有 2^5-8 个节点有左右子树，所以答案为 1 + 2 + 4 + 8 + 16 + 32 + (32-8)*2 =111。

6.将森林转化为对应的二叉树，若在二叉树中，节点 u 是节点 v 的父节点的父节点，则在原来的森林中，u 和 v 可能具有的关系是_____。

Ⅰ.父子关系 Ⅱ.兄弟关系 Ⅲ. u 的父节点和 v 的父节点是兄弟关系

A. Ⅱ B.Ⅰ、Ⅱ C.Ⅰ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ

解答：B。将森林转化为二叉树——从根节点开始，使每个节点的左节点指向其最左方的左节点，右节点指向其兄弟节点（不同二叉树的根节点视为兄弟节点）。对于前两种情况，如下所示，对于第三种，若u，v 的父节点是兄弟关系，则u和v处于不同分支上，不具备任何关系。

父子关系兄弟关系

7.下列关于无向连通图特性的叙述中，正确的是_____。

Ⅰ.所有顶点的度之和为偶数 Ⅱ.边数大于顶点个数减一 Ⅲ. 至少有一个顶点的度为 1

A. Ⅰ B.Ⅱ C.Ⅰ、Ⅱ D.Ⅰ、Ⅲ

解答：A。无向连通图——图中所有节点之间都是连通的（图中任一节点都可通过某条路径到达其余所有节点）且路径无向。Ⅰ 所有顶点的度之和=边数*2 ，一定是偶数。 Ⅱ 一条直线，端点为顶点，不符合题目要求 Ⅲ 若无向连通图为三角形，没有一个顶点的度为1

8.下列叙述中，不符合 m 阶b树定义的是_____.

A.根节点最多有 m 棵子树 B.所有的叶节点都在同一层上

C.各节点内关键字均升序或降序排序 D.叶节点之间通过指针连接

解答：D. B树，也叫B-树，是一种多路平衡查找树。一个 m 阶 B 树的每个节点最多拥有 m 个子树，一个节点最多拥有 m-1 个关键字，A 正确。b 树中，所有叶子节点都在同一层，B 正确。B树中关键节点按升序排序，C正确。叶节点，没有子节点的节点，且B树中叶子节点并不相连，因此D错误。

一棵 m 阶 B 树满足下列条件：

（1）每个节点至多有 m 棵子树。

（2）除根节点和叶子节点外，每个节点的子树数量至少为 m 的一半。

（3）根节点至少有两棵子树（除非 B 树只包含一个节点）

（4）所有叶节点在同一层上。B树的叶节点可以看成一种外部节点，不包含任何信息。

9.已知关键字序列 5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字 3 ，跳调整后得到的小根堆是_____。

A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28

C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19

解答：A。

10. 若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_____。

A. 冒泡排序 B.插入排序 C.选择排序 D.二路归并排序

解答：B。

若是冒泡排序，则排序后最大或最小的元素在两端，但11，5并不是最大值或最小值，所以 A 不正确。

插入排序，假设数组长度为 n ，插入排序对数组进行 n 次操作，第 x 次是前 x+1 个元素有序。数组序列中前三个元素有序，因此可能是插入排序，B 正确。

选择排序，在序列中选出最大或最小元素后将其放在数组首位或末尾，将未排序元素作为一个新的序列重复此操作直至完全有序。若是选择排序，两端为最大或最小元素，C不正确。

二路归并排序，又称合并排序。采用分治思想，将两个序列划分为若干个有序子表后，两两合并。序列中子表 arr[0],arr[1] ,子表arr[1],arr[2] ，子表arr[3],arr[4]，子表arr[5],arr[6]，子表arr[7],arr[8]，并不按照同一顺序排序，故 D 不正确。

11.冯.诺伊曼计算机中指令与数据均以二进制数据的形式存放在存储器中，CPU区分它们的依据是_____。

A.指令操作码的译码结果 B.指令和数据的寻址方式

C.指令周期的不同阶段 D.指令和数据所在的存储单元

解答：C。

12.一个C语言程序在一台 32 位机器上运行。程序定义了 3 个变量 x，y 和 z，其中 x 和 z 是 int 型，y 是 short 型。当 x = 127 ，y=-9 时，执行赋值语句 z=x+y 后，x、y 和 z 的值分别是_____。

A.x=0000007FH y=FFF9H z=00000076H

B.x=0000007FH y=FFF9H z=FFFF0076H

C.x=0000007FH y=FFF7H z=FFFF0076H

D.x=0000007FH y=FFF7H z=00000076H

解答：D 。x的16进制表示为 0000007FH，9的二进制表示为 0000 1001B 按位取反加一为 11110111B ，对应的16进制为 F7 ，所以 y 的 16进制为 FFF7H。在计算 x+y 时，y 由short 转化为 int ，因为二进制首位为 1，因此前面补 F，即 y=FFFF FFF7H，x+y=0000 007FH+FFFF FFF7H= 0000 00076H，产生进位 1 自然丢弃。

13.浮点数加、减运算过程一般包括对阶、位数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位（均含两位符号位）。若有两个数 X=2^7 *(29/32),Y=2^5*(5/8)，则用浮点加法计算 X+Y 的最终结果为 _____。

A.00111 1100010 B.00111 0100010 C.01000 0010001 D.发生溢出

解答：D

x = 29/32 * 2^7 阶码为 7，尾数为 29/32

y =5/8 * 2^5 阶码为 5 ，尾数为 5/8

计算 x+y：

（1）对阶，阶码小的向阶码大的看齐，x不变，y =5/8 * 2^7/2^2 = 5/32 * 2^7

（2）尾数求和，x 的尾数为 29/32，即 0.11101

y的尾数为 5/32 ，即0.00101

尾数之和 0.11101+0.00101 = 1.00010

（3）规格化，x+y=1.00010 * 2^7=0.10001 *2^8

(4) 判断溢出。因为有两位符号位，根据答案，阶码共有 5 位，2位阶符，3 位数值部分，无法表示 8 即 01000 阶码符号位为 01 ，故发生溢出，选D。

14.某计算机的 Cache 共有 16 块，采用 2 路组相联映射方式(即每组 2 块)。每个主存块大小为 32B ，按字节编址，主存 129 号单元所在主存块应装入到的 Cache 组号为_____。

A. 0 B.1 C.4 D.6

解答：C

Cache 高速缓冲存储器简称快存，是为了解决 CPU 和主存之间速度匹配问题而设置的。

（1）Cache 有 16块，每组 2 块，则共有 8 组。

（2）每个主存块为 32B，所以129 号单元在主存第 4 个块上（129/32 向下取整）。

（3）Cache 采用二路组相联映射方式，组间直接映射（第 i 个块映射到第 i%8 个组内），组内全相联映射（与第 i 个组对应的块可以放置在组内任意位置）。

综上所述，129 号单元，主存第 4 个块上的数据存放的 Cache 组号为 4%8 =4。

15.某计算机主存容量为 64KB，其中 ROM 区为 4KB，剩余为 RAM 区，按字节编址。现在要用 2K*8 位的 ROM 芯片和 4K*4 的位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数量分别是______。

A.1、15 B.2、15 C.1、30 D.2、30

解答：D。

ROM——只读存储器（只能读出）。RAM——随机存储器（既能读出又能写入）。按字节编址——存储单位的最小单位是字节（8b）。

计算机按字节编址，即主存的 ROM 区为 4K*8 位， ROM芯片大小为 2K*8 位，因此需要 (4K*8) / (2K*8) = 2 个ROM芯片

计算机按字节编址，即最小单位是 8b，而 RAM 芯片最小单位是 4 b，因此需要两个 RAM 芯片为一组来保证计算机可以按字节编址，此时一组的大小为 4K*8 ，需要 (64KB-4KB)*8/ (4K*8) =15 组，即 30 个 RAM 芯片。

综上所述，选 D。

16.某机器字长为 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一个字节为操作码字段，第二个字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址是 2000H，相对位移量字段的内容是 06H，则该转移指令成功转移后的目标地址是______。

A.2006H B.2007H C.2008H D.2009H

解答：C

相对寻址：操作数的有效地址是主存地址、程序计数器PC的内容与相对位移量三者之和。因为指令为两字节指令，且没取一个字节 PC 加1，因此主存地址为 2000H+02H+06H=2008H。

17.下列关于 RISC 的叙述中，错误的是_____。

A.RISC 普遍采用微程序控制器

B.RISC 大多数指令在一时钟周期内完成

C.RISC 内部的通用寄存器数量相对 CISC 较多

D.RISC 的指令集、寻址方式和指令格式种类相对 CISC 少

解答：A

RISC——精简指令集计算机。CISC——复杂指令集计算机。

RISC 大多采用硬布线控制器。CISC一般采用微程序控制器。

18.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别是 90ns，80ns，70ns，60ns，则该计算机的 CPU 时钟周期至少是______。

A.90ns B.80ns C.70ns D.60ns

解答：A。

指令流水线，并行执行指令的模式。CPU 时钟周期，CPU完成一个基本操作所需的时间，是计算机中最基本、最小的时间单位。若 CPU 时间周期为 B、C、D，则在执行 A对应功能段时一个时钟周期内无法完成该基本操作，与定义不符。

19.相对于微程序控制器，硬布线控制器的特点是______。

A.指令执行速度慢，指令功能的修改和扩展容易

B.指令执行速度慢，指令功能的修改和扩展难

C.指令执行速度快，指令功能的修改和扩展容易

D.指令执行速度快，指令功能的修改和扩展难

解答：D

微程序控制器的基本原理：微操作控制信号以微程序的形式存放在控制存储器中，执行指令时读出即可。因为微程序是存放在控制存储其中的，所以修改和扩展较为容易。

硬布线控制器：微操作控制信号由组合逻辑电路根据当前指令码、状态和时序，即使产生。因为组合逻辑电路在与物理上的线路密切相关，因此一旦控制部件构成后，除非重新设计和物理上对他重新布线，修改和扩展近乎不可能。

指令执行速度上，微程序控制器需要先读取，再执行，较慢。硬布线控制器，可以根据当前指令码、状态和时序直接执行，运行较快。

20.假设某系统总线在一个总线周期中并行传输 4B 信息，一个总线周期占用两个时钟周期，总线时钟频率为 10MHz，则总线带宽是_____。

A.10MB/s B.20MB/s C.40MB/s D.80MB/s

解答：B

总线带宽=单位总线周期传递数据量/总线传输周期=单位总线周期传递数据量/(2*时钟传输周期)= 单位总线周期传递数据量*时钟频率/2=10MHz*4B/2=10M s^-1 *4B/2=20MB/s。

21.假设某计算机存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失（未命中）50次，则 Cache 的命中率是_______。

A.5% B.9.5% C.50% D.95%

解答：D

Cache的命中率=Cache的命中次数/访存次数=（1000-50）/1000=95%。

22.下列选项中，能引起外部中断的事件是______。

A.键盘输入 B.除数为 0 C.浮点运算下溢 D.访存缺页

解答：A

中断：CPU 暂停正在执行的程序，转去执行相应的事件处理程序，待处理完成后再返回原程序中断处或调度其他程序执行的过程。

内中断：中断的信号来自 CPU 内部、与当前执行的指令有关。

外中断：终端的信号来自 CPU 外部、与当前执行的指令无关。

浮点运算上溢：数据大于定义类型所能表示的最大值或小于定义类型范围的最小值。

浮点运算下溢：数据在定义类型所能表示的最小正数和最大负数之间。

浮点运算上溢会造成内部中断；而浮点运算下溢将会按 0 处理，不会造成中断。

23.单处理系统中，可并行的是_______。

Ⅰ进程与进程 Ⅱ处理机与设备 Ⅲ处理机与通道 IV设备与设备

A.Ⅰ、Ⅱ 和 Ⅲ B.Ⅰ、Ⅱ 和 IV C.Ⅰ、Ⅲ 和 IV D.Ⅱ、Ⅲ 和 IV

解答：D

进程需要用到处理机，因此进程与进程不可并行。Ⅱ、Ⅲ 都只有一个需要用到处理机器，而 IV不需要用到处理机，因此 Ⅱ、Ⅲ 和 IV 可并行。

24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是_______。

A.时间片轮转调度算法 B.短进程优先调度算法

C.先来先服务调度算法 D.高响应比优先调度算法

解答：D

时间片轮转调度算法：每个进程依次执行 x 个单位时间。不考虑进程等待时间和执行时间，是抢占型调度。

短进程优先调度算法：优先执行需要执行时间短的进程。考虑进程等待时间。

先来先服务调度算法：按照先后顺序执行进程。考虑进程时间。

高响应比优先调度算法：优先级=（等待时间+执行时间）/ 执行时间 = 1+等待时间 /执行时间。综合考虑进程等待时间和执行时间。

25.某计算机系统中有 8 台打印机，由 K 个进程竞争，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是______。

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

解答：C

死锁是指两个或两个以上的进程在执行任务的过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象，若无外力作用，他们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在等待的进程称为死锁进程。

2 个进程，最多需要 6 台打印机，不可能产生死锁。

3 个进程，最多需要 9 台打印机，俩个进程分别占据 3 台打印机，完成后释放，剩余进程得到资源，不会产生死锁。

4 个进程，最多需要 12 台打印机，若每个进程占据两台打印机，系统将处于死锁状态。

26.分区分配内存管理方式的主要保护措施是_______。

A.界地址保护 B.程序代码保护 C.数据保护 D.栈保护

解答：A

分区分配内存管理方式：内存被分为不同的块和区，每个进程基于需求分配内存。因为每个进程都拥有独立的进程空间，因此需要进行界地址保护，防止访问越界。

27.一个分段式存储管理系统，地址长度为 32 位，其中段号占 8 位，则最大段长是______。

A.2^8B B.2^16B C.2^24B D.2^32B

解答：C

分段式存储管理系统：将进程空间根据逻辑整体分为一个个段，每个段都有短号和段内地址。此外每段的物理大小不同，

地址长度 32 位，段号占 8 位，因此最大段长即段内位移最大值为 2 的（32-8=24）次方比特。

28.下列文件物理结构中，适合随机访问且易于文件扩展的是______。

A.连续结构 B.索引结构 C.链式结构且磁盘块定长 D.链式结构且磁盘块变长

解答：B

随机访问：可以随机访问该数据结构中的任意一个节点。

连续结构：类似于数组的结构。

索引结构：系统为每个文件建立一张索引表，索引表中记录文件的各个逻辑块对应的物理块。。

链式结构：类似于链表的结构。分为显示与隐式两种，如无特殊指明，一般指隐式。

隐式：下一个磁盘块的位置保存在当前磁盘块末尾。

显示：将用于链接文件的各物理块的指针显示地存放在文件分配表中。

29.假设磁头当前位于第 105 道，正在向磁道序号增加方向移动。现有一个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用 SCAN 调度（电梯调度）算法得到的磁盘访问序列是________。

A.110，170，180，195，68，45，35，12

B.110，68，45，35，12，170，180，195

C.110，170，180，195，12，35，45，68

D.12，35，45，68，110，170，180，195

解答：A

SCAN 算法（电梯调度）算法：先往一个方向扫描至请求序列中的最大或最小磁道，然后从该磁道开始反向扫描，重复此操作直至所有请求序列中的磁道均已访问。因工作原理类似于电梯而得名。

30.文件系统中，文件访问控制信息存储的合理位置是_______。

A.文件控制块 B.文件分配表 C.用户口令表 D.系统注册表

解答：A

按名存取：用户只需向系统提供所访问文件的名字，便能快速准确地找到指定文件在外存上的存储位置。

为了实现按名存取，文件系统会为每个文件设置一个文件控制块（FCB）。他是一种用于存放控制文件需要的各种信息的数据结构。一般包括：基本信息（文件名，物理地址，逻辑地址），存取控制信息（文件权限相关），使用信息（文件建立、修改信息）。

文件分配表：描述文件系统中簇（硬盘逻辑存储的基本单元）的分配状态和文件内容之间的链接关系的表。简单地说，是描述文件所在位置的表。

用户口令表：用于存储用户的账号和密码。

系统注册表：用于存储系统和应用程序的设置信息。

31.设文件 F1 的当前引用计数值为 1 ，先建立 F1 的符号链接（软连接）文件 F2，再建立 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是______。

A. 0、1 B. 1、1 C. 1、2 D. 2、2

解答：B

软链接：软链接文件实际上是一个文本文件，其中包含有另一文件的位置信息。类似于快捷方式。

硬链接：通过索引节点来连接。

建立符号链接即软链接时，引用计数值直接复制；建立硬链接时，引用计数值加一。

删除符号链接时，直接删除，无影响；删除硬链接时，引用计数值减一，若值不为 0，不删除当前文件，只删除链接。

初始时，只有 F1，引用计数值为 1；建立 F2 后，F1 的引用计数值不变，F2 的引用计数值为 1；建立 F3 后，F1 和 F3 的引用计数值变为 2 ，F2 的引用计数值不变，为 1；删除 F1 后，F3 的引用计数值变为 1 ，F2 的引用计数值依然不变为 1。

对于软链接，创建后只有在再次打开时才可能变更。

32.程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是_______。

A. 逻辑设备号 B.物理设备名 C.主设备号 D.从设备号

解答：A

系统调用：软中断处理程序，用于让程序从用户态陷入内核态，以执行相应的操作。可以看作内核态的函数调用。

设备管理具有独立性的特点，操作系统以系统调用方式请求某类设备时，使用的是逻辑设备名。而在程序实际运行时，逻辑设备名会转化为对应的物理设备名。

进行实际输入输出操作的是物理设备。而操作系统中不直接使用设备的物理名称，而是用另一名称，这一名称成为逻辑设备名。

33.在 OSI 参考模型中，自下而上第一个提供端到端服务的层次是_______。

A.数据链路层 B.传输层 C.会话层 D.应用程

解答：B

OSI 参考模型从下到上依次为：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。

物理层：负责数据流的物理传输工作，利用传输介质为数据链路层提供物理连接。

数据链路层：在通信实体间建立数据链路连接，传输的基本单位为帧。为网络层提供差错控制和流量流量控制服务。负责的是相邻节点之间的通信，比如说交换机和路由器。

网络层：为数据在节点之间传输创建逻辑链路，通过路由选择算法为分组选择最佳路径，从而实现拥塞控制，网络互联等功能。网络层是路由器的最高层。

传输层：主要为用户提供端到端的服务处理数据报错误，数据包顺序等传输问题。向上层提供可靠、透明的数据传输服务，同时确保数据能完整的传输到网络层。

会话层：主要功能是维护两个节点之间的传输链接，确保点到点连接不中断以及管理数据交换等功能。会话层在应用程序中建立、管理和终止会话的同时决定使用何种通信方式，如全双工通信（双方能同时发送数据）和半双工通信（一方传输完数据后，另一方再回应）。

表示层：主要处理在两个通信系统中交换信息的表示方式，主要包括数据格式变化，加解密方式，数据的压缩与解压等。

应用层：为应用程序或用户提供各种请求服务。应用层中包含若干独立的用户通用服务协议模块，为网络用户用户之间的通信提供专用的程序服务。

34.在无噪声的情况下，若某通信链路的带宽为 3KHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是_____。

A.12kbps B.24kbps C.48kbps D.96kbps

解答：B

QAM 调制技术——正交振幅调制。

奈奎斯特定理：理想情况下（无噪声），信道容量（信道所能承载的最大数据传输速率）=2*信道的带宽* log2(信号的状态数)。

信道的带宽= 3Khz

因为采用 4 相位，每个相位具有 4 种振幅，所以信号的状态数是16。

信道容量=2*3Khz*log2(16)=2*3k*4bps=24kbps

香农定理：对于带宽为 W 赫兹，信噪比为 S(信号功率)/N（噪声功率）的信道，其信道容量即最大数据传输速率为：C=W*log2(1+S/N)(bps)

35.数据链路层采用后退 N 帧（GBN）协议，发送方已经发送了 0-7 的帧。当计时器超时时，若发送方只收到 0，2，3 号帧的确认，则发送方需要重发的帧数是_______。

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

解答：C

后退 N 帧（GBN）协议：从错处重发已发出的 N 个帧。发送方收到 3 ，表名 0，1，2，3 都已收到，因此 4 出错，重发 4，5，6，7，需要重发的帧数为 4。

36.以太网交换机进行转发决策使用的 PDU 地址是______。

A.目的物理地址 B.目的 IP 地址 C.源物理地址 D.源 IP 地址

解答：A

PDU 即协议数据单元：协议层的协议在对等层之间交换的信息。

以太网交换机工作在数据链路层，使用物理地址进行转发。

37.在一个采用 CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1 Gbps，电缆中信号传输速度为 200000km/s。若最小数据帧长度减小 800 bit，则最远的两个站点之间的距离至少需要______。

A. 增加 160m B.增加 80m C.减少 160m D.减少 80m

解答:D

CSMA/CD 协议：所有节点都共享网络信道，节点在发送数据之前，首先检测信道是否空闲，如果信道空闲则发送，否则就等待；发送信息后，再对冲突进行检测，当发现冲突时，取消发送。

CSMA/CD 协议在发送帧时可能因为在发送时产生冲突而中断，此时的已发送的都是无效帧，为了区别这些帧，规定了最小数据帧长。

最小数据帧长 (bit) =2*总线传播时延*数据传输速率（mbps）=2*数据传输速率 * 两站点间的最大距离（m）/ 信号在网络上的传输速度。

当最小帧长为 800bit 时，两站点间的最大距离=最小数据帧长*信号在网络上的传输速度/2/数据传输速率=800 (bit) * 2*10^8 (m/s) /2 / (1024*1024*1024) (bps)= 800 *2*10^8/2/10^9 m= 80 m。所以应该减少 80m。

38.主机甲和主机乙之间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的 TCP 段，分别包含 300B 和 500B 的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发给主机甲的确认序列号是______。

A.500 B.700 C.800 D.1000

解答：D

TCP 中对段的确认中返回的确认序列号是希望收到的下一个报文数据段的第一个字节的的序列号。因此是200+300+500=1000.。

39.一个 TCP 连接总是以 1KB 的最大段长发送 TCP 段，发送方有足够多的数据要发送。当发送窗口为 16KB 时发生了超时，如果接下来的四个 RTT（往返时间）时间内的 TCP 段的传输都是成功的，那么当第四个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口的大小是____。

A.7KB B.8KB C.9KB D.16KB

解答：C

TCP 拥塞控制，当出现超时时，拥塞窗口大小变为 1 ，慢开始门限 ssthress 变为当前拥塞窗口的一半。当拥塞窗口大小<ssthresh 时，每次变为原来的两倍，若计算结果大于 ssthresh ，则拥塞窗口的大小变为 ssthresh；若拥塞窗口大小>ssthresh时，每次将拥塞窗口大小加一。

发生超时时，拥塞窗口大小为 1 ，ssthress 为 8。第一次肯定应答后，拥塞窗口变为 2；第二次肯定应答后，拥塞窗口变为 4；第三次肯定应答后，拥塞窗口变为 8>=ssthress；第四次肯定应答后，拥塞窗口变为 9。

40.FTP 客户和服务之间传递 FTP 命令时，使用的连接是_____。

A.建立在 TCP 之上的控制连接 B.建立在 TCP 之上的数据连接

C.建立在 UDP 之上的控制连接 D.建立在 UDP之上的数据连接

解答：A

FTP 即文件传输协议，适用于在网络上进行文件传输的一套标准协议，工作在 OSI 的第七层，TCP 的第四层，使用的是 TCP 传输。

FTP 工作时使用两个并行的 TCP 连接，控制连接端口号21，数据连接端口号 20。

控制连接：服务器监听在 21 号端口，等待客户连接，建立在这个端口上的连接称为控制连接。控制连接用来除数控制信息（如连接请求，传送请求）。

数据连接：用来连接客户端与服务器以进行数据传输，实际完成文件的传输，在传送完毕后即结束连接。

因此使用的是建立在 TCP 上的控制连接。

二、综合应用题

41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点的最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

（1）设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点

（2）选择离 u 最近且尚未在最短路径中的一个顶点 v ，加入最短路径中，修改当前顶点 u=v

（3）重复（2），知道 u 是目标顶点为止

请问该方法能否求得最短路径？若该方法可行，试证明之；否则，请举例说明。

解答：不能。局部的最优并不一定导致整体的最优，以下图中顶点 A 到顶点 C 的最短路径为例，按题目中的方法得到的最短路径是 A-B-C ，但实际最短路径是 A-C，局部最优不等于整体最优。

42.（15分）已知一个带有表头节点的单链表，节点结构为 data| link。假设该链表只给出了头指针 list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的节点（k 为正整数）。若查找成功，算法输出该节点的 data 域，并返回 1；否则，只返回 0。要求：

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（C、C++ 或 Java 语言实现），关键之处请给出简要注释。

解答：

基本设计思想：基于双指针解题，开始时，使 left 指针指向第一个节点，right 指针指向第 k 个节点，然后将两指针同时后移 x 个节点直至 right 指针指向节点的下一个节点为空。

详细实现步骤：

（1）left 指针指向表头节点的下一个节点，若 left 为空，直接返回 0。

（2）使 right 指针指向 left 指针指向的节点，往后移动 k-1 个节点，若此过程中某个节点为空，则直接返回 0 。

（3）当 right 指针指向节点的下一个节点非空时，将 left 指针和 right 指针同时后移一个节点。重复此操作直至 right 节点的下一个节点为空。

（4）输出此时 left 指针指向节点的 data 域并返回 1 。

程序设计语言 Java ：

public class ListNode{
    int data;            //数据域
    ListNode next;        //下一个节点
    
};
class Solution{
	public int  getKth(ListNode head,int k) {
		ListNode left=head.next;        
		if(head==null) {    //空链表，倒数第 k （正整数） 个节点一定不存在
			return 0;
		}
		ListNode right=left;
		for(int i=0;i<k-1;i++) {
			right=right.next;
			if(right==null) {        //链表长度小于 k ，倒数 k 个节点一定不存在
				return 0;
			}
		}
		while(right.next!=null) {        //left ，right 同时后移直至 right.next 为空
			left=left.next;
			right=right.next;
		}
		System.out.println(left.data);    //输出 data 
		return 1;
	}
}

43.（8 分）某计算机的 CPU 主频为 500MHz，CPI 为 5 （即执行每条指令平均需 5 个时钟周期）。假定某外设的数据传输率为 0.5MB/s , 采用中断方式与主机进行数据传送，以 32 位为传送单位，对应的中断服务程序包含 18 条指令，中断服务的其他开销相当于 2 条指令的执行时间。请回答以下问题，要求给出计算过程。

（1）在中断方式下，CPU 用于该外设 I/O 的时间占整个 CPU 时间的百分比是多少？

（2）当该外设数据传输率达到 5MB/s 时，改用 DMA 方式传送数据。假定每次 DMA 传送块大小为 5000B ，且 DMA 预处理和后处理的总开销为 500 个时钟周期，则 CPU 用于该外设 I/O 的时间占整个 CPU 时间的百分比是多少（假设 DMA 与 CPU 之间没有访存冲突）？

知识点：CPU 主频：1 秒中的时钟脉冲周期数，即时钟周期的倒数。

CPU 时钟周期：一个时钟脉冲所需要的时间，也叫节拍脉冲或 T 周期，是 CPU 中的最小时钟单位。

中断传送方式：当外设需要与 CPU 进行信息交换时，由外设向 CPU 发出请求信号，使 CPU 暂停正在执行的程序，转去执行数据的输入/输出操作，数据传送结束后，CPU 再去执行被暂停的程序。

DMA 传送方式：当需要传送数据时，DMA 控制器首先要求 CPU 放弃对总线的控制；然后开始进行数据传送。再数据全部传输完成后，DMA 控制器通知 CPU 可以使用内存并放弃对总线的控制权。

当是速率的基本单位时，1 Mb/s=1000 kb/s；当是存储的单位时，1Mb=1024 kb

解答：（1）外设以 32 位为传送单位，因此每次中断传送 4B 数据，为达到 0.5 MB/s 的数据传输率，每秒需要中断 0.5*1000*1000B/4B=500000/4=125000 次，一次中断服务的所有开销为 20 条指令的时间即 20*5=100 个时钟周期，因此 1 秒内用于该外设的时钟周期数为 100*125000= 12500000=12500K=12.5M

计算机的主频是 500 MHz，即 1 秒内的时钟周期数是 500M

因此 CPU 用于该外设 I/O 的时间占整个 CPU 时间的 12.5M/500M=2.5%

（2）外设每次输送 5000B 大小的数据，因此为达到 5MB/s 即 5000000 B/s 的传输速率，每秒需要传输 5000000/5000=1000 次，每次的时间开销为 500 个时钟周期，因此 1 秒内的总开销为 500*1000=500000=500K=0.5M 个时钟周期。

计算机 1 秒内的时钟周期数是 500M。

因此 CPU 用于该外设 I/O 的时间占整个 CPU 时间的 0.5/500=0.1%

44.（13分）某计算机字长 16 位，采用 16 位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为 1 时表示有效，为 0 时表示无效。例如，控制信号 MDRine 为 1 时表示允许数据从 DB 打入 MDR，MDRin 为 1 时表示允许数据从内总线打入 MDR 。假设 MAR 的输出一直处于使能状态。加法指令 “ADD （R1），R0” 的功能是 (R0)+ ((R1)) ->(R1)，即将 R0 中的数据与 R1 的内容所值内存单元的数据相加，并将结果送入 R1 的内容所指数据单元中保存。

下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

知识点：MDR 主存数据寄存器：MDR 用来保存要被写入地址单元或从地址单元读入的数据。

MAR 主存地址寄存器：用来保存数据被传输到的位置的地址或者数据来源位置的地址。

定长指令字结构：指令系统中所有指令长度都相同。

解答：

时钟	功能	有效控制信号
C5	MAR<-(R1)	R1out,MARin
C6	MDR<-M(MAR)	MemR,MDRinE
C7	A<-(MDR)	MDRout,Ain
C8	AC<-(A)+(R0)	ADD,R0out,ACin
C9	MDR<-(AC)	ACout,MDRin
C10	M(MAR)<-(MDR)	MDRoutE,MemW

45.（7分）三个进程 P1、P2、P3 互斥使用一个包含 N（N>0）个单元的缓冲区。P1 每次使用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中；P2 每次用 getodd() 从该缓冲区取出一个奇数并用 countodd() 统计奇数个数；P3 每次用 geteven() 从该缓冲区取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。

解答：

因P1，P2，P3 对缓冲区的占用互斥，故设置互斥变量 mutex；因P1，P2，P3 共享缓冲区内资源，故设置共享变量empty，依题意，初始值为 N；因P1 与 P2 对偶数的放置与取用同步，故设置共享变量odd；因P1 与 P3 对奇数的放置与取用同步，故设置共享变量even：

semaphore mutex=1;
semaphore odd=0,even=0;
semaphore empty=N;
main(){
    P1(){
        while(true){
            int num=produce();
            P(empty);    //判断缓冲区内是否有剩余空间
            P(mutex);    //判断缓冲区是否被占用
            put();
            V(mutex);      //释放缓冲区
            if(num%2!=0){
                V(odd);    //奇数向P2发送消息   
            }else{
                V(even);    //偶数向P3发送消息
            }
        }
    }
    P2(){
        while(true){
            P(odd);    //判断是否有奇数产生
            P(mutex);    //判断缓冲区是否被占用
            getodd();
            V(mutex);    //释放缓冲区
            V(empty);    //向P1发送消息，缓冲区存在空的单元
            countodd();
        }
    }
    P3(){
        while(true){
            P(even);     //判断是否有偶数产生
            P(mutex);    //判断缓冲区是否被占用
            geteven();
            V(mutex);    //释放缓冲区
            V(empty);    //向P1发送消息，缓冲区存在空的单元
            counteven();
        }
    }
}

46.（8分）请求分页管理系统中，假设某进程的页表内容见下表。

页号	页框（Page Frame）号	有效位（存在位）
0	101H	1
1		0
2	254H	1

页面大小为 4KB ，一次内存的访问时间为 100ns，一次快表（TLB）的访问时间为 10ns，处理一次缺页的平均时间为 10^8ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设：（1）TLB 初始为空（2）地址转换时先访问 TLB ，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）（3）有效位为 0 表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到缺页中断的指令处重新执行。设有虚地址访问序列 2362H，1565H，25A5H，请问：

（1）依次访问以上上述三个虚地址，各需多少时间？给出计算过程。

（2）基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。

知识点：分页存储管理系统允许程序存放到若干不相邻的空闲块中，从而提高主存空间的利用率。

快表（转换后援缓冲）：相联存储器，用来存放进程最近访问的部分页表项。

驻留集：请求分页管理系统中给进程分配的内存块的集合。给一个进程分配的物理页框的集合就是这个京城的驻留集。

解答：（1）页面大小为 4KB即 2^12B，因此地址中，低12位为页内地址，其余为页号。

地址 2362H，页号为 2H，页内地址为 362H。首先访问 TLB ，消耗 10ns，因初始为空，未命中；接着访问页表（在内存中），消耗 100ns，命中；最后合成物理地址，访问主存（内存分为主存和高速缓存 Cache），消耗 100ns。综上所述，访问 2363H 需要 10ns+100ns+100ns=210ns

地址1565H，页号为 1H，页内地址为 565H。首先访问 TLB，消耗 10ns，未命中；接着访问页表，消耗 100ns，未命中；然后进行缺页冲断处理，消耗 10^8ns；再访问TLB，消耗10s，命中；最后合成物理地址并访问，消耗 100ns。综上所述，访问 1565H 需要 10ns+100ns+10^8ns+10ns+100ns=100000220ns

地址 25A5H，页号为 2H，业内地址为 565H。首先访问 TLN，消耗 10ns，因为第一个地址页号为 2，已经被放入 TLB ，因此直接命中；然后合成物理地址并访问，消耗 100ns。综上所述，访问 25A5H 需要 110ns

（2）当访问 1565H 时，产生缺页中断，因采用最近最少使用置换算法（LRU）和局部淘汰策略且驻留集大小为 2 ，所以页号为 0 的页面被置换。此时物理地址为 101565H。

47.（9分）某网络拓扑如下图所示，路由器 R1 通过接口 E1、E2 分别连接局域网 1、局域网 2，通过接口 L0 连接路由器 R2，并通过路由器 R2 连接域名服务器与互联网。R1 的 L0 接口 IP 地址是 202.118.2.1，R2 的 L0 接口的 IP 地址是 202.118.2.2，L1 接口的 IP 地址是 130.11.120.1，E0 接口的 IP 地址是 202.118.3.1，域名服务器的 IP 地址是 202.118.3.2。

R1 和 R2 的路由表结构为：

目的网络 IP 地址

子网掩码

下一跳 IP 地址

接口

（1）将 IP 地址空间 202.118.1.0/24 划分两个子网，分别分配给局域网 1，局域网 2，每个局域网需分配的 IP 地址数不少于 120 个。请给出子网划分结果，说明理由或给出必要的计算过程。

（2）请给出 R1 的路由表，使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。

（3）请采用路由聚合技术，给出 R2 到局域网 1 和局域网 2 的路由

知识点：域名服务器的子网掩码默认是 255.255.255.255

当直接发送时，无下一跳 IP 地址

路由聚合技术：将不同子网聚合，具体操作为将从开始不相同的比特位到末尾填充 0，该部分子网掩码变为主机号。

解答：（1）因为每个子网的 IP 地址数不少于 120 个，所主机号至少有 7 (2^7=128) 位，而子网掩码为 11111111 11111111 11111111 0000000，所以划分结果为子网1 202.118.1.0/25 和子网 2 202.118.1.128/25，将子网 1 分配给局域网 1 ，子网 2 分配给局域网 2 即可。

（2）

目的网络 IP 地址	子网掩码	下一跳 IP 地址	接口
202.118.1.0	255.255.255.128		E1
202.118.1.128	255.255.255.128		E2
202.118.3.2	255.255.255.255	202.118.2.2	L0
0.0.0.0	0.0.0.0	202.118.2.2	L0