Skip to content

Latest commit

 

History

History
57 lines (47 loc) · 2.8 KB

E02R.md

File metadata and controls

57 lines (47 loc) · 2.8 KB
Raw

CSC 212 Exam 02 Review

Programming Portion

You should be able to:

  • implement all of the data structures we have covered since exam 01.
  • deduce the appropriate data structure given a particular problem.

Programming Example Questions

  1. Implement both a queue and a stack using arrays.
  2. Select the top-k elements from an array of integers, where k=5.
  3. Implement a calculator program capable of evaluating fully-parenthesized mathematical equations.
  4. Implement the data structure best suited for a music playlist player.

Comprehension Portion

You should be able to:

  • evaluate a given problem and select the best data structure to solve it.
  • draw a given data structure after a set of operations.

Comprehension Example Questions

  1. Given the following scenarios, select an appropriate data structure and justify your decision:
    1. A local firm is attempting to keep track of it's top-3 customers in terms of money spent. They wish to always know who the top three spenders are, not necessarily how they rank amongst themselves.
    2. You are building a new Operating System. One crucial component to any OS is the CPU scheduler, which takes in jobs from the system, and performs them in a specific order. Some basic requirements for a scheduler are jobs should always get completed eventually, and some jobs are much more critical than others.
    3. During development of a new mathematics engine, you realized you are currently not checking for balanced parenthesis, having assumed all of your inputs would be valid in that sense. Now, you must device a linear time solution to check whether or not the parenthesis in a given expression are balanced.
    4. Suspicious activity has been detected by your local bank, and you've been hired to help narrow down transactions to look at. Thankfully, you've already devised a scheme to weed out the fraudulent activity. You begin with a transaction marked as fraudulent, denoted by an index position in an array of doubles. Your goal is to find all the nearest transactions in value that are smaller than the flagged one. Ensure that your algorithm runs in linear time so that processing times remain low at the bank.
  2. Draw the resulting Red/Black tree after each of the following operations:
    1. Insert(10)
    2. Insert(15)
    3. Insert(20)
    4. Insert(17)
    5. Insert(10)
    6. Insert(9)
    7. Remove(9)
    8. Remove(20)
    9. Remove(15)
  3. Draw the resulting BST after each of the following operations:
    1. Insert(10)
    2. Insert(15)
    3. Insert(20)
    4. Insert(17)
    5. Insert(5)
    6. Insert(9)
    7. Remove(9)
    8. Remove(20)
    9. Remove(10)
  4. Draw the resulting circular linked list after each of the following operations:
    1. for (int i = 0; i < 5; ++i) pushfront(i)
    2. pushback(0)
    3. popfront()
    4. popfront()
    5. popback()
    6. erase(0)