代做Data Structures- 这是一个数据结构方面的理论类型的代写
CIS 313 Intermediate Data Structures
Final Examination
- This is an open text and open notes exam.
- Write your answers on your own paper. The instructor will have blank paper in case you have none.
- Consider the use of lemma 8.4 of the text (p 199) to sortnnumbers ofbbits each. Suppose we chooseb= lgnlg lgn.
(a) What is the largest integer that can be expressed (in unsigned binary) usingbbits?
(b) Ifris chosen to be lgn, how long doesRadixSorttake, according to the lemma?
(c) How long does it take ifr= lg lgnis chosen instead?
(d) Which choice ofris faster?
[10 points]
- SupposeAis an array ofnintegers, and consider the following piece of code that constructs a binary search tree fromA:
buildBST(A)
BST T
for i = 1 to n
T.insert(A[i])
return T
LetCbe the total number of comparisons made bybuildBST, and letIbe the internal path
length (p 1180) of the treeTreturned bybuildBST. CompareCandI. IsCbigger thanI,
smaller, unrelated? Justify your answer. [10 points]
- Put the following values into an initially empty B-tree of different parameters
15 , 6 , 12 , 30 , 22 , 17 , 10 , 5 , 9 , 14 , 23 , 1 , 17 , 29 , 18 , 24 , 7 , 26 , 35 , 33 , 27
(a) parametert= 3, which will have at least 3 children (at least 2 keys) per node and at
most 6 children (at most 5 keys).
(b) parametert= 4
[14 points]
- Start with the Fibonacci heap of figure 1 at the end of the exam. This is a min heap – it happens to consist of just one tree. Marked nodes are circled.
(a) Decrease 35 to 29.
(b) Then decrease 22 to 13.
(c) And then decrease 49 to 24.
(d) Insert 21, 22, 23
(e) Perform an extractMin.
[14 points]
- Regarding red-black trees
(a) From the RB tree of figure 2 (dotted lines mean red), delete 30.
(b) Again from the RB tree of figure 2 (the original one, before part (a)), delete 1.
[12 points]
- Suppose you have an arraySof sizen, where each element of the array represents a vote for a person. A voteS[i] is represented by the SSN of the candidate (so it can be a very large number). We do not know the number of candidates. A person wins if they receive a majority(at leastdn+1 2 e) of the votes. Give an efficient procedure to determine if there is a winner (and, if so, who). How fast is your method? [10 points]
Total:70 points
Figure 1: Fibonacci heap for question 4
- Figure 2: red-black tree for question