1. INSERTION SORT: Here is a list of numbers, partly sorted.
The vertical bar | marks the end of the sorted region.
Insert the next value, and show the resulting list.
-2 1 7 11 14 | 6 4 18
2. Here is a list of numbers, initially not sorted.
Run the first complete pass of BUBBLE SORT, and show the resulting list.
11 4 28 2 23 42 8 12
3. Here is a list of numbers, initially not sorted.
Run the first pass of SELECTION SORT (select maximum); show the resulting list.
11 4 28 2 23 42 8 12
4. What is the asymptotic (big-0) cost of each of the following operations, as a function of n, the size of the array?
a) Bubble sort with input initially reverse-sorted:
b) Insertion sort with input initially sorted:
c) Insertion sort with input initially reverse-sorted:
d) Merge sort with input initially sorted:
e) Merge sort with input initially reverse-sorted:
5. Here is a Binary Search Tree (BST).
Insert 13 into it, and draw the resulting tree beside it. see image.
6. Here is the same BInary Search Tree (BST).
Delete the 29 node. Draw the resulting tree beside it. see image.
7. Here is the same Binary Search Tree (BST).
Delete the root node. Draw the resulting tree beside it. see image.
8. Here is a binary search tree (not a BST): see image.
a) List the nodes as they are visited by preorder traversal.
b) List the nodes as they are visited by inorder traversal.
c) List the nodes as they are visited by postorder traversal.
9. Here is sorting algorithm that uses a BST.
The traverse() function is a generator that yields each of the values in the BST, as it performs inorder traversal.
def tree sort( a_list ):
tree = BST ()
for x in a_list:
tree.insert( x )
i = 0
for x in tree.traverse():
a_list[i] = x
i += 1
What is the asymptotic cost of this algorithm, in the worst case? Explain briefly.
10. Draw expression trees (i.e. parse trees) for the following infix expressions.
Remember tha operators done later occur higher in the tree.
a) num = 6 / (foo + 15) * (9 - baz)
b) 3 - 6 + 9 - 12
11. Consider this postfix expression:
4 -1 - 9 6 3 - - *
If this expression is evaluated using this stack-based algorithm:
if token is an operand:
push the token
if token is an operator:
pop two values
apply the operator
push the result
a) How many values will be on the stack, at most (how big does the stack get)?
b) what is the value of the expression?
12) Consider a linked list with "dummy" sentinel nodes at head and tail. Here is the list initially:
Head -> 3 -> 2 -> Tail
Draw the list, after all these operations are completed, in this order:
add_head ( 3 )
add_tail ( 4 )
add_tail ( 6 )
add_head ( 5 )
13. You are given an implementation of a stack, with push(), pop(), and top() methods. What does this code print?
s = Stack()
s.push( 3 )
s.push( 5 )
print( s.top() ) #look closely at this one
print( s.pop() )
s.push( 1 )
s.push( 9 )
print( s.pop() )
print( s.pop() )
s.push( 2 )
print( s.top() )
14. Consider this code, which partially implements a binary tree: