1. Trees
(a) (4) Find a tree diagram, above, that is NOT a binary search tree. Explain why it is not.
(b) (4) Trees 2 and 3 look something like min-heap. One is, one is not. Which one is not?
Explainwhy.
(c) (4) Is tree 4, above, balanced? If not, why not? If so, add one node to make it unbalanced.
(d) (4) Write down the values of the nodes in tree 3, in the order that a breadth-first search
wouldvisit them.
(e) (4) If you start with a binary search tree with 30 elements in it, and delete the minimum
element10 times, the resulting tree will have a bad property. Explain what this property is and
why it will occur.
2. Red-Black Trees
(4) Start with the red-black tree on the right. The root is black, and 21 and 88 are both red. Insert a node
containing 30 and show how the tree changes. Be very clear about the colors of the four nodes at the end of the
process.
(a) (4) After inserting the 30, how many more nodes can
youinsert in this tree without causing a re-balancing
operation? What nodes would you insert?
(b) (4) After inserting the 30, is it possible to force a rebalancing
by adding just one more node? If so, where?
(c) (4) Explain why, in general, an AVL tree or a Red-Black treegives better performance
than a binary search tree.
3. Heaps
The diagram below is a min-heap of integers. Starting with this heap, make the changes below, in
order, using the result from the prior change. Redraw the heap as you work out each change.
Figure 1:
(a) (4) Insert the number 13 into this heap.
(b) (6) Delete the top item on the heap and readjust the rest according to the deletion algorithm.
4. Quicksort.
tree 1
tree 2 tree 3 2
8
11 12
6
5
37
3
17
2
8
11 12
6
5
37
3
2 17
8
11
12
6
5
37
3
17
tree 4
2
8
11
6 12
5
37
3
17
2 4 3 5 6 3 8 29 14 25 19 32 61 21 16 30 38 15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
21 88
45
These questions apply to the version of quicksort that was discussed in class. In that program, two
functions implement the heart of the quicksort algorithm:
void quick(int first, int last);// recursive int partition( int first, int last ); // a
nested loop
(a) (3) The first step in the partition process is to select a pivot element and move it into position.
Do that for the array below. In the space given, rewrite the array with the pivot in place.
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Before: 68 38 91 30 74 25 97 63 23 25 71 49 35 40 29 41
w.Pivot:___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
(b) (6) Using the array with the pivot element in place, simulate one pass of the partition() function
when called thus: split = partition(0, 15). Copy the data onto the blank line below as the
scanners pass over it, showing each swap that takes place. Show the final swap that involves
the pivot.
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
After: ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
(c) (2) What integer result will be returned by partition and stored in split?
(d) (4) What will the arguments be for the two recursive calls on quick()?
5. Expressions
(a) (4) Start with the parse tee on the right. Do a prefixtreewalkon this tree and write down the resulting prefix
expression.
(b) (4) Now do a postfix treewalk and write down the
resultingpostfix expression.
(c) (4) This parse tree is the result of performing a
precedenceparse on an ordinary C arithmetic expression.
What is that expression? Remember, infix expressions
sometimes need parentheses.
y
+
x 2 3
*
=
https://customwriting.s3.amazonaws.com/GH347/eedsaa.pdf?versionId=vVKYsqGWHvbFU5siWhporAqh_gTGlRVU&AWSAccessKeyId=AKIAIDY3BOXYKEAMAEOQ&Expires=1462292948&Signature=FaQF4SSgmJ1R9hNPqicreU%2BW0zs%3D
TAKE ADVANTAGE OF OUR PROMOTIONAL DISCOUNT DISPLAYED ON THE WEBSITE AND GET A DISCOUNT FOR YOUR PAPER NOW!
