# CS代考程序代写 data structure algorithm t An

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