int BB(int n){
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n % 2) return 1 + BB(n / 2);
	return BB(n / 2);
}

n in Decimal	n in Binary	BB(n)
2
5
8
13
31

b. What does BB compute?

Problem 2: Consider the following code

void main(){
	int N = 100;
	int* A = new int[N];        		//a.
	for (int i = 0; i < N; i++)     	//b.
		A[i] = RandomLong(1, 1000); 

	cout << Search(A, 100, 500);     	//c.
}

int Search(int A[], int size, int key){  	//d.
	for (int i = 0; i < size; i++)
	if (A[i] == key) return i;
	return -1;
}

• a.( 2 points) What is A and why is it declared this way?

• b.( 2 points) What is the purpose of this loop?

• c.( 2 points) What possible values might be printed by this statement?
  What do they mean?

• d.(9 points) What are the minimum, maximum, and average number of compares executed when this function is called?

Explain your answers.

Last Updated: April 19, 1997 2:52 pm by