Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE214 COMPUTER SCIENCE II

SAMPLE MIDTERM EXAM  II

1.1 Which of the following is a common property among all balanced binary search trees of n nodes?

(a) Each node can be colored as red or black.

(b) All leaves have the same depth.

(c) The depth of the tree is log₂ (n+1) – 1.

(d) The depth of the tree is O(log₂ n).

(e) none of these answers

1.2 Which of the following is a common property among B-Trees, 2-3-4 trees, and full binary trees of n

nodes?

(a) More than one data value can be stored in each node.

(b) All leaves have the same depth.

(c) The depth of the tree is log₂ (n+1) – 1.

(d) The depth of the tree is O(log₂ n).

(e) none of these answers

1.3 What is the depth of the shortest binary tree that contains 11 nodes?

(a) 2          (b) 3                    (c) 4                (d) 5           (e) none of these answers

1.4 How many distinct binary search trees can be built with three numbers 51, 23, and 45?

(a) 1                   (b) 3              (c) 5                (d) 6                (e) none of these answers

1.5 Can a complete binary search tree (binary search tree that is also a complete binary tree) also be

a heap?

(a) always          (b) never              (c) some cases   (d) most cases  (e) none of these answers

1.6 How many distinct complete binary search trees can be built with four numbers 10, 20, 30, and 40?

(a) 1                   (b) 4              (c) 5                (d) 14                (e) none of these answers

1.7 A binary tree has n null references stored in it. What is the number of nodes in that tree?

(a) n - 1          (b) n + 1  (c) 2ⁿ (d) log(n)          (e) none of these answers

1.10 A hash table is created to store integer keys using a hash function h(k) = k mod 19. The current state of the hash table is shown below. All keys were inserted without any collisions.

At what position will the key 29 be stored in the hash table using h(k) above if linear probing is used to resolve collisions?

(a)  6 (b) 10      (c) 12 (d) 17 (e) none of these answers

2. For each of the following algorithms performed on a collection of n integers, write down its

worst-case order of complexity as a function of n in simplified Big O notation. Assume that

the most efficient data structure and algorithm are used.

3. A heap is stored using an array as follows:

Show the contents of the array after 85 is inserted into the heap.

4. USE THE FOLLOWING BINARY SEARCH TREE FOR PARTS (a) – (d):

(a) Write the inorder traversal of the binary tree above. _____________________________

(b) Write the preorder traversal of the binary tree above. _____________________________

(c) Write the postorder traversal of the binary tree above. _____________________________

(d) Draw the tree after the node containing M is removed.

USE THE FOLLOWING INFORMATION TO ANSWER PROBLEMS 5.1-5.3:

The following code shows the incomplete implementation of insert operation in a Heap class using recursion. The constructor for this class creates a data array and sets the heapSize to zero.

public void insert(int item) throws Exception

{

if (isFull()) throw new Exception();

heapSize++;

data[heapSize-1] = item;

fixHeap(heapSize-1);

}

private void fixHeap(int n)

{

int position, temp;

if ( a )

{

position = b ;

if (data[position] < data[n]) {

temp = data[n];

data[n] = data[position];

data[position] = temp;

fixHeap( c );

}

else return;

}

}

public boolean isFull()

{

return (heapSize == data.length);

}

5.1 What is the correct expression for a?

(a) (n*2)+1 < heapSize (b) n >= 0            (c) n > 0

(d) n > 1                        (e) none of these answers

5.2 What is the correct expression for b?

(a) (n * 2)+1              (b) (n * 2)+2            (c) (n + 1)/2

(d) (n – 1)/2                             (e) none of these answers

5.3 What is the correct expression for c?

(a) ( n * 2) + 1             (b)  n / 2                        (c)  n – 1

(d) (n – 1)/2                            (e) none of these answers

USE THE FOLLOWING INFORMATION TO ANSWER PROBLEMS 6.1-6.3:

The following code shows the incomplete implementation of two methods of a priority queue class. To dequeue an element with O(1) complexity, the queue is maintained sorted in decreasing order at all times. The elements are removed as usual from the front of the queue, but instead of inserting (enqueueing) to the rear of the queue, a new element is inserted in a sorted array (no sorting algorithm is used). Assume that the size of the data array is unlimited.

public int dequeue() throws Exception {

int answer;

if (front < 0) throw new Exception;

answer = data[front];

if (front == rear){

front = -1; rear = -1;

}else front++;

return(answer);

}

public static void enqueue(int item) {

int i, position;

if (rear == -1) {

front = 0;  rear = 0; data[rear] = item;

return;

}

position = front;

for (i=front; i <= rear; i++) {

if ( a )

position++;

else

break;

}

for ( b ; i > position; i--) {

data[i] = data[i-1];

}

c ;

rear++;

}

6.1 What is the correct expression for a?

(a) item >  data[i] (b) item < data[i] (c) item <= data[i] (d) item >= data[i] (e) none of these answers

6.2 What is the correct expression for b?

(a) i=front + 1           (b) i=rear + 1 (c)  i=rear

(d) i=front                (e) none of these answers

6.3 What is the correct expression for c?

(a) data[rear]=item (b) data[front]=item  (c) data[rear++]=item

(d) data[position]=item  (e) none of these answers

7. USE THE FOLLOWING METHOD TO ANSWER  PARTS (a)-(c):

public static boolean mystery(int[] data,int k,int s,int n) {

int p;

if (n > 0)

{

p = s + (n/2);

System.out.println("s="+s+" n="+n+" p="+p);

if (k == data[p]) return true;

if (k < data[p])

return mystery(data,k,s,n/2);

else

return mystery(data,k,p+1,(n-1)/2); // part c

}

return false;

}

(a) Assuming that an int is 2 bytes and a memory reference is 4 bytes, how many bytes are          required for one activation record for mystery?  Show your work.

(b) What is the result of mystery and its output after it is called with the following parameters:

data={10,  12, 34,  45, 60},  k= 88, s=0, n = 5

(c) Remove the second tail recursion in mystery (i.e. replace it with non-recursive statements).

public static boolean mystery2(int[] data,int k,int s,int n){

int p;

_____________________________

{

p = s + (n/2);

System.out.println("s="+s+" n="+n+" p="+p);

if (k == data[p]) return true;

if (k < data[p])

return mystery2(data,k,s,n/2);

else

____________________________

____________________________

}

return false;

}

8. Let the class BTNode represent a node of a binary tree that stores an int, as shown below:

public class BTNode {

private int data;

private BTNode left;

private BTNode right;

// usual BTNode methods (getData, getLeft, getRight,
// setData, setLeft, setRight, constructor)

// Other methods

}
Write Java code for the following recursive BTNode method.

Public void childCount()

For each node in the binary tree rooted at this node, set the data field to the total number of nodes in its left and right subtrees. Following is an example of a tree after childCount is called. As you notice, all the leaves are set to zero, and the root contains the number of nodes in the tree minus one (root is not counted).