In each of the following examples, please choose the best data structure(s). Opt

Question

In each of the following examples, please choose the best data structure(s).

Options are: Array, Linked Lists, Stack, Queues, Trees (BSTs, AVLs, Heaps), Graphs, Sets, Hash Tables. Note that there may not be one clear answer.

1. You have to store social network “feeds”. You do not know the size, and things may need to be dynamically added.

2. You need to store undo/redo operations in a word processor.

3. You need to evaluate an expression (i.e., parse).

4. You need to store the friendship information on a social networking site. I.e., who is friends with who.

5. You need to store an image (1000 by 1000 pixels) as a bitmap.

6. To implement printer spooler so that jobs can be printed in the order of their arrival.

7. To implement back functionality in the internet browser.

8. To store the possible moves in a chess game.

9. To store a set of fixed key words which are referenced very frequently.

10. To store the customer order information in a drive-in burger place. (Customers keep on coming and they have to get their correct food at the payment/food collection window.)

11. To store the genealogy information of biological species.

Explanation / Answer

1. You have to store social network “feeds”. You do not know the size, and things may need to be dynamically added.
Ans. These are modelled with Graphs. Trees can also be an option.

2. You need to store undo/redo operations in a word processor.
Ans. Stack

3. You need to evaluate an expression (i.e., parse).
Ans. Stack as well as Trees(Parsers)

4. You need to store the friendship information on a social networking site. I.e., who is friends with who.
Ans. Graphs

5. You need to store an image (1000 by 1000 pixels) as a bitmap.
Ans. Array

6. To implement printer spooler so that jobs can be printed in the order of their arrival.
Ans. Queues or Priority queues

7. To implement back functionality in the internet browser.
Ans. Doubly-linked list for both backward and forward implementations otherwise just Linked list.
   Even Stack can be implemented. Just keep pushing the pages, when going back pop the last page.

8. To store the possible moves in a chess game.
Ans. Not sure, Possibly BitArray

9. To store a set of fixed key words which are referenced very frequently.
Ans. Sets

10. To store the customer order information in a drive-in burger place. (Customers keep on coming and they have to get their correct food at the payment/food collection window.)
Ans. Binary Search Tree

11. To store the genealogy information of biological species.
Ans. Hash Tables

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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