I would like it if someone could explain to me these test questions, and help me understand them better, because some are confusing me.
1) Which of the following statements about sorting 5 elements is the strongest statement that is directly implied by the information theoretic lower bound?
(a) 6 comparisons are sufficient
(b) 6 comparisons are necessary and sufficient
(c) 7 comparisons are necessary
(d) 7 comparisons are sufficient
(e) 7 comparisons are necessary and sufficient
2) 1000 random integers are generated randomly with a uniform distribution over the range 1
to 1000 inclusive. Which of the following would indicate a poor generator?
(a) the average of the numbers is about 499
(b) each number appears exactly once
(c) no four consecutive numbers are all even
(d) two of the above
(e) all of (a), (b), and (c)
3) Which of the following must be true about file compression in general?
(a) All files can be compressed
(b) For any file, there must be some codes that are longer than others
(c) The code must be a prefix code
(d) All of the above
(e) none
4) Which of the following characterizes a Huffman coding tree?
(a) all items are stored at the leaves
(b) no nodes have one child
(c) the tree is balanced
(d) a and b only
(e) all a,b, and c
5) Which of the following is a valid prefix code for a file containing only the characters a,b, c, and d?
a) a=1,b=0,c=01,d=10
b)a=10,b=01,c=00,d=11
c)a=1,b=01,c=101,d=0001
d)a=1,b=10,c=100,d=1000
e) All are valid
6) Which one is false for Huffman coding?
a) Huffman coding results in full tree
b) Nodes at greater depth in the tree have larger code
c) Huffman's algorithm constructs optimal prefix code
d) For a file containing only k characters, Huffman coding can result in a code of length k
e) all above are true
7) When the edge (u,v) is added to a directed graph which of the following does not occur?
a) u is added to the dictionary if it did not exist
b) v is added to the dictionary if it did not exist
c) v is added to u's adjacency list
d) u is added to v's adjacency list
e) all the above occur
My answers were B, A, D, D, D, D, E respectively, but these were wrong, and I would like for someone to explain why. Thank you.
