AP Computer Science 1995 Exam, Free-response in C++

# AP Computer Science1995 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 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

### A exam

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 Name
```
part 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```

Problem 2

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.

void ReverseArray(apvector<int> & a, int numElts) // precondition: numElts = # of entries in a // postcondition: elements of a are reversed

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.

void ReverseVertical(apmatrix<int> & m, int col) // precondition: 0 <= col < m.numcols() // the number of rows in m is m.numrows()

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.

void ReverseMatrix(apmatrix<int> & m) // precondition: m.numrows() == m.numcols()

Problem 3 Case Study problem
Problem 4

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.

int SumSeq(Sequence s) // postcondition: returns sum of all entries in s { int sum = 0; s.SetToFirst(); while (! s.IsEnded()) { sum += s.CurrentValue(); s.Advance(); } return sum; }
class Sequence { public: Sequence(); // default constructor bool IsEnded(); // precondition: current position is c // postcondition: returns true if c is invalid; // otherwise, returns false int CurrentValue(); // precondition: current position is c, which is valid // postcondition: returns value at position c void Advance(); // precondition: current position is c, sequence has m elements // postcondition: if 1 <= c < m, then current position = c+1 // if c == m, then current position is invalid void SetToFirst(); // postcondition: current position is first position <other member functions> private: <appropriate declarations> }; part A

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}
```

### AB exam

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 deleted```
part 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)`

### Answers to C++ Free-response questions

```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++;
}
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();
while (! s.IsEnded() && lastVal < s.CurrentValue())
{
length++;
lastVal = s.CurrentValue();
}
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