TCSS 342 – Data Structures
Midterm exam practice
Short-answer questions
1. What is an invariant?
2. What is the list invariant?
3. What is the ordered list invariant?
4. What is the stack invariant?
5. What is the queue invariant?
6. Give a closed form expression of the summation:
∑
=1
7. Give a simplified expression of the summation:
∑2
=1
8. What is the sum of the numbers from 1 to 1000?
9. What is the sum of the numbers from 9 to 42?
10. The script of "Romeo and Juliet" by William Shakespeare is an example of an abstraction.
What is a corresponding concrete?
11. How many basic operations are there on this line of code?
int i = j++;
12. What is the worst-case running time of the Stack push and pop operations?
13. Compare the runtime of get(index) for an ArrayList and a LinkedList.
14. Compare the runtime of add(item) for an ArrayList and a LinkedList.
15. What is the difference between a stack and queue?
16. Describe the methods for accessing elements in a stack.
17. If we are using a binary search on a list of size 1024 what is the worst-case number of
operations we will use to find our target?
18. If we are searching a linked list of items for a specific item that is not in the list, how many
comparisons will we use in the worst case? How many comparisons will we use on
average? How many in the best case? Be exact with your answer.
19. If we are searching a list of items for a specific item we know is in the list, how many
comparisons will we use in the worst case? How many comparisons will we use on
average? Be exact with your answer.
20. If we have a small number of items to sort (less than 100) which sorting procedure would
you recommend using? Give a short reason why.
21. If we have an array of size 1 billion which sorting procedure would you recommend using?
22. If we have a list of items to sort that are almost in order which sorting procedure would
you recommend using? Give a short reason why.
23. You are going to sort a linked list. What sorting procedure would you choose and what is
the run time of your selected procedure?
24. What is the worst-case runtime of bubblesort?
25. What is the best-case runtime of bubblesort?
26. What is the worst-case runtime of insertionsort?
27. What is the worst-case runtime of selectionsort?
28. What is the worst-case runtime of mergesort?
29. What is the worst-case runtime of quicksort?
30. What is the average case runtime of quicksort?
31. How many nodes in a complete binary tree of depth 6 (assume the root has depth 0)?
32. What is the depth of a binary heap with 1337 items in it (assume the root has depth 0)?
33. When is the root node displayed in a post-order traversal of a tree?
34. How does Huffman coding works to encode a message given the frequency of each
character on that message?
35. How does LZW update its string directory when it sees a message = where is
a string already on , is a single character such that is not on , and is the
remaining part of ?
36. What is a priority queue?
37. What is the heap invariant?
38. How many operations (big-O) will it take for a binary heap to remove the root and then
satisfy the heap invariant?
39. What is the worst-case number of operations for a heap insert?
40. What is the worst-case number of operations for searching for the highest-priority
element on a heap?
41. Describe how we can use a heap to sort a list of numbers. What is the worst-case runtime
of your procedure?
42. What is the binary search tree (BST) invariant?
43. How can we use a BST to sort efficiently? What is the worst-case runtime of your
procedure?
44. What is the worst-case number of operations for a naive BST search?
45. What is the worst-case number of operations for a self-balancing (AVL) BST search?
46. What rotation(s) are necessary in an AVL tree if the tree becomes left-left imbalanced
after an insertion?
47. What rotation(s) are necessary in an AVL tree if the tree becomes left-right imbalanced
after an insertion?
48. In an AVL (sub)tree, how many rotations must we do in the worst case if we find an
imbalanced node? How many rotations are needed to restore the balance for the whole
AVL tree?
49. What are the additional invariants a red-black tree must satisfy besides the BST invariant?
50. What is the worst-case number of operations for a red-black tree search?
Long-answer questions
1. Consider the code below that removes duplicate integers from a list of integers. Evaluate
the number of operations taken by this code under the assumption that every
declaration, assignment, check, negation, subtraction, and ArrayList method takes exactly
operations, except method contains which we assume uses linear search and thus takes
× operations where is the size of the ArrayList being searched.
List removeDuplicates(List dups){
0: List newList = new ArrayList<>();
1: while (!dups.isEmpty()){
2: if (!newList.contains(dups.get(dups.size() – 1)) {
3: newList.add(dups.get(dups.size() – 1));
}
4: dups.remove(dups.size() – 1);
}
}
a. For each line state the number of operations taken on that line as a constant or a function
of n and/or where n is the size of the input list dups and is the size of new List during
the current execution of the while loop.
b. For the while loop on line 1-4 state a summation that expresses the runtime of the entire
loop.
c. What is a good guess at an upper bound on the number of operations taken by this code?
(i.e. state () such that the runtime is (())).
2. Consider an environment where only stacks are available but you need a queue. You
decide to implement a queue using two stacks as below.
a. Describe how you would add a new element to your queue.
b. Describe how you would remove an element from your queue if Stack 1 is not empty.
c. Describe how you would remove an element from your queue if Stack 1 is empty.
3. Draw the binary tree that corresponds to these traversals.
Pre-order: [A,B,C,D,E,F,G,H]
In-order: [C,B,E,F,D,G,A,H]
Post-order: [C,F,E,G,D,B,H,A]
4. You have a binary search tree with the values 1,2,3,4,5,6,7,8 but you can’t remember its
shape. All you have is its pre-order traversal:
[6,4,2,1,3, 5, 8,7]
Draw the tree you have lost. (Hint: The in-order traversal of a binary search tree lists the
elements in increasing order.)
5. Draw a minimum-heap by inserting 8 random numbers into an empty heap and then
remove the minimum element until the heap is empty.
6. Compress the phrase "SAVVY SYLVIA SAVORS LOVELY VIALS OF VELVETY SALVIA" using
Huffman compression (don’t forget to include the blank characters).
7. Compress the phrase "SAVVY SYLVIA SAVORS LOVELY VIALS OF VELVETY SALVIA" using
LZW compression (don’t forget to include the blank characters).
8. Select 30 numbers at random from 0-99 and insert them into binary search tree. Draw
the resulting tree after each add for a naive BST. After building your tree delete a leaf
node, a node with one child, and a node with two children. Show the final tree.
9. Select 30 numbers at random from 0-99 and insert them into an AVL tree. Draw the
resulting tree after each add including necessary rotations. After building your tree,
delete a leaf node, a node with one child, and a node with two children (indicate which
nodes are being deleted). Show the final tree.
10. Select 30 numbers at random from 0-99 and insert them into a red-black tree. After
building your tree, delete a leaf node, a node with one child, and a node with two
children(indicate which nodes are being deleted). Show the final tree.