The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 - Data Structures
Week 7 Homework

1. Indicate whether of the following problems requires a stack, a first-in first-out queue, a priority queue, or some other data structure for its solution:

a. A program that needs to read in the names of students and write them out in reverse order.

b. A resource manager that assigns resources based on a first-come, first-served basis.

c. A payroll system that processes employee records by employee number.

d. A task scheduler that schedules tasks on a priority basis

2. Write a procedure that accepts an integer stack as a parameter and removes all the negative entries. This procedure should use a local stack to accomplish its task. Provide a driver procedure to test it. The driver should contain an instantiation of the generic stack package.

3. Suppose a priority queue were implemented by enqueuing new arrivals at the back of the queue and dequeuing by searching for the member with the highest priority. What would the big-O of these two operations be?

4. Evaluate the following prefix expressions:

a. x + 2 3 + 1 3

b. + x - 4 1 2 6

c. + + + 1 2 3 5

d. - + 9 1 x 2 3

5. Translate the following infix expressions to postfix:

a. 4 + 7 - (2 x 3)

b. (8 / 2) - 4 + 3 - 2

c. 9 x 2 + 6 - 1 + 3

d. 5 - 4 + 6 / 3 x 2