$[4$ pts$]$ Assume that you need to keep track of some data. To store those data, you have the

following options:

A$)$ A linked list maintained in sorted order.

B$)$ A linked list of unsorted records.

C$)$ A binary search tree.

D$)$ An array maintained in sorted order.

E$)$ An array of unsorted records.

For each of the following scenarios, which of the above choices would be the best $($i$.$e$.$ you will

pick$)?$ Justify your answer.

$3\mathrm{.}1)$ The records are guaranteed to arrive in sorted order 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 a maximum of $1000$ searches.

$3\mathrm{.}2)$ The records arrive with values having a uniform random distribution $($i$.$e$.,$ the BST is likely

to be well balanced in case you want to use it$).1,000,000$ insertions are performed, followed by

$10$ searches.

$3\mathrm{.}3)$ The records arrive with values having a uniform random distribution $($i$.$e$.,$ the BST is likely

to be well balanced in case you want to use it$).1000$ insertions are interspersed with $1000$

searches.

$3\mathrm{.}4)$ The records arrive with values having a uniform random distribution $($i$.$e$.,$ the BST is likely

to be well balanced in case you want to use it$).1000$ insertions are performed, followed by

$1,000,000$ searches.