2024年408真题

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

装填因子=7/11 20: H(20)=5，装入5