Block 6: Application of data structures

Home > Preview

The flashcards below were created by user ccc on FreezingBlue Flashcards.


  1. An airline keeps track of ticket booking, flights and such. Airports have unique
    airport codes, flights have unique flight numbers and airplanes have unique
    identifiers. For each task below, suggest a suitable data structure from the following
    options: Stack, List, Set, Map, Tree, Graph, Queue.
    Storing which plane each flight uses.
    Suggested data structure:
    • Map where keys are flight numbers and values are airplane IDs.
    • Only one value per flight.
  2. An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.

    Keeping track of which flights serve meals and which do not.
    Suggested data structure:
    A set of flight numbers, containing the flights where meals are served.
  3. An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.

    Storing a phone number for each booking on all flights, and the order in which
    they were booked.
    Suggested data structure:
    • A list of phone number/flight number pairs. New bookings are added last
    • in the list to record the order of bookings.

    • The same number can book
    • many tickets.
  4. An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.

    Storing known airports and all flights between them.
    Suggested data structure:
    • A directed graph where nodes are airports and edges are flights.
    • Allows finding routes involving multiple flights efficintly.
  5. Here is a program that wants to learn names and numbers.
    The method requstUserInput() lets the user to enter a line of text.
    ArrayList.add(x) adds x last in the list.

    ArrayList.indexOf(x) uses linear search to find the first index of x, or -1 if x is not in the list.

    Image Upload
    Suggest a more suitable data structure than lists. Do you think it would improve
    the complexity of any operations? Motivate your answers.
    • This is a typical case where a map should be used.
    • This will replace both
    • lists with a single map from strings to strings.
    • Instead of indexOf, get is used
    • and instead of two adds, use a single put.
    • Since indexOf is a linear search,
    • using for instance a hash map instead would be a significant speedup.
  6. Image Upload
    • Node a = g.newNode("a");
    • Node b = g.newNode("b");
    • Node c = g.newNode("c");
    • Node d = g.newNode("d");

    • g.addEdge(a, 8, c);
    • g.addEdge(a, 4, d);
    • g.addEdge(c, 1, d);
    • g.addEdge(b, 6, d);
  7. For a part of a simple application that handles authenticated users, suggest a
    suitable data structure for each task from the following options: Stack, List, Set,
    Map, Tree, Graph, Queue.
    Write what the elements/keys/values/nodes/edges etc.
    are. Also write a short motivation for each choice (for instance which operations
    become efficient, where are duplicates allowed/prevented, etc).

    Storing the last login time for each user.
    Suggested data structure:
    • Map where keys are user id's and values are times.
    • Only one value per user and they can be updated quickly
    • on each login.
  8. For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).

    Storing the user ID's of the last ten logins into the system.
    Suggested data structure:
    • A linked list/queue of user id's. Each login adds a new id
    • to the front and drops one from the back of the list.
    • Constant time operation.
  9. For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).

    Keep track of which users have administrative privileges.
    Suggested data structure:
    • A set of user id's. No duplicates and quick lookup.
    • Ordering is not needed.
  10. For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).

    For each user, which other users have been marked as ”blocked” or ”trusted”.
    Suggested data structure:
    A directed graph where nodes are user-id's and edges represent blocking/trusting.

Card Set Information

Author:
ccc
ID:
329517
Filename:
Block 6: Application of data structures
Updated:
2017-03-14 15:58:13
Tags:
Block Application data structures
Folders:

Description:
Block 6: Application of data structures
Show Answers:

Home > Flashcards > Print Preview