2024年408真题

本文参考了王道《2025年计算机专业基础综合考试历年真题参考答案》

02.

与表达式 x + y * (z - u) / v 等价的后缀表达式( )。

• ○ A. xyzu-*v/+
• ○ B. xyzu-v/*+
• ○ C. +x/*y-zuv
• ○ D. +x*y/-zuv

显示答案

正确答案：A. xyzu-*v/+

41.

2023年10月26日，神舟十七号载入飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载入航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G采用矩阵存储，类型定义如下。

typedef struct                  //图的类型定义
{
   int numVertices, numEdges;   //图的顶点数和有向边数
   char VerticesList[MAXV];     //顶点表，MAXV为已知定义常量
   int Edge[MAXV][MAXV];        //邻接矩阵
}MGraph;

请设计算法：int uniquley(MGraph G)，判定G是否存在唯一的拓扑序列，若是，则返回1，否则返回0。要求如下。
1）给出算法的基本设计思想。(4分）
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(9分）

显示答案

（1）算法设计思想：
建立图G各顶点的入度表indegree[]，其中各元素初始值为0。
初始将入度为0的点加入队列queue，若有多个入度为0的点，则存在多个拓扑序列，返回0。
每次选择入度为0的顶点v，将与v组成边的顶点的入度减1，重复执行这个过程。
● 若每次选中的入度为0的点有且仅有1个，且共进行了G.numVertices次，则意味着存在唯一的拓扑序列，返回1。
● 否则不存在拓扑序列，或存在多个拓扑序列，返回0。

（2）C++代码：

  int uniquely(MGraph G) {
  int n = G.numVertices;
  // 初始化入度，初值为0
  int indegree[n];
  memset(indegree, 0, sizeof(indegree));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (G.Edge[i][j]) {
        indegree[j]++;
      }
    }
  }

  int queue[n];
  int front = 0, rear = 0;
  int count = 0; //拓扑排序执行次数
  for (int i = 0; i < n; i++) {
    if (indegree[i] == 0) {
      // 入度为0的点入队
      queue[rear++] = i;
    }
    if (rear - front > 1)
      return 0;
  }
  // 队列非空
  while (front < rear) {
    int x = queue[front++];
    // 拓扑序列的长度和点的长度相同
    count++;
    for (int j = 0; j < n; j++) {
      // 如果存在边，则对应的入度--
      if (G.Edge[x][j]) {
        indegree[j]--;
        if (indegree[j] == 0) {
          queue[rear++] = j;
        }
        if (rear - front > 1) {
          return 0; //序列不唯一
        }
      }
    }
  }
  return count == n;
}

42.

将关键字序列依次存储到初始为空、长度为11的散列表HT中，散列函数 。H(key)计算出的初始散列地址为 ，发生冲突时探查地址序列是 ，其中 。请回答下列问题。
1）画出所构造的HT，并计算HT的装填因子。（6分）
2）给出在HT中查找关键字14的关键字比较序列。（2分）
3）在HT中查找关键字8，确认查找失败时的散列地址是多少？（2分）

显示答案

HT如下表：

散列地址	0	1	2	3	4	5	6	7	8	9	10
关键字	11		14	7		20	9			3	18

H(20)=5，装入5
H(3)=9，装入9
H(11)=0，装入0
H(18)=10,装入10
H(9)=5，冲突， ,装入6
H(14)=9，冲突， ，冲突，，装入2
装填因子为7/11。
2）关键字序列：3，18，14。
,和关键字3比较，未命中；
，和关键字18比较，未命中；
，和关键字14比较，命中。
3）确认查找失败时的散列地址为7。
，和关键字14比较，未命中；
，和关键字7比较，未命中；
，和关键字9比较，未命中；
，和关键字11比较，未命中；
，为空位置，查找失败。

45.

（7分）某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为32位，页表项的大小为4字节，页大小为4MB，虚拟地址结构如下。
| 页号（10位） | 页内偏移量（22位） |
进程P的页表起始虚拟地址为B8C0 0000H，被装载到从物理地址6540 0000H开始的连续主存空间中。请回答下列问题，要求答案用十六进制表示。
1）若CPU在执行进程P的过程中，访问虚拟地址1234 5678H时发生了缺页异常，经过缺页异常处理和MMU地址转换后得到的物理地址是BAB4 5678H,在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？（3分）
2）进程P的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？（4分）

显示答案

46.

（8分）计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区B用于存放一个数据分组，对B的操作有C1、C2和C3。C1将一个数据分组写入B，C2从B中读出一个数据分组，C3对B中的数据分组进行修改。要求B为空时才能执行C1，B非空时才能执行C2和C3。请回答下列问题。
1）假设进程P1和P2均需要执行C1，实现C1的代码是否为临界区？为什么？（2分）
2）假设B初始为空，进程P1执行C1一次，进程P2执行C2一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值。（3分）
3）假设B初始不为空，进程P1和P2各执行C3一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值。（3分）

显示答案

1）实现C1的代码是临界区，因为代码C1执行对B的写操作，P1和P2需要互斥执行C1。

2）B初始为空，所以只能执行C1,C2无法执行。而执行过程中需要保证对B的互斥访问，故仅需一个同步信号量即可保证P1和P2互斥访问B。

Semaphore S = 0; //定义信号量S，实现P1与P2的同步
P1
-------------
   ...
   C1;
   signal(S);
   ...
-------------
P2
-------------
   ...
   wait(S);
   C2;
   ...
-------------

3）
缓冲区B初始非空，因此仅需一个互斥信号量mutex来保证P1和P2互斥访问B。

Semaphore mutex = 1; //实现P1与P2互斥执行C3
P1
-------------
	...
	wait(mutex)
   C3;
   signal(mutex);
   ...
-------------
P2
-------------
	...
	wait(mutex)
   C3;
   signal(mutex);
   ...
-------------