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.
