2024-234

 

 

 

The graph above represents the social network of a group of people in a research lab, illustrating co-authorship among the researchers. Based on this information, which of the following options is the average clustering coefficient rounded to the nearest tenth:

 

A) ⟨C⟩ = 0.2

B) ⟨C⟩ = 0.4

C) ⟨C⟩ = 0.6

D) ⟨C⟩ = 0.8

E) None of the above 

 

Original idea by: Matheus Lindino

2024-233

 

Which of the adjacency matrices below represents the graph above?

A) 0 0 1 1 1

    0 0 1 0 1

    1 1 0 1 1

    1 0 1 0 1

    1 1 1 1 0

 

B) 0 0 1 1 1

    0 0 1 0 1

    1 1 0 0 1

    1 0 0 0 1

    1 1 1 1 0

C) 0 1 1 0 0

    0 0 0 1 1

    1 1 0 1 1

    1 1 1 0 1

    0 1 0 0 1

 

D) 0 0 1 1 0

    0 0 1 0 1

    1 1 0 0 1

    1 0 0 0 1

    0 1 1 1 0

 

E) None of the above 

 

Original idea by: Gustavo Henrique Sencio de Souza 

2024-232

Given the following directed graph:

Which sequence represents a valid depth-first search (DFS) traversal order that involves only one tree?

A. a-d-b-f-c-e

B. a-d-f-b-e-c

C. e-c-d-f-b-a

D. c-d-b-a-f-e

E. None of the above

Original idea by: Darlinne Hubert Palo Soto

2024-231

How does a Depth-First Search (DFS) provide a topological sort ?

A) Sorting nodes by finishing time, in ascending order

B) Selecting nodes in a random order

C) Visiting nodes in alphabetical order

D) Sorting nodes by finishing time, in descending order

E) None of the above

Original idea by: Cinthia Kleiner

2024-230

 

Given the curriculum chart for the Computer Engineering course above, a student needs to schedule which subjects should be taken.  Which of the options below indicates the topological sort order obtained by taking the reverse order of finishing times in a particular DFS, where nodes are selected in alphabetical/numerical order in the main loop and also in the adjacency lists:

a) LA -> CEI -> DC1 -> DC2 -> C1 -> C2 -> C3 -> SP -> A1 -> A2

b) LA -> CEI -> DC1 -> DC2 -> A1 -> A2 -> C1 -> C2 -> C3 -> SP

c) C1 -> CEI -> C2 -> LA -> A1 -> DC1 -> C3 -> A2 -> DC2 -> SP

d) CEI -> C1 -> DC1 -> A1 -> LA -> C2 -> DC2 -> A2 -> C3 -> SP

e) None of the above

Original idea by: Matheus Lindino

2024-229

During a Depth-First Search (DFS) on a directed graph G, the following edges are traversed:

• Edge (u, v), where v has already been visited and fully explored.
• Edge (x, y), where y has been visited but not fully explored yet.
• Edge (a, b), where b has been fully explored, but belongs to a different branch from a in the DFS tree.

Of course, each edge is traversed when it origin node is being explored.  Which of the following options correctly classifies these edges according to their type in a DFS traversal?

A) (u, v) is a forward edge, (x, y) is a back edge, (a, b) is a back edge.

B) (u, v) is a cross edge, (x, y) is a forward edge, (a, b) is a tree edge.

C) (u, v) can be a forward or cross edge, (x, y) is a back edge, (a, b) is a cross edge.

D) (u, v) is a back edge, (x, y) is a cross edge, (a, b) is a forward edge.

E) None of the above

Original Idea by Sergio Sanchez