A graph is said to be acyclic if it contains _____________

• A) exactly one cycle
• B) at least one cycle
• C) no cycles
• D) always more than one cycle

The _____________is a problem for which the greedy algorithm approach provides an optimal solution.

• A) Activity selection
• B) NP complete problem
• C) Dynamic programming
• D) Knapsack Problem

Bag is a _________

• A) program
• B) data structure
• C) type of algorithm
• D) compiler

A graph is ___________ if every vertex can reach every other vertex.

• A) Connected
• B) Loop
• C) Acyclic
• D) Cycle

Forward edge is:

• A) (u, v) where v is a proper descendent of u in the tree.
• B) (u, v) where v is a proper ancesstor of u in the tree.
• C) (u, v) where u is a proper ancesstor of v in the tree.
• D) (u, v) where u is a proper descendent of v in the tree.

If the graph is represented using an adjacency matrix, then Depth-first search takes __________ time.

• A) O(V^2)
• B) O(V + E)
• C) O(E + 1)
• D) O(V)

Graphs can be represented by an _________ and____________.

• A) adjacency Right, adjacency Left
• B) adjacency list, adjacency Matrix
• C) Queue, Stack
• D) Binary, Linear

In Huffman Encoding, the characters with smallest probabilities are placed at the ________ depth of the tree.

• A) Average
• B) Maximum
• C) Minimum
• D) Root

Traversing a graph means visiting __________ in the graph.

• A) no node
• B) more than one node
• C) every node
• D) at least one

Which of the following algorithms provides an optimal solution for the activity selection problem?

• A) Brute Force
• B) Recursive
• C) Greedy
• D) Divide and Conquer

In Activity Selection, we say that two activities are non-interfering if their start-finish interval _________ overlap.

• A) Once
• B) Do not
• C) Sometimes
• D) Do

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

The prefix code generated by Huffman algorithm ________ the expected length of the encoded string.

• A) Minimizes
• B) Maximizes
• C) Keeps Constant
• D) Balances

_______________ 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) Node
• B) Vertices
• C) Tree
• D) Graph

Queue data structure work on _____ principles.

• A) FIFO (first in, first out)
• B) LOFI (last out, first in)
• C) LIFO (last in, first out)
• D) JLO (just in, last out)

In digraph G=(V,E) ;G has cycle if and only if

• A) The DFS forest has both back and forward edge
• B) BFS forest has forward edge
• C) The DFS forest has forward edge.
• D) The DFS forest has back edge

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

• A) Infinite set of nodes
• B) Infinite set of vertices V
• C) Infinite set of objects
• D) Finite set of vertices V

In Activity selection problem, intuitively _________.

• A) We do not like long activities
• B) There are always short activities as input
• C) Duration of the activities does not matter
• D) Short activities are not attractive

Which of the following is true about Huffman Coding?

• A) In Huffman coding, no code is prefix of any other code
• B) Huffman coding may become lossy in some cases
• C) Huffman coding is not an efficient coding way
• D) Huffman Codes may not be optimal lossless codes in some cases

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

• A) Out-degree
• B) Complete degree
• C) In-degree
• D) Node