【答案1】
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【答案1】
(1)
1. 遍历图统计所有顶点的入度，将入度为0的顶点都入队。
2. 循环执行：
①如果队中元素个数不为1，说明拓扑序列不唯一或不存在，return0。
② 出队一个顶点记为 v，count++。
③更新所有与顶点ν相连的顶点i的入度，若i的入度为0，则将i入队。
3. 如果 count等于顶点数则拓扑序列唯一，return 1；否则拓扑序列不存在，return 0。
(2) 代码如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 178 页及 Markdown 上下文人工校对
> 最终 count 判断被放进 while，第一次循环便提前返回，且闭括号丢失。
int uniquely1(MGraph G)
{
int inDegree[MAXV] = {0}, queue[MAXV];
int front = 0, rear = 0, count = 0;
for (int i = 0; i < G.numVertices; i++)
for (int j = 0; j < G.numVertices; j++)
if (G.Edge[i][j] != 0) inDegree[j]++;
for (int i = 0; i < G.numVertices; i++)
if (inDegree[i] == 0) queue[rear++] = i;
while (front < rear)
{
if (rear - front != 1) return 0;
int v = queue[front++];
count++;
for (int i = 0; i < G.numVertices; i++)
if (G.Edge[v][i] != 0 && --inDegree[i] == 0) queue[rear++] = i;
}
return count == G.numVertices;
}
原资料配图 · 转写内容请回源核验
原资料配图 · 转写内容请回源核验
原资料配图 · 转写内容请回源核验
拓扑排序为什么使用队列？
可能有多个入度为0的顶点。
然后呢？
有多个选择时就会return0,是不
是只需要考虑选择唯一时的情况？
选择唯一就可以不使用队列!
原资料配图 · 转写内容请回源核验
拓扑排序的步骤：
1. 选择入度为0的顶点并输出它。
2. 从图中删除该顶点和所有以它为弧头的边。
3. 重复步骤1、2，直到不存在入度为0的顶点。
原资料配图 · 转写内容请回源核验
1. 遍历图并统计所有顶点的入度，count是入度为0的顶点的数量，入度为0的顶点记为v。
2. 循环执行：
②ν是本次选择的顶点，将 count 清零重新计数。
① 如果 count 不为 1，说明拓扑序列不唯一或不存在，return 0。
③更新所有与顶点ν相连的顶点j的入度，若j的入度为0，则计数器count++。
3. 拓扑序列唯一，return 1。
(2) 代码如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 180 页及 Markdown 上下文人工校对
> 无队列版本未给初始 v 赋值，主循环错嵌，count++ 缺花括号且 return 1 提前。
int uniquely(MGraph G)
{
int inDegree[MAXV] = {0}, queue[MAXV];
int front = 0, rear = 0, count = 0;
for (int i = 0; i < G.numVertices; i++)
for (int j = 0; j < G.numVertices; j++)
if (G.Edge[i][j] != 0) inDegree[j]++;
for (int i = 0; i < G.numVertices; i++)
if (inDegree[i] == 0) queue[rear++] = i;
while (front < rear)
{
if (rear - front != 1) return 0;
int v = queue[front++];
count++;
for (int i = 0; i < G.numVertices; i++)
if (G.Edge[v][i] != 0 && --inDegree[i] == 0) queue[rear++] = i;
}
return count == G.numVertices;
}
bool visited[MAXv] = {false};
//计算每个顶点的入度
for (int i = 0; i < G.numVertices; i++)
for (int j = 0; j < G.numVertices; j++)
if (G.Edge[i][j] > 0)
inDegree[j]++;
int count = 0;
for (int j = 0; j < G.numVertices; j++)
if (inDegree[j] == 0)
{
v = j;
count++; //
}
int D_min = INT_MAX;
for (int i = 0; i < n; i++)
if (D[i] < D_min) D_min = D[i];
// D_min 初始设为最大的整数
//遍历 D 循环选出最小的 D
// D[i]比D_min 小，D_min 更新
int min(int a, int b)
{
if (a < b) return a;
else return b;
int max(int a, int b)
{
if (a > b) return a;
else return b;
}
}
int D_min = INT_MAX;
//遍历 D 循环选出最小的 D
for (int i = 0; i < n; i++)
D_min = min(D_min, D[i]);
int a;
float b;
char c;
char d[10];
scanf("%d%f%c%s", &a, &b, &c, &d);
printf("%d%f%c%s", a, b, c, d);
真
ww
//输入整数a、浮点数b、字符c、字符串d
//输出整数a、浮点数b、字符c、字符串d
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//冒泡排序
for(int i = n-1; i > 1; i--)
for (int j = 0; j < i; j++)
if (A[i] < A[j])
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
//冒泡排序
for(int i = n-1; i > 1; i--)
for (int j = 0; j < i; j++)
if (A[i] < A[j]) swap(A[i], A[j]);
for (i = 0; i < n; i++)
cout<<A[i];
while (p != NULL)
{
cout << p->data;
p = p->next;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
if (A[i][j] > A[i][k] + A[k][j])
A[i][j] = A[i][k] + A[k][j];
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
for (k = 0; k < j; k++)
if (A[i][j] > A[i][k] + A[k][j])
A[i][j] > A[i][k] + A[k][j];
// 22 考研真题
for (i = 1; i < n; i*=2)
for (j = 0; j < i; j++)
sum++;
void Inorder(BTNode *p)
{
if (p == NULL) return;
Inorder(p->lchild);
visit(p);
Inorder(p->rchild);
}
// 单个变量不考虑
int i, j, k;
//数组考虑元素个数，空间复杂度 0(n)
int a[n];
//链表考虑结点个数，空间复杂度 0(n)
Node* L = (Node*)malloc(sizeof(Node));
Node* p = L;
for (int i = 0; i < n; i++)
{
p->next = (Node*)malloc(sizeof(Node));
p = p->next;
}
void InOrder(BTNode *p)
{
if (p == NULL) return;
Inorder(p->lchild);
visit(p);
Inorder(p->rchild);
}