1(10 points) Given the function:

int see(int k, int A[], int lower, int upper){
// precondition:  lower and upper are valid indexes in A
// postcondition:  returns the positon of the value k in A
//                 returns -1 if k is not in A
//                 A is left unghanged

	cout << lower << "   " << upper <<  endl;
	if ((upper - lower) < 0) return -1;
	int N = (lower + upper)/2;
	if (A[N] == k) return N;
	if (A[N] > k) return see(k, A, lower, N - 1);
	return see(k, A, N + 1, upper);
}

int A[10] = {9, 11, 14, 23, 34, 39, 42, 61, 75, 88};
cout << see(34, A, 0, 9) << endl;
cout << see(75, A, 0, 9) << endl;
cout << see( 6, A, 0, 9) << endl;
cout << see(25, A, 0, 9) << endl;

Output:		Comments:
0   9      N=4	A[N]=34 == 34
4
0   9      N=4	A[N]=34 < 75
5   9      N=7	A[N]=61 < 75
8   9      N=8	A[N]=75 == 75
8
0   9      N=4	A[N]=34 > 6
0   3      N=1	A[N]=11 > 6
0   0      N=0	A[N]=9 > 6
0   -1	    upper - lower < 0
-1
0   9      N=4	A[N]=34 > 25
0   3      N=1	A[N]=11 < 25
2   3      N=2	A[N]=14 < 25
3   3      N=4	A[N]=23 < 25
4   3      upper - lower < 0

b. Write the postcondition for the function
See above.

2 (5 points) The picture at the right is the 14th level of the Gosper C Curve. It is given by the grammar:

Turning angle: 90
S -> F+F
F -> F+F-

Show the string and corresponding drawing for levels 1 and 2.

Don't worry about the orientation.

3 (5 points) Given the function:

void makeLL(Node* & head, Node* & tail){
	long L = 0;
	Node* extra;
	while (ReadingLong("enter int: ",L)){
		extra = new Node;
		extra->data = L;
		if (L % 2) {
			extra->next = head;
			head = extra;
			if (!tail) tail = head;
		}
		else 
		{
			extra->next = Null;
			// for more general use, the next line should read:
			// if (tail tail->next = extra;
			tail->next = extra;
			tail = extra;
			if (!head) head = tail;
		};
	};
};

Node* head = Null;
Node* tail = Null;
makeLL(head, tail);

enter int:  3
enter int:  5
enter int:  6
enter int:  4
enter int:  7
enter int:         // return was pressed here

The code makes a single linked list. The odd numbers are inserted at the head and the even numbers at the tail.

Last Updated: May 11, 1997 11:53 am by