CSIS-10BFINAL REVIEW SOLUTIONS Open Notes & Book
CSIS-10BFINAL REVIEW SOLUTIONS Open Notes & Book
1.Draw the (Nyhoff template, linked) stack from chapter 12 that results from
Stack<int> s;int x;
s.push(23);
s.push(12);
x=s.top();
s.pop();
s.push(18);
s.push(20); /
what is stored in x? 12
2.Draw the (Nyhoff template, linked) queue that results from
Queue<int> q;int x;
for (x=5; x<8; x++){
q.enqueue(x);
q.enqueue(x+1);
q.dequeue( ); } /
what is stored in x? 8
3. Consider the following function:
void test_b(int n)
{
if (n>0)
test_b(n-2);
cout < n < " ";
}
What is printed by the call test_b(4)? Answer: 0 2 4
test(4) calls test(2) then print 4
| ^
V |
test(2) calls test(0) then print 2
| ^
V |
test(0) print 0return (base case)
For 4-6 Consider the following function:
void star(int n)
{
if (n>0) {
cout<"*";
star(n-1);
}
else cout <endl;
}
4. What value of n is considered the "base case"?
A. 0 C. n-1
B. anything larger than 0 D. this function does not have a base case
5. How many recursive calls (not counting the first one below) are made when the statement:
star(5); is executed? 5
Show the output produced by star (5); Answer: *****
6. The following function produces a triangle using recursion, but it then scrolls off the screen and you get "runtime stack overflow" error. Please fix the function so that triangle is still recursive and the statement: triangle (3); produces
***
**
*
void triangle (int n)
{
star(n);
if (n>0)
triangle(n-1);
}
7. Why do recursive functions for lists and trees need recursive partners?
A. To allow you to change a pointer
B. So the primary function can call the recursive partner with an initial argument
C. To provide an inheritance relationship
D. One function performs the recursion, the other defines an operator
8. What is the significance of passing a pointer to a function by reference?
A. When the function changes p, the change WILL affect the actual pointer argument.
B. When the function changes p, the change will NOT affect the actual pointer argument.
C. When the function changes *p, the change WILL affect the the object pointed to.
D. When the function changes *p, the change will NOT affect the the object pointed to.
E. The pointer points to a large object.
9. Here is a small binary tree:
14
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 40
Write the order of the nodes visited in:
A. An in-order traversal: 1 2 3 14 7 10 11 40 30
B. A pre-order traversal: 14 2 1 3 11 10 7 30 40
C. A post-order traversal: 1 3 2 7 10 40 30 11 14
10. Draw the Binary Search Tree that results when you insert the following items in the following order (words are compared alphabetically as in the dictionary):
wash, fold, dry, clean, up, down, left, right
11. What is the maximum number of nodes that must be examined to find an element in your tree above?
5
12. Redraw the tree assuming elements are inserted as follows:
fold, down, up, dry, wash, clean, right, left
13.Which tree gives a better search performance? The Second One
14. Draw the heap that results from inserting the following numbers:
20, 33, 2, 49, 76, 17, 9, 14, 27
15. Redraw the following heap after three removal operations:
OriginalFirst removal SecondThird
44 2513 11
/ \ / \ / \ / \
11 25 11 13 11 7 10 7
/ \ / \ / \ / \ / \ / \ / \ /
10 3 1 13 10 3 1 4 10 3 1 4 4 3 1
/ \ /
7 4 7
16. Draw a hash table of size 10 using the hash function k % 10 and linear probing to insert the keys 5, 29, 20, 11, 0, 18, 44, 27, 15, 19
0 / 201 / 11
2 / 0
3 / 19
4 / 44
5 / 5
6 / 15
7 / 27
8 / 18
9 / 29
17. determine the number of items checked in order to retrieve the following keys (including the item itself):
51 check
152 checks
19 5 checks
18. Classify (using Big-O) the order of these functions of N:
a)100N2 ___ O(N2)_____
b)0.01N3 ___ O(N3)___
c) Which has the larger order, a or b ? ____b____
19. Write down the order (Big-O) of how these programs' execution time grows with increasing N.
a) for (i = 0; i < 10; i++) ___O(1)_
sum = sum + N;
b) sum=0;
k=N;
while (k>1) __O(log2N)______
{sum=sum+k;
k=k/2;
}
20. For the following code, if the List constructor displays CREATE, the copy constructor displays COPY, the assignment operator displays ASSIGN and the destructor displays DESTROY, what sequence of messages will the following code display:
void Print(List <int> L){ }
void main( )
{
List<int> data, data2;
data.insert(5);
data2=data;
Print(data2);
List<int> data3(data2);
} / ANSWER:
CREATE
CREATE
ASSIGN
COPY
DESTROY
COPY
DESTROY
DESTROY
DESTROY
21. Draw the list "big" that results from the following:
List<List<int> big;List<int> one, two, three;
one.insert(0, 4);
one.insert(0, 5);
two=one;
three=one;
three.insert(0, 6);
two.erase(0);
big.insert(0, three);
big.insert(1, two);
big.insert(2, one); /
22. Now modify the list big to add a 7 at very last node in the very last List in big.
one=big.retrieve(2);
one.insert(2, 7);
big.replace(2, one);
23. For the Nyhoff BST class in Chapter 12, write a pair of functions height() and heightAux() to determine the height of the tree. Use the following function headers. (Remember the height of a null subtree is 0, see p657):
int BST<DataType>::height()
{
return heightAux(myRoot);
}
int BST<DataType>::heightAux(BST<DataType>::BinNodePointer subTreeRoot)
{
if (subTreeRoot==0)
return 0;
else
{
int left=heightAux(subTreeRoot->left);
int right=heightAux(subTreeRoot->right);
if (left>right)
return 1 + left;
else
return 1 + right;
}
}
24. Draw the following array after it has been processed by heapify algorithm
(see p735-753)
before:
8 / 12 / 5 / 9 / 17 / 2 / 11after
17 / 12 / 11 / 9 / 8 / 2 / 51