CS 205 Quiz #8A Nov 20, 2012
NAME: ___________________________SOLUTIONS_____________________________________
RUID:___________________________________________________________________________
Electronic Devices are not permitted during the quiz. These include but are not restricted to calculators, computers and cell phones. No communication between students or anyone outside of class is permitted during the quiz. Textbooks, notes and any other written materials are not permitted during the quiz.
DO NOT OPEN UNTIL INSTRUCTED TO DO SO
1. For each of the following trees, write True if it is a binary search tree where items are maintained in alphabetical order. Otherwise, write False. B cannot appear left of A because B>A ____False____ a) Several other problems exist
____False____ b)
B cannot appear left of A because B>A Several other problems exist
____True____ c)
____True____ d)
2. For each of the following codes, write True if it is a prefix code. Otherwise, write False.
____True________ a)
a: 11, e: 00, t: 10, s: 01
____False_______ b)
a: 0, e: 1, t: 01, s: 001
t starts with as bit string. Thus, ambiguity will arise within any transmitted messages
____True________ c)
a: 101, e: 11, t: 001, s: 011, n: 010
____True________ d)
a: 010, e: 11, t: 011, s: 1011, n: 1001, i: 10101
3. For each of the following codes, compute the average number of bits to encode a single character if the character frequencies are as shown. Additionally, specify whether or not the code is a Huffman code (write True if it is a Huffman Coding, otherwise write False). a) code: frequencies: a: 10, b: 11
a: 0.1,
b: 0.9
Average Bits: _________2__________
Huffman Code: _____False_______
Average bits = 0.1 * 2 + 0.9 * 2 = 2 Not a Huffman code because too many bits are used. a Huffman code. [a:0 b:1] would be
b)
code: frequencies:
a:
10,
b:
11,
c:
a: 0.2,
b: 0.3,
c: 0.5
Average Bits: ________1.5_________
Huffman Code: _____True_______
Average bits = 0.2 * 2 + 0.3 * 2 + 0.5 * 1 = 1.5
c)
code: frequencies:
a: 110000, a: 0.1,
b:
01,
c: 001 c: 0.4
b: 0.5,
Average Bits: ________2.8__________
Huffman Code: _____False______
Average bits = 0.1 * 6 + 0.5 * 2 + 0.4 * 3 = 2.8 Not a Huffman code because too many bits are used. would be a Huffman code. [a:00 b:1 c:01]
4. Consider the following tree rooted at node a.
For each of the blanks below, select the correct visitation order of vertices for the specified type of traversal. A) a, b, c, d, e, f, g, h C) h, g, f, e, d, c, b, a E) a, b, c, d, e, f, g, h G) h, g, f, e, d, c, b, a I) c, b, d, a, f, g, h, e K) h, g, e, f, a, d, b, c M) c, d, b, f, g, h, e, a O) h, g, f, e, d, c, b, a B) a, b, e, c, d, f, g, h D) a, e, b, f, d, c, h, g F) h, g, f, d, c, e, b, a H) g, h, c, d, f, b, e, a J) c, d, g, h, b, f, a, e L) c, d, b, g, h, f, e, a N) c, b, d, a, e, g, f, h P) h, f, g, e, a, d, b, c
Q) That type of traversal is impossible for this tree R) None of the above answers is correct
______A______ i) Preorder Traversal
______N______ ii) Inorder Traversal
______L______ iii) Postorder Traversal
5. Compute the value of each of the following expressions assuming each is in prefix, infix or postfix notation as indicated. (As in the book, indicates exponentiation.) If the value cannot be computed due to lack of operators or lack of operands, write Impossible.
______3______ a) Prefix: + - * 2 3 5 / 2 3 4 From pg. 781, Section 11.3:
______5______ b) Prefix: - * / 15 - 7 + 1 1 3 + 2 + 1 1 From http://en.wikipedia.org/wiki/Polish_notation: - * / 15 - 7 + 1 1 3 + 2 + 1 1 = - * / 15 - 7 2 3 + 2 + 1 1 = - * / 15 5 3 + 2 + 1 1 = - * 3 3 + 2 + 1 1 = 9 + 2 + 1 1 = 9 + 2 2 = 9 4 = 5
_____17______ c) Infix: ((3 + 1) (4 2)) + ((7 4)/3)
_____14______ d) Infix: 5 + ((2 + 7) * ((5 3) 0))
_____4_______ e) Postfix: 7 2 3 * - 4 9 3 / + From pg. 781, Section 11.3:
_____40______ f) Postfix: 9 3 / 5 + 7 2 - * (9 3 /) 5 + 7 2 - * = (3 5 +) 7 2 - * = 8 (7 2 -) * = (8 5 *) = 40
