万卷网 > 题目详情
题型:单选题

给定两个无向图 G1和 G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。

为了简化问题,假设图的节点编号从 0 到 n-1,并且图的边以邻接表的形式给出。下面程序中横线处应该给出的是?( )

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
string graphHash(vector<vector<int>>& graph) {
    vector<string> nodeHashes(graph.size());
    for (int i = 0; i < graph.size(); i++) {
        vector<int> neighbors = graph[i];
        sort(neighbors.begin(), neighbors.end());
        string hash;
        for (int neighbor : neighbors) {
            _______________________________
        }
        nodeHashes[i] = hash;
    }
    sort(nodeHashes.begin(), nodeHashes.end());
    string finalHash;
    for (string h : nodeHashes) {
        finalHash += h + ";";
    }
    return finalHash;
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> G1(n);
    for (int i = 0; i < n; i++) {
        int k;
        while (cin >> k) {
            G1[i].push_back(k);
            if (cin.get() == '\n') break;
        }
    }
    vector<vector<int>> G2(n);
    for (int i = 0; i < n; i++) {
        int k;
        while (cin >> k) {
            G2[i].push_back(k);
            if (cin.get() == '\n') break;
        }
    }
    string hash1 = graphHash(G1);
    string hash2 = graphHash(G2);
    if (hash1 == hash2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}
A.

hash += to_string(neighbor);

B.

hash += to_string(neighbors);

C.

hash += to_string(neighbor) + ",";

D.

hash -= to_string(neighbors);

更新时间:2026-03-27 18:53:14 |
【知识点】 CCF—GESP C++七级

相似题推荐

单选题

下面关于二叉树的说法正确的是( )。

A.

任意二叉树的中序遍历与后序遍历必定不相同。

B.

对任意二叉树,若已知先序遍历与后序遍历,则该二叉树唯一确定。

C.

若二叉树有 个结点,根节点高度为 ,则其高度满足: [log2(n+1)]<=h<=n。

D.

在二叉树的先序遍历中,根后紧跟的结点一定是根的左孩子。

2026-07-27
判断题

选择排序是一种不稳定的排序算法,而冒泡排序是一种稳定的排序算法。2025.12-7

A.正确 B.错误
2026-07-27
单选题

假设一个算法时间复杂度的递推式是 ,和T(0) = 1 ,那么这个算法的时间复杂度是(  )。

A.

B.

C.

O(n2)

D.

O(n2 log n)

2026-07-27
单选题

一棵深度为6(根节点深度为1)的完全二叉树,节点总数最少有( )。

A.

31

B.

32

C.

63

D.

64

2026-07-27
单选题

下面程序中,函数 query 的时间复杂度是( )。

#include <iostream> 

int query(int n, int *a, int x) { 
    int l = 0, r = n; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        if (a[mid] >= x) 
            r = mid; 
        else 
            l = mid + 1; 
    } 
    if (l == n) 
        return -1; 
    return l; 
} 

int main() { 
    int n = 10; 
    int x = 3; 
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7}; 
    std::cout << query(n, num, x) << "\n"; 
    return 0; 
}
A.

O(1)

B.

O(log n)

C.

O(n)

D.

O(n log n)

2026-07-27
公众号
客服 反馈
顶部