Final Exam Practice Problems — CS 112, Boston University

pdf

School

Boston University *

*We aren’t endorsed by this school

Course

112

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by andrewleenyk

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 1/14 Final Exam Practice Problems As we get closer to the exam, solutions will be posted under Other Content on Blackboard. These problems are not comprehensive, so make sure to review all of the relevant materials. 1. Which of the following data structures would be most appropriate for a program that simulates the operation of an airport in order to determine the maximum delays encountered by arriving and departing planes? a. queue b. binary tree c. heap d. stack e. hash table 2. A stack s of integers initially contains the following data from top to bottom: The following code is then executed: After this code has been executed, what are the contents of the stack? a. {8, 10} b. {10, 8} c. {15, 3} d. {10, 8, 6, 3} e. none of the above 3. Suppose that items A, B, C, D and E are pushed, in that order, onto an initially empty stack S. S is then popped four times; as each item is popped off, it is inserted into an initially empty queue. {6, 2, 7, 3} int x = s.pop(); int y = s.pop(); int z = s.pop(); s.push(x + y); int w = s.pop(); s.push(w + z);

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 2/14 If two items are then removed from the queue, what is the next item that will be removed from the queue? a. item A b. item B c. item C d. item D e. item E 4. If the keys in the tree below are printed using a postorder traversal, what will the result be? a. G E F A B C D b. G E A B F C D c. A E B G C F D d. A E B C F D G e. A B E C D F G Questions 5 and 6 involve binary trees whose nodes have the following structure: 5. Consider the following method: G / \ E F / \ / \ A B C D public class Node { public char val; public Node left; public Node right; } public static int mystery(Node root) { if (root != null) { if (root.left == null && root.right == null) { return 0 ; } int sum = mystery(root.left) + mystery(root.right); if (sum == 0 ) { Node temp = root.left; root.left = root.right;

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 3/14 What does this method do to the tree whose root is referred to by the parameter root ? a. swaps the left and right subtrees of the root node b. swaps any two leaf nodes that have the same parent c. swaps the leftmost and rightmost leaves d. replaces the tree with its mirror image e. none of the above 6. Consider the following methods: If root initially points to the root of the following tree: what tree results from the execution of the following statements? root.right = temp; } } return - 1 ; } public static void preorder(Node root, Stack<Character> s) { if (root != null) { s.push(root.val); preorder(root.left, s); preorder(root.right, s); } } public static void postorder(Node root, Stack<Character> s) { if (root != null) { postorder(root.left, s); postorder(root.right, s); root.val = s.pop(); } } A / \ B C / \ / \ D E F G

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 4/14 a. b. c. d. e. 7. If a binary search tree is not allowed to have duplicates, there is more than one way to delete a node in the tree when that node has two children. One way involves choosing a replacement node from the left subtree. If this is done, which node are we looking for? a. the largest node in the subtree b. the smallest node in the subtree c. the root of the left subtree Stack<Character> s = new LLStack<Character>(); preorder(root, s); postorder(root, s); A / \ B C / \ / \ D E F G A / \ C B / \ / \ G F E D G / \ D F / \ / \ A B E C A / \ C B / \ / \ F G D E G / \ F D / \ / \ E C B A

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 5/14 d. the next-to-smallest node in the subtree e. it doesn’t matter – any node in the left subtree will do 8. The binary search tree shown below was constructed by inserting a sequence of items into an empty tree. Which of the following input sequences will not produce this binary search tree? a. 5, 3, 4, 9, 12, 7, 8, 6, 20 b. 5, 9, 3, 7, 6, 8, 4, 12, 20 c. 5, 9, 7, 8, 6, 12, 20, 3, 4 d. 5, 9, 7, 3, 8, 12, 6, 4, 20 e. 5, 9, 3, 6, 7, 8, 4, 12, 20 9. If the keys in the tree below are printed using a preorder traversal, what will the result be? a. 9 4 17 16 12 11 6 b. 9 17 6 4 16 22 12 c. 6 9 17 4 16 22 12 d. 6 17 22 9 4 16 12 e. 6 17 9 4 22 16 12 6 / \ 17 22 / \ / \ 9 4 16 12

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 6/14 10. A binary tree is constructed of nodes that are instances of the following class: Consider the following method: You consult three consultants, and you get the following three opinions about what the method does when passed a reference to the root node of a binary tree: I. It returns the last node visited by an inorder traversal. II. It returns the last node visited by a postorder traversal. III. It returns the last node visited by a level-order traversal. Which of these opinions is correct regardless of the contents of the tree? a. I only b. II only c. III only d. I and III e. II and III 11. Note: We didn’t cover B-trees this semester, so you can ignore this question. Which of the following data structures is most appropriate for situations in which you need to eﬃciently manage key-value pairs that are stored on disk? a. an array b. a linked list c. a binary search tree d. a 2-3 tree e. a B-tree public class Node { public char val; public Node left; public Node right; } public static Node mystery2(Node root) { if (root.right == null) { return root; } else { return mystery2(root.right); } }

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 7/14 12. The following array represents a max-at-top heap: Two remove operations are performed on this heap, and then 20 is inserted. What does the array representation of the heap look like at the end of these operations? a. {34, 25, 18, 16, 12, 20} b. {34, 25, 20, 18, 16, 12} c. {34, 25, 20, 16, 12, 18} d. {20, 16, 18, 2, 12, 5} e. {20, 18, 16, 12, 5, 2} 13. An array of 7 integers is being sorted by the heapsort algorithm. After the initial phase of the algorithm (constructing the heap), which of the following is a possible ordering for the array? a. {85, 78, 45, 51, 53, 47, 49} b. {85, 49, 78, 45, 47, 51, 53} c. {85, 78, 49, 45, 47, 51, 53} d. {45, 85, 78, 53, 51, 49, 47} e. {85, 51, 78, 53, 49, 47, 45} 14. Consider the following hash table: 0 1 2 up 3 4 down 5 right 6 behind The table is being maintained using open addressing with quadratic probing and a hash function that assigns a hash code equal to the number of characters in the key. { 34 , 25 , 18 , 16 , 12 , 5 , 2 }

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 8/14 If we now insert items with keys of "left" and "under" in that order, where will the new items end up? a. "left" in position 0, and "under" in position 1 b. "left" in position 1, and "under" in position 3 c. "left" in position 1, and "under" in position 0 d. "left" in position 1, but overﬂow occurs for "under" e. overﬂow occurs for both "left" and "under" 15. Now consider the following hash table: 0 1 2 up 3 4 down 5 above 6 It is also being maintained using open addressing but with double hashing. The first hash function is the same one as in the previous problem, and the second hash function is based on the first character of the key: The gray cells are ones from which an item has been removed. If we now insert "check" , what is the probe sequence? a. 2, 0 b. 2, 0, 5, 3 c. 5, 0 d. 5, 0, 2, 4, 6, 1 e. none of the above 16. In the previous problem, where would "check" be inserted? h2(key) = key.charAt(0) - 'a'

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 9/14 a. position 6 b. position 3 c. position 0 d. position 1 e. nowhere, because overﬂow occurs 17. With a poorly chosen hash function or a table that is too small, it is possible to have a situation in which the search time in a hash table with n items goes to: a. O ( n ) b. O ( n !) c. O (log n ) d. O ( n ²) e. O (1) 18. A police department wants to maintain a database of up to 1800 license-plate numbers of people who receive frequent tickets so that it can be determined very quickly whether or not a given license plate is in the database. Speed of response is very important; eﬃcient use of memory is also important, but not as important as speed of response. Which of the following data structures would be most appropriate for this task? a. a sorted linked list b. a sorted array with 1800 entries c. a hash table using open addressing with 1800 entries d. a hash table using open addressing with 3600 entries e. a hash table using open addressing with 10000 entries 19. We did not cover this topic, so you can safely skip this problem: A Huffman tree is constructed for a text document containing 5 characters. The character 'e' appears most frequently, and the character 'i' has the next highest frequency. Which of the following could be the Huffman tree for this document?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 10/14 a. I only b. II only c. III only d. either II or III e. none of these 20. The keys in the middle row of a standard keyboard (ASDFGHJKL) are inserted in succession into an initially empty binary search tree. What does the tree look like after this sequence of insertions has been completed? 21. The keys in the middle row of a standard keyboard (ASDFGHJKL) are inserted in succession into an initially empty 2-3 tree. Draw diagrams to illustrate the growth of the tree, showing the tree just before and just after all splits. 22. Write a static method called countOccurrences() that counts the number of times that a specified character appears in a binary tree that has been built using instances of the Node class from questions 5 and 6 above. The method should take two arguments: a. a reference to the root node of the tree b. the value of type char for which you are searching. You should not assume that the tree is binary search tree. 23. The following array is to be sorted using heap sort:

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 11/14 a. What does the array look like after the initial, heap-creation phase of the algorithm? b. What does the array look like after one element has been put into its final position? c. What does the array look like after two elements have been put into their final position? 24. You are given an empty hash table of size 7. The items that you are inserting have integer keys, and the following hash function is used: The following sequence of key-value pairs is to be inserted: Insert these items using each of the following approaches. If overﬂow occurs, say so, and indicate the item that causes the overﬂow. a. open addressing with linear probing b. open addressing with quadratic probing c. open addressing with double hashing and h2(key) = key/7 + 1 (using integer division) d. separate chaining 25. Recall our generic Stack interface: a. Write a static client method numSmaller(Stack<Integer> stack, int val) that takes a stack of integers and an integer val and that returns the number of values in the stack that are smaller than val . After the method returns, the items in the stack { 6 , 17 , 22 , 9 , 4 , 16 , 12 } h(key) = key % 7 (15, 100) (17, 50) (8, 2) (23, 200) (3, 11) (5, 75) public interface Stack <T> { boolean push(T item); T pop(); T peek(); boolean isEmpty(); boolean isFull(); }

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 12/14 should be in the same positions as they were at the beginning of the method. Your method may use either another stack or a queue to assist it. b. Rewrite your method to make it a generic method that works for a stack and a value of any type that implements the Comparable interface. 26. Imagine that we want to adapt insertion sort to work on linked lists of integers that are constructed using instances of the following class: As with the array-based version of the algorithm, we would consider the elements of the list from left to right, and we would insert each element in the correct position with respect to the elements that come before it in the list. However, because we’re dealing with a linked list, the algorithm wouldn’t be able to perform a backwards pass to determine the appropriate location for a given element. Rather, it would perform a forwards pass to find the point of insertion. Write a helper method called insert() that could be used to perform the insertion of a single node. It should take two parameters: a reference called first to the first node in the linked list, and a reference called toInsert to the node that is being inserted (which you may assume is in position 1 or greater in the list). The method should: perform a forwards pass to determine where toInsert should be inserted in the portion of the list from the front of the list to the current position of toInsert make whatever adjustments are needed to put toInsert in the correct position return a reference to the first node in the linked list after the insertion. You may assume that the nodes that come before toInsert in the list are already sorted with respect to each other. For example, consider the following linked list: After executing the following line of code: public class IntNode { public int item; public IntNode next; }

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 13/14 the linked list should look like this: 27. a. When insertion sort is used to sort an array of n elements, both the number of moves and the number of comparisons are proportional to n ² in the worst case. In the version of insertion sort that is adapted for linked lists, one of the two types of operations would have a more eﬃcient growth function. State which type, and explain why. b. What would the overall eﬃciency of the adapted algorithm be in the worst case? In the best case? Use big-O notation, and explain your answers brieﬂy. The remaining questions deal with binary trees that are constructed of nodes that are instances of the following class: 28. The following method uses recursion to search for a key in the binary search tree whose root node is referred to by the parameter root . If it finds the key, it returns a reference to the corresponding data item. If it doesn’t find it, it returns null . first = insert(first, n); public class Node { public int key; public Object data; public Node left; public Node right; } public static Object search(Node root, int key) { if (root == null) { return null; } else if (key == root.key) { return root.data; } else if (key < root.key) { return searchTree(root.left, key); } else { return searchTree(root.right, key); } }

12/17/23, 8:15 PM Final Exam Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/final_practice.html 14/14 Rewrite this method so that it uses iteration instead of recursion. 29. Write a method named mirror() that takes a reference to the root node of a binary tree and creates a new tree (with its own nodes) that is the mirror image of the original tree. The method should return a reference to the root of the new tree. For example: if root is a reference to the root of this tree: then mirror(root) should return a reference to the following tree: 30. What is the running time of your implementation of the mirror() method in the best case? In the worst case? Use big- O notation, and explain your answers brieﬂy. 1 / \ 2 3 / \ 4 5 / \ 6 7 1 / \ 3 2 / \ 5 4 / \ 7 6

Final Exam Practice Problems — CS 112, Boston University

Related Documents