1995 Exam, Free-response in C++

**Owen Astrachan**

This document is a good-faith attempt at translating the free-response questions of the 1995 Advanced Placement Computer Science examinations from Pascal to C++.

This document is NOT an official publication of Educational Testing Service or the College Board.

This document was generated using the **LaTeX**2`HTML` translator Version 0.6.4 (Tues Aug 30 1994) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:

**latex2html** `examc++.tex`.

The translation was initiated by Owen L. Astrachan on Fri Jul 7 15:00:10 EDT 1995

**Problem 1**

Assume that names are stored in variables of the (standard)
*apstring* class. Recall that the member function
*length*() returns the number of characters in a string, and that
the indexing operator [] can be used to access individual characters in
a string.

(note to reader: as an alternative, we could supply part of a string class, or mimic the exam and provide a record-like definition as shown below.)

const int MAXLENGTH = < some positive integer >; struct string // mimics Pascal version, NOT a C++ class { apvector<char> letters; int length; // number of characters stored in letters };

** part A **

Write the function *CommaPosition* whose header is given below. If
there is no comma in *Name*, then *CommaPosition* returns -1.
Otherwise, *CommaPosition* returns the index, or position, of the
comma in *Name*. Assume that there is at most one comma in *Name*.

For example:

NameCommaPosition(Name)W, Jeff 1 Smith, 5 Jones -1 , 0 Doe,Roxanne 3 ,Susan 0

Complete function *CommaPosition* below the following header:

int CommaPosition(const apstring & Name) // precondition: Name contains at most one comma. // postcondition: returns -1 if there is no comma in Name // or returns the position/index of the comma in Name

Write the function *PrintFirstLast* whose header is given below.
*PrintFirstLast* should print the name(s) stored in parameter *Name* as follows:

If there is no comma inNamethen nothing is printed; otherwise,PrintFirstLastshould print all characters after the comma, if any, followed by a space, followed by all characters before the comma, if any.

For example:

NameOutput ofPrintFirstLastW,Jeff Jeff W Smith, Smith Jones , Doe,Roxanne Roxanne Doe ,Susan Susan

In writing *PrintFirstLast* you may call the function *CommaPosition* of part (a).
Assume that *CommaPosition* works as specified, regardless of what you
wrote in part (a).

Complete function *PrintFirstLast* below the following header.

void PrintFirstLast (const apstring & Name) //precondition: Name contains at most one comma

In parts (a) and (b) of this problem you may use function *Swap*,
which interchanges the values of its two parameters.

void Swap(int & a, int & b); // precondition: a == avalue, b == bvalue // postcondition: a == bvalue, b == avalue

** part A **

Write function *ReverseArray*, whose header is given below. Function
*ReverseArray* rearranges the elements in
*a* so that they are in reverse order.
For example, the result of
`ReverseArray(a,5)`

is illustrated below.

Before call toReverseArray(a,5)After call toReverseArray(a,5)+----+----+----+----+----+ +----+----+----+----+----+ | 61 | 34 | 18 | 99 | 73 | | 73 | 99 | 18 | 34 | 61 | +----+----+----+----+----+ +----+----+----+----+----+

Complete function *ReverseArray* below the following header.

** part B **

Write function *ReverseVertical*, whose header is given below.
Function *ReverseVertical* rearranges the elements of one column of
apmatrix *m* so that they are in reverse order. For example, the
result of
`ReverseVertical(m,2)`

, where `m.numrows() == 4`, is illustrated below.

Before call toAfter call toReverseVertical(m,2)+----+----+----+----+ +----+----+----+----+ | 61 | 34 | 18 | 99 | | 61 | 34 | 35 | 99 | +----+----+----+----+ +----+----+----+----+ | 11 | 22 | 44 | 33 | | 11 | 22 | 77 | 33 | +----+----+----+----+ +----+----+----+----+ | 55 | 66 | 77 | 88 | | 55 | 66 | 44 | 88 | +----+----+----+----+ +----+----+----+----+ | 25 | 45 | 35 | 55 | | 25 | 45 | 18 | 55 | +----+----+----+----+ +----+----+----+----+ReverseVertical(m,2)

Complete function *ReverseVertical* below the following header.

** part C **

Write function *ReverseMatrix*, whose header is given below. Function
*ReverseMatrix* rearranges the elements in *m*,
an * N x N * matrix, so that they
are in reverse order. A matrix is reversed when both the rows are
reversed i.e., (r_0, r_1, ... r_{n-1})
becomes (r_{n-1}, ... r_1, r_0) and the
elements within each row are reversed, as was done in part (a). For
example, the result of `ReverseMatrix(m)`

,
where `N = 4`

is illustrated below.

Before call toAfter call toReverseMatrix(m)+----+----+----+----+ +----+----+----+----+ | 61 | 34 | 18 | 99 | | 55 | 35 | 45 | 25 | +----+----+----+----+ +----+----+----+----+ | 11 | 22 | 44 | 33 | | 88 | 77 | 66 | 55 | +----+----+----+----+ +----+----+----+----+ | 55 | 66 | 77 | 88 | | 33 | 44 | 22 | 11 | +----+----+----+----+ +----+----+----+----+ | 25 | 45 | 35 | 55 | | 99 | 18 | 34 | 61 | +----+----+----+----+ +----+----+----+----+ReverseMatrix(m)

In writing *ReverseMatrix*, all array manipulations must be done
using
functions *ReverseArray* and *ReverseVertical* of parts (a) and
(b). This means that no apvector variable can appear on the left-hand side
of the assignment operator (=). You will receive no credit
for part (c) if your code includes such assignment statements or calls
to *Swap*.
Assume that *ReverseArray* and
*ReverseVertical* work as specified regardless of what you wrote
for parts (a) and (b).

Complete function *ReverseMatrix* below the following header.

Consider an abstract data type that represents a finite, nonempty
sequence of integers. Each such sequence has a designated ``current
position.'' These sequences are represented by variables of type
*Sequence*. For example, variable *S* of type *Sequence*,
might represent the sequence.

3, 26, 18, 11 18

where the underline indicates that the current position is the second position and that the integer 26 is at that position.

Sequences may have an ``invalid'' current position. A sequence with an invalid current posiition is said to be ``ended.''

Assume that the following public member functions have been defined
for the class *Sequence*. (More precise specifications are given
before part (a).)

IsEndedreturns true if the current position is invalid; otherwise, returns false.SetToFirstsets the current position to be the first positionCurrentValuereturns the integer value at the current position. It is an error to make this call when the sequence is ended.AdvanceIt is an error to callAdvancewhen the sequence is ended. If the current position is the last position, then the current position is changed to be invalid Otherwise, the current position is changed to the position following the one that was current whenAdvancewas called.

The following example demonstrates the use of some of these operations
in the definition of a function *SumSeq* that returns the sum of the
integers in sequence *S*.

Write the body of function *Length* whose header is given
below. *Length* returns the number of integers in its sequence
parameter. Note that *Length* is NOT a member function.

int Length(Sequence s) // precondition: s contains m elements // postcondition: returns m

** part B**

Write the function *LenOfIncreasing*, whose header is given below.
*LenOfIncreasing* returns the length of the longest (strictly)
increasing segment in *s* beginning with, and including, the integer
at its current position.

Examples: (the current position is indicated with an *)

SequencesIncreasing SegmentLenOfIncreasing(s)3 6 11 6 5* 6 8 9 11 5 3 5 6 8 9 11 5 7 -1 2 5 8 6 6 7 7* 30 7 30 2 1 7 6 3 5* 9 9 9 10 10 4 5 9 2 3 5 8 9 12* 4 6 9 15 12 1

Complete function *LenOfIncreasing below the following header.*

int LenOfIncreasing(Sequence s) // precondition: s represents n_1, n_2, ... , n_m; // current position of s is c; 1 <= c <= m // postcondition: returns the largest integer r between 1 and // m (inclusive) such that n_c < n_{c+1} < ... < n_{c+r-1}

**Problem 1**
(same as A2)

**Problem 2**

This question involves reasoning about two implementations of of a data structure called a priority list. A priority list is a collection of items, each of which contains both data and a unique integer priority. The ``maximal'' item in a priority list is the element whose integer priority has the greatest value. Both data and an integer priority are specified when inserting an element into a priority list. Only the maximal element, the item with the highest integer priority, is accessible in a priority list.

A priority list class *Plist*
supports the following public member functions.

FunctionDescriptionPlistconstructs and initializes an empty priority listIsEmptyreturns true if the priority list is empty; otherwise returns falseInsert(info,pri)inserts item with datainfoand prioritypriFindMax(info,pri)setsinfoandprioto the data and priority of the maximal itemDeleteMaxdeletes the maximal element

Consider the following two methods for implementing priority lists. Type declarations are given in part (b) of this problem.

** Method 1**

A priority list is an unsorted linked list.
The *Insert* operation inserts an item as the first
node of the list.

** Method 2**

A priority list is a linked list sorted by priority field from largest
to smallest (so that the first node in the list is always the maximal
item of the priority list). The *Insert* operation
inserts an item so that the list remains sorted by priority.

Precise specifications for the member functions described above are given below.

Plist::Plist() //postcondition: represents an empty priority list bool Plist::IsEmpty() const //postcondition: returns true if priority list is empty (has 0 items); // otherwise, returns false void Plist::Insert(const DataType & info, int pri) // precondition: no item in priority list has priority pri // postcondition: A new item whose data field has value info and whose // priority field has value pri has been inserted void PQeue::FindMax(DataType & info, int & pri) const // precondition: IsEmpty() == false, (priority list is non-empty) // postcondition: the values of info and pri are those of the maximal item void Plist::DeleteMax() // precondition: IsEmpty() == false, (priority list is non-empty) // postcondition: the maximal item has been deleted

Complete the table below, In each cell give the worst-case time
complexity for the corresponding operation and implementation of a
priority list of *n* items. Use *O*-notation and briefly justify
each answer.

Method 1 Method 2 Plist Time: O(1) Reason: single assignment to pointer, e.g., first = NULL Insert FindMax Time: O(1) Reason: maximal item is at the front of the list; therefore, only a single access is needed.

** part B **

In this part, you will write functions *Insert* and *FindMax*
for one of the methods for implementing priority lists
described at the beginning of this question. You MUST use the same
method in writing both *Insert* and *FindMax*. It may be the
case that it is easier to write code for one of the methods than for
the other. Think carefully before choosing a method. Circle below
the method you will use to implement *Insert* and
*FindMax*.
Method 1 Method 2

You must use the following type declarations to implement priority lists regardless of which method you chose.

class DataType; struct Node { DataType data; // data associated with item int priority; // unique priority associated with item Node * next; }; class Plist { public: Plist(); int IsEmpty() const; void Insert(const DataType &, int); void FindMax(DataType &, int &) const; void DeleteMax(); private: Node * myFirst; // pointer to first node in linked list };

Complete functions *Insert* and *FindMax* below the following
headers.

void Plist::Insert(const DataType & info, int pri) // precondition: no item in priority list has priority pri // postcondition: A new item whose data field has value info and whose // priority field has value pri has been inserted

void PQeue::FindMax(DataType & info, int & pri) const // precondition: IsEmpty() == false, (priority list is non-empty) // postcondition: the values of info and pri are those of the maximal item

**Problem 3**
Case Study Problem

**Problem 4**

Assume that binary trees are implemented using the following definitions.

struct TreeNode { int info; TreeNode * left, * right; };

** part A **

Write function *IsChild* whose header is given below.
*IsChild* returns true if the node pointed to be parameter
*second* is a child (either left or right) of the node
pointed to be parameter *first*, and returns false otherwise.

bool IsChild(TreeNode * first, TreeNode * second) // precondition: second != NULL // postcondition: returns true if second is a child of first // returns false otherwise

** part B **

Write the function *IsDescendant* whose header is given below.
*IsDescendant* returns true if there is a path from the node pointed
to by parameter *first* to the node pointed to by parameter
*second*, where a path is a nonempty sequence of left or right children

For example, consider the tree diagrammed below:

function call value returned IsDescendant(NodeC, NodeA) false IsDescendant(NodeA, NodeB) true IsDescendant(NodeB, NodeA) false IsDescendant(NodeC, NodeD) true IsDescendant(NodeA, NodeA) false

In writing *IsDescendant* you may call function *IsChild*
of part (a). Assume that *IsChild* works as specified, regardless of
what you wrote in part a.

Complete *IsDescendant* below the following header.

bool IsDescendant(TreeNode * first, TreeNode * second) // precondition: second != NULL

** part C **

Write function *ChangeTree*, whose header is given below.
*ChangeTree* removes from *t* all nodes that have exactly one
child, replacing the removed node with the child. (All removed nodes
should be returned to available storage.)
If *A* and
*B* are nodes in *t* that do NOT have exactly one child, and
if *IsDescendant(A,B)* is true before the call
*ChangeTree(t)*, then *IsDescendent(A,B)* must be true
AFTER the call *ChangeTree(t)*.

For example:

In writing *ChangeTree*, you may call function *HasOneChild*,
defined below.

bool HasOneChild(TreeNode * t) // postcondition: returns true if t has exactly one child, else returns false { if (t != NULL && // t exists (t->left == NULL && t->right != NULL || t->left != NULL && t->right == NULL)) { return true; } return false; }

Complete function *ChangeTree* below the following header.

void ChangeTree(TreeNode * & t)

int CommaPosition(const apstring & Name) // precondition: Name contains at most one comma. // postcondition: returns -1 if there is no comma in Name // or returns the position/index of the comma in Name { int k; int len = Name.length(); // with struct def, use = Name.length for(k=0; k < len; k++) { if (Name[k] == ',') return k; } return -1; // ',' not found in Name } void PrintFirstLast (const apstring & Name) //precondition: Name contains at most one comma { int k; int len = Name.length(); int comma = CommaPosition(Name); // index of comma if (comma != -1) { for(k=comma+1; k < len; k++) // print first name { cout << Name[k]; } cout << ' '; for(k=0; k < comma; k++) // print last name { cout << Name[k]; } } } void ReverseArray(apvector<int> & a, int numElts) // precondition: numElts = # of entries in a // postcondition: elements of a are reversed { int k; int limit = numElts/2; // half-way for(k=0; k < limit; k++) { Swap(a[k],a[numElts-k-1]); } } void ReverseVertical(apmatrix<int> & a, int col) { int k; int limit = a.numrows()/2; // half-way for(k=0; k < limit; k++) { Swap(a[k][col],a[N-k-1][col]); } } int ReverseMatrix(apmatrix& m) { int k; int dimension = m.numrows(); for(k=0; k < dimension; k++) { ReverseArray(m[k],dimension); } for(k=0; k < dimension; k++) { ReverseVertical(m,k); } } int Length(Sequence s) // precondition: s contains m elements // postcondition: returns m { int count = 0; // counter for # of elements of s s.SetToFirst(); while (! s.IsEnded()) { count++; s.Advance(); } return count; } // alternate version using for-loop int Length(Sequence s) // precondition: s contains m elements // postcondition: returns m { int count = 0; // counter for # of elements of s for(s.SetToFirst(); ! s.IsEnded(); s.Advance()) { count++; } return count; } int LenOfIncreasing(Sequence s) { int lastVal; int length = 1; // length at least one if (! s.IsEnded()) { lastVal = s.CurrentValue(); s.Advance(); while (! s.IsEnded() && lastVal < s.CurrentValue()) { length++; lastVal = s.CurrentValue(); s.Advance(); } return length; } else { return 0; // no increasing seq, no elements } } // method 1 void Plist::Insert(const DataType & info, int pri) { Node * temp = new Node; temp->data = info; temp->priority = pri; temp->next = myFirst; // points to old first node myFirst = temp; // update to new first node } // method 2 void Plist::Insert(const DataType & info, int pri) { Node * trav = myFirst; // used to traverse list Node * temp = new Node; // create, initialize temp->data = info; temp->priority = pri; // find where node belongs if (myFirst == NULL || pri > myFirst->priority) // special case, first node { temp->next = myFirst; myFirst = temp; } else // can look one ahead { while (trav->next != NULL && pri < trav->next->priority) { trav = trav->next; } // found where new node belongs, link it in temp->next = trav->next; trav->next = temp; } } // method 1 int Plist::FindMax(DataType & info, int & pri) const { Node * trav = myFirst; Node * max = myFirst; if (myFirst != NULL) // be safe, no NULL dereferences { trav = myFirst->next; // start at second node, max at first while (trav != NULL) { if (trav->priority > max->priority) { max = trav; } trav = trav->next; } info = max->data; // found max, set parameters pri = max->priority; } } // method 2 int Plist::FindMax(DataType & info, int & pri) const { if (myFirst != NULL) { info = myFirst->data; pri = myFirst->priority; } } bool IsChild(TreeNode * first, TreeNode * second) // precondition: second != NULL // postcondition: returns true if second is a child of first // returns false otherwise { return first && (first->left == second || first->right == second); } bool IsDescendant(TreeNode * first, TreeNode * second) // precondition: second != NULL { if (first != NULL) { if (IsChild(first,second) || IsDescendant(first->left,second) || IsDescendant(first->right,second)) { return true; } } return false; } void ChangeTree(TreeNode * & t) { if (t != NULL) { ChangeTree(t->left); // remove all one-child nodes ChangeTree(t->right); // from children if (HasOneChild(t)) { Node * temp = t; // will delete this node if (t->left != NULL) // move to to only child t = t->left; else t = t->right; delete temp; } } }

Owen L. Astrachan Last modified: Fri Apr 27 21:56:09 EDT 2001