Scribd
Upload
105 views3 pages

Dsa Q31

The document contains 10 multiple choice questions about data structures and algorithms topics like greedy algorithms, Huffman coding, and Fibonacci numbers. Specifically, it tests knowledge of which problems can be solved with greedy approaches, constructing Huffman codes from letter probabilities, calculating average code lengths, decoding Huffman encoded strings, properties of Huffman codes, and applying Huffman coding to message frequencies.

Uploaded by

sanskriti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
105 views3 pages

Dsa Q31

The document contains 10 multiple choice questions about data structures and algorithms topics like greedy algorithms, Huffman coding, and Fibonacci numbers. Specifically, it tests knowledge of which problems can be solved with greedy approaches, constructing Huffman codes from letter probabilities, calculating average code lengths, decoding Huffman encoded strings, properties of Huffman codes, and applying Huffman coding to message frequencies.

Uploaded by

sanskriti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

DATA STRUCTURE & ALGORITHMS

1. Which of the following is not an application of Greedy approach?

(i) 0/1 Knapsack


(ii) Fractional Knapsack
(iii) All pair shortest path
(iv) Single Source shortest path
(v) Optimal Merge Patterns

(a) Only (ii), (iv) & (v) (b) Only (ii), (iii) & (v)
(c) Only (i) & (iii) (d) Only (i), (iii) & (iv)

2. Suppose the letters a, b, c, d, e has probability 1/2, 1/4, 1/8, 1/16, 1/32 respectively. Which one
of the following is the Huffman code for the letters a, b, c, d, e respectively?

(a) 11, 10, 011, 010, 001 (b) 0, 10, 110, 1110, 1111
(c) 1, 10, 01, 001, 0001 (d) 110, 100, 010, 000, 001

3. Suppose the letters a, b, c, d, e have probabilities 1/2, 1/4, 1/8, 1/16, 1/32 respectively. What is
the average number of bits required per message if Huffman code is used for encoding a, b, c, d
& e?

(a) 3 (b) 3.75


(c) 1.75 (d) 2.75

4. A file contains the following characters and their corresponding frequencies as shown below:
a: 45, b: 13, c: 12, d: 16, e: 9, f: 5

If we use Huffman coding for data comparisons, the average length will be:

(a) 2.24 (b) 2.48


(c) 1.24 (d) 1.48

5. Total running time of Huffman coding is


(Hint: Consider using Minheap)

1
(a) O(n2) (b) O(n log n)
(c) O(n2 log n) (d) O(n3)

6. The tree shown below is a Huffman code tree for the letters a, b, c, d, e & f. What would be
the encoding of the string edaa?

(a) 011011100000 (b) 011101100000


(c) 011101110000 (d) 011011000000

7. Given a Huffman code tree for the letters A, B, C, D & E. What is the last character in the
string encoded by
01110101110110

(a) A (b) B
(c) C (d) D

8. Which of the following is True about Huffman’s Coding?

2
(i) Huffman code is a data compression, encoding technique that follows greedy approach
(ii) An optimal code is always represented by a full binary tree

(a) Only (i) (b) Only (ii)


(c) Both (i) & (ii) (d) Neither (i) nor (ii)

9. What would be the optimal Huffman code for the string “abbbce” for the given set of
frequencies, based on the first 8 Fibonacci numbers?

(a) 111110000011111011111111110
(b) 100000111100001110000011111
(c) 111111100011111000111111110
(d) 100000111000011110010011111

10. Consider a set of 4 messages (M1 – M4) whose frequency of occurrences in the text is as
given:
(0.37, 0.51, 0.05, 0.07)

Using frequency dependent Huffman Coding the codes of the messages M2 and M3 respectively.

(a) 0, 110 (b) 0, 011


(c) 1, 000 (d) 1, 001

You might also like