2019年考研408计算机统考真题在线评测（附答案）

第41题

设线性表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)。

第42题

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

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

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

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

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

【答案解析】

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

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

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

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

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

第43题

有 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

第44题

某计算机系统中的磁盘有 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。 将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

第45题

已知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 时调出“溢出异常处理程序”。

第46题

对于题 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题

某网络拓扑如题 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 会接收到数据报。