Sample Data Structures Exam Questions for Sorting, Hash Functions, and Hash Tables

This is a list of exam questions I've asked on past exams for my data structures class at the University of Pittsburgh.

1. Why is inheritance potentially a problem for a SortedList?
2. Assuming a Set is built with a sorted array as its backing structure, what is the computational complexity of the remove(Object) method?  State any assumptions you make and explain your answer.
3. Assuming a Set is built with a sorted array as its backing structure, what is the computational complexity of the contains(Object) method?  State any assumptions you make and explain your answer.
4. Explain how the binary search algorithm works.  If no code is written, be sure to provide a detailed description.  Illustrate with an example.
5. What is one distinct advantage of using an array-backed SortedList over a linked approach?
6. What is one distinct advantage of using a linked approach to a SortedList over an array-backed approach?
7. Show the steps involved in performing an insertion sort on the array [5, 3, 9, 5, 7, 4].  Be sure to show every swap operation.
8. Why is the Iterator an important pattern in software development?  Give an example of why iterators are necessary.
9. What are 2 of the criteria for an effective hashcode?
10. Two ways to look up data quickly are searching a sorted array with binary search, and using a hash table.  What are the advantages of each? Give one example of a situation where you’d want to use a sorted array with binary search, and give one example of a situation where you’d want to use a hash table.
11. Describe a situation where the computational complexity of a HashMap could approach O(n).
12. Assume you are building an information system for the 150,000 students graduating in Pennsylvania in 2014.  You need to be able to quickly access student records, so you want to build a HashMap for fast retrieval. Assuming the following is the data available, write an effective hashCode method for the Student object.  Be sure to state any assumptions you make.
13. Add the following hash codes to a hash table with an initial capacity of 11, using a linear probing collision resolution strategy: [5, 17, 43, 3, 12, 56, 16, 2, 6, 45].
14. Why might you need to use a dictionary / map structure with duplicate keys?  Give an example.
15. Add the following hashcodes to the table with an initial capacity of 11, using a separate chaining strategy: [5, 17, 43, 3, 12, 56, 16, 2, 6, 45, 57, 11, 10, 1, 0, 9].
16. If the following hashcode method is used for a Store object, how might this negatively affect a hashtable used to store and retrieve information about a large retail chain’s department stores? Identify the problems and state any assumptions you make.
17. Perform a binary search for the number 303 on the following array.  Show the comparison, sub-array, and operations at each step: [15, 75, 99, 100, 106, 128, 285, 333, 343, 345, 360, 365, 408, 474, 496].
18. What is a Set?  How does a Set differ from a List?  Name at least one method that a Set should have that a List might not, and at least one method that a Set cannot have that a List can.
19. What are the steps taken when sorting the following array using a merge sort? Show the breakdown of the array and the re-assembly in each step: [2, 3, 6, 5, 1, 7, 8, 9].
20. Why are the bubble sort and selection sort algorithms rarely used in practice?
21. Why might a separate chaining collision resolution strategy be more attractive than using a linear probing collision resolution strategy for a hash table-based Map / Dictionary?
22. In certain situations, insertion sort must do a lot of work to complete something seemingly simple.  What is this problem, and how does the shell sort algorithm help to alleviate this?
23. In a hash table that uses a linear probing collision resolution strategy, removing is not as simple as finding the proper address and removing the item there.  Why is this?
24. What is a priority queue?  What does it do?
25. Implement an add(String) method for a hash table that uses a linear probing collision resolution strategy.
26. Implement an add(String) method for a hash table that uses a separate chaining collision resolution strategy.