文章

63

粉丝

0

获赞

0

访问

3.1k

头像
2023年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年11月2日 17:35
阅读数 29

1.用出度减入度之差的数组degree,遍历邻接矩阵时,若存在i到j的边,则i的出度加1, degree[i]++;  j的入度加1 ,degree[j]--;最后统计出度减入度数组中大于0的顶点

    int printVertices(MGraph G){
        // 出度减入度之差的数组
        int *degree = new int[G.numVertices];

        for(int i=0;i<G.numVertices;i++){
            for(int j=0;j<<G.numVertices;j++){
                // 存在i到j的边
                if(G.Edge[i][j]!=0){
                    // i的出度加1
                    degree[i]++;
                    // j的入度加1
                    degree[j]--;

                }
            }
        }
        // 统计出度减入度数组中大于0的顶点
        int count=0;
        for(int i=0;i<G.numVertices;i++){
            if(degree[i]>0){
                count++;
                cout<<i<<printl;
            }
        }
        return count;
    }

 


评分及理由

(1)得分及理由(满分4分)

学生给出的算法设计思想是:使用一个degree数组记录每个顶点出度减入度的差值,遍历邻接矩阵时,如果存在i到j的边,则degree[i]加1(表示出度增加),degree[j]减1(表示入度增加)。最后统计degree数组中大于0的顶点即为K顶点。

这个思路与标准答案不同但同样正确,能够准确找出出...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发