Cross edge is :

• A) (u, v) where u and v are either ancestor or descendent of one another.
• B) (u, v) where u is ancesstor of v and v is not descendent of u.
• C) (u, v) where u and v are not ancestor of one another
• D) (u, v) where u and v are not ancestor or descendent of one another

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

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

The activity scheduling is a simple scheduling problem for which the greedy algorithm approach provides a/an ________solution.

• A) Sub optimal
• B) Simple
• C) Non optimal
• D) Optimal

Each vertex can reach every other vertex is called____________.

• A) Connected graph
• B) Ordered graph
• C) Unconnected graph
• D) Unordered graph

Back edge is:

• A) (u, v) where v is an ancestor of u in the tree.
• B) (u, v) where u is a mid of v in the tree.
• C) (u, v) where u is an ancestor of v in the tree.
• D) (u, v) where v is a predecessor of u in the tree.

The number of edges that come out of a vertex is called the ________ of that vertex in a digraph.

• A) out-degree
• B) post-degree
• C) in-degree
• D) pre-degree

Brute-force is a simple strategy for computing ______________.

• A) Longest path
• B) Complete path
• C) Easiest path
• D) shortest path

The ancestor and descendent relation can be nicely inferred by the ______________ lemma.

• A) node
• B) addition
• C) parenthesis
• D) division

Fractional Knapsack is founded on ____________ method.

• A) Greedy
• B) Recursive
• C) Dynamic Programming
• D) Divide and Conquer

The Binary Tree constructed by Huffman Encoding is a:

• A) Full binary tree
• B) Incomplete binary tree
• C) None of the given options
• D) Partial binary tree

In context of activity selection algorithm, time is dominated by sorting of the activities by _________.

• A) Average Times
• B) Finish Times
• C) CPU Burst Times
• D) Start Times

__________________ data structure is used to perform the Depth-first search.

• A) Queue
• B) Array
• C) Stack
• D) Tree

If we implement the bag by using a queue, we have ________________________.

• A) Loop
• B) BFS
• C) DFS
• D) Graph

In general, the activity selection problem is to select a ___________.

• A) maximum-size set of mutually non-interfering activities
• B) maximum-size set of interfering activities
• C) minimum-size set of mutually non-interfering activities
• D) minimum-size set of interfering activities

Which of the following is true about graph?

• A) A graph may contain many edges and no vertices
• B) A graph may contain no edges and no vertices
• C) A graph may contain no edges and many vertices
• D) A graph may contain no vertices and many edges

Huffman algorithm uses a ___________________to generate a prefix code T that minimizes the expected length B(T) of the encoded string.

• A) Heuristic Approach
• B) Greedy Approach
• C) Dynamic Programming
• D) Null Approach

The running time of the traversal algorithm depends on ____________and __________ which is used for the bag.

• A) Edges, Vertices
• B) Parent Node, Child Node
• C) Graph representation, Data structure
• D) Root, Leaf

Using ASCII standard the string “greedy” will be encoded with

• A) 48 bits
• B) 44 bits
• C) 40 bits
• D) 120 bits

If the graph is represented using an adjacency list, then Breadth-first search takes _________ time.

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

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)
• D) Not equal to Sum of out-degree(v)