NEW
Font size
WorksheetsAlgorithmic Network Analysis - Quiz I
Total questions: 20
Worksheet time: 11mins
A computational problem is considered tractable if:
It has a high storage space requirement
It can be solved in exponential time
There exists an efficient algorithm for solving it
It involves complex mathematical operations
What measure of complexity is commonly used to describe the least amount of time needed to solve a problem?
Best-case complexity
Worst-case complexity
Average-case complexity
Polynomial complexity
The tiling problem is an example of:
A tractable problem
An efficient algorithm
Intractable problem
Polynomial complexity
What is the first step in a depth-first search (DFS) of a graph?
Select the vertex with the highest degree as the starting vertex.
Select a first vertex to visit and label it.
Sort all the vertices in descending order of their degrees.
Visit all vertices and mark them unvisited.
In a graph represented by adjacency lists, in what order are the vertices adjacent to a given vertex listed?
In decreasing order of their degrees
In increasing order of their degrees
In increasing order of their subscripts
In decreasing order of their subscripts
In a DFS forest, what structure is each component of the forest?
A directed acyclic graph (DAG)
A disconnected subgraph
A rooted tree
A cycle
What does the depth-first search index (Dfi) of a vertex represent?**
The distance from the starting vertex
The number of back edges connected to the vertex
The degree of the vertex in the graph
The order in which the vertex was first visited during DFS
In a connected graph, what does the set of edges in a BFS traversal form?
-
-
A subgraph
A spanning tree
A connected component
A cycle
If all vertices adjacent to the current active vertex have been visited in DFS, what does the algorithm do next?
Selects the vertex with the smallest index
Backtracks to the previous vertex
Moves to a random unvisited vertex
Stops the search
A graph in which any two distinct points are adjacent is called a null graph.
True
False
A connected acyclic graph is called __________
star
loop
tree
cyclic
What is the size of a tree of order p?
p
p-1
p+1
p-2
Which of the following statements is true about a forest in graph theory?
A forest must have the same number of edges as vertices.
A forest is a connected graph.
Every component of a forest is a tree.
A forest contains exactly one cycle.
If a tree has 7 vertices, how many edges does it have?
6
7
5
8
The size of a tree is equal to its order.
True
False
A forest must have the same number of edges as vertices.
True
False
Which statement is true regarding the relationship between connected graphs and spanning trees?
Spanning trees only exist in trees, not in other types of graphs.
A tree contains multiple spanning subgraphs.
A graph is connected if and only if it contains a spanning tree.
Every connected graph contains exactly one spanning tree.
What data structure is used in Breadth-First Search (BFS) to keep track of the vertices?
Linked List
Array
Queue
Stack
What kind of graph structure does BFS create in a disconnected graph?
A Hamiltonian cycle
A complete graph
A spanning forest
A spanning tree
What is the time complexity of the Breadth-First Search (BFS) algorithm in a graph with p vertices and q edges?
- a) \( \)
- b) \( O(p \times q) \)
- c) \( O(p^2) \)
- d) \( ) \)
O(p + q)
O(p^2)
O(q^2
O(p - q)
