Scribd
Upload
57 views4 pages

1501midterm Practice Questions KEY

Uploaded by

Benjamin Bravo
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
57 views4 pages

1501midterm Practice Questions KEY

Uploaded by

Benjamin Bravo
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/ 4

1501 Midterm Practice Questions

KEY

1/4
1. ( 12 points ) Consider using Huffman encoding to compress the following string:
“DONTTELLMEILLTELLYOU”.
Show the following:

• The Huffman tree


• The codeword/character pairs

State any assumptions that you make.

ANSWER:

20

12

4 4
6

2 2 2

T E L O D N M I Y U
3 3 6 2 1 1 1 1 1 1

Figure 1: An example solution Huffman tree (others possible)

Codeword/character pairs for this Huffman Tree:


000 T
001 E
01 L
100 O
1010 D
1011 N
1100 M
1101 I
1110 Y
1111 U

2/4
2. ( 14 points ) Consider the alphabet {A, B, E, N}.
Construct a de la Briandais trie over this alphabet containing the following words:

BEE, NAB, BEAN, BAN, BEEN, BAE

Be sure to make the details clear, such as how complete keys are differentiated from prefixes,
and how references are organized in the node.

ANSWER:
Either of these two would be a valid solution:
value

null
next

B N
value

value
null null
next

next
E A A
value

value

value
null null null
next

next

next
E A N E B
value

value

value

value

value

True null True True True


next

next

next

next

next

N N
value

value

True True
next

next

Figure 2: A non-null value terminated DLB

3/4
B N

E A A

E A N E B

^ N N ^ ^ ^

^ ^

Figure 3: A DLB using a termination character

3. ( 16 points ) Consider the array representation of a min heap.

i. Show the state of an array-backed min heap after inserting the following numbers in the
order shown.
14, 5, 7, 3, 15, 1

ii. Show the state of the array-backed heap after performing one removal.

iii. Show the state of the array-backed heap after performing a second removal.

ANSWER:
Operation
Inserts 1 5 3 14 15 7
Remove (1) 3 5 7 14 15
Remove (3) 5 14 7 15

4/4

You might also like