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 LaTeX2HTML 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:
Name CommaPosition(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 Namepart B
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 in Name then nothing is printed; otherwise, PrintFirstLast should print all characters after the comma, if any, followed by a space, followed by all characters before the comma, if any.
For example:
Name Output of PrintFirstLast
W,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 to ReverseArray(a,5) After call to ReverseArray(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 to ReverseVertical(m,2) After call to ReverseVertical(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 | +----+----+----+----+ +----+----+----+----+
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 to ReverseMatrix(m) After call to ReverseMatrix(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 | +----+----+----+----+ +----+----+----+----+
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).)
IsEnded returns true if the current position is invalid;
otherwise, returns false.
SetToFirst sets the current position to be the first position
CurrentValue returns the integer value at the current position.
It is an error to make this call when the sequence is ended.
Advance It is an error to call Advance when 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
when Advance was 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 *)
Sequence s Increasing Segment LenOfIncreasing(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.
Function Description Plist constructs and initializes an empty priority list IsEmpty returns true if the priority list is empty; otherwise returns false Insert(info,pri) inserts item with data info and priority pri FindMax(info,pri) sets info and prio to the data and priority of the maximal item DeleteMax deletes 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 deletedpart A
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;
}
}
}