考研真题

（8 分）某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引 导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各 分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程 序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分 区引导程序外，还需要执行 ROM 中的引导程序。请回答下列问题。 

（1）系统启动过程中操作系统的初始化程序、分区引导程序、ROM 中的引导程序、磁盘引 导程序的执行顺序是什么？ 

（2）把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、 对磁盘进行分区，执行这 4 个操作的正确顺序是什么？ 

（3）磁盘扇区的划分和文件系统根目录的建立分别是在第（2）问的哪个操作中完成的？

【答案解析】 

（1）执行顺序依次是 ROM 中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始 化程序。 

（2）4 个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系 统的安装。 

（3）磁盘扇区的划分是在磁盘的物理格式化操作中完成的。文件系统根目录的建立是在逻辑 格式化操作中完成的。

（9 分）某网络拓扑如题 47 图所示，以太网交换机 S 通过路由器 R 与 Internet 互联。路由 器部分接口、本地域名服务器、H1、H2 的 IP 地址和 MAC 地址如图中所示。在 t0 时刻 H1 的 ARP 表和 S 的交换表均为空，H1 在此刻利用浏览器通过域名 www.abc.com 请求访问 Web 服 务器，在 t1 时刻（t1＞t0）S 第一次收到了封装 HTTP 请求报文的以太网帧，假设从 t0 到 t1 期 间网络未发生任何与此次 Web 访问无关的网络通信。

请回答下列问题。 

（1）从 t0到 t1 期间，H1 除了 HTTP 之外还运行了哪个应用层协议？从应用层到数据链路层， 该应用层协议报文是通过哪些协议进行逐层封装的？ 

（2）若 S 的交换表结构为：< MAC 地址，端口>，则 t1时刻 S 交换表的内容是什么？ 从 t0 到 t1 期间，H2 至少会接收到几个与此次 Web 访问相关的帧？接收到的是什么帧？帧的 目的 MAC 地址是什么？

【答案解析】 

（1）从 t0 到 t1 期间，H1 除了 HTTP 之外还运行了 DNS 应用层协议；DNS 报文从应用层到 数据链路层，逐层封装关系是：DNS 报文→UDP 数据报→IP 数据报→CSMA/CD 帧。 （2）S 在 t1 时刻的交换表为：

（3）H2 至少会接收到 2 个帧；接收到的均是封装 ARP 查询报文的以太网帧；这些帧的目的 MAC 地址均是：FF-FF-FF-FF-FF-FF。

设线性表L=（a₁ ，a₂，a₃，···，a_n-2,a_n-1, a_n）采用带头结点的单链表保存，链表中的 结点定义如下：

typedef struct node
{ int data; 
struct node*next; 
} NODE；

请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到 线性表L' =（a1 ，a_n, a₂，a_n-1,a₃，a_n-2,···）。要求： 

（1）给出算法的基本设计思想。 

（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。 

（3）说明你所设计的算法的时间复杂度。

【答案解析】

（1）算法的基本设计思想：先观察 L (a1 ,a2,a3,……,an-2, an-1,an ) 和 L’ (a1,an ,a2 ,an-1, a3 ,an- 2,……)，发现 L’ 是由 L 摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了 方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 O(1)，不能借 助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置 两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正 好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取 一个结点，按要求重排。 

（2）算法实现：

void change_list(NODE *h) {
        NODE *p,*q,*r,*s; 
        p=q=h; 
        while(q->next!=NULL) { // 寻找中间结点 
              p=p->next; //p 走一步 
              q=q->next; 
             if(q->next!=NULL) q=q->next; //q 走两步 
      }  
     q=p->next; //p 所指结点为中间结点， q 为后半段链表的首结点 
     p->next=NULL; 
     while(q!=NULL) { // 将链表后半段逆置 
           r=q->next; 
          q->next=p->next; 
          p->next=q; 
          q=r; 
    }  
    s=h->next; //s 指向前半段的第一个数据结点，即插入点 
    q=p->next; //q 指向后半段的第一个数据结点 
    p->next=NULL; 
    while(q!=NULL) { // 将链表后半段的结点插入到指定位置
          r=q->next; //r 指向后半段的下一个结点 
          q->next=s->next; // 将 q 所指结点插入到 s 所指结点之后 
          s->next=q; s=q->next; //s 指向前半段的下一个插入点 
          q=r; 
      }  
}

（3）第 1 步找中间结点的时间复杂度为 O(n)，第 2 步逆置的时间复杂度为 O(n)，第 3 步合 并链表的时间复杂度为 O(n)，所以该算法的时间复杂度为 O(n)。

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列 占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④入队操作和出队操作的时间复杂度始终保持为 O(1)。请回答下列问题： 

（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？ 

（2）画出队列的初始状态，并给出判断队空和队满的条件。 

（3）画出第一个元素入队后的队列状态。 

（4）给出入队操作和出队操作的基本过程。

【答案解析】

（1）顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求 ①容易满足；链式存储方便开辟新空间，要求②容易满足；对于要求③，出队后的结点并不 真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间， 赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一 个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入 队操作和出队操作的时间复杂度均为 O(1)，要求④可以满足。因此，采用链式存储结构（两 段式单向循环链表），队头指针为 front，队尾指针为 rear。 

（2）该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加 空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也 要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。初始时，创建只有一个 空闲结点的循环单链表，头指针 front 和尾指针 rear 均指向空闲结点，如下图所示。

队空的判定条件： front == rear。 队满的判定条件： front == rear->next 。 

（3）插入第一个元素后的状态如下图所示。

（4）操作的基本过程如下：

有 n（n≥3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在 圆桌中心有 m（m≥1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两 侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学 家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作［wait()、signal()操作］描述上 述过程中的互斥与同步，并说明所用信号量及初值的含义。

【答案解析】 回顾传统的哲学家问题，假设餐桌上有 n 个哲学家、n 根筷子，那么可以用这种方法避免死 锁：限制至多允许 n-1 个哲学家同时“抢”筷子，那么至少会有 1 个哲学家可以获得两根筷 子并顺利进餐，于是不可能发生死锁的情况。本题可以用碗这个限制资源来避免死锁：当碗 的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m，确保不会出现所有哲学家 都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量 m 大于等于哲学家的 数量 n 时，为了让碗起到同样的限制效果，我们让碗的资源量等于 n-1，这样就能保证最多只 有 n-1 个哲学家同时进餐，所以得到碗的资源量为 min{ n-1, m}。在进 PV 操作时，碗的资源 量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。具体过程如下：

// 信号量
semaphore bowl; // 用于协调哲学家对碗的使用
semaphore chopsticks[n]; // 用于协调哲学家对筷子的使用
for(int i=0; i<n; i++)
      chopsticks[i]=1; // 设置两个哲学家之间筷子的数量
bowl=min(n-1,m); //bowl ≤ n-1，确保不死锁
CoBegin
while(TRUE) { // 哲学家 i 的程序
       思考;
  P(bowl); // 取碗 
  P(chopsticks[i]); // 取左边筷子 
  P(chopsticks[(i+1)%n]); // 取右边筷子 就餐;  
  V(chopsticks[i]); 
  V(chopsticks[(i+1)%n]); 
  V(bowl); 
} 
CoEnd

某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：

（1）磁盘的容量是多少？

（2）假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100 260、60 005、101 660 和 110 560。若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是 什么？

（3）第 100 530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？

【答案解析】 

（1）磁盘容量 = 磁盘的柱面数每个柱面的磁道数每个磁道的扇区数每个扇区的大小 = (300 ×10×200×512/1024)KB = 3×10⁵KB。 

（2）磁头在 85 号柱面上，对 SSTF 算法而言，总是访问当前柱面距离最近的地址。注意每个簇包含 2 个扇区，通过计算得到， 85 号柱面对应的簇号为 85000～85999 。通过比较得 出，系统最先访问离 85000～85999 最近的 100260，随后访问离 100260 最近的 101660， 然后访问 110560，最后访问 60005。顺序为 100260、101660、110560、60005。 

（3）第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁道号、扇区号构成。 柱面号=⌊簇号/每个柱面的簇数⌋ = ⌊100530/(10×200/2)⌋=100。 磁道号=⌊(簇号%每个柱面的簇数)/每个磁道的簇数⌋=⌊530/(200/2)⌋=5。 扇区号=扇区地址%每个磁道的扇区数=(530×2)%200=60。 将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

已知f(n)=n!=n×(n-1)×（n-2）×···×2×1，计算 f(n)的 C 语言函数 f1 的源程 序（阴影部分）及其在 32 位计算机 M 上的部分机器级代码如下：

int f1(int n){
           1 00401000               55                  push ebp 
               …                            …                        …
              if(n>1) 
           1100401018 83 7D 08 01 cmp dword ptr [ebp+8],1 
           120040101C 7E 17 jle f1+35h (00401035) 
                 return n*f1(n-1); 
           130040101E 8B 45 08 mov eax, dword ptr [ebp+8] 
           1400401021 83 E8 01 sub eax, 1 
           1500401024 50 push eax 
           1600401025 E8 D6 FF FF FF call f1 ( 00401000) 
               …               …                     … 
           1900401030 0F AF C1 imul eax, ecx 
           2000401033 EB 05 jmp f1+3Ah (0040103a) 
              
                  else return 1; 
          2100401035 B8 01 00 00 00 mov eax,1 
}
             …                   …                   … 
         2600401040 3B EC cmp ebp, esp
            …                    …                    … 
         300040104A C3 ret

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题： 

（1）计算 f(10)需要调用函数 f1 多少次？执行哪条指令会递归调用 f1？ 

（2）上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？ 

（3）根据第 16 行的 call 指令，第 17 行指令的虚拟地址应是多少？已知第 16 行的 call 指令 题 47 图 采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？已知第 16 行的 call 指令的 后 4 字节为偏移量，M 是采用大端方式还是采用小端方式？ 

（4）f(13) = 6227020800，但 f1(13)的返回值为 1932053504，为什么两者不相等？要使 f1(13)能返回正确的结果，应如何修改 f1 的源程序？ 

（5）第 19 行的 imul 指令（带符号整数乘）的功能是 R[eax]←R[eax]×R[ecx]，当乘法器输 出的高、低 32 位乘积之间满足什么条件时，溢出标志 OF = 1？要使 CPU 在发生溢出时转异常 处理，编译器应在 imul 指令后应加一条什么指令？

【答案解析】 

（1）计算 f(10)需要调用函数 f1 共 10 次，执行第 16 行的 call 指令会递归调用 f1。 

（2）第 12 行的 jle 指令是条件转移指令，其含义为小于等于时转移，本行代码的意义为：当 n≤1 时，跳转至地址 0040 1035H。第 16 行的 call 指令为函数调用指令，第 20 行的 jmp 指 令为无条件转移指令，第 30 行的 ret 指令为子程序的返回指令，这三条指令一定会使程序跳 转执行。 

（3）其长度计算机 M 上按字节编址，第 16 行的 call 指令的虚拟地址为 0040 1025H，长度 为 5 字节，故第 17 行的指令的虚拟地址为 0040 1025H + 5 = 0040 102AH 。第 16 行的 call 指令采用相对寻址方式，即目标地址= (PC) +偏移量，call 指令的目标地址为 0040 1000H， 所以偏移量=目标地址- (PC) = 0040 1000H - 0040 102AH = FFFF FFD6H。根据第 16 行的 call 指令的偏移量字段为 D6 FF FF FF，可以确定 M 采用小端方式。 

（4）因为 f(13) = 6227020800，其结果超出了 32 位 int 型数据可表示的最大范围，因此 f(13) 的返回值是一个发生了溢出的错误结果。为使 f1(13)能返回正确结果，可将函数 f1 的返回值 类型改为 double（或 long long，或 long double，或 float）类型。 

（5）若乘积的高 33 位为非全 0 或非全 1，则 OF=1。编译器应在 imul 指令后加一条“溢出 自陷指令”，使得 CPU 自动查询溢出标志 OF，当 OF=1 时调出“溢出异常处理程序”。

对于题 45，若计算机 M 的主存地址为 32 位，釆用分页存储管理方式，页大小 为 4KB，则第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中（说明理由）？若指令 Cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块 内地址？哪几位表示 Cache 组号？哪几位表示标记（tag）信息？读取第 16 行的 call 指令时， 只可能在指令 Cache 的哪一组中命中（说明理由）？

【答案解析】

 因为页大小为 4KB，所以虚拟地址的高 20 位为虚拟页号。第 1 行的 push 指令和第 30 行的 ret 指令的虚拟地址的高 20 位都是 00401H，因此两条指令在同一页中。 指令 Cache 有 64 块，采用 4 路组相联映射方式，故指令 Cache 共有 64/4 = 16 组，Cache 组号共 4 位。主存块大小为 64B，故块内地址为低 6 位。综上所述，在 32 位主存地址中，低 6 位为块内地址，中间 4 位为组号，高 22 位为标记。 因为页大小为 4KB，所以虚拟地址和物理地址的最低 12 位完全相同，因而 call 指令虚拟地 址 0040 1025H 中的 025H = 0000 0010 0101B 为物理地址的低 12 位，对应的 7～10 位为 组号，故对应的 Cache 组号为 0。

某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1～H4 的 IP 地址配置以 及 R 的各接口 IP 地址配置如图中所示。现有若干以太网交换机（无 VLAN 功能）和路由器两 类网络互连设备可供选择。

请回答下列问题： 

（1）设备 1、设备 2 和设备 3 分别应选择什么类型的网络设备？ 

（2）设备 1、设备 2 和设备 3 中，哪几个设备的接口需要配置 IP 地址？为对应的接口配置 正确的 IP 地址。 

（3）为确保主机 H1～H4 能够访问 Internet，R 需要提供什么服务？ 

（4）若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收 该数据报？

【答案解析】 

（1）以太网交换机（无 VLAN 功能）连接的若干 LAN 仍然是一个网络（同一个广播域），路 由器可以连接不同的 LAN、不同的 WAN 或把 WAN 和 LAN 互联起来，隔离了广播域。IP 地 址 192.168.1.2/26 与 192.168.1.3/26 的网络前缀均为 192.168.1.0，视为 LAN1。IP 地址192.168.1.66/26 与 192.168.1.67/26 的网络前缀均为 192.168.1.64，视为 LAN2。所以设备 1 为路由器，设备 2、3 为以太网交换机。 

（2）设备 1 为路由器，其接口应配置 IP 地址。IF1 接口与路由器 R 相连，其相连接口的 IP 地址为 192.168.1.253/30，253 的二进制表示形式为 11111101，故 IF1 接口的网络前缀也应 为 192.168.1.111111，已分配 192.168.1.253，去除全 0 全 1，IF1 接口的 IP 地址应为 192.168.1.254。LAN1 的默认网关为 192.168.1.1，LAN2 的默认网关为 192.168.1.65，网关 的 IP 地址是具有路由功能的设备的 IP 地址，通常默认网关地址就是路由器中的 LAN 端口地 址，设备 1 的 IF2、IF3 接口的 IP 地址分别设置为 192.168.1.1 和 192.168.1.65。 

（3）私有地址段：C 类 192.168.0.0~192.168.255.255，即 H1～H4 均为私有 IP 地址，若要 能够访问 Internet，R 需要提供 NAT 服务，即网络地址转换服务。 （4）主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，主机号全为 1，为本网络的 广播地址，由于路由器可以隔离广播域，只有主机 H4 会接收到数据报。

给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如,数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

答：（1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数 n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n 时返回n+1。当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。经过以上分析可以得出算法流程：从A[0]开始遍历A，若0

（2）

int findMissMin(int A[],int n) {
int i,*B;//标记数组
B=(int *)malloc(sizeof(int)*n); //分配空间
memset(B,0,sizeof(int)*n);//赋初值为0
for(i=0; i<n; i++)
if(A[i]>0&&A[i]<=n)//若A[i]的值介于1~n，则标记数组B
B[A[i]-1]=1;
for(i=0; i<n; i++) //扫描数组B，找到目标值
if (B[i]==0) break;
return i+1;//返回结果
}

（3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。

拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光纤的铺设费用。

请回答下列问题。

（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用。

（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。

（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

答：

（1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动Prim算法或Kruskal算法作图。注意本题最小生成树有两种构造，如下图所示。

方案的总费用为16。

（2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用Prim算法（或kruskal算法）。

（3）TTL=5，即IP分组的生存时间（最大传递距离）为5，方案1中TL和BJ的距离过远，TTL=5不足以让IP分组从H1传送到H2，因此H2不能收到IP分组。而方案2中TL和BJ邻近，H2可以收到IP分组。

假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。

（1）若设备A采用定时查询I/O方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百分比至少是多少？

（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？

（3）若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分比最大是多少？

答：

（1）程序定时向缓存端口查询数据，由于缓存端口大小有限，必须在传输完端口大小的数据时访问端口，以防止部分数据没有被及时读取而丢失。设备A准备32位数据所用时间为4B/2MB=2µs，所以最多每隔2µs必须查询一次，每秒的查询次数至少是1s/2µs=5×105，每秒CPU用于设备A输入/输出的时间至少为5×105×10×4 = 2×107个时钟周期，占整个CPU时间的百分比至少是2×107/500M = 4%。

（2）中断响应和中断处理的时间为400×（1/500M）=0.8µs，这时只需判断设备B准备32位数据要多久，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新、造成丢失。经过计算，设B准备32位数据所用时间为4B/40MB=0.1µs，因此，设备B不适合采用中断I/O方式。

（3）在DMA方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制。设备B每秒的DMA次数最多为40MB/1000B=40000，CPU用于设备B输入/输出的时间最多为40000×500 = 2×107个时钟周期，占CPU总时间的百分比最多为2×107/500M = 4%。

某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。

根据题44图回答下列问题。

（1）主存物理地址占多少位？

（2）TLB采用什么映射方式？TLB用SRAM还是DRAM实现？

（3）Cache采用什么映射方式？若Cache采用LRU替换算法和回写(Write Back)策略，则Cache每行中除数据(Data)、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？

（4）若CPU给出的虚拟地址为0008 C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由。若CPU给出的虚拟地址为0007 C260H，则该地址所在主存块映射到的Cache组号是多少？

答：（1）物理地址由实页号和页内地址拼接，因此其位数为16+12 = 28；或直接可得20+3+5 = 28。

（2）TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB中每项都有一个比较器，没有映射规则，只要空闲就行。TLB采用静态存储器SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。

（3）图中可以看到，Cache中每组有两行，故采用 2 路组相联映射方式。因为是2路组相联并采用LRU替换算法，所以每行（或每组）需要1位LRU位；因为采用回写策略，所以每行有1位修改位（脏位），根据脏位判断数据是否被更新，如果脏位为1则需要写回内存。28 位物理地址中Tag字段占20位，组索引字段占3位，块内偏移地址占5位，故Cache共有23 = 8组，每组2行，每行有25 = 32B；故Cache总容量为8×2×(20+1+1+1+32×8) = 4464位 = 558字节。

Cache中有效位用来指出所在Cache行中的信息是否有效。

（4）虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找TLB表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号008CH恰好在TLB表中对应实页号 0040H（有效位为1，说明存在），虚拟地址的后3位为页内地址040H，则对应的物理地址是 0040040H。物理地址为0040040H，其中高20位00400H为标志字段，低5位00000B为块内偏移量，中间3位010B为组号2，因此将00400H与Cache中的第2组两行中的标志字段同时比较，可以看出，虽然有一个Cache行中的标志字段与00400H相等，但对应的有效位为0，而另一Cache行的标志字段与00400H不相等，故访问Cache不命中。

因为物理地址的低12位与虚拟地址低12位相同，即为0010 0110 0000B。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此虚拟地址0007 C260H所在的主存映射到Cache组号为3。

请根据题44图给出的虚拟储管理方式，回答下列问题。

（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？

（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。

（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？

答：

（1）由图可知，地址总长度为32位，高20位为虚页号，低12位为页内地址。且虚页号高10位为页目录号，低10位为页号。展开成二进制则表示为：0000 0001 1000 0000 0110 0000 0000 1000 B

故十六进制表示为0180 6008H。

（2）PDBR为页目录基址地址寄存器（Page-Directory Base Register），其存储页目录表物理内存基地址。进程切换时，PDBR的内容会变化；同一进程的线程切换时，PDBR的内容不会变化。每个进程的地址空间、页目录和PDBR的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新PDBR。同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。

（3）改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。

某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。

（1）该文件系统能支持的最大文件长度是多少？(给出计算表达式即可)

（2）文件系统用1M（1M=220）个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件?

（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？

答：

（1）簇大小为4KB，每个地址项长度为4B，故每簇有4KB/4B = 1024个地址项。最大文件的物理块数可达8+1×1024+1×10242+1×10243，每个物理块（簇）大小为4KB，故最大文件长度为(8+1×1024+1×10242+1×10243)×4KB = 32KB+4MB+4GB+4TB。

（2）文件索引节点总个数为1M×4KB/64B = 64M，5600B的文件占2个簇，512M个簇可存放的文件总个数为512M/2 = 256M。可表示的文件总个数受限于文件索引节点总个数，故能存储64M个大小为5600B的图像文件。

（3）文件F1大小为6KB＜4KB×8 = 32KB，故获取文件F1的最后一个簇的簇号只需要访问索引节点的直接地址项。文件F2大小为40KB，4KB×8＜40KB＜4KB×8+4KB×1024，故获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。

某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销告部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。

请回答下列问题。

（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？

（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？

答：

（1）广播地址是网络地址中主机号全1的地址（主机号全0的地址，代表网络本身）。销售部和技术部均分配了192.168.1.0/24的IP地址空间，IP地址的前24位为子网的网络号。于是在后8位中划分部门的子网，选择前1位作为部门子网的网络号。令销售部子网的网络号为0，技术部子网的网络号为1，则技术部子网的完整地址为 192.168.1.128；令销售部子网的主机号全1，可以得到该部门的广播地址为192.168.1.127。每个主机仅分配一个IP地址，计算目前还可以分配的主机数，用技术部可以分配的主机数，减去已分配的主机数，技术部总共可以分配计算机主机数为27-2 = 126（减去全0和全1的主机号）。已经分配了208-129+1 = 80个，此外还有1个IP地址分配给了路由器的端口(192.168.1.254)，因此还可以分配126-80-1=45台。

（2）判断分片的大小，需要考虑各个网段的MTU，而且注意分片的数据长度必须是8B的整数倍。由题可知，在技术部子网内，MTU = 800B，IP分组头部长20B，最大IP分片封装数据的字节数为⌊(800-20)/8⌋×8 = 776。至少需要的分片数为⌈(1500-20)/776⌉ = 2。第1个分片的偏移量0；第2个分片的偏移量为 776/8 = 97。

请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b) * (c * (-d)和(a * b)+(-(c-d))。

二叉树结点定义如下：

typedef struct node{
    char data[10];                 //存储操作数或操作符
    struct node *left, *right;
}BTree;

请回答下列问题。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

答：

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

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分)

表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。

（2）算法实现(10分)

void BtreeToE(BTree *root) {
    BtreeToExp(root,1); //根的高度为1
}
void BtreeToExp(BTree *root, int deep) {
    if(root == NULL) return;
    else if(root->left == NULL && root->right == NULL)//若为叶结点
        printf("%s",root->data);//输出操作数
    else {
        if(deep>1) printf("(");//若有子表达式则加1层括号
        BtreeToExp(root->left，deep+1);
        printf("%s",root->data); //输出操作符
        BtreeToExp(root->right,deep+1);
        if(deep>1) printf(")");//若有子表达式则加1层括号
    }
}

使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。

（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

（2）图G的MST是唯一的吗？

（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？

答：

（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合S。当算法终止时，S就是最小生成树。

①S中顶点为A，候选边为(A,D)、(A,B)、(A,E)，选择(A,D)加入S。

②S中顶点为A、D，候选边为(A,B)、(A,E)、(D,E)、(C,D)，选择(D,E)，加入S。

③S中顶点为A、D、E，候选边为(A,B)、(C,D)、(C,E)，选择(C,E)加入S。

④S中顶点为A、D、E、C，候选边为(A,B)、(B,C)，选择(B,C)加入S。

⑤S就是最小生成树。

依次选出的边为：

(A，D),(D，E),(C，E),(B，C) （4分）

（2）图G的MST是唯一的。（2分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的MST唯一。

（3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。

已知，计算f(n)的C语言函数f1如下：

int f1(unsigned n){
    int sum=1, power=1;
    for(unsigned i=0;i<=n-1;i++){
        power *= 2;
        sum += power;
    }
    return sum;
}

将f1中的int都改为float，可得到计算f(n)的另一个函数f2。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。请回答下列问题。

（1）当n=0时，f1会出现死循环，为什么？若将f1中的变量和n都定义为int型，则f1是否还会出现死循环？为什么？

（2）f1(23)和f2(23)的返回值是否相等？机器数各是什么(用十六进制表示)？

（3）f1(24)和f2(24)的返回值分别为33 554 431和33 554 432.0，为什么不相等？

（4）f(31)=232-1，而f1(31)的返回值却为-1，为什么？若使f1(n)的返回值与f(n)相等，则最大的n是多少？

（5）f2(127)的机器数为7F80 0000H，对应的值是什么？若使f2(n)的结果不溢出，则最大的n是多少？若使f2(n)的结果精确(无舍入)。则最大的n是多少？

答：

（1）由于i和n是unsigned型，故“i<=n-1”是无符号数比较，n=0时，n-1的机器数为全1，值是232-1，为unsigned型可表示的最大数，条件“i<=n-1”永真，因此出现死循环。(2分)

若i和n改为int类型，则不会出现死循环。(1分)

因为“i<=n-1”是带符号整数比较，n=0时，n-1的值是-1，当i=0时条件“i<=n-1”不成立，此时退出for循环。(1分)

（2）f1(23)与f2(23)的返回值相等。（1分）f(23) = 223+1-1 = 224-1，它的二进制形式是24个1。int占32位，没有溢出。float有1个符号位，8个指数位，23个底数位，23个底数位可以表示24位的底数。所以两者返回值相等。

f1(23)的机器数是 00FF FFFFH。（1分）

f2(23)的机器数是 4B7F FFFFH。（1分）

显而易见前者是24个1，即 0000 0000 1111 1111 1111 1111 1111 1111（2），后者符号位是 0，指数位为 23+127(10) = 1001 0110（2），底数位是 111 1111 1111 1111 1111 1111（2）。

（3）当n=24时，f(24) = 1 1111 1111 1111 1111 1111 1111 B，而float型数只有24位有效位，舍入后数值增大，所以f2(24)比f1(24)大1。(1分)

（4）显然f(31)已超出了int型数据的表示范围，用f1(31)实现时得到的机器数为32个1，作为int型数解释时其值为-1，即f1(31)的返回值为-1。(1分)

因为int型最大可表示数是0后面加31个1，故使f1(n)的返回值与f(n)相等的最大n值是30。(1分)

（5）IEEE 754标准用“阶码全1、尾数全0”表示无穷大。f2返回值为float型，机器数7F80 0000H对应的值是+∞。(1分)当n=126时，f(126) = 2127-1 = 1.1…1×2126，对应阶码为127+126=253，尾数部分舍入后阶码加1，最终阶码为254，是IEEE 754单精度格式表示的最大阶码。故使f2结果不溢出的最大n值为126。(1分)当n=23时，f(23)为24位1，float型数有24位有效位，所以不需舍入，结果精确。故使f2获得精确结果的最大n值为23。(1分)

在按字节编址的计算机M上，题43中f1的部分源程序(阴影部分)与对应的机器级代码(包括指令的虚拟地址)如下：

     int fl(unsigned n)

1    00401020   55          push ebp

     ......        ...          ......

         for(unsigned i=0; i<=n-1; i++)

     ......        ...          ......

20   0040105E   39 4D F4    cmp dword ptr[ebq-0Ch],ecx

     ......        ...          ......

     {    power *= 2;

 ......        ...          ......

23   00401066 D1 E2      shl edx,1

 ......  ...         ......

  return sum;

 ......        ...           ......

35   0040107F C3           ret

  }

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。

（1）计算机M是RISC还是CISC？为什么？

（2）f1的机器指令代码共占多少字节？要求给出计算过程。

（3）第20条指令cmp通过i减n-1实现对i和n-1的比较。执行f1(0)过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么？要求给出计算过程。

（4）第23条指令shl通过左移操作实现了power*2运算，在f2中能否也用sh1指令实现power*2？为什么？

答：

（1）M为CISC。(1分)M的指令长短不一，不符合RISC指令系统特点。(1分)

（2）f1的机器代码占96 B。(1分)

因为f1的第一条指令“push ebp”所在的虚拟地址为0040 1020H，最后一条指令“ret”所在的虚拟地址为0040 107FH，所以，f1的机器指令代码长度为0040 107FH-0040 1020H+1 = 60H = 96个字节。(1分)

（3）CF=1。(1分)cmp指令实现i与n-1的比较功能，进行的是减法运算。在执行f1(0)过程中，n=0，当i=0时， i=0000 0000H，并且n-1=FFFF FFFFH。因此，当执行第20条指令时，在补码加/减运算器中执行“0减FFFF FFFFH”的操作，即0000 0000H+0000 0000H+1=0000 0001H，此时，进位输出C=0，减法运算时的借位标志CF=C⊕1=1。(2分)

（4）f2中不能用shl指令实现power*2。(1分)

因为 shl 指令用来将一个整数的所有有效数位作为一个整体左移；而f2中的变量power是float型，其机器数中不包含最高有效数位，但包含了阶码部分，将其作为一个整体左移时并不能实现“乘2”的功能，因而f2中不能用shl指令实现power*2。(2分)浮点数运算比整型运算要复杂，耗时也较长。