Test: Graphs - 2 - Software Development MCQ

Which of the following algorithms can be used to find all the connected components in an undirected graph?

In a directed acyclic graph (DAG), a topological sort is:

What is the output of the following code?
#include <iostream>
#include <list>

int main() {
    std::list<int> adjList[3];
    adjList[0].push_back(1);
    adjList[1].push_back(2);
    adjList[2].push_back(0);

    for (int i = 0; i < 3; i++) {
        std::cout << "Vertex " << i << " is connected to: ";
        for (int v : adjList[i]) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

What is the output of the following code?
#include <iostream>
#include <stack>

void topologicalSortUtil(int v, bool visited[], std::stack<int>& stack) {
    visited[v] = true;

    for (int u : adjList[v]) {
        if (!visited[u]) {
            topologicalSortUtil(u, visited, stack);
        }
    }

    stack.push(v);
}

int main() {
    // Graph initialization and input omitted for brevity

    std::stack<int> stack;
    bool visited[V] = {false};

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, visited, stack);
        }
    }

    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }

    return 0;
}

What is the output of the following code?
#include <iostream>
#include <queue>

void bfs(int v, bool visited[], std::vector<int> adjList[]) {
    std::queue<int> queue;
    visited[v] = true;
    queue.push(v);

    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();

        std::cout << u << " ";

        for (int i : adjList[u]) {
            if (!visited[i]) {
                visited[i] = true;
                queue.push(i);
            }
        }
    }
}

int main() {
    // Graph initialization and input omitted for brevity

    bool visited[V] = {false};

    bfs(0, visited, adjList);

    return 0;
}

What is the output of the following code?
#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> matrix = {
        {0, 1, 1},
        {1, 0, 1},
        {1, 1, 0}
    };

    int count = 0;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = i + 1; j < matrix[i].size(); j++) {
            if (matrix[i][j] == 1) {
                count++;
            }
        }
    }

    std::cout << "Number of edges in the graph: " << count << std::endl;

    return 0;
}

What is the output of the following code?
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {2, 4, 6, 8, 10};
    std::vector<int>::iterator it;
    
    it = std::find(arr.begin(), arr.end(), 5);
    
    if (it != arr.end()) {
        std::cout << "Element found at index: " << std::distance(arr.begin(), it) << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }
    
    return 0;
}

Which of the following algorithms can be used to find the minimum spanning tree (MST) of an undirected graph?

What is the output of the following code?
```cpp
#include <iostream>
#include <queue>

void dfs(int v, bool visited[], std::vector<int> adjList[]) {
    visited[v] = true;
    std::cout << v << " ";

    for (int i : adjList[v]) {
        if (!visited[i]) {
            dfs(i, visited, adjList);
        }
    }
}

int main() {
    // Graph initialization and input omitted for brevity

    bool visited[V] = {false};

    dfs(0, visited, adjList);

    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {5, 3, 9, 1, 7};
    std::sort(arr.begin(), arr.end(), std::greater<int>());
    
    for (int i : arr) {
        std::cout << i << " ";
    }
    
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {2, 4, 6, 8, 10};
    std::vector<int>::reverse_iterator it;
    
    for (it = arr.rbegin(); it != arr.rend(); ++it) {
        std::cout << *it << " ";
    }
    
    return 0;
}
```

What is the output of the following code?
```cpp
#include <iostream>
#include <stack>

void dfs(int v, bool visited[], std::vector<int> adjList[]) {
    std::stack<int> stack;
    visited[v] = true;
    stack.push(v);

    while (!stack.empty()) {
        int u = stack.top();
        stack.pop();

        std::cout << u << " ";

        for (int i : adjList[u]) {
            if (!visited[i]) {
                visited[i] = true;
                stack.push(i);
            }
        }
    }
}

int main() {
    // Graph initialization and input omitted for brevity

    bool visited[V] = {false};

    dfs(0, visited, adjList);

    return 0;
}
```