Question B1

Lookup tables are a vital part of most information systems, 
since they invariably require items of information to be selected
(looked up) from tables of data. Because of their importance,
you have studied several search data structures suitable for lookup tables
You are writing an "application generator" (a program that writes other programs)
and you have reached a section that calls for a lookup table to be inserted.
You have to write a dialogue between the application generator and the
programmer in which the application generator asks questions of the 
programmer to determine what is the most appropriate data structure
to use for the lookup table in this particular application.
Write out the list of questions that you would make the application
generator ask the programmer.
For each question, explain (a) why you asked that particular question,
(b) how the programmer's answer would guide the choice of the
best lookup table for the current application.
As an example, your dialogue might start like this:

Question:
On average, how many records will the table contain?
Comments:
If the answer, n, is less than some small number, p, then
the data can be stored on punched cards, since the number of data
items is so small that the user can flip through the punch cards
in much less than the required response time.
if n > p but less q (where q is the number of items the
target computer can search in less than 1 second), then ....
and so on ..

You are not expected to provide accurate numbers for any parameters
such as p and q which will appear in your answer, but to get full
marks for this question, you should provide very rough estimates
(very rougn means within two orders of magnitude here!) for the
values.  As these values change daily as computer speeds
increase, even wild guesses will get credit here.

Question B
Searching and sorting are both vital operations for information
systems. 
Some data structures may be used for both operations and some are
only useful for one or the other.
Make a list of the data structures that you know and indicate
whether the structure can be used for searching or sorting or both.
In each case, indicate the primary use of the structure.
Some comments indicating how effective each structure primarily
used for searching is at sorting (or vice versa) will help to
ensure full marks.
In this question, interpret "data structure" as including an algorithn
to operate on it. So that two algorithms for operating on the same
data structure (eg two algorithms operating on trees) should both be
mentioned.