文章

15

粉丝

0

获赞

6

访问

864

头像
【2024年】408计算机统考真题模拟考试 - 第41题答案笔记
数据结构
发布于2025年5月6日 23:49
阅读数 31

计算机考研408统考历年真题及答案解析

(1) 根据题干可得,G是一个AOV网;只需要在进行拓扑排序的过程中,检查是否有两个及以上的候选点(即两个及以上的入度为0的顶点),即可判断拓扑排序序列是否唯一
(2)

// 使用栈存储候选点
// 使用的基础操作有:
// init(&S):初始化栈

// push(&S, x):将x入栈

// pop(&S, &x): 栈顶元素出栈并用x返回

// empty(S):判断栈是否为空,空则返回true,否则返回false

typedef struct {
    int data[MAXV];

    int top;    // 栈顶指针
} SqStack;

void init(SqStack &S) {
    S.top = -1;
}

bool empty(SqStack S) {
    return S.top == -1;
}
void push(SqStack &S, int x) {
    // 由于data的容量为MAXV,因此不可能出现满了还需要入栈的情况
    S.data[++S.top] = x;
}
void pop(SqStack &S, int &x) {
    if (empty(S))

        return;

    x = S.data[S.top];

    S.top--;

}
// 算法主体
int uniquely(MGraph G) {

    SqStack S;
    init(S);

    // 记录所有顶点的入度
    int inDegrees[G.numVertices];

    // 初始化inDegrees[]
  ...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发