You must keep track of some data. Your options are: (a) A linked list maintained

Question

You must keep track of some data. Your options are: (a) A linked list maintained in sorted order. (b) A linked list of unsorted records. (c) A binary search tree. (d) An array-based list maintained in sorted order. (e) An array-based list of unsorted records. For each of the following scenarios, show the letter for the one choice that would be best. Then is inserted, its key value will always be greater than that of the last record inserted). A total of 1000 inserts will interspersed with 1000 searches. (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.

Explanation / Answer

1. (e) an array should be used for storing 1000 values which are coming in sorted way i.e whenever a record is inserted its key value is always greater than that of last inserted record key value.

Reason : since the data is already sorted we will have
Insertion in O(1); searching in O(log n) (binary search) and deletion in O(n); and if we use binary tree or link list searching will be O(n) as well as deletion and insertion will be O(n); so for the sake of better searching and insertion we will use array. since data coming is already sorted there is no need of option (d) i.e An array-based maintained in sorted order.

2. (c) Binary Search Tree: Since the data coming has uniform distribution so we will have the binary tree balanced. we know BALANCED Binary Search Tree is AVL tree in which the operation whether insertion, searching and deletion all are O(log n). where as using other data structure will cost us O(n) for one or two operation.   

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.