Name ___________________

CPTR246 Spring '00 (100 total points) Exam 3

1. Is the stack a LIFO or FIFO data structure? (2 points)

2. Is the queue a LIFO or FIFO data structure? (2 points)

3. Draw (as described in class) the linked list of integers of a stack after the following operations are executed. (5 points)

push 10

push 54

push 92

pop

push 18

push 6

pop

4. Draw (as described in class) the linked list of integers of a queue after the following operations are executed. (5 points)

enqueue 10

enqueue 54

enqueue 92

dequeue

enqueue 18

enqueue 6

dequeue

5. Answer the following questions regarding this tree: (2 points each)

What is the root?

How many nodes are in the tree?

List the leaves in the tree.

Name the children of node 5:

Name the parent of node 12:

6. Define a structure called compactDisk that contains the following information: (6 points)

Title of CD (a string of at most 40 characters)

Name of artist (a string of at most 40 characters)

Cost of the CD (a double)

Number of songs on the CD (an integer)

7. Define an array called myCollection that can hold up to 500 compactDisk objects. (4 points)

8. Assume that the array defined in question 7 has been loaded with information about your CD collection and that the following integer object contains how many CDs you have.

int howMany;

Write code that will compute and display on the screen how much you've spent on your collection. (10 points)

9. Use program point9.C as a reference. Write a function called staffSize that will return the number of employees in the linked list. It will take 1 parameter, the linked list of employees built in the program (actually the pointer to the first employee in the linked list). The function is to return the number of employees. (8 points for a non-recursive solution, 11 points for a recursive solution - You may try both and I will give you the most points I can find!)

10. Use program point9.C as a reference. Write a function called giveRaise that will give a raise to an employee. It will take 3 parameters, the linked list of employees built in the program (actually the pointer to the first employee in the linked list), an integer for the employee's ID, and a double that will be the new hourly rate for the employee. The function is to find the employee in the linked list and update their hourly rate. The function is to return true if the employee is found in the list, false otherwise. (20 points)

11. Use program stack.h as a reference. Write a member function called Remove that will take an integer as a parameter, find the first time that it appears in the stack, and remove it. It will take 1 parameter, the integer to be removed. You may assume that the integer is in the stack. The function is to return nothing.

(a) Begin by indicating what changes need to be made to the class declaration: (5 points)

class Stack {

public: // see function def's for pre and post

Stack::Stack() { top = 0;}

Stack::~Stack();

bool Stack::IsEmpty() {return (top == 0);}

bool Stack::IsFull();

bool Stack::Peek(int & x);

void Stack::Push(int x);

bool Stack::Pop(int & x);

void Stack::Display();

private:

Node * top; // points to the first Node in the stack

};

(b) Write the member function definition: (20 points)

(an extra sheet of paper is attached for your use, just in case you need it)