For graph traversal, Breadth-first search strategy ________

• A) Can be both recursive and non-recursive
• B) Cannot be recursive
• C) is always recursive
• D) Cannot be non-recursive

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.

Bag is a _________

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

Graphs can be represented by an _________ and____________.

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

Which of the following algorithms solves the fractional knapsack problem most effectively?

• A) Greedy algorithm
• B) Dynamic programming
• C) Backtracking
• D) Divide and conquer

In general in comparison with Fractional Knapsack problem, ______________

• A) We cannot compare them
• B) Both are easy to solve
• C) 0-1 knapsack problem is very easy to solve
• D) 0-1 knapsack problem is hard to solve

For graph traversal, Breadth-first search strategy ________

• A) is always recursive
• B) Can be both recursive and non-recursive
• C) Cannot be non-recursive
• D) Cannot be recursive

For traversing the graphs, _____________can be visualized as a wave front propagating inward towards root node.

• A) Depth-first Search
• B) Linear search
• C) Binary search
• D) Breadth-first search

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

Huffman algorithm generates an optimum _______ code.

• A) None of the given options
• B) Infix
• C) Postfix
• D) Prefix

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

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

In undirected graph, by convention all the edges are called _________ edges.

• A) Forward
• B) Back
• C) Cross
• D) Both forward and back

Keeping in mind the shortest-path, if given scenarios occur in computer networks like the internet where data packets have to be routed. The vertices are_________and Edges are _____________which may be wired or wireless.

• A) Communication links, routers
• B) Internet, routers
• C) Routers, communication links
• D) Routers, internet

A free tree with n _________ have exactly n-1 _________.

• A) vertices,edges
• B) edges,vertices
• C) nodes,vertices
• D) vertices,nodes

Which technique is used in the implementation of Kruskal solution for the MST?

• A) Dynamic Programming Technique
• B) The algorithm combines more than one of the above techniques i.e. Divide-and-Conquer and Dynamic Programming
• C) Greedy Technique
• D) Divide-and-Conquer Technique

Which of the following statement is false about Dijkstra’s Algorithm?

• A) It can be applied on graphs having a negative weight function
• B) Its implementation in data structure is possible through the priority queue
• C) It works on a weighted directed graph
• D) It is used to solve Single-source shortest path

Overall time for Kruskal algorithm is:

• A) Θ(ElogV)
• B) Θ(logE)
• C) Θ(VlogE)
• D) Θ(ElogE)

There exist a unique path between any ________ vertices of a free tree.

• A) Two
• B) Four
• C) One
• D) Three

In Timestamped DFS, If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u, we get ______________.

• A) a line
• B) a cycle
• C) nothing
• D) a graph

In computing the ____________ components of a digraph, vertices of the digraph are partitioned into subsets.

• A) best
• B) worst
• C) weakly connected
• D) strongly connected