Data Structures (CIS22 RS)

Data Structures (CIS22 RS)

Test 3

1. This question refers to big-O notation.

1.1What is the time complexity of the following function in terms of n?

int sum(int a[], int n){

if (n==0) return 0;

return a[n-1]+sum(a,n-1);

}

1.2What is the worst case and best case time complexities of the function call bsearch(a,n,x) in terms of n? Discuss what the arrays look like in the worst and best situations, respectively.

int bsearch(int a[], int n, int x){

return bsearch1(a,0,n-1,x);

}

int bsearch1(int a[], int lb, int ub,int x){

int m;

if (lb > ub) return –1;

m = (lb + ub)/2;

if (x == a[m]) return m;

else if (x<a[m]) return bsearch1(a,lb,m-1,x);

else return bsearch1(a,m+1,ub,x);

}

1.3What is T(n) in polynomial form if

T(1) = 1;

T(n) = n + T(n-1)?

2. The following shows part of the definition of the merge function that merges two sorted sequences a[lb],...,a[m] and a[m+1],...,a[ub], and stores the resulting sorted sequence in a from lb to ub. A global array named temp is used. Fill in the blank box with appropriate statements to complete the function definition.

void merge(int a[], int lb, int m, int ub){

int s = lb;

int s1 = lb;

int s2 = m+1;

while (s1<=m) temp[s++] = a[s1++];

while (s2<=ub) temp[s++] = a[s2++];

for (i=lb;i<=ub;i++) a[i] = temp[i]; /* copy the sequence from temp to a */

}

3. The two basic operations used in heap sort are called bubbleUp and bubbleDown. The bubbleUp operation is used when a new element is added into the heap. It compares the element with its parent and switches them if the parent is smaller. This step is repeated until the parent is bigger than the element. The bubbleDown operation is used to reorganize the heap after the root is removed from the heap and the last element in the heap is moved to the root. It compares the element with its children and

switches the element with the bigger child if there is a child that is bigger than the element. This step is repeated until the no child is bigger than the element. The following picture illustrates the bubbleDown operation.

bubbleDown

3.1 Implement the function bubbleUp(a,i) wherea is the array representation*) of theheap and i is the index of the node to be bubbled up.

void bubbleUp(int a[], int i)

3.2Implement the function bubbleDown(a, i,n) where a is the array representation of the heap, n is the number of elements in the heap, and i is the index of the node to be bubbled down.

void bubbleDown(int a[], int i, int n)

*)In array representation of a complete binary tree, the root is stored in position 0; and for each node that is stored in position i, its left child is stored in position 2*i+1 and its right child is stored in position 2*i+2.