t An
Quiz 1: Graphs 19/03/2019, 20)36
! Students have either already taken or started taking this quiz, so be careful about editing it. If you change any quiz questions in a significant way, you may want to consider regrading students who took the old version of the quiz.
Show Question Details
Points 8 ! Published ”
Details
Questions
swer
# Question1 1pts
A complete graph is one where every two vertices are connected with an edge. Suppose we run DFS on a complete graph. What would the DFS tree look like?
It will be a simple path
It won’t be a tree. It will be a forest made up of many small trees. It will be a binary tree
None of the other answers
# Question2 1pts
A complete graph is one where every two vertices are connected with an edge. Suppose you run BFS on a complete graph G(V,E) starting from some node s in V . What would the BFS layers look like?
Each layer will have a single node.
It’s impossible to tell. The structure of the layers will depends on the order the algorithm scans the adjacency lists of each vertex.
swer
t An
https://canvas.sydney.edu.au/courses/12842/quizzes/48549/edit Page 1 of 4
c
c
swer
# Question3 1pts
What is the time complexity of BFS when the graph data structure is implemented with adjacency lists? Select the tightest bound that holds. Here n is the number of vertices in the graph and m is the number of edges in the graph.
O(n+m) O(1) O(n2+m) O(n+m2)
swer
# Question4 1pts
What is the time complexity of DFS when the graph data structure is implemented with adjacency lists? Select the tightest bound that holds.Here n is the number of vertices in the graph and m is the number of edges in the graph.
O(n+m) O(1) O(n2+m) O(n+m2)
None of the other answer
# Question5 1pts
There exists a connected undirected graph such that every edge in the graph is a cut edge. True
swer
t An
t An
Quiz 1: Graphs 19/03/2019, 20)36
t An
https://canvas.sydney.edu.au/courses/12842/quizzes/48549/edit Page 2 of 4
c
c
c
# Question6 1pts
If a graph G with n vertices is connected and does not contain any cycle then:
G has exactly n edges.
G has exactly n-1 edges.
G has exactly n+1 edges.
None of the other answers are correct
swer
# Question7 1pts
Which two graph representations were covered in the lecture?
proportional representation adjacency list representation modular representation adjacency matrix representation
swer
swer
False
# Question8 1pts
What is the transitive closure of an undirected tree?
The complete graph A simple path
A bipartite graph
swer
t An
t An
t An
Quiz 1: Graphs
19/03/2019, 20)36
t An
https://canvas.sydney.edu.au/courses/12842/quizzes/48549/edit
Page 3 of 4
c
c
c
c
Quiz 1: Graphs 19/03/2019, 20)36
$ New Question $ New Question Group % Find Questions
Notify users this quiz has changed
Cancel Save
A tree
https://canvas.sydney.edu.au/courses/12842/quizzes/48549/edit Page 4 of 4