CS502 Final Term MCQs Set 3 by VU Topper RM

Q1. Vu-Topper RM (1 marks)

Which of the following problems is NOT solved using dynamic programming?

1. Matrix chain multiplication problem
2. Edit distance problem
3. Fractional knapsack problem
4. 0/1 knapsack problem

Correct answer: Fractional knapsack problem

Q2. Vu-Topper RM (1 marks)

Breadth-first search is a traversal strategy for_________. A. Tree B. Link List C. Array

D. Graph

Q3. Vu-Topper RM (1 marks)

In a digraph, the number of edges coming in of a vertex is called the

A. Node

B. In-degree

C. Out-degree D. Complete degree

Q4. Vu-Topper RM (1 marks)

In an undirected graph, we say that an edge is _______________on a vertex if the vertex is an endpoint of the edge. A. Tree B. Directed C. Undirected

D. Incident

Q5. Vu-Topper RM (1 marks)

Which graph traversal algorithm uses a stack to keep track of vertices?

1. Depth First Search
2. Greedy Algorithm
3. Divide and Conquer
4. Breadth First Search

Correct answer: Depth First Search

Q6. Vu-Topper RM (1 marks)

In general, a graph G = (V,E) consists of a ___________ and E, a binary relation on V called edges.

A. Finite set of vertices V

B. Infinite set of objects C. Infinite set of nodes D. Infinite set of vertices V

Q7. Vu-Topper RM (1 marks)

Each time we traverse graph by Breadth-first search algorithm, we count the distance from _________ A. left most node B. neighbors of the starting node

C. starting node

D. right most node

Q8. Vu-Topper RM (1 marks)

For traversing the graphs, _____________can be visualized as a wave front propagating inward towards root node. A. Binary search B. Linear search

C. Breadth-first search

D. Depth-first Search

Q9. Vu-Topper RM (1 marks)

In a digraph, the number of edges coming out of a vertex is called the

A. Node B. In-degree

C. Out-degree

D. Complete degree

Q10. Vu-Topper RM (1 marks)

Brute-force is a simple strategy for computing ______________.

A. shortest path

B. Longest path C. Complete path D. Easiest path

Q11. Vu-Topper RM (1 marks)

In general in comparison with Fractional Knapsack problem,

a. knapsack problem is very easy to solve

b. knapsack problem is hard to solve

c. We cannot compare them d. Both are easy to solve

Q12. Vu-Topper RM (1 marks)

_______________ is a good way to model some sort of “connection” or “relationship” or “interaction” between pairs of objects taken from a set of objects. A. Vertices B. Tree

C. Graph

D. Node

Q13. Vu-Topper RM (1 marks)

For a digraph G = (V, E), Sum of in-degree(v) ____________ A. < Sum of out-degree(v)

B. = Sum of out-degree(v)

C. Sum of out-degree(v)