5.5.2 真题

强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 5.5.2 真题

## 2021年41题

(15 分)已知无向连通图 G 由顶点集V和边集E 组成，E > 0，当 G 中度为奇数的顶点个数为不大于2的偶数时，G 存在包含所有边且长度为E|的路径(称为EL路径)。设图G采用邻接矩阵存储，类型定义如下：

typedef struct{ 1 图的定义
    图中实际的顶点数和边数
    char VerticesList[MAXv]; //顶点表。MAXV为已定义常量
    int Edge[MAXV] [MAXV]; //邻接矩阵
}MGraph;


请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。

【解析】分析可知本题需要访问所有顶点，统计所有顶点的度，然后判断有多少个度为奇数的顶点，只需要对邻接矩阵一次遍历即可实现。【答案】（1）访问所有的顶点，两层循环判断每两个顶点间是否有边相连、统计所有顶点的度，进而求出有多少个度为奇数的顶点，对邻

int IsExistEL(MGraph G)
{
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int degree = 0;
        for (int j = 0; j &lt; G.numVertices; j++)
        if (G.Edge[i][j] == 1)
        degree++;
        if (degree % 2 == 1)
        count++;
        if (count == 0 |l count == 2)
        return 1;
        else
        return 0;
    }
    typedef struct // 图的类型定义
    int numVertices,numEdges;// 图的顶点数和有向边数
    char VerticesList[MAXV ]; // 顶点表MAXV为已定义常量
    int Edge[ MAXV ][ MAXV ]; // 邻接矩阵
}MGraph;


(3)时间复杂度：O(n²)空间复杂度：O(1)

<!-- page 245 -->

(13 分）已知有向图 G 采用邻接矩阵存储，类型定义如下：

将图中出度大于入度的顶点称为K顶点。例如在下图中，顶点a和b为K顶点。


请设计算法：int printVertices(MGraph G)，对给定的任意非空有向图G，输出G中所有的K顶点，并返回K顶点的个数。要求：1）给出算法的基本设计思想。2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

【解析】出度大于入度的顶点称为K顶点，本题关键是遍历图求出所有顶点的入度和出度，才能判断出顶点是否为K顶点。依次判断所有顶点是否为K顶点，并统计数量即可。

【答案】注：以下两种答案本质一样，仅供参考

(1) 图的邻接矩阵 G. Edge[i][j]>0 表示i到j 有边，二重循环遍历邻接矩阵，算出每个顶点的入读indegree 和出度 outdegree，然后判断每个顶点是否为 K 顶点，如果是则输出并且计数器 count+1，最后返回 count 即可。(2) 写法 1： KN

<!-- verified-by-hand -->
> [!success] 已结合原文第 245 页及 Markdown 上下文人工校对
> 中文解释未加注释符，导致本来正确的代码不可编译。
int printVertices(MGraph G)
{
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int indegree = 0, outdegree = 0;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (G.Edge[i][j] &gt; 0) outdegree++;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (G.Edge[j][i] &gt; 0) indegree++; // j 到 i 有边
        if (outdegree &gt; indegree)
        {
            printf(&quot;%c&quot;, G.VerticesList[i]);
            count++;
        }
    }
    return count;
}


<!-- page 246 -->

## 写法2:

<!-- verified-by-hand -->
> [!success] 已结合原文第 246 页及 Markdown 上下文人工校对
> 输出伪代码和孤立字符替代了 if 复合语句的花括号，count++ 因而无条件执行。
int printVertices(MGraph G)
{
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int indegree = 0, outdegree = 0;
        for (int j = 0; j &lt; G.numVertices; j++)
        {
            if (G.Edge[i][j] &gt; 0) outdegree++;
            if (G.Edge[j][i] &gt; 0) indegree++;
        }
        if (outdegree &gt; indegree)
        {
            printf(&quot;%c&quot;, G.VerticesList[i]);
            count++;
        }
    }
    return count;
}


## 2024年41题

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

<!-- verified-by-hand -->
> [!success] 已结合原文第 246 页及 Markdown 上下文人工校对
> 邻接矩阵图结构体左花括号丢失，int 与 numVertices 粘连。
typedef struct
{
    int numVertices, numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;


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

<!-- page 247 -->


## 【解析1】

【答案1】(1)

1. 遍历图统计所有顶点的入度，将入度为0的顶点都入队。

2. 循环执行：① 如果队中元素个数不为 1，说明拓扑序列不唯一或不存在，return 0。②出队一个顶点记为 v，count++。③更新所有与顶点v相连的顶点i的入度，若i的入度为0，则将i入队。

3. 如果 count 等于顶点数则拓扑序列唯一，return 1；否则拓扑序列不存在，return 0。 (2)代码如下：

int uniquely1(MGraph G)
{
    int inDegree[MAXV] = {0}; // 存储每个顶点的入度
    int queue[MAXV]; //用于存储入度为0的顶点
    int front = 0, rear //队列的前后指针
    int count = 0; //拓扑序列中的顶点计数
    //计算每个顶点的入度
    for (int i = 0; i &lt; G.numVertices; i++)
    for (int j = 0; j &lt; G.numVertices; j++)
    if (G.Edge[i][j] != 0)
    inDegree[j]++;
    /7将所有入度为0的顶点入队
    for (int i = 0; i &lt; G.numVertices; i++)
    if (inDegree[i] == 0)
    queue[rear++] = i;
    // 进行拓扑排序
    while (front &lt; rear)
    {
        //如果队列中有多个顶点，说明图的拓扑序列不唯
        if (rear - front &gt; 1)
        return 0;
        count++;
        for (int i = 0; i &lt; G.numVertices; i++)
        if (G.Edge[v][i] != 0)
        {
            inDegree[i]--; //如果入度变为0，则加入队列
            if (inDegree[i] == 0)
            queue[rear++] = i;
        }
    }
    if (count == G.numVertices)
    return 1; // 拓扑序列包含所有顶点，图的拓扑序列唯一
    else
    return 0; //拓扑序列不包含所有顶点，图的拓扑序列不存在
}


<!-- page 248 -->

## 【解析2】

<table><tr><td>拓扑序列</td><td>条件</td></tr><tr><td>存在且唯一</td><td>每次选择结点时都只有一个结点可选</td></tr><tr><td>存在且不唯</td><td>选择结点时不止一个结点可选</td></tr><tr><td>不存在</td><td>图中有环，环中的顶点未被访问</td></tr></table>


拓扑排序为什么使用队列？


可能有多个入度为0的顶点。


【答案2】（1)

拓扑排序的步骤：

1. 选择入度为0的顶点并输出它。

2. 从图中删除该顶点和所有以它为弧头的边。

3. 重复步骤1、2，直到不存在入度为0的顶点。


1. 遍历图并统计所有顶点的入度，count是入度为0的顶点的数量，入度为0的顶点记为V。

2. 循环执行：① 如果 count 不为 1，说明拓扑序列不唯一或不存在，return 0。②ν 是本次选择的顶点，将 count 清零重新计数。③更新所有与顶点v相连的顶点j的入度，若j的入度为0，则计数器 count++。

3. 拓扑序列唯一，return 1。(2) 代码如下：

int uniquely(MGraph G)
{
    int v, inDegree[MAXV] = {0};
    //计算每个顶点的入度
    for (int i = 0; i &lt; G.numVertices; i++)
    for (int j = 0; j &lt; G.numVertices; j++)
    if (G.Edge[i][j] &gt; 0)
    inDegree[j]++;
    int count = 0;
    for (int j = 0; j &lt; G.numVertices; j++)
    if (inDegree[j] == 0)
    {
        v = j;
        count++;
    }
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        if (count != 1)
        return 0; // 若count不等于1,拓扑序列不存在或不唯
        count = 0;  // 下一次选择时入度为0的顶点数先设为0
        int temp = v;
        for (int j = 0; j &lt; G.numVertices; ++j)
        if (G.Edge[temp][j] != 0)
        {
            inDegree[j]--; // 将v所连弧尾顶点的入度-1
            if (inDegree[j] == 0)
            {
                v = j;
                count++; // 如果j的入度为0则count++
            }
        }
        return 1; //循环执行完，拓扑序列唯
    }
}


<!-- page 250 -->

## 6补充知识

## 6.1 注释与函数

考试中的注释也是必不可少的，因为重要的是让老师理解我们的思路，所以在关键位置处写注释有助于老师阅读。当然如果你的代码足够清晰、明确，也可以不写注释。

在变量的定义处告知该变量是做什么的：

bool visited[MAXV] = {false}; // 表示顶点是否已入队


在使用伪代码处和函数调用处告知这部分实现哪些功能：

输出 xxx
swap(A[L], A[i]); //交换A[L] 与 A[i]


代码逻辑复杂的地方告知其功能：

计算每个顶点的入度
for (int i = 0; i &lt; G.numVertices; i++)
for (int j = 0; j &lt; G.numVertices; j++)
if (G.Edge[i][j] &gt; 0)
inDegree[j]++;
int count = 0;
for (int j = 0; j &lt; G.numVertices; j++)
if (inDegree[j] == 0)
{
    v = j;
    count++; // 统计入度为 0一的顶点数
}


很多简单的代码、库函数写起来浪费时间，考试时建议只写调用而不写具体内部实现，只要让老师知道你想干嘛即可。但重要的代码一定不能这样，否则是0分。比如说本题就是考察快速排序，如果直接调用Qsort()而不写快排具体过程，当然拿不到分。

那如何判断？只要这部分代码有可能超过你的所有代码1/4 或者超过5 行（表示他对于你的代码很重要)，就一定要写。

以下是给大家总结的最常见可以偷懒节省时间的地方，考试时简写，使用的时候写清楚功能而不需要给出具体实现细节。

## 6.1.1 最大最小值INT\_MAX、INT\_MIN

从名字可以看出来，INT\_MAX 是最大的整数值，INT\_MIN 是最小的整数值（C 语言自带函数，在头文件limits.h中)，他常用于比较选择最大最小值时，比如初值设为INT\_MAX，那遇到任意值都会比他小或者相等，这样只要遇到比他小的就更新为更小的值。

<!-- page 251 -->

int D_min = INT_MAX; // Dmin初始设为最大的整数
for (int i = 0; i &lt; n; i++) //遍历 D循环选出最小的D
if (D[i] &lt; D_min) D_min = D[i]; // D[i]比 D_min 小, D_min 更新


## 6.1.2 比大小函数 max(a, b)、min(a, b)

函数定义如下(不用掌握)：

int min(int a, int b)
{
    if (a &lt; b) return a;
    else return b;
}
int max(int a, int b)
{
    if (a &gt; b) return a;
    else return b;
}


使用这两个函数能让我们的代码变得简洁、清晰：

int D_min = INT_MAX; // D_min 初始设为最大的整数
//遍历D循环选出最小的D
for (int i = 0; i &lt; n; i++)
D_min = min(D_min, D[i]);


如果我们是要选出最小值，则初值应该赋最大可能值。如果我们是要选出最大值，则初值应该赋最小可能值。 A

## 6.1.3 输入输出函数 scanf、printf

C 语言中的输入、输出函数分别是 scanf 和printf 函数，因为和变量的类型有关，写起来比较麻烦，在考试中可以用 C++，那我们可以使用 C++的 cin、cout 函数来输入、输出，而不用管变量的类型，会简洁很多。

int a;
float b;
char c;
char d[10];
scanf(&quot;%d%f%c%s&quot;,&amp;a,&amp;b,&amp;c,&amp;d); //输入整数a、浮点数b、字符c、字符串d
printf(&quot;%d%f%c%s&quot;, a, b, c, d); //输出整数a、浮点数b、字符c、字符串d


考试中需要记住如下格式：

<!-- page 252 -->

i++;
x=a[i];


<table><tr><td rowspan=1 colspan=1>整型int</td><td rowspan=1 colspan=1>浮点型 float</td><td rowspan=1 colspan=1>字符型 char</td><td rowspan=1 colspan=1>字符串 char[]</td></tr><tr><td rowspan=1 colspan=1>%d</td><td rowspan=1 colspan=1>%f</td><td rowspan=1 colspan=1>%c</td><td rowspan=1 colspan=1>%s</td></tr></table>

如果怕自己记错，也可以直接写中文，如：输入a、b、c、d；输出a、b、c、d。写中文还有一个好处，需要循环输入输出的时候，中文描述更简便，如循环输出int 数组 a中的值：

for (int i = 0; i &lt; n; i++)
printf(&quot;%d &quot;, a[i]);


用中文描述：

输出数组a


除以上两种写法外，还可以用 C++ 的写法，输出是 cout << a[i]，输入是 cin >> a[i]。

## 6.1.4 a[i++] 和 a[++i]

这两个写法是不一样的，a[i++]中i在前表示先使用 a[i]，再 i+1；a[++i] 中先 i+1，再使用 a[i](此时i是+1 后的结果)。这两种写法相当于两步缩写成了一步。

假设 a[0] = 0, a[1] = 1, i = 0。

x = a[i++] 这条指令，相当于先用再加：

x = a[i];
i++;


x的值为 a[0] = 0。

• x = a[++i] 这条指令，相当于先加再用：

x 的值为 a[1] = 1。