GATE CSE 2007 | Greedy Method Question 23 | Algorithms

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

There is a minimum spanning tree containing e.

If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.

Every minimum spanning tree has an edge of weight w .

e is present in every minimum spanning tree.

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?

2.1875

2.25

1.9375

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Dijkstra’s algorithm starting from S.

Warshall’s algorithm

Performing a DFS starting from S.

Performing a BFS starting from S.

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?

0, 10, 110, 1110, 11110, 11111

11, 10, 011, 010, 001, 000

11, 10, 01, 001, 0001, 0000

110, 100, 010, 000, 001, 111

PREVIOUS NEXT