2. (a) A bounded queue can be implemented using an array. i. The following diagram shows an example queue implemented using an ordinary array (i.e. front rear): front = 1 2 rear =3 4 5 Lisa Bart Marge Redraw the diagram showing the queue status after inserting 'Maggie' and a deletion. ii. Explain a drawback of the queue implementation based on an ordinary array, using big-O notation. iii. One can avoid the problem of the ordinary array-based implementation if a dif- ferent kind of an array is used. Explain this, using big-O notation. (b) Consider an unknown data structure and the following operations, where a letter represents an insertion of that letter into the data structure and the asterisk * means extracting and printing one number: PGU * YA* **BHO * XR** The data structure is initially empty. The output resulting from these operations is: UA Y GORXH What is the data structure? Choose one structure amongst the following: a map, a queue, a stack, and a set. Justify your answer. (c) If a stack is to be implemented using a linked list, will you use a singly-linked list or a doubly-linked list? Justify your answer, using big-O notation. (a) A map can be implemented using one of the three representations: an array, a linked list, or a binary search tree. i. Give the following map, Module Code CS1 01 CS2 02 OOP 05 HCI 09 DB 04 ADS 06 Choose one of the three representations such that its search algorithm will be most time-efficient and draw a diagram showing how the map would be represented. Using Big-O notation, state the time complexity of the algorithm and justify your answer. ii. Give the following map, Code Module 4 1 He 5 Kr 2 Ne 6 Xe 10 Rn Choose one among the three representations such that its deletion algorithm will be most time-efficient and draw a diagram showing how the map would be represented. Using Big-O notation, state the time complexity of the algorithm and justify your answer. (e) A set (consisting of words) can be implemented using either an array or a singly-linked list. State the time complexity of an algorithm for adding a new item to the set in an array implementation and a singly-linked list implementation, respectively, assuming that both the array and the list are sorted. Justify your answer. Ar