Consider a data set of 100 items. Which of the following is a search algorithm (are search algorithms) that could possibly examine 25 items in this set before succeeding?

Linear search
Binary search

(a) I only

Consider the following C++ code fragment.

for(int i = 0; i < n; i++) {
for(int j = 0; j < n/5; j++) {
body;
}
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
(a) O(n2)

Consider the following definition of a recursive function f.

bool f(int x)
{
if((x & 1) == 1) return (x == 1);
return f(x >> 1); // right shift
}

The value returned by the call f(x) will determine whether the input x is
(c) a power of 2

Consider the following C++ function that uses a divide and conquer approach to calculate the sum of a range of numbers.

int sum(int i, int j) {
if (i == j) {
return i;
}
else {
int mid = (i+j) / 2;
int result = sum(i,mid) + sum(mid+1,j);
return result;
}
}
Which of the following lines of code from the above function divides this problem into sub-problems?
(a) int result = sum(i,mid) + sum(mid+1,j);
Consider the following definition of a recursive function, power, that will perform exponentiation.

int power(int b, int e)
{
if(e == 0) return 1;
if(e % 2 = 0) return power(b * b, e/2);
return b * power(b * b, e/2);
}

Asymptotically in terms of the exponent e, the number of calls to power that occur as a result of the call power(b,e) is
(a) logarithmic
Consider the following C++ code fragment.

for(int i = 0; i < n; i += 2) {
for(int j = i; j > 0; j -= 3) {
body
}
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
(b) O(n2)
Consider the following C++ code fragment.

for(int i = 0; i < n; i += 2) {
for(int j = 0; j < n; j += 3) {
for(int k = 0; k < n; k += 4) {
body;
}
}
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
(a) O(n3)
Consider the following C++ code fragment.

for(int i = 1; i < n; i *= 2) body;

If body executes in O(1) time, then the asymptotic running time that most closely bounds the code fragment above is
(d) O(log n)

Consider the following code fragment.

for(int i = n; i > 0; i /= 2) body;

If body executes in O(1) time, then the asymptotic running time that most closely bounds the fragment is
(c) O(log n)
Consider the following outline of a template sorting function.

template<class T> void sort(T a[], int n) {... }

For a given sorting algorithm S, which of the following is true about using this outline to implement S?
(c) It is a reasonable way to implement S.
Consider the following partial C++ templated class definition.

template<typename A, typename B>
class...
The line of code template<typename A, typename B> will generally be followed by
(d) a class definition containing the generic type parameters A and B.
Consider the following template swap function and data types.

template<typename T> void swap(T& a, T& b){
T tmp = a; a = b; b = tmp;
}
char c1, c2;
int i1, i2;
float A[10];
Which of the following calls to swap produces a compile time error?

swap(i1, c2)
swap(c1, i2);
swap(A[5], A[2]);
(d) I and II
Consider the following C++ program segment:

try {
throw out_of_range("out of range");
}
catch (logic_error& e) {
cout << e.what();
}
catch (...) {
cout << "exception encountered";
}
The above program segment will output which of the following character strings?
(a) "out of range"
Consider the following outline of a template array class.

template<typename T> class Array {... }
Which of the following is true about using this outline to implement a general container class?
(c) It is a reasonable way to implement such a class.
Consider the following template swap function.

template<typename T> void swap(T& a, T& b){
T tmp = a; a = b; b = tmp;
}
Determining the right choice of type parameter T occurs at which of the following times?
(a) Compile time only
Consider the following inheritance declarations.

class Base { public: int x; private: int y; }; class Derived: public Base { public: int z; }; Derived D;

Under these declarations, which of the following statements, if any, will fail to compile?

(c) D.y = 555;

 

Consider the following partial C++ template class definition.

template<typename T> class Array { public: T& operator[](int i) {return arr[i];}... private: int len; T *arr; };

Which of the following is a (are) correct template instantiation(s)?

I.Array<int> A;

II.Array<double> A;

III.Array<Array<int> > A;

(d) I, II, and III

Consider the following template swap function and data types.

template<typename T> void swap(T& a, T& b){ T tmp = a; a = b; b = tmp; } char c1, c2; int i1, i2; float A[10];

Which of the following calls to swap produces a compile time error?

I.swap(i1, c2)

II.swap(c1, i2);

III.swap(A[5], A[2]);

(b) I and II
Consider the following program fragment that calls the method count_if in the C++ Standard Template Library.

deque<int> numbers;
...
count_if(numbers.begin(), numbers.end(), is_odd);
Which of the following declarations for the method is_odd is correct for the call to count_if?
(a) bool is_odd(int i);
Consider the following C++ program fragment.

vector<int> A(10);
A.push_back(5000);
At the end of an execution of this fragment, the size of vector A is
(c) 11
Consider the following definition of a recursive function f.

int f(int x)
{
if(x == 0) return 1;
return x * f(x);
}

For which inputs x will the call f(x) terminate?
(a) For x = 0 only
Consider the execution of the following.

vector<int> A(10,20);
Which of the following accurately describes what is created?
(d) An array of 10 ints, each initialized to 20
Consider the function defined as follows.

int f(int n)
{
if(n == 0) return 0;
if((n & 1) == 0) return f(n/2);
return f(n/2) + 1;
}

The value returned by the call f(10); is
(c) 2
Consider the following definition of a recursive function ff.

int ff(int n)
{
if(n == 0) return 1;
return 2 * ff(n - 1);
}

If n > 0, what is returned by ff(n)?
(d) 2n

Consider the following definition of a recursive function ff in C++.

int ff(int n, int m)
{
if(n == 0) return m;
return ff(n - 1, m + 1);
}
Which of the following characterizes the value returned by the call f(n,m)?
(a) The sum of m and n
Consider the following C++ program fragment, which is a partial declaration of the class string.

class string {
public:
string(const char* cstring = "");
bool operator== (const string & rhs);
...
};
Given this class and two string objects called s1 and s2, which of the following is not a legal statement?
(c) bool ans = ("hello" == s1);
Consider the following declaration that makes use of a user-defined class Thing.

vector<Thing> A(10);
In order that it compile, the class Thing must have which of the following?
(d) a default constructor
Consider the following C++ program segment, assuming that string is a class.

string str1("Hello, World");
str1[5] = 'Z';
The overloaded operator[] function invoked in the above program segment should have which of the following return types?
(d) char &
Consider the following C++ program segment, which uses the STL.

stack<int,vector<int> > S;

Execution of the statement results in creation of which of the following?
(a) A stack of integers
Consider the execution of the following.

list<int> A(10,20);

Which of the following accurately describes what is created?
(c) A linked list of 10 ints, with each element initially 20
Consider the following sequence of operations applied to an empty queue:

Insert element with value 3
Insert element with value 8
Remove element
Insert element with value 1
Remove element
Insert element with value 7

The next element removed from this queue will have which of the following values?
(b) 1
Consider the following C++ code segment intended to traverse the list L in reverse order.

list<int>::iterator it;
for(it = L.end(); it!= L.begin(); --it) {
cout << *it << endl;
}

The code segment will not serve the intended purpose because
(d) an attempt is made to access a non-existing list element

Consider the following C++ program segment, which uses the STL.

stack<int> X;
X.push(2);
X.push(14);
X.pop();
X.push(37);
X.push(40);
X.pop();
cout << X.top();
What is the output when this program segment is executed?
(c) 37
Consider the following code fragment, where L is a linked list of integers.

for(it = L.begin(); it!= L.end(); ++it)
*it += 10;

Execution of this fragment has the effect of
(d) adding 10 to each list element

D

Decomposition of a problem involves which of the following?
(c) Identifying entities and relationships that will aid in solving the problem
Differences between the STL adapter queue and the STL container deque include which of the following?

queue provides support for iterators, whereas deque does not.
queue provides access to only the first and last elements in a collection, whereas deque permits access to an entire collection.
(b) II only
Djikstra's algorithm may be used to find the _____ path in a graph that contains edges with _____ weights.
(c) shortest, only positive
Dijkstra's algorithm and the Bellman-Ford algorithm both determine
(c) the shortest path between two nodes in a graph
During a failed search for an element in a completely balanced binary search tree of size 1,000,000, approximately how many nodes of the tree are visited?
(a) 20

 

E

 

Each of the following is a basic C++ type except
(c) byte
Each of the following C++ code fragments produces a memory leak except:
(b) int *A = new int[10]; delete [] A;
Execution of which of the following statements sets an STL iterator it so that it points to the first element of a container A?
(d) it = A.begin();
Each of the following indicates a reasonable way to implement graphs except
(c) a binary search tree

 

F

 

For an STL iterator it, execution of the statement

it--;
does which of the following?
(d) Steps the iterator backwards to the previous item.