Exercise 3.5 You must keep track of some data. Your options are: ( 1) A linked-l
ID: 3601066 • Letter: E
Question
Exercise 3.5 You must keep track of some data. Your options are:
(1) A linked-list maintained in sorted order.
(2) A linked-list of unsorted records.
(3) A binary search tree.
(4) An array-based list maintained in sorted order.
(5) An array-based list of unsorted records.
For each of the following scenarios, which of these choices would be best? Explain your answer.
(a) The records are guaranteed to arrive already sorted from lowest to highest (i.e., whenever a record is inserted, its key value will always be greater than that of the last record inserted). A total of 1000 inserts will be interspersed with 1000 searches.
Answer:
(b) The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1,000,000 insertions are performed, followed by 10 searches.
Answer:
(c) The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1000 insertions are interspersed with 1000 searches.
Answer:
(d) The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1000 insertions are performed, followed by 1,000,000 searches.
Answer:
Explanation / Answer
a) Unsorted Array Since the records are already sorted we dont need a sorted data structure. In this case BST will be unbalanced so we cant use BST. We are left with either unsorted array or unsorted list. Both have insertion complexity of O(1) and search complexity of O(n). Since in this case data is already sorted the search complexity will be O(log n). Since the size of the data is already known, unsorted array is prefered.
b) Unsorted Array Since the number of insertions are very very high and number of search operations are very low, we must choose between unsorted array or insorted list as they have minimum insertion complexity of O(1). Since the size of the data is already known, unsorted array is prefered.
c) BST The number of insertions is equal to the number of search operations, which means they both have the same impact.
d) BST The number of search operations is very high so we need to choice the DS with the best search time complexity. That would be either BST or sorted array. BST is better in the insert, so we will choose it.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.