TOC PREV NEXT

Quiz — Dynamically allocated data

The exercises on this quiz all involve linked structures and code that manipulates them. Examples include producing code that references a given part of a box-and-arrow diagram, drawing a diagram that represents the structure built by a given code segment, analyzing code, and writing a function that implements some list operation.

Restrictions on C constructs described in "C constructs to avoid" apply for this quiz as usual.

Readings

A Computer Science Tapestry, sections 12.1 and 12.2.

C++ Program Design, sections 9.5 (destructors), 12.1 through 12.3 (pointers, covered in a C context), and 12.8 (pointers, covered in a C++ context). Chapter 12 unfortunately relies heavily on C-style examples. Moreover, linked lists aren't covered until after templates; an example appears in section 14.5.

Computing Fundamentals with C++, chapters 14, 15, and 20. Ignore use of the & operator in chapter 14 and of C-style arrays in sections 15.1 and 15.2.

Sample exercises

All exercises in sections 12.1 and 12.2 of A Computer Science Tapestry will be useful.

Exercises in C++ Program Design are not helpful for this quiz.

All exercises in chapter 15 of Computing Fundamentals with C++, including self-check exercises but not programming projects, will be useful. If you're not experienced with recursion, work through the exercises in chapter 20 as well.

Sample quiz

  1. Consider the type declarations given below. 
	class TreeNode {
	public:
		...
	private:
		int myInfo;
		TreeNode* myLeft;
		TreeNode* myRight;
	};
Identify the C++ type of each storage location outlined in bold in the diagram below and, using the tree variable, give an expression that names the storage location.


  1. Consider the following class declarations: 
    class TreeNode {
public:
	...
private:
	int myInfo;
	TreeNode* myLeft, myRight;
}

    class TreeNode {
public:
	...
private:
	int myInfo;
	TreeNode *myLeft, *myRight;
};

    Briefly explain the effect of each declaration, and indicate which of the two is equivalent to the definition given in exercise 1.

  2. Consider the class 
	class ListNode {
	public:
		ListNode (int k);	// initialize myValue to k and myNext to 0
		ListNode (int k, ListNode* ptr);	// initialize myValue to k and myNext to ptr
		~ListNode ();       // delete the node and all nodes
				    // accessible through it;
				    // precondition: this != 0.
		int First ();       // return the value stored in the list node
		ListNode *Rest ();  // return the list consisting of
				    // the remaining elements
		void Print ();      // print the list
	private:
		int myValue;
		ListNode* myNext;
	};
Write a ListNode member function called Odds that returns a pointer to a list of the odd integers in the object list. The order of the values in the list returned should be the same as in the object list. Do not modify the object list; make copies of the nodes that contain odd integers.
  1. Identify all bugs in the following function, a ListNode member function called RemoveEvens that is intended to remove nodes that contain even integers from a nonempty object list and delete them. 
	void ListNode::RemoveEvens () {
		for (ListNode *temp = this; temp != 0; temp = temp->myNext) {
			if (temp->myNext->value % 2 == 0) {	// even number?
				delete temp->myNext;
				temp->myNext = temp->myNext->myNext;
			}
		}
	}

Solutions to sample quiz questions

  1. The two outlined locations are tree->myRight->myInfo of type int and
    tree->myLeft->myRight->myLeft of type TreeNode *.
  2. The first declaration causes a compile-time error by trying to declare myRight as a TreeNode, not a TreeNode *. The second declaration is equivalent to the declaration in exercise 1.
  3. The easiest way to do this uses recursion. 
	ListNode *ListNode::Odds () {
		if (this == 0) {		// nothing left
			return 0;
		} else if (myValue%2 == 0) {	// even number
			return myNext->Odds ();
		} else {			// odd number
			return new ListNode (myValue, myNext->Odds( ));
		}
	}
Here's an iterative version. 
	ListNode *ListNode::Odds () {
		ListNode *first = 0;
		ListNode *last = 0;
		for (ListNode *temp = this; temp != 0; temp = temp->myNext) {
			if (temp->value%2 != 0) {	// odd
				if (first == 0) {
					first = last = new ListNode (temp->myValue);
				} else {
					last->myNext = new ListNode (temp->myValue);
					last = last->myNext;
				}
			}
		}
		return first;
	}
  1. There are several problems with the given function. First, the value in the first list element is never checked; fixing this requires maintaining a dummy header node in each list, since assignment to this is not allowed. Second, the loop termination condition is incorrect; it should be temp->myNext != 0. Finally, the node with the even value is deleted too soon; the contents of its myNext member needs to be saved first, in order to update temp->myNext correctly.
TOC PREV NEXT