COSC 2415 Exam 2 Review

COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

Exam 2 Review Exercises

I recommend that you do the following exercises as you study the chapters in the textbook. Answers to the Quick Quiz exercises are in Appendix F at the back of your textbook. Questions marked with an asterisk (*) have answers or additional comments. Click here for comments and answers to Other Questions..

The exam will emphasize both C++ coding and concepts. Be sure to review the Summary (Chapter Notes, Programming Pointers, and ADT Tips) at the end of each chapter. Following is a sample question over concepts.

Give a brief description of pass-by-value and pass-by-reference. In what situations should pass-by-value be used? In what situations should pass-by-reference be used?

Chapter 6

Quick Quiz 6.4: 1-3,4*,5*,6.

Section 6.6 Array-Based Implementation of Linked Lists - this section will not be covered on the exam.

Other Questions: Problems 1-6 use this simple Node class:

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

1. Write an algorithm to search the linked-list who's first node is pointed to by first for a given value called item. If item is found, return a pointer to the predecessor of the node that contains item. Return NULL if item is in the first node or is not in the list.

2. Write C++ code to insert the node pointed to by newptr after the node pointed to by predptr. This is the first case in the discussion of insertion on pages 290-292 of your book.

3. Write C++ code to insert the node pointed to by newptr at the beginning of the list. This is the second case in the discussion of insertion on pages 290-292 of your book.

4. Write C++ code to delete the node pointed to by ptr given the pointer predptr to the predecessor node. This is the first case in the discussion of deletion on pages 292-293 of your book.

5. Write C++ code to delete the first node in the list. This is the second case in the discussion of deletion on pages 292-293 of your book.

6. Describe what is output by the following code or explain why an error occurs.

Node *p1, *p2;
p1 = new(nothrow) Node;
p2 = new(nothrow) Node;
p1->data = 12;
p2->data = 34;
p1 = p2;
p2->next = p1;
cout << p1->data << " " << p2->data << endl;
cout << p1->next->data << " " << p2->next->data << endl;

7. Given only the pointer (named current) to a node in a singly-linked list (not the first node), can you write code to delete the node? See the picture below.

     +---+---+     +---+---+     +---+---+     +---+---+
-->  | 2 | --+---> | 4 | --+---> | 6 | --+---> | 8 | --+--->
     +---+---+     +---+---+     +---+---+     +---+---+
                       ^
                       |
                   current

Chapter 7

Quick Quiz 7.2: 1,2,3,4,5.

Quick Quiz 7.4: 1-5.

Quick Quiz 7.5: 1-4.

Other Questions:

For questions 1 and 2, assume the static array implementation of a queue from Figure 8.2 where the QueueElement is char and capacity is 5.

1. After executing the code below, show the values of myFront, myback, and myArray for the Queue object q; also indicate any errors that occur.

Queue q; char ch;
q.enqueue( 'X' );
q.enqueue( 'Y' );
q.enqueue( 'Z' );
while ( !q.empty( ) )
{
   ch = q.front( );
   q.dequeue( );
}

2. After executing the code below, show the values of myFront, myback, and myArray for the Queue object q; also indicate any errors that occur.

Queue q; char ch;
ch = 'q';
for ( int i=1; i<=3; i++ )
{
   q.enqueue( ch );
   ch++;
   q.enqueue( ch );
   ch = q.front( );
   q.dequeue(  );
}

3. Write a full( ) member function for the static array implementation of a queue from Figure 8.2. Your function should return true if the queue is full, and false otherwise.

4. Assume that the Queue class is implemented using a linear linked list as in Section 8.3 of the textbook. Write a member function back( ) that returns the element at the back of the queue. The function should fail if the queue is empty.

Chapter 9

Quick Quiz 9.3: 1-9,11,12.

Section 9.4 The vector Container - vector is a good example of a container class. This section WILL be covered on the exam.

Sections 9.5 - 9.8 WILL NOT be covered on the exam.