QUESTION:
Consider the following letters: S, T, R, U, C, T, U, R, E, S
For each of the ADTs in (a)–(f) below:
i) Show, by using a conceptual diagram, the following data structures after the letters have been inserted in the order that they are encountered.
ii) Indicate the best‐case time complexity of searching the ADT for an arbitrary letter which is stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big‐Oh) notation.) In a sentence, explain why this time complexity will occur.
iii) Indicate the average‐case time complexity of searching the ADT for an arbitrary letter which is stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big‐Oh) notation.) In a sentence, explain why this time complexity will occur.
iv) Indicate the worst‐case time complexity of searching the ADT for an arbitrary letter which is not stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big‐Oh) notation.) In a sentence, explain why this time complexity will occur.
a) stack;
b) binary tree;
c) priority queue (in ascending alphabetical order);
d) set;
e) bag; and
f) tree of degree four (4) which is kept as compact as possible but which is not re‐balanced after values are inserted.
NOTE: Apart from the conceptual diagram, answers only need to be single sentences that show your logic.
WhatsApp us