CSAS1112 - Practice Exam 2

This practice exams lists some sample questions, covering the topics that will be covered in the actual exam. The actual exam may or may not contain questions similar to this practice exam, but the format of the actual exam will be very similar to this practice one. However, this practice exam is somewhat longer than the actual exam.
There may be some more questions later. Please check back Monday before class, if possible. If there are new questions, it will be indicated here.

1. Define the following terms: List, Stack, Queue, FIFO, LIFO. What operations are part of a Stack ? What operations are part of a Queue ? What does the keywords new and delete do ? What is a pointer ? What data type can a pointer point to ? How much memory does a pointer, a double, an integer, and a char use in Turbo C++ for DOS ? What are the simularities between an array and a list ? What are the differences between a array and a list ?

2. Decide which of the following statements are true and which are false:

	A double occupies more memory than an int
	A pointer to a double ocupies more memory than a pointer to an int
	If the characters 'b', 'e', 'r', 't' are first pushed into a stack, then popped from the stack, the result will spell 'bert'.
	If the characters 'b', 'e', 'r', 't' are first enqueued into a queue, then dequeued from the queue, the result will spell 'bert'.
	When considering a stack, a queue, and a list, the queue is most similar to an array.
	In a stack of size N, one needs to access N / 2 nodes to retrieve the middle node [trick questions]

3. List the output of the following program segment. If an error is contained in the program, please mark and explain the error. For the rest of the program, assume that all lines with an error are removed from the program.

#include <iostream.h>

class Node
{
   public: double data;
   public: Node *next;
};

int main(void)
{
   double *px, *py;
   double x, y;
   Node *p, *q, *r;

   x = 9.5;
   y = -2.0;
   px = 8.6;
   *px = 10.0;
   *x = *px;
   x = *px;
   py = &y;
   p = new Node(); q = new Node(); r = new Node();
   p->data = 1.0;
   q->data = 2.0;
   r->data = 3.0;
   p->next = q;
   q->next = r;
   r->next = p;
   cout << *px << endl;
   cout << x << endl;
   cout << *py << endl;
   cout << q->next;
   cout << p->next->next->next->next->data << endl;
   delete q;
   cout << p->next->next->next->next->data << endl;
   return 0;
}

4. Write some sample code for the following situation:

Delete a node in a double-linked list, as indicated in the following picture. You do not have to provide a complete function or class, nor do you need to worry about special cases such as deleting the only node. Note: each node has three fields, a prior and next pointer, and a data field.

Insert a node in a double-linked list, as indicated in the following picture. You do not have to provide a complete function or class, nor do you need to worry about special cases such as inserting the first node. Note: each node has three fields, a prior and next pointer, and a data field.

Write the complete 'insert' method for a double-linked list. Make sure you cover, if necessary, special situations. Note that a double linked list has a head and a current pointer, and each node has fields as above. Insertion can take place either at the head of the list, or at the current node (your choice, please indicate).

Write the complete 'remove' method for a double-linked list. Make sure you cover, if necessary, special situations. Note that a double linked list has a head and a current pointer, and each node has fields as above. The current node is to be deleted, and the the current pointer after deletion could either point to the node before the deleted one, after the deleted one, or to the head of the list (your choice, please indicate).

5. Write the code for the indicated methods of the specified classes. Note that you can assume the Node class has been defined as usual already.

	For the Queue class, write the code for enqueue.
	For the Stack class, write the code for pop
	For the Queue class, write the code for dequeue
	For the Stack class, write the code for push
	For the Queue class, write the code for peek
	For the Stack class, write the code for peek

6. Assume you have a fully functioning Stack and Queue class. Use these methods to write code to do the following:

	To convert a double number to its binary representation. The binary representation should be printed out to the screen.
	To check a string for being a Palindrom (i.e. a string that reads the same backwards as well as forwards).
	At least one question that will be new.

(bgw)