2009 年 408 真题
本节正在编写中，敬请期待。
选择题
数据结构
1
为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主 机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数 据则要排队到最后才能打印，显然不符题意，故选 B。
2
设栈 S 和队列 Q 的初始状态均为空，元素 a, b, c, d, e, f, g 依次进入栈 S 。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b, d, c, f, e, a, g，则栈 S 的容量至少是（ ）。
由千队列的特点是先进先出，即栈 S 的出栈顺序就是队 Q 的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。
| 序号 | 说明 | 栈内 | 栈外 | 序号 | 说明 | 栈内 | 栈外 |
|---|---|---|---|---|---|---|---|
| 1 | a入栈 | A | 8 | e入栈 | ae | bdc | |
| 2 | b入栈 | Ab | 9 | f入栈 | aef | bdc | |
| 3 | b出栈 | A | b | 10 | f出栈 | ae | bdcf |
| 4 | c入栈 | Ac | b | 11 | e出栈 | a | bdcfe |
| 5 | d入栈 | Acd | b | 12 | a出栈 | bdcfea | |
| 6 | d出栈 | Ac | bd | 13 | g入栈 | g | bdcfea |
| 7 | c出栈 | A | bdc | 14 | g出栈 | bdcfeag |
栈内的最大深度为 3，故栈 S 的容量至少是 3。
【另解】元素的出栈顺序是 b,d,c,f,e,a,g, 可推出进栈出栈顺序为 Push(S,a),Push(S,b), Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e), Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为 0，每做一次 Push 进行一次“+1”操作， 每做一次 Pop 进行一次“-1”操作，记录容量的最大值为 3，所以选 C。
3
给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是（）。
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即 遍历的方式是 RNL。本题考查的遍历方法并不是二叉树的 3 种基本遍历方法，对于考生而言， 重要的是要掌握遍历的思想。
4
下列二叉排序树中，满足平衡二叉树定义的是（ ）。
B 根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 1 。而其余 3 个 选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。
5
已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是（）。
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个 满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7， 显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8×2=16 个叶结点，故完全二叉树的结点个数最多为 $(2^{7} - 1) - 16 = 111$ 个结点。
6
将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中， u 和 v 可能具有的关系是（ ）。
I. 父子关系
II. 兄弟关系
III. u 的父结点与 v 的父结点是兄弟关系
森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应 森林关系中可能是兄弟关系或原本就是父子关系。
情形 I：若结点 V 是结点 u 的第二个孩子结点，在转换时，结点 V 就变成结点 u 第一个孩 子的右孩子，符合要求。
情形 II：结点 u 和 V 是兄弟结点的关系，但二者之中还有一个兄弟结点 k, 则转换后，结 点 V 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。
情形 III: 若结点 u 的父结点与 v 的父结点是兄弟关系，则转换后，结点 u 和 v 分别在两者 最左父结点的两棵子树中，不可能出现在同 一条路径中。
【逆向法】由题意可知 u 是 v 的父结点的父结点，如下图所示有 4 种情况：
根据树与二叉树的转换规则，将这 4 种情况转换成树种结点的关系。(1) 在原来的树中 u 是 v 的父结点的父结点； (2) 在树中 u 是 v 的父结点； (3) 在树中 u 是 v 的父结点的兄弟； (4) 在树中 u 与 v 是兄弟关系。由此可知 I 和 II 正确。
7
下列关于无向连通图特性的叙述中，正确的是
Ⅰ. 所有顶点的度之和为偶数
Ⅱ. 边数大于顶点个数
Ⅲ. 至少有一个顶点的度为 1
每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度）， 故所有顶点的度之和为边数的两倍，I 正确。n 个顶点、-1 条边可以构成无向连通图，比如树， Ⅱ错误。顶点数为 N(N≥1) 的无向完全图中不存在度为 1 的顶点，Ⅲ错误。
8
下列叙述中，不符合 m 阶 B 树定义要求的是（）。
选项 A、B 和 C 都是 B-树的特点，而选项 D 则是 B+树的特点。注意区别 B-树和 B+树各 自的特点。
9
已知关键字序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是（）。
根据关键字序列得到的小顶堆的二叉树形式如下图所示。
插入关键字 3 时，先将其放在小顶堆的末端，如图 (2) 所示。 再将该关键字向上进行调整， 得到的结果如图 (3) 所示。 所以，调整后的小顶堆序列为 3, 5, 12, 8, 28, 20, 15, 22, 19。
10
若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。
解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确 定一个元素的最终位置，而题目中，前 2 个元素和后 2 个元素均不是最小或最大的 2 个元素并 按序排列。 选项 D 中的 2 路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时 的序列中并没有两两元素有序排列。 插入排序在每趟排序后能确定前面的若干元素是有序的， 而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。
组成原理
11
冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）
虽然指令和数据都是以二进制形式存放在存储器中，但 CPU 可以根据指令周期的不同阶段 来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。 本题容易 误选 A, 需要清楚的是，CPU 只有在确定取出的是指令之后，才会将其操作码送去译码，因此， 不可能依据译码的结果来区分指令和数据。
12
一个 C 语言程序在一台 32 位机器上运行。程序中定义了三个变量 x，y 和 z，其中 x 和 z 是 int 型，y 为 short 型。当 x=127，y=-9 时，执行赋值语句 z=x+y 后，x、y 和 z 的值分别是：
C 语言中的整型数据为补码形式，int 为 32 位，short 为 16 位，故 x、y 转换成十六进制为 0000007FH、FFF7H。执行 z=x+y 时，由于 x 是 int 型，y 为 shot 型，需将短字长数据转换成 长字长数据，称之为“符号扩展”。由于 y 的符号位为 1，故在 y 的前面添加 16 个 1，即可将 y 上升为 it 型，其十六进制形式为 FFFFFFF7H。最后执行加法，即 O0OO007FH+FFFFFFF7H= 00000076H, 其中最高位的进位 1 自然丢弃。故选 D。
【排除法】对于 x 的值，4 个选项都一样，无须计算；z=x+y=127-9=118>0, 前 4 个 字节必然全 O, 排除 BC; 只需算出 y=-9 的值即可，其十六进制形式为 FFF7H, 排除 A。
【提示】解题时，应先排除明显错误的选项，然后再推敲剩下的选项。
13
浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位（均含 2 位符号位）。若有两个数 X=2^7×29/32，Y=2^5×5/8，则用浮点加法计算 X+Y 的最终结果是。
X 的浮点数格式为 00,111;00,11101（分号前为阶码，分号后为尾数），Y 的浮点数格式为 00,101;00,10100。然后根据浮点数的加法步骤进行运算。
第一步：对阶。X、Y 阶码相减，即 00,111-00,101=00,111+11,0111=00,010，可知 X 的阶码比 Y 的价码大 2（这一步可直接目测）。根据小阶向大阶看齐的原则，将 Y 的阶码加 2， 尾数右移 2 位，将 Y 变为 00,111；00,00101。
第二步：尾数相加。即 00,11101+00,00101=01,00010，尾数相加结果符号位为 01，故需右规。
第三步：规格化。将尾数右移 1 位，阶码加 1，得 X+Y 为 01,000；00,10001。
第四步：判溢出。阶码符号位为 01，说明发生溢出。
本题容易误选选项 B、C, 这是因为选项 B、C 本身并没有计算错误，只是它们不是最终结果，选项 B 少了第 3 步和第 4 步，选项 C 少了第 4 步。
【偷懒法】本题也可以直接用数学知识对原数进行计算，然后将计算的结果转换成浮点数 的格式。X+Y=29/32×2+5/8×25=29/32×27+5/32×27=(29/32+5/32)×27=34/32×27=17/32×28, 阶码用补码表示，数值位 3 位，最大只能表示 7，即 X+Y 的结果的阶码 8 超出了该浮点数的 表示范围，故溢出。
14
某计算机的 Cache 共有 16 块，采用 2 路组相联映射方式（即每组 2 块）。每个主存块大小为 32 字节，按字节编址。主存 129 号单元所在主存块应装入到的 Cache 组号是。
由于 Cache 共有 16 块，采用 2 路组相联，因此共分为 8 组，组号为 0,1,2，…，7。主存的 某一字块按模 8 映射到 Cache 某组的任一字块中，即主存的第 0,8，l6,…字块可以映射到 Cache 第 0 组的任一字块中。每个主存块大小为 32 字节，故 129 号单元位于第 4 块主存块（注意是从 0 开始），因此将映射到 Cache 第 4 组的任一字块中。
15
某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为 RAM 区，按字节编址。现要用 2K×8 位的 ROM 芯片和 4K×4 位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是 ( )。
首先确定 ROM 的个数，ROM 区为 4KB, 选用 2K×8 位的 ROM 芯片，需要 4Kx8 / 2K×8 =2 片， 采用字扩展方式：RAM 区为 60KB, 选用 4Kx4 位的 RAM 芯片，需要 60K×8 /4K×4 = 30 片， 采用字和位同时扩展方式。
16
某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为 06H，则该转移指令成功转移后的目标地址是
相对寻址 EA=(PC)+A, 首先要求的是取指令后 PC 的值。转移指令由两个字节组成，每取 一个字节 PC 值自动加 1，因此取指令后 PC 值为 2000H+2H=2002H, 故 EA=(PC)+A=2002H+ 06H=2008H。
【易错点】本题易误选 A 或 B。选项 A 没有考虑 PC 值的自动更新，选项 B 虽然考虑了 PC 值要自动更新，但没有注意到该转移指令是一条两字节指令，P℃值仅仅“+1”而不是“+2”。
17
下列关于 RISC 的叙述中，错误的是 ( )。
相对于 CISC,RISC 的特点是指令条数少；指令长度固定，指令格式和寻址种类少：只有 取数/存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU 中通用寄存器多；大部 分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。 选项 B、C、D 都是 RISC 的特点，选项 A 是错误的，因为 RISC 的速度快，所以普遍采用硬布 线控制器，而非微程序控制器。
18
某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为 90 ns、80 ns、70 ns、和 60 ns，则该计算机的 CPU 时钟周期至少是 ( )。
流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确 完成。
19
相对于微程序控制器，硬布线控制器的特点是 ( )。
微程序控制器采用了 “存储程序 ” 的原理， 每条机器指令对应 一个微程序，因此修改 和扩充容易，灵活性好，但每条指令的执行都要访问控制存储器，所以速度慢。硬布线控制 器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩 展困难，灵活性差。
20
假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10M Hz，则总线带宽是______。
总线带宽是指单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡 量，单位 Bs。由题意可知，在 1 个总线周期（=2 个时钟周期）内传输了 4 字节信息，时钟周 期=1/10MHz=0.1μs, 故总线带宽为 4B/(2×0.1μs)=4B/(0.2×10s)=20MB/s。
21
假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失（未命中）50 次，则 Cache 的命中率是 ( )。
命中率=Cache 命中次数 I 总访问次数。 需要注意的是看清题，题中说明的是缺失 50 次， 而不是命中 50 次，仔细审题是做对题的第 一 步。
22
下列选项中，能引起外部中断的事件是 ( )。
外部中断指的是 CPU 执行指令以外的事件产生的中断，通常是指来自 CPU 与内存以外的 中断。A 中键盘输入属于外部事件，每次键盘输入 CPU 都需要执行中断以读入输入数据，所以 能引起外部中断。 B 中除数为 0 属于异常，也就是内中断，发生在 CPU 内部。C 中浮点运算下 溢将按机器零处理，不会产生中断。 而 D 访存缺页属于 CPU 执行指令时产生的中断，也不属 于外部中断。 所以能产生外部中断的只能是输入设备键盘。
操作系统
23
单处理机系统中，可并行的是（ ）。
Ⅰ. 进程与进程 Ⅱ. 处理机与设备 Ⅲ. 处理机与通道 Ⅳ. 设备与设备
在单处理机系统（不包含多核的情况）中，同一 时刻只能有一个进程占用处理机，因此进 程之间不能并行执行。 通道是独立于 CPU 的控制输入／输出的设备，两者可以并行，显然，设 备与设备之间也是可以并行的。
24
下列进程调度算法中，综合考虑进程等待时间和执行时间的是______。
在高响应比优先调度算法中，选出响应比最高的进程投入执行，响应比 R 定义如下：响应 比 R=（等待时间＋执行时间）／执行时间。它综合考虑 了每个进程的等待时间和执行时间，对于 同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量；而长进程的响应比可以 随等待时间的增加而提高，不会产生进程无法调度的情况。
25
某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是（）。
这种题用到组合数学中鸽巢原理的思想。 考虑最极端情况，因为每个进程最多需要 3 台打 印机，如果每个进程已经占有了 2 台打印机，那么只要还有多的打印机，总能满足一个进程达 到 3 台的条件，然后顺利执行，所以将 8 台打印机分给 K 个进程，每个进程有 2 台打印机，这 个情况就是极端情况，K 为 4。
26
分区分配内存管理方式的主要保护措施是______。
每个进程都拥有自己独立的进程空间，若一个进程在运行时 所产生的地址在其地址空间之 外， 则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检 查是否允许，如果允许则执行，否则产生地址越界中断。
27
一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是______。
分段存储管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。地 址长度为 32 位，段号占 8 位，则位移量占 32-8=24 位，故最大段长为 $2^{24}$ B。
28
下列文件物理结构中，适合随机访问且易于文件扩展的是（）。
文件的物理结构包括连续、 链式、 索引三种，其中链式结构不能 实现随机访问，连续结构 的文件不易于扩展。 因此随机访问且易于扩展是索引结构的特性。
29
假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用 SCAN 调度（电梯调度）算法得到的磁道访问序列是 ______。
SCAN 算法类似电梯的工作原理。 首先，当磁头从 105 道向序号增加的方向移动时，便会 按照从小到大的顺序服务 所有大于 105 的磁道号 (110,170,180,195); 往回移动时又会按照从 大到小的顺序进行服务 (68, 45,35, 12)。
30
文件系统中，文件访问控制信息存储的合理位置是______。
为了实现 “ 按名存取 ”，在文件系统中为每个文件设置用于描述和控制文件的数据结构， 称之为文件控制块 (FCB )。在文件控制块中，通常包含以下三类信息，即基本信息、存取控制 信息及使用信息。
31
设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接（软链接）文件 F2，再建立 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是______。
建立符号链 接时， 引用计数值直接复制；建立硬链接时， 引用计数值加 1。删除文件时，删除 操作 对于符号链接是不可见的， 这并不影响文件系统， 当以后再通过符号链接访问时， 发现文 件 不存在， 直接删除符号链接；但对于硬链接则不可以直接删除， 引用计数值减 1, 若值 不为 O, 则不能删除此文件， 因为还有其他硬链接指向此文件。
当建立 F2 时，Fl 和 F2 的引用计数值都为 1。 当再建立 F3 时，Fl 和 F3 的引用计数值就 都变成了 2。 当后来删除 Fl 时，F3 的引用计数值为 2-1 = 1, F2 的引用计数值 一直不变。
32
程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是（ ）
设备管理具有设备独立性的特点， 操作系统以系统调用方式来请求某类设备时， 使用的是 逻辑设备名。 而在程序实际执行时， 将逻辑设备名 转换为对应的物理 设备名。
计算机网络
33
在 OSI 参考模型中，自下而上第一个提供端到端服务的层次是（）
传输层提供应用进程间的逻辑通信（通过端口号）， 即端到端的通信。 而数据链路层负责 相邻结点之间的通信， 这个结点包括了交换机和路由器等数据通信 设备， 这些设备 不能称为端 系统。网络层负责主机到主机的逻辑通信。 因此选 B。
34
在无噪声情况下，若某低通通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是（ ）。
采用 4 个相位，每个相位有 4 种幅度的 QAM 调制方法，每个信号可以有 16 种变化，传输 4bit 的数据。根据奈奎斯特定理，信息的最大传输速率为 2×3k×4=24kbps。
35
数据链路层采用后退 N 帧（GBN）协议，发送方已经发送了编号为 0~7 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是（ ）
在后退 N 帧协议中，当接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续 帧，发送方超时后需重传该数据帧及其后续的所有帧。这里应注意，连续 ARQ 协议中，接收 方一般采用累积确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到 3 的确认帧就表示编号为 0,1,2,3 的帧已接收，而此时发送方未收到 1 号帧的确认只能代表确 认帧在返回的过程中丢失了，而不代表 1 号帧未到达接收方。因此需要重传的帧为编号是 4,5,6， 7 的帧。
36
以太网交换机进行转发决策时使用的 PDU 地址是______。
交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层 使用物理地址进行转发， 而转发到目的地通常是使用 目的地址。 因此 POU 地址是目的物理地址。
37
在一个采用 CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1Gbps，电缆中的信号传播速度是 200 000km/s 。若最小数据帧长度减少 800 比特，则最远的两个站点之间的距离至少需要______。
若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现碰撞窗口 的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为 S, 则 可以得到如下公式（注意单位的转换）：
减少的往返时延=减少的发送时延，即 $2 \times [s/(2 \times 10^{8})]= 800/(1×10^{9})$。即，由于帧长减少而 缩短的发送时延，应等于由于距离减少而缩短的传播时延的 2 倍。
可得 s=80, 即最远的两个站点之间的距离最少需要减少 80m。
【注意】CSMA/CD 的碰撞窗口 = 2 倍传播时延，报文发送时间 » 碰撞窗口。
38
主机甲与主机乙之间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的 TCP 段，分别包含 300 字节和 500 字节的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是______。
返回的确认序列号是接收 端期待收到对方下一个报文段数据部分的第一个字节的序号， 因 此乙在正确接收到两个段后， 返回给甲的确认序列号是 200+ 300 + 500 = 1000。
39
一个 TCP 连接总是以 1KB 的最大段长发送 TCP 段，发送方有足够多的数据要发送。当拥塞窗口为 16KB 时发生了超时，如果接下来的 4 个 RTT（往返时间）时间内的 TCP 段的传输都是成功的，那么当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口大小是______。
在发生超时后，慢开始门限 ssthresh 变为 16KB/2= 8KB, 拥塞窗口变为 1KB。在接下来的 3 个 RTT 内，执行慢开始算法，拥塞窗口大小依次为 2KB、4KB、8KB, 由于慢开始门限 ssthresh 为 8KB , 因此之后转而执行拥塞避免算法， 即拥塞窗口开始 “ 加法增大 ”。因此第 4 个 RTT 结 束后 ， 拥塞窗口的大小为 9KB。
40
FTP 客户和服务器间传递 FTP 命令时，使用的连接是______。
对于 FTP 文件传输， 为了保证可靠性， 选择 TCP 协议，排除 C、D。FTP 的控制信息是带 外传送的， 也即 FTP 使用了一个分离的控制连接来传送命令， 故选 A。
解答题
数据结构
41
带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
① 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；
② 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；
③ 重复步骤②，直到 u 是目标顶点时为止。
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。
42
已知一个带有表头结点的单链表，结点结构为：
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（ k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：
(1) 描述算法的基本设计思想；
(2) 描述算法的详细实现步骤；
(3) 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++或 Java 语言实现），关键之处请给出简要注释。
组成原理
43
某计算机的 CPU 主频为 500MHz，CPI 为 5（即执行每条指令平均需 5 个时钟周期）。假定某外设的数据传输率为 0.5M B/s，采用中断方式与主机进行数据传送，以 32 位为传输单位，对应的中断服务程序包含 18 条指令，中断服务的其他开销相当于 2 条指令的执行时间。请回答下列问题，要求给出计算过程。
(1) 在中断方式下，CPU 用于该外设 I/ O 的时间占整个 CPU 时间的百分比是多少？
(2) 当该外设的数据传输率达到 5M B/s 时，改用 DMA 方式传送数据。假定每次 DMA 传送块大小为 5000B，且 DMA 预处理和后处理的总开销为 500 个时钟周期，则 CPU 用于该外设 I/ O 的时间占整个 CPU 时间的百分比是多少？（假设 DMA 与 CPU 之间没有访存冲突）
44
某计算机字长 16 位，采用 16 位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为 1 时表示有效、为 0 时表示无效。例如控制信号 MDRinE 为 1 表示允许数据从 DB 打入 MDR，MDRin 为 1 表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于使能状态。加法指令“ADD (R1)，R0”的功能为 (R0)+((R1)) → (R1)，即将 R0 中的数据与 R1 的内容所指主存单元的数据相加，并将结果送入 R1 的内容所指主存单元中保存。
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
| 时钟 | 功能 | 有效控制信号 |
|---|---|---|
| C1 | MAR ← (PC) | PCout, MARin |
| C2 | MDR ← M(MDR) PC ← (PC) + 1 | MemR, MDRinE, PC+1 |
| C3 | IR ← (MDR) | MDRout, IRin |
| C4 | 指令译码 | 无 |
操作系统
45
三个进程 P1、P2、P3 互斥使用一个包含 N(N>0) 个单元的缓冲区。P1 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中；P2 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数；P3 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
46
请求分页管理系统中，假设某进程的页表内容如下表所示：
页面大小为 4KB，一次内存的访问时间是 100ns，一次快表 (TLB) 的访问时间是 10ns，处理一次缺页的平均时间 10^8 ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2，采用最近最少使用置换算法 (LRU) 和局部淘汰策略。假设
① TLB 初始为空；
② 地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；
③ 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。
设有虚地址访问序列 2362H、1565H、25A5H，请问：
(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。
(2) 基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。
计算机网络
47
某网络拓扑如下图所示，路由器 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 的路由表结构为：
(1) 将 IP 地址空间 202.118.1.0/24 划分为 2 个子网，分别分配给局域网 1、局域网 2，每个局域网需分配的 IP 地址数不少于 120 个。请给出子网划分结果，说明理由或给出必要的计算过程。
(2) 请给出 R1 的路由表，使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。
(3) 请采用路由聚合技术，给出 R2 到局域网 1 和局域网 2 的路由。