首页 > > 详细

辅导COMP2119调试数据结构

THE UNIVERSITY OF HONG KONG 
FACULTY OF ENGINEERING 
DEPARTMENT OF COMPUTER SCIENCE 
COMP2119 Introduction to Data Structures and Algorithms 
Date: 16 Dec, 2019 Time: 9:30am - 12:30pm 
Write Your University Number here: ___________ _ 
Please read the following before you begin. 
1. Only approved calculators as announced by the Examinations Secretary can be used in this 
examination. It is your responsibility to ensure that your calculator operates satisfactorily, 
and you must record the name and type of the calculator used in the first page of your 
answer script, or here: 
2. You are advised to spend around 5 minutes to go through all the questions before you begin 
writing. Allocate the time for each part of the question carefully. 
3. If you have a printer or plan to annotate the given PDF file, you may write your answer in 
the designated space. Alternatively, if you are going to first write your answer on blank pieces 
of paper, the designated space will give you an idea of the length of the solution. 
4. Attempt ALL questions. The full mark for the exam is 100 points. 
For marking use: 
Question 1 
Question 2 
Question 3 
Question 4 
Question 5 
Page 1 of 13 
1 Asymptotic Notation (20 points) 
( a) (12 pt) Solve the following recurrence relations and give the simplest expression using Big-Theta 
notation. You do not need to give a full proof. 
(i) T(n) = T(lfoJ) + logn, T(O) = T(l) = 1. 
(ii) T(n) = T(n - 3) + n2 , T(O) = T(l) = T(2) = 1. 
(iii) T(n) = T(lfoJ) + 1, T(l) = 1. 
(iv) T(n) =T(liJ)+T(liJ)+T(l�j)+n, T(O) =0. 
Page 2 of 13 
(b) (8 pt) For each of the following statements, state whether it is true or false. 
(i) n2 = O(n). 
(iii) n logn = 0(1). 
Page 3 of 13 
2 Dictionary Abstract Datatype (15 points) 
Recall that the dictionary abstract data type stores a collection of keys, and supports the operations 
insert, delete, and search. If the keys are totally ordered, then it can also support FindMin and 
FindMax. Each key can be stored using 0(1) space. 
In each of the following scenarios, describe briefly how the specifications can be achieved, or explain 
why it is not possible. 
(a) (3 pt) Suppose all the elements are given at the beginning, and there is no insertion or deletion 
afterwards. Only the search operation will be used later, and a good guarantee on the worst 
case search time is required. 
(b) ( 3 pt) Elements will be inserted and deleted frequently. The average running time for insert, 
delete and search is O ( 1). 
(c) (3 pt) All operations insert, delete and search are used frequently. A guarantee on the worst 
case running time is needed. 
Page 4 of 13 
(d) (3 pt) Insertions will be done frequently. However, only FindMin (i.e. returning the element 
with minimum key) and DeleteMin (i.e., deleting the element with minimum key) are needed. 
Moreover, only average 0(1) time is needed for each operation. 
(e) (3 pt) Each key has value in {1,2, . . . ,n}. Each insertion or deletion has worst-case 0(1) 
time. Moreover, FindRange[a .. b] needs to return all elements whose keys are in [a .. b], where 
the running time is proportional to the number of elements returned. 
Page 5 of 13 
3 Binary Search Tree (15 points) 
(a) (2 pt) What is the property that needs to be satisfied by a binary search tree? 
(b) (2 pt) In addition to being a binary search tree, what property needs to be maintained for an 
AVL tree? 
(c) (6 pt) Suppose in a binary tree with n nodes, at every node, the difference of heights of the left 
and the right sub-tree is at most b, where b is some parameter that is at least 1. Prove that 
the height of the tree is at most O(blogn). 
Page 6 of 13 
( d) ( 5 pt) Recall that in a binary search tree, each node is defined as follows. 
struct node { 
int key; 
node *left; 
node *right; 
node *parent; 
Write a procedure in a C-like language that takes a pointer to the root of a binary tree, and 
returns true if and only if it is a binary search tree that also satisfies the AVL property; 
otherwise, it returns false. 
Page 7 of 13 
4 Sorting ( 30 points) 
For each of the following scenarios, describe a method (briefly in words) to satisfy the specifications. 
Please provide brief explanation. You may use pseudo code too, if you prefer. 
(a) (6 pt) Suppose the elements are given in an array of length n, where each key is an arbitrary 
number. Only 0(1) extra space should be used, and elements in the array should be rearranged 
into a sorted order. Worst-case running time should be 0( n log n). 
(b) ( 6 pt) Suppose the elements are given in a singly-linked list, where only the pointer to the head 
is available to the algorithm. The algorithm should return the sorted elements in a singly-linked 
list, by restructuring the links of the list without creating or destroying nodes. Moreover, extra 
memory used should be as little as possible. If n is the number of elements in the list, the 
algorithm should run in 0( n log n) time. 
Page 8 of 13 
(c) (6 pt) Suppose you are given a collection of n elements, each of which is an integer in the range 
{l, 2, . . . , n }. Give an algorithm with optimal asymptotic running time that returns the set of 
elements that appears at least once in the collection in sorted order. 
(d) (6 pt) Suppose you are given an array of n elements, where each element is an integer in 
{l, 2, 3, . . . , nk} for some small constant k 2: 2. The task is to sort the elements with asymptotic 
running time strictly better than O(n logn). (You may use extra O(n) space.) 
Page 9 of 13 
(e) (6 pt) Suppose the elements are given in an array of length n, where each key is an arbitrary 
number. However, you are guaranteed that for each element, its initial index position and 
its final index position in sorted order differ by at most B. The value B is known to the 
algorithm. The task is to rearrange the elements in the array into sorted order, with running 
time O(n log B). You may use O(B) extra space. 
(In the next question, we describe a data structure to solve this problem using only 0(1) extra 
space.) 
Page 10 of 13 
5 Shifting Wrapped-Around Heap (20 points) 
Recall that an array H[l. .K] can be used to represent a binary tree, where the children of H[i] are 
H[2i] and H[2i + 1]. For K = 6, below is an example of a min-heap, where the root contains the 
minimum value. 
I �[i] I � I � I � I : I � I � I 
(a) (3 pt) Draw the binary tree represented in the above example. 
(b) In order to solve question 4(e) using only 0(1) extra space, we need to design a heap data 
structure that is "shifting" within some other array A[O .. n -1], where K :S n. We assume that 
the size K of the heap does not change. There are two variables s and r with the following 
invariants. 
• The elements of the heap are stored in A[s .. s + K -1]. 
• The heap elements are "wrapped around" such that the root of the heap is stored at A[r]. 
Study the following example carefully, where the above heap H is stored inside A with s = 2 
and r = 4. 
(3 pt) In terms of i, s, r and K, define an expression h(i) such that the element at H[i] is 
stored at A[h(i)]. In the above example, h(l) = 4 and h(6) = 3. 
Page 11 of 13 
( c) ( 4 pt) Implement the operation ShiftHeap () that is called when s + K < n. The operation 
overwrites the entry A[s + K] with A[s] . To avoid losing data, the operation should return the 
original value of A[s + K] . After calling Shift O to the above example, the result is as follows. 
(d) (4 pt) Suppose the root of the heap A[r] is overwritten with some potentially large value that 
might cause the heap property to be violated. Write an operation FixRoot () to maintain the 
heap property again. (You may use h(i) from above.) 
Page 12 of 13 
(e) (6 pt) Write an algorithm to solve 4(e) using only 0(1) extra space. In addition to the above 
subroutines, you may assume the following subroutines are already defined for you. 
• BuildHeap O: It constructs a heap from elements in A[O .. K -1] and sets s = r = O; the 
running time is O(K), using 0(1) extra space. 
• SortHeap O: It rearranges the elements in A[s .. s + K - 1] into sorted order in time 
O(K log K) using 0(1) extra space. 
 
联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!