Name ___________________

CPTR246 Spring '01 (100 total points) Exam 3

1. Enter the values that will be in the linked list of integers, and draw the links (arrows), of a stack after the following operations are executed. (5 points)

push 35

push 65

push 8

push 18

pop

push 99

pop

2. Enter the values that will be in the linked list of integers, and draw the links (arrows), of a queue after the following operations are executed. (5 points)

enqueue 35

dequeue

enqueue 65

enqueue 8

dequeue

enqueue 18

enqueue 99

3. What does the acronym LIFO stand for? (2 points)

4. What does the acronym FIFO stand for? (2 points)

5. Answer the following questions regarding this tree:

What is the root? (2 points)

How many nodes are in the tree? (2 points)

List the leaves in the tree. (2 points)

Name the children of node 8: (2 points)

Name the parent of node 8: (2 points)

List the nodes as they would be visited in a breadth-first search: (3 points)

List the nodes as they would be visited in a depth-first (preorder) search: (3 points)

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

Title of the book(a string of at most 80 characters)

Name of the author (a string of at most 40 characters)

Number of pages in the book (an integer)

Genre of the book (a characters object, like ‘M’ for mystery, etc.)

7. Define an array called myLibrary that can hold up to 1000 book objects. (4 points)

8. Assume that the array defined in question 7 has been loaded with information about your collection of books and that the following integer object contains how many are in it.

int bookCount;

Write code that will display on the screen the title of all books in your collection written by Mark Twain. (10 points)

9. Use program point9.C as a reference. Write a function called Fire that will remove an employee from the list, without a memory leak. It will take 2 parameters, the linked list of employees built in the program (actually the pointer to the first employee in the linked list), and an integer for the ID of the employee who is being fired. The function is to find the employee in the linked list and remove him/her. You may assume that the employee is in the list. The function is to return a pointer to the updated linked list. [HINT: Under what special case would the pointer to the updated linked list be different than the pointer to the original list?] (15 points)


10. Use program stack.h as a reference. Write the following two new member functions:

TimesThere takes an integer as a parameter and returns the number of times that integer appears on the stack. Therefore, it will take 1 parameter, the integer to be counted and returns an integer.

SwapTopTwo will do just that, reverse the first two entries in the stack, by changing the links (pointers). It has no parameters, but does return false if there are less than two entries on the stack, true otherwise.

(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() { top = 0;}

~Stack();

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

bool IsFull();

bool Peek(int & x);

void Push(int x);

bool Pop(int & x);

void Display();

private:

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

};

Use the following two pages to code the functions.

(b) Write the member function definition for TimesThere: (15 points)

(repeated for your convenience)

TimesThere takes an integer as a parameter and returns the number of times that integer appears on the stack. Therefore, it will take 1 parameter, the integer to be counted and returns an integer.

(c) Write the member function definition for SwapTopTwo: (15 points)

(repeated for your convenience)

SwapTopTwo will do just that, reverse the first two entries in the stack, by changing the links (pointers). It has no parameters, but does return false if there are less than two entries on the stack, true otherwise.