Prerequisite Concepts for Analysis of Algorithms
Basic Data Structures (Version 7)
Printable Version
Concept: mathematics notation

${\mathrm{log}}_{2}n$ is:
 $\omega \left({\mathrm{log}}_{10}n\right)$
 $o\left({\mathrm{log}}_{10}n\right)$
 $\Theta \left({\mathrm{log}}_{10}n\right)$

${\mathrm{log}}_{2}n$ is equal to:
 $\genfrac{}{}{0.1ex}{}{{\mathrm{log}}_{2}n}{{\mathrm{log}}_{10}2}$
 $\genfrac{}{}{0.1ex}{}{{\mathrm{log}}_{2}n}{{\mathrm{log}}_{2}10}$
 $\genfrac{}{}{0.1ex}{}{{\mathrm{log}}_{10}n}{{\mathrm{log}}_{10}2}$
 $\genfrac{}{}{0.1ex}{}{{\mathrm{log}}_{10}n}{{\mathrm{log}}_{2}10}$

$\mathrm{log}\left(nm\right)$ is equal to:
 $m\mathrm{log}n$
 ${\left(\mathrm{log}n\right)}^{m}$
 $\mathrm{log}n+\mathrm{log}m$
 $n\mathrm{log}m$

$\mathrm{log}\left({n}^{m}\right)$ is equal to:
 $n\mathrm{log}m$
 ${\left(\mathrm{log}n\right)}^{m}$
 $\mathrm{log}n+\mathrm{log}m$
 $m\mathrm{log}n$

${\mathrm{log}}_{2}2$ can be simplified to:
 2
 ${\mathrm{log}}_{2}2$ cannot be simplified any further
 4
 1

${2}^{{\mathrm{log}}_{2}n}$ is equal to:
 ${n}^{2}$
 ${\mathrm{log}}_{2}n$
 n
 ${2}^{n}$

${n}^{2}$ is $o\left({n}^{3}\right)$. Therefore, $\mathrm{log}{n}^{2}$ is $?\left(\mathrm{log}{n}^{3}\right)$.
Choose the tightest bound.
 little omicron
 little omega
 theta
 big omega
 big omicron

$\mathrm{log}{n}^{n}$ is $\Theta (?)$.
 log ${n}^{\mathrm{log}n}$
 log n
 n log n
 n

$\mathrm{log}{2}^{n}$ is $\Theta (?)$.
 ${2}^{n}$
 $n\mathrm{log}n$
 $\mathrm{log}n$
 n

The number of permutations of a list of n items is:
 ${2}^{n}$
 n!
 $n\mathrm{log}n$
 $\mathrm{log}n$
 n
Concept: relative growth rates

What is the correct ordering of growth rates for the following functions:

$f\left(n\right)={n}^{0.9}\mathrm{log}n$

$g\left(n\right)=1.{1}^{n}$

$h\left(n\right)=9.9n$
 f < h < g
 g < f < h
 h < f < g
 g < h < f
 f < g < h
 h < g < f

What is the correct ordering of growth rates for the following functions:

$f\left(n\right)=n{\left(\mathrm{log}n\right)}^{2}$

$g\left(n\right)=n\mathrm{log}{2}^{n}$

$h\left(n\right)=n\mathrm{log}\left(\mathrm{log}n\right)$
 g > f > h
 h > g > f
 f > h > g
 h > f > g
 g > h > f
 f > g > h
Concept: order notation

What does big Omicron roughly mean?
 worse than
 better than
 worse than or the same as
 better than or the same as
 the same as

What does $\omega $ roughly mean?
 worse than or the same as
 better than
 the same as
 better than or the same as
 worse than

What does $\theta $ roughly mean?
 the same as
 worse than
 better than or the same as
 worse than or the same as
 better than

T or F:
All algorithms are $\omega \left(1\right)$.

T or F:
All algorithms are $\theta \left(1\right)$.

T or F:
All algorithms are $\Omega \left(1\right)$.

T or F:
There exist algorithms that are $\omega \left(1\right)$.

T or F:
There exist algorithms that are $O\left(1\right)$.

T or F:
All algorithms are $O\left({n}^{n}\right)$.

Consider sorting 1,000,000 numbers with mergesort. What
is the time complexity of this operation? [THINK!]
 constant, because n is fixed
 ${n}^{2}$, because mergesort takes quadratic time
 n log n, because mergesort takes n log n time
Concept: comparing algorithms using order notation
The phrase by a stopwatch means
the actual amount of time needed for the algorithm to run to
completion, as measured by a stopwatch.

T or F:
If $f=\omega \left(g\right)$, then
algorithm f always runs faster than g (by a stopwatch), in all cases.

T or F:
If $f=\omega \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always runs faster than g (by a stopwatch),
regardless of input size.

T or F:
If $f=\omega \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always runs faster than g (by a stopwatch),
above a certain input size.

T or F:
If $f=\omega \left(g\right)$, then
algorithm f always runs faster than g (by a stopwatch),
above a certain input size.

T or F:
If $f=\theta \left(g\right)$, then
algorithm f always takes the same time as g (by a stopwatch),
in all cases.

T or F:
If $f=\theta \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always takes the same time as g (by a stopwatch),
regardless of input size.

T or F:
If $f=\theta \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always takes the same time as g (by a stopwatch),
above a certain input size.

T or F:
If $f=\theta \left(g\right)$, then
algorithm f always takes the same time as g (by a stopwatch),
above a certain input size.

T or F:
If $f=\theta \left(g\right)$, then
algorithm f always takes the same time as g (within a constant factor),
in all cases.

T or F:
If $f=\theta \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always takes the same time as g (within a constant factor),
regardless of input size.

T or F:
If $f=\theta \left(g\right)$ and the input causes worstcase behaviors, then
algorithm f always takes the same time as g (within a constant factor),
above a certain input size.

T or F:
If $f=\theta \left(g\right)$, then
algorithm f always takes the same time as g (within a constant factor),
above a certain input size.

T or F:
If $f=\omega \left(g\right)$, then
f and g can be the same algorithm.

T or F:
If $f=\Omega \left(g\right)$, then
f and g can be the same algorithm.

T or F:
If $f=o\left(g\right)$, then
f and g can be the same algorithm.

T or F:
If $f=O\left(g\right)$, then
f and g can be the same algorithm.

T or F:
Suppose algorithm $f=\theta \left(g\right)$.
f and g can be the same algorithm.

T or F:
If $f=\Omega \left(g\right)$ and $g=O\left(f\right)$,
then $f=\Theta \left(g\right)$.

T or F:
If $f=\Omega \left(g\right)$ and $g=O\left(f\right)$,
then f and g must be the same algorithm.
Concept: analyzing code
In the pseudocode, the lower limit of a
for
loop
is inclusive, while the upper limit is exclusive.
The additive step, if not specified, is one.
Tracing recursive functions
When asked about the number of recursive calls, do not include
the original call.

How many recursive calls are made if $n=5$?
Assume the initial value of i is zero.
function f(i,n)
{
if (i < n)
{
println(i);
f(i+1,n);
}
return 0;
}
 3
 4
 the function recurs infinitely
 6
 none of the other answers are correct
 5

How many recursive calls are made if $n=81$.
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
println(i);
f(i*3,n);
}
return 0;
}
 the function recurs infinitely
 none of the other answers are correct
 3
 4
 5
 6

How many recursive calls are made if $n=64$.
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
println(i);
f(i*sqrt(n),n);
}
return 0;
}
 none of the other answers are correct
 4
 7
 9
 2
 1
 8
 the function recurs infinitely

How many recursive calls are made if $n=64$.
Assume the initial value of i is zero.
function f(i,n)
{
if (i < n)
{
println(i);
f(i+sqrt(n),n);
}
return 0;
}
 the function recurs infinitely
 2
 1
 9
 7
 none of the other answers are correct
 8
 4
Time complexity, recursive functions, single recursion

What is the time complexity of this function?
Assume the initial value of i is zero.
function f(i,n)
{
if (i < n)
{
println(i);
f(i+1,n);
}
return 0;
}
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(1\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$

What is the time complexity of this function?
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
println(i);
f(i*3,n);
}
return 0;
}
 $\theta \left({\left(\mathrm{log}n\right)}^{3}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$

What is the time complexity of this function?
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
f(i*sqrt(n),n);
println(i);
}
}
 $\theta \left(n\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(1\right)$
 $\theta \left(n\sqrt{n}\right)$

What is the time complexity of this function?
Assume positive, integral input and integer division.
function f(n)
{
if (n > 0)
{
for (var i from 0 until n)
println(n);
f(n/2);
}
return 0;
}
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\sqrt{n}\right)$
Time complexity, recursive functions, double recursion
Space complexity, recursive functions, single recursion

What is the space complexity of this function?
Assume positive, integral input and integer division.
function f(x,n)
{
if (x > 0)
{
f(x/2,n);
for (var i from 0 until n)
println(n);
}
}
 $\theta \left(1\right)$
 $\theta \left(n\mathrm{log}x\right)$
 $\theta \left(\mathrm{log}x\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta (x/2)$
 $\theta \left(nx\right)$
 $\theta \left(n\right)$
 $\theta \left(x\right)$

What is the space complexity of this function?
Assume the initial value of i is zero.
function f(i,n)
{
if (i < n)
{
f(i+2,n);
println(i);
}
}
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(1\right)$

What is the space complexity of this function?
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
f(i*3,n);
println(i);
}
}
 $\theta \left({n}^{2}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(1\right)$

What is the space complexity of this function?
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
f(i*sqrt(n),n);
println(i);
}
}
 $\theta (n\sqrt{n})$
 $\theta \left(n\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$

What is the space complexity of this function?
Assume the initial value of i is one.
function f(i,n)
{
if (i < n)
{
f(i+sqrt(n),n);
println(i);
}
}
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta (n\sqrt{n})$
 $\theta \left(n\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\sqrt{n}\right)$
Space complexity, recursive functions, double recursion
Time complexity, iterative loops, single loops

What is the time complexity of this code fragment?
for (i from 0 until n by 1)
println(i);
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left({n}^{\sqrt{n}}\right)$

What is the time complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * 2;
}
 $\theta \left({\left(\mathrm{log}n\right)}^{2}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\mathrm{log}n\right)$

What is the time complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * sqrt(n);
}
 $\theta \left(n\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta (n\sqrt{n})$
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left(\sqrt{n}\right)$
Time complexity, iterative loops, double loops

What is the time complexity of this code fragment?
for (i from 0 until n by 1)
for (j from 0 until i by 1)
println(i,j);
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(1\right)$

What is the time complexity of this code fragment?
i = 1;
while (i < n)
{
for (j from 0 until n by 1)
println(i,j);
i = i * 2;
}
 $\theta \left({n}^{2}\right)$
 $\theta \left(1\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$

What is the time complexity of this code fragment?
i = 1;
while (i < n)
{
for (j from 0 until i by 1)
println(i,j);
i = i * 2;
}
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(n\mathrm{log}n\right)$

What is the time complexity of this code fragment?
for (i from 0 until n)
{
j = 1;
while (j < n)
{
println(i,j);
j = j * 2;
}
}
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$

What is the time complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * 2;
}
for (j from 0 until n by 2)
println(j);
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left(n\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left({n}^{2}\right)$

What is the time complexity of this code fragment?
for (i from 0 until n by 2)
println(i);
for (j from 0 until n by 1)
println(j);
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(1\right)$

What is the time complexity of this code fragment?
for (i from 0 until n by 1)
println(i);
j = 1;
while (j < n)
{
println(j);
j = j * 2;
}
 $\theta \left(n\right)$
 $\theta \left(n\sqrt{n}\right)$
 $\theta \left({\mathrm{log}}^{2}n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(1\right)$
Space complexity, iterative loops, single loops

What is the space complexity of this code fragment?
for (i from 0 until n by 1)
println(i);
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(1\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$

What is the space complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * sqrt(n);
}
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$

What is the space complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * 2;
}
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$
Space complexity, iterative loops, double loops

What is the space complexity of this code fragment?
for (i from 0 until n by 1)
println(i);
for (j from 0 until n by 1)
println(j);
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(1\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(\mathrm{log}n\right)$

What is the space complexity of this code fragment?
i = 1;
while (i < n)
{
println(i);
i = i * 2;
}
for (j from 0 until n by 1)
println(j);
 $\theta \left(1\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$

What is the space complexity of this code fragment?
for (i from 0 until n by 1)
println(i);
j = 1;
while (j < n)
{
println(j);
j = j * 2;
}
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(1\right)$
 $\theta \left({n}^{2}\right)$

What is the space complexity of this code fragment?
for (i from 0 until n by 1)
for (j from 0 until i by 1)
println(i,j);
 $\theta \left(n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left(\mathrm{log}n\right)$

What is the space complexity of this code fragment?
i = 1;
while (i < n)
{
for (j from 0 until i by 1)
println(i,j);
i = i * 2;
}
 $\theta \left(\sqrt{n}\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(1\right)$

What is the space complexity of this code fragment?
for (i from 0 until n)
{
j = 1;
while (j < n)
{
println(i,j);
j = j * 2;
}
}
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left({n}^{2}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$

What is the space complexity of this code fragment?
i = 1;
while (i < n)
{
for (j from 0 until n by 1)
println(i,j);
i = i * 2;
}
 $\theta \left({n}^{2}\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(\sqrt{n}\right)$
Concept: analysis of classic, simple algorithms

Which of the following describes the classic recursive fibonacci's time complexity?
 $\theta \left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta (n\sqrt{n})$
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(\Phi \right)$
 $\theta \left(1\right)$
 $\theta \left(\genfrac{}{}{0.1ex}{}{\Phi}{n}\right)$
 $\theta \left({\Phi}^{n}\right)$

Which of the following describes the classic recursive fibonacci's space complexity?
 $\theta \left(\sqrt{n}\right)$
 $\theta \left(1\right)$
 $\theta (n\sqrt{n})$
 $\theta \left(n\right)$
 $\theta \left(\genfrac{}{}{0.1ex}{}{\Phi}{n}\right)$
 $\theta \left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$

Which of the following describes iterative factorial's time complexity?
 $\theta \left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta (n\sqrt{n})$
 $\theta \left(\genfrac{}{}{0.1ex}{}{\Phi}{n}\right)$
 $\theta \left(1\right)$
 $\theta \left(n\right)$

Which of the following describes iterative fibonacci's space complexity?
 $\theta \left(1\right)$
 $\theta \left(n\right)$
 $\theta \left(\genfrac{}{}{0.1ex}{}{\Phi}{n}\right)$
 $\theta \left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{n}}\right)$
 $\theta \left(\sqrt{n}\right)$
 $\theta (n\sqrt{n})$
Concept: searching

T or F:
The following code reliably sets the variable min to
the minimum value of an unsorted, nonempty array.
min = 0;
for (i from 0 until array.length)
if (array[i] < min)
min = array[i];

T or F:
The following code reliably sets the variable max to
the maximum value in an unsorted, nonempty array.
max = array[0]
for (i from 0 to array.length)
if (array[i] > max)
max = array[i]

T or F:
The following function reliably returns
True
if the value of item is present in the unsorted,
nonempty array.
function find(array,item)
{
found = False;
for (i from 0 until array.length)
if (array[i] == item)
found = True;
return found;
}

T or F:
The following function reliably returns
False
if the value of item is missing in the unsorted,
nonempty array.
function find(array,item)
{
found = True;
for (i from 0 unitl array.length)
if (array[i] != item)
found = False;
return found;
}

What is the average and worst case time complexity, respectively,
for searching an unordered list?
 log, log
 linear, log,
 log, linear
 linear, linear

What is the average and worst case time complexity, respectively,
for searching an ordered list?
 log, log
 linear, log
 log, linear
 linear, linear
Concept: sorting

The following strategy is employed by which sort:
find the most extreme value in the unsorted portion
and place it at the boundary of the sorted and unsorted
portions?
 bubble sort
 selection sort
 mergesort
 quicksort
 insertion sort
 heapsort

The following strategy is employed by which sort:
sort the lower half of the items to be sorted, then sort the upper half,
then arrange things such that the largest item in the lower half
is less than or equal to the smallest item in the upper half ?
 selection sort
 heapsort
 bubble sort
 insertion sort
 mergesort
 quicksort

The following strategy is employed by which sort:
take the first value in the unsorted portion and place it
where it belongs in the sorted portion?
 heapsort
 bubble sort
 quicksort
 mergesort
 insertion sort
 selection sort

The following strategy is employed by which sort:
pick a value and arrange things such that
the largest item in the lower portion is
less than or equal to the value and that
the smallest item in the upper portion is
greater than or equal to the value,
then sort the lower portion, then sort the upper ?
 insertion sort
 bubble sort
 selection sort
 heapsort
 mergesort
 quicksort

Which sort optimizes the worst case behavior of bubble sort?
 selection sort
 insertion sort
 heapsort
 stooge sort
 quicksort
 mergesort
Concept: space and time complexity

What is the best time case complexity for classical mergesort?
 cubic
 linear
 quadratic
 n log n
 log n

What is the worst case complexity for classical mergesort?
 log n
 cubic
 linear
 n log n
 quadratic

If quicksort is implemented such that the
pivot is chosen to be the first element in the array,
the worst case behavior of the sort is:
 quadratic
 linear
 exponential
 log linear

If quicksort is implemented such that the
a random element is chosen to be the pivot,
the worst case behavior of the sort is:
 linear
 exponential
 log linear
 quadratic

What is the best case complexity for quicksort?
 cubic
 n log n
 log n
 linear
 quadratic

What is the best case complexity for classical selection sort?
 n log n
 quadratic
 log n
 cubic
 linear

What is the worst case complexity for classical selection sort?
 linear
 quadratic
 n log n
 log n
 cubic

What is the best case complexity for classical insertion sort?
 linear
 n log n
 log n
 quadratic
 cubic

What is the worst case complexity for classical insertion sort?
 log n
 n log n
 quadratic
 cubic
 linear
Concept: simple arrays
Assume zerobased indexing for all arrays.
In the pseudocode, the lower limit of a
for
loop
is inclusive, while the upper limit is exclusive.
The step, if not specified, is one.
For all types of fillable arrays, the size is the number of elements
added to the array; the capacity is the maximum
number of elements that can be added to the array.

Consider a small array a and large array b.
Accessing the element in the first slot
of a takes more/less/the same amount of
time as accessing the element in the first slot of b.
 more time
 it depends on how the arrays were allocated
 less time
 the same amount of time

Consider a small array a and large array b.
Accessing the element in the last slot of a b takes
more than/less than/the same amount of time as accessing an element in
the middle slot of a. Both indices are supplied.
 more time
 it depends on how the arrays were allocated
 less time
 the same amount of time

Accessing the middle element of an array takes more/less/the same
amount of time than accessing the last element.
 less time
 the same amount of time
 it depends on how the array were allocated
 more time

What is a major characteristic of a simple array?
 inserting an element between indices i and i+1can be done in constant time
 getting the value at an index can be done in constant time
 finding an element can be done in constant time

What is a not a major characteristic of a simple array?
 finding an element can be done in constant time
 setting the value at an index can be done in constant time
 swapping two elements can be done in constant time
 getting the value at an index can be done in constant time

Does the following code set the variable v to
the minimum value in an unsorted array
with at least two elements?
v = 0;
for (i from 0 until array.length)
if (array[i] < v)
v = array[i];
 yes, if all the elements are positive
 yes, if all the elements are negative
 always
 only if the true minimum value is zero
 only if all elements have the same value
 never

Does the following code set the variable v to
the minimum value in an unsorted array
with at least two elements?
v = array[0];
for (i from 0 until array.length)
if (array[i] < v)
v = array[i];
 yes, if all the elements are negative
 only if all elements have the same value
 yes, if all the elements are positive
 never
 only if the true minimum value is at index 0
 always

Does the following code set the variable v to
the minimum value in an unsorted array
with at least two elements?
v = array[0];
for (i from 0 until array.length)
if (array[i] > v)
v = array[i];
 only if all elements have the same value
 never
 yes, if all the elements are positive
 only if the true minimum value is at index 0
 yes, if all the elements are negative
 always

Does the following code set the variable v to
the minimum value in an unsorted, nonempty array?
v = array[0];
for (i from 0 until array.length)
if (array[i] > v)
v = array[i];
 only if the true minimum value is at index 0
 never
 only if all elements have the same value
 yes, if all the elements are positive
 always
 yes, if all the elements are negative

Does this find function return the expected result?
Assume the array has at least two elements.
function find(array,item)
{
var i; var found = False;
for (i from 0 until array.length)
if (array[i] == item)
found = True;
return found;
}
 never
 always
 only if the item is not in the array
 only if the item is in the array

Does this find function return the expected result?
Assume the array has at least two elements.
function find(array,item)
{
var i;
for (i from 0 until array.length)
if (array[i] == item)
return False;
return True;
}
 never
 only if the item is in the array
 always
 only if the item is not in the array

Is this find function correct?
Assume the array has at least two elements.
function find(array,item)
{
var i; var found = True;
for (i from 0 until array.length)
if (array[i] != item)
found = False;
return found;
}
 never
 only if the item is in the array
 only if the item is not in the array
 always

Does this find function return the expected result?
Assume the array has at least two elements.
function find(array,item)
{
var i;
for (i from 0 until array.length)
if (array[i] == item)
return True;
return False;
}
 only if the item is in the array
 never
 always
 only if the item is not in the array
Concept: simple fillable arrays
Assume the back index in a simple fillable array
points to the first available slot.

What is not a property of a simple fillable array?
 elements are presumed to be contiguous
 there exists an element that can be removed in constant time
 elements can be added in constant time
 the underlying simple array can increase in size

What is a property of a simple fillable array?
 more that one element can be next to an empty slot
 an element can be added anywhere in constant time
 any element can be removed in constant time
 elements are presumed to be contiguous

Adding an element at back of a simple fillable
array can be done in:
 linear time
 constant time
 quadratic time
 logarithmic time

Removing an element at front of a simple fillable
array can be done in:
 constant time
 quadratic time
 logarithmic time
 linear time

Suppose a simple fillable array has size s and capacity c.
The next value to be added to the array will be placed at index:
 c + 1
 s + 1
 s
 c
 c  1
 s  1

Suppose for a simple fillable array,
the size is one less than the capacity.
How many values can still be added?
 two
 this situation cannot exist
 zero, the array is full
 one

Suppose for a simple fillable array,
the capacity is one less than the size.
How many values can still be added?
 two
 this situation cannot exist
 one
 zero, the array is full

Suppose a simple fillable array is empty.
The size of the array is:
 one
 the capacity of the array
 the length of the underlying simple array
 zero

Suppose a simple fillable array is full.
The capacity of the array is:
 its size minus one
 the length of the underlying simple array
 one
 zero

Which code fragment correctly inserts a new element into
index j of a simple fillable array with size s? Assume there is room
for the new element.
for (i from j until s2)
array[i] = array[i+1];
array[i] = newElement;

for (i from s2 until j)
array[i+1] = array[i];
array[i] = newElement;
 both are correct
 neither are correct
 the second fragment
 the first fragment

Which code fragment correctly inserts a new element into
index j of an array with size s?
for (i from j until s2)
array[i+1] = array[i];
array[i] = newElement;

for (i from s2 until j)
array[i] = array[i+1];
array[i] = newElement;
 neither are correct
 the first fragment
 the second fragment
 both are correct
Concept: circular arrays
For circular arrays, assume f is the start index, e is the
end index, s is the
size, and c is the capacity of the array. Both f and e
point to the first available slots.

What is a property of a theoretical (not practical) circular array?
 any element can be removed in constant time
 elements do not have to be contiguous
 an element can be added anywhere in constant time
 there are two places an element can be added

What is not a property of a theoretical (not practical) circular array?
 inserting an element in the middle can be done in constant time
 appending an element can be done in constant time
 prepending an element can be done in constant time
 elements are presumed to be contiguous

The next value to be added to the front of a circular
array will be placed at index:
 s  f
 f  1
 f
 c  f
 c  1
 s + f

Suppose for a circular array,
the size is equal to the capacity. Can a value be added?
 No, the array is completely full
 Yes, there is room for one more value

Suppose a circular array is empty. The size of the array is:
 the length of the array
 zero
 the capacity of the array
 one

In a circular array,
which is not a proper way to correct the start index f after
an element is added to the front of the array?

f = 1; f == 0? c  1 : f;

if (f == 0) f = c  1; else f = f  1;

f = f == 0? c  1 : f  1;

f = 1; f = f < 0? c  1 : f;

f = (f  1 + c) % c;

T or F:
In a circular array, the start index (after correction)
can never equal the size of the array.

T or F:
In a circular array, the start index (after correction)
can never equal the capacity of the array.

Is a separate end index e needed in a circular array?
 no, it can be computed from s, c, and f.
 no, it can be computed from s and f.
 no, it can be computed from c and f.
 no, it can be computed from s and c.
 yes
Concept: dynamic arrays

What is not a major characteristic of a dynamic array?
 elements are presumed to be contiguous
 the array can grow to accommodate more elements
 the only allowed way to grow is doubling the size
 finding an element takes at most linear time
 inserting an element in the middle takes linear time

Suppose a dynamic array has size s and capacity c,
with s equal to c. Is the array required to grow
on the next addition?
 no
 yes
 yes, but only if the dynamic array is not circular

Suppose array capacity grows by 50%
every time a dynamic array fills.
If the only events are insertions, the growing events:
 occur more and more frequently
 occur less and less frequently
 occur periodically
 cannot be characterized in terms of frequency

Suppose array capacity doubles
every time a dynamic array fills,
If the only events are insertions,
the average cost of an insertion, in the limit, is:
 linear
 constant
 the log of the size
 the log of the capacity

Suppose array capacity grows by 10
every time a dynamic array fills,
If the only events are insertions,
the average cost of an insertion, in the limit, is:
 the log of the size
 constant
 the log of the capacity
 linear
 quadratic

Suppose array capacity grows by 10
every time a dynamic array fills,
If the only events are insertions, the growing events:
 occur more and more frequently
 occur less and less frequently
 occur periodically
 cannot be characterized in terms of frequency

If array capacity grows by 10
every time a dynamic array fills,
the average cost of an insertion in the limit is:
 constant
 the log of the size
 the log of the capacity
 linear
Concept: singlylinked lists (insertions)

Appending to a singlylinked list
without a tail pointer takes:
 constant time
 n log n time
 linear time
 log time

Appending to a singlylinked list
with a tail pointer takes:
 linear time
 constant time
 n log n time
 log time

Suppose you have a pointer to a node near the end of
a long singlylinked list.
You can then insert a new node just prior in:
 log time
 n log n time
 linear time
 constant time

Suppose you have a pointer to a node near the end of
a long singlylinked list.
You can then insert a new node just after in:
 n log n time
 log time
 linear time
 constant time

Suppose you have a pointer to a node near the end of a long
singlylinked list.
You can then insert a new node just after
with as few pointer assignments as:
 1
 5
 4
 2
 3
Concept: singlylinked lists (deletions)

Removing the first item from a singlylinked list
without a tail pointer takes:
 log time
 constant time
 n log n time
 linear time

Removing the last item from a singlylinked list
with a tail pointer takes:
 n log n time
 linear time
 log time
 constant time

Removing the last item from a singlylinked list
without a tail pointer takes:
 constant time
 linear time
 log time
 n log n time

Removing the first item from a singlylinked list
with a tail pointer takes:
 constant time
 linear time
 log time
 n log n time

In a singlylinked list, you can move the tail pointer back
one node in:
 constant time
 log time
 n log n time
 linear time

Suppose you have a pointer to a node in the middle of a singlylinked list.
You can then delete that node in:
 log time
 constant time
 n log n time
 linear time
Concept: doublylinked lists (insertions)

Appending to a noncircular, doublylinked list
without a tail pointer takes:
 n log n time
 linear time
 log time
 constant time

Appending to a noncircular, doublylinked list
with a tail pointer takes:
 log time
 n log n time
 linear time
 constant time

Removing the first item from a noncircular, doublylinked list
without a tail pointer takes:
 linear time
 log time
 constant time
 n log n time

Suppose you have a pointer to a node in the middle of a doublylinked list.
You can then insert a new node just after in:
 constant time
 n log n time
 linear time
 log time

Suppose you have a pointer to a node in the middle of a doublylinked list.
You can then insert a new node just prior
with as few pointer assignments as:
 4
 3
 5
 1
 2

T : F:
Making a doublylinked list circular
removes the need for a separate tail pointer.
Concept: doublylinked lists (deletions)

Removing the first item from a doublylinked list
with a tail pointer takes:
 n log n time
 linear time
 constant time
 log time

In a doublylinked list, you can move the tail pointer back
one node in:
 log time
 constant time
 n log n time
 linear time

In a doublylinked list, what does a tailpointer gain you?
 the ability to prepend the list in constant time
 the ability to remove the last element of list in constant time
 the ability to both prepend and remove the first element of list in constant time
 the ability to both append and remove the last element of list in constant time
 the ability to remove the first element of list in constant time
 the ability to append the list in constant time
Concept: inputoutput order

These values are pushed onto a stack in the order given: 1 5 9.
A pop operation would return which value?
 9
 5
 1

LIFO ordering is the same as:
 LILO
 FILO
 FIFO
Concept: time and space complexity

Consider a stack based upon a fillable array
with pushes onto the back of the array.
What is the time complexity of the worst case behavior
for push and pop, respectively?
You may assume there is sufficient space for the push operation.
 constant and constant
 constant and linear
 linear and linear
 linear and constant

Consider a stack based upon a circular array
with pushes onto the front of the array.
What is the time complexity of the worst case behavior
for push and pop, respectively?
You may assume there is sufficient space for the push operation.
 constant and linear
 linear and linear
 linear and constant
 constant and constant

Consider a stack based upon a dynamic array
with pushes onto the back of the array.
What is the time complexity of the worst case behavior
for push and pop, respectively?
You may assume there is sufficient space for the push operation
and that the array never shrinks.
 linear and constant
 linear and linear
 constant and constant
 constant and linear

Consider a stack based upon a dynamic array
with pushes onto the back of the array.
What is the time complexity of the worst case behavior
for push and pop, respectively?
You may assume there is sufficient space for the push operation
and that the array may shrink.
 constant and linear
 linear and linear
 constant and constant
 linear and constant

Consider a stack based upon a dynamic circular array
with pushes onto the front of the array.
What is the time complexity of the worst case behavior
for push and pop, respectively?
You may assume the array may grow or shrink.
 linear and constant
 linear and linear
 constant and linear
 constant and constant

Consider a stack based upon a singlylinked list without
a tail pointer with pushes onto the front of the list.
What is the time complexity of the worst case behavior
for push and pop, respectively?
 constant and linear
 linear and constant
 linear and linear
 constant and constant

Consider a stack based upon a singlylinked list with
a tail pointer with pushes onto the front of the list.
What is the time complexity of the worst case behavior
for push and pop, respectively?
 constant and constant
 constant and linear
 linear and linear
 linear and constant

Consider a stack based upon a noncircular, doublylinked list without
a tail pointer with pushes onto the front of the list.
What is the time complexity of the worst case behavior
for push and pop, respectively?
 constant and linear
 constant and constant
 linear and linear
 linear and constant

Consider a stack based upon a doublylinked list with
a tail pointer with pushes onto the front of the list.
What is the time complexity of the worst case behavior
for push and pop, respectively?
 constant and linear
 linear and linear
 constant and constant
 linear and constant

Suppose a simple fillable array with capacity c
is used to implement two stacks,
one growing from each end. The stack sizes at any given time
are stored in i and j, respectively.
If maximum space efficiency is desired,
a reliable condition for the stacks being full is:

i == c/21  j == c/21

i == c/21 && j == c/21

i == c/2 && j == c/2

i + j == c

i + j == c2

i == c/2  j == c/2
Concept: stack applications
For the following questions,
assume the tokens in a postfix equation are processed with the following code,
with all functions having their obvious meanings and integer division.
s.push(readEquationToken());
s.push(readEquationToken());
while (moreEquationTokens())
{
t = readEquationToken();
if (isNumber(t))
s.push(t);
else /* t must be an operator */
{
operandB = s.pop();
operandA = s.pop();
result = performOperation(t,operandA,operandB);
s.push(result);
}
}

If the tokens of the postfix equation
8 2 3 ^ / 2 3 * + 5 1 * 
are read in the order given,
what are the top two values in s immediately after the result of
the first multiplication is pushed?
 1 6
 5 6
 3 3
 1 2
Concept: inputoutput order

These values are enqueued onto a queue in the order
given: 1 5 9 4. A dequeue operation would return which
value?
 5
 9
 1
 4

FIFO ordering is the same as:
 LILO
 FILO
 LIFO
Concept: complexity

Consider a queue based upon a simple fillable array
with enqueues onto the front of the array.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
Assume there is room for the operations.
 linear and constant
 constant and linear
 linear and linear
 constant and constant

Consider a queue based upon a circular array
with enqueues onto the front of the array.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
Assume there is room for the operations.
 constant and linear
 linear and constant
 linear and linear
 constant and constant

Consider a queue based upon a singlylinked list without
a tail pointer with enqueues onto the front of the list.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
 linear and linear
 linear and constant
 constant and linear
 constant and constant

Consider a queue based upon a singlylinked list with
a tail pointer with enqueues onto the front of the list.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
 linear and linear
 constant and constant
 constant and linear
 linear and constant

Consider a queue based upon a doublylinked list with
a tail pointer with enqueues onto the front of the list.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
 constant and linear
 constant and constant
 linear and linear
 linear and constant

Consider a queue based upon a noncircular, doublylinked list without
a tail pointer with enqueues onto the front of the list.
What is the time complexity of the worst case behavior
for enqueue and dequeue, respectively?
 linear and linear
 constant and constant
 linear and constant
 constant and linear
Concept: complexity

Consider a worstcase binary search tree with n nodes. What is the
average case time complexity for finding a value at a leaf?
 constant
 log n
 n log n
 $\sqrt{n}$
 quadratic
 linear

Consider a binary search tree with n nodes. What is the
worst case time complexity for finding a value at a leaf?
 constant
 quadratic
 log n
 n log n
 linear
 $\sqrt{n}$

Consider a binary search tree with n nodes.
What is the minimum and maximum height (using order notation)?
 linear and linear
 constant and linear
 log n and log n
 constant and log n
 log n and linear
Concept: balance

Which ordering of input values builds the most unbalanced BST?
Assume values are inserted from left to right.
 1 7 2 6 3 5 4
 4 3 1 6 2 8 7
 1 2 3 4 5 7 6

Which ordering of input values builds the most balanced BST?
Assume values are inserted from left to right.
 4 3 1 6 2 8 7
 1 4 3 2 5 7 6
 1 2 7 6 0 3 8
Concept: tree shapes

What is the best definition of a perfect binary tree?
 all null children are equidistant from the root
 all leaves have zero children
 all nodes have zero or two children
 all leaves are equidistant from the root

Suppose a binary tree has 10 leaves. How many nodes in the
tree must have two children?
 9
 7
 8
 10
 no limit

Suppose a binary tree has 10 nodes. How many nodes are
children of some other node in the tree?
 8
 9
 7
 10
 no limit

Let P0, P1, and P2 refer to nodes that have zero, one or two children,
respectively.
Using the generally accepted definition,
what is a full binary tree?
 all leaves are equidistant from the root
 all interior nodes P1, except the root
 all interior nodes are P1
 all nodes are P2
 all interior nodes are P2; all leaves are equidistant from the root
 all interior nodes are P2

Let P0, P1, and P2 refer to nodes that have zero, one or two children,
respectively.
Using the generally accepted definition,
what is a perfect binary tree?
 all interior nodes are P2
 all interior nodes P1, except the root
 all interior nodes are P1
 all interior nodes are P2; all leaves are equidistant from the root
 all leaves are equidistant from the root
 all nodes are P0 or P2

Let P0, P1, and P2 refer to nodes that have zero, one or two children,
respectively.
Using the generally accepted definition,
what is a degenerate binary tree?
 all leaves are equidistant from the root
 all interior nodes are P2; all leaves are equidistant from the root
 all interior nodes are P2
 all nodes are P0 or P2
 all interior nodes P1, except the root
 all interior nodes are P1

Let P0, P1, and P2 refer to nodes that have zero, one or two children,
respectively.
Using the generally accepted definition
of a complete binary tree, which of the following actions
can be used to make any complete tree?
Assume the leftmost and rightmost sets may be empty.
 making the leftmost leaves of a perfect tree P1 or P2
 making the leftmost leaves of a perfect tree P2
 another name for a perfect tree
 making the leftmost leaf of a perfect tree P1
 removing the rightmost leaves from a perfect tree

T or F:
All perfect trees are full trees.

T or F:
All full trees are complete trees.

T or F:
All complete trees are perfect trees.

How many distinct binary trees can be formed from exactly two nodes
with values 1, 2, or 3 respectively (hint: think about how many permutations of values there are for each tree shape)?
 6
 4
 3
 5
 2

How many distinct binary tree shapes can be formed from exactly two nodes?
 2
 1
 4
 3
 5

Let k be the the number of steps from the root to a leaf in a
perfect tree. What are the number of nodes
in the tree?
 ${2}^{k}1$
 ${2}^{k+1}$
 ${2}^{k+1}1$
 ${2}^{k1}+1$
 ${2}^{k1}1$

Let k be the the number of steps from the root to the furthest leaf in a
binary tree. What would be the minimum number of nodes
in such a tree? Assume k is a power of two.
 k
 (log k) + 1
 k + 1
 ${2}^{k+1}$
 ${2}^{k+1}1$
 log k

Let k be the the number of steps from the root to the furthest leaf in a
binary tree. What would be the maximum number of nodes
in such a tree? Assume k is a power of two.
 k + 1
 ${2}^{k+1}$
 (log k) + 1
 log k
 k
 ${2}^{k+1}1$
Concept: ordering in a BST

For all child nodes in a BST, what relationship holds between the value
of a left child node and the value of its parent?
Assume unique values.
 less than
 there is no relationship
 greater than

For all sibling nodes in a BST, what relationship holds between the value
of a left child node and the value of its sibling?
Assume unique values.
 there is no relationship
 greater than
 less than

Which statement is true about
the successor of a node in a BST, if it exists?
 it is always an interior node
 it may be an ancestor
 has no right child
 it is always a leaf node
 has no left child

Consider a node which holds neither the smallest or the
largest value in a BST.
Which statement is true about the node which holds
the next higher value of a node in a BST, if it exists?
 it may be an ancestor
 it is always an interior node
 it is always a leaf node
 has no left child
 has no right child
Concept: traversals

Consider printing out the node values of
a binary tree with 25 nodes to the left of the root
and 38 nodes to the right. How many nodes are processed
before the root's value is printed in a preorder traversal?
 0
 54
 38
 25
 none of the other answers are correct
 53

Consider printing out the node values of
a binary tree with 25 nodes to the left of the root
and 38 nodes to the right. How many nodes are processed
before the root's value is printed in an inorder traversal?
 53
 25
 0
 54
 none of the other answers are correct
 38

Consider printing out the node values of
a binary tree with 25 nodes to the left of the root
and 38 nodes to the right. How many nodes are processed
before the root's value is printed in a postorder traversal?
 38
 25
 63
 none of the other answers are correct
 0
 54

Consider a perfect BST with even values 0 through 12,
to which the value 7 is then added.
Which of the following is an inorder
traversal of the resulting tree?
 0 2 4 6 7 8 10 12
 12 10 8 7 6 4 2 0
 0 4 2 7 8 10 12 6
 7 0 2 4 6 8 10 12
 6 2 10 0 4 8 12 7
 0 2 4 6 8 10 12 7

Consider a perfect BST with even values 0 through 12,
to which the value 7 is then added.
Which of the following is a levelorder
traversal of the resulting tree?
 0 2 4 6 7 8 10 12
 6 2 10 0 4 8 12 7
 12 10 8 7 6 4 2 0
 0 4 2 7 8 10 12 6
 0 2 4 6 8 10 12 7
 7 0 2 4 6 8 10 12

Consider
a levelorder traversal
of C B A D F E
and an inorder traversal
of B C A F D E .
Do these traversals generate a unique tree and, if so,
what is that tree's
preorder traversal?
 yes, C B A D F E
 yes, C B A F D E
 no
 yes, C A D B E F
 yes, but the correct answer is not listed

Consider
an inorder traversal
of B C A F D E
and a preorder traversal
of C B A D F E .
Do these traversals generate a unique tree and, if so,
what is that tree's
postorder traversal?
 no
 yes, F A D B E C
 yes, B F E D A C
 yes, but the correct answer is not listed
 yes, B F A E D C

Consider
an inorder traversal
of B C A F D E
and a postorder traversal
of C B A D F E .
Do these traversals generate a unique tree and, if so,
what is that tree's
levelorder traversal?
 yes, E A C F B D
 yes, E F C D B A
 yes, but the correct answer is not listed
 no
 yes, E F A D B C

Consider
a levelorder traversal
of C F D E B A
and an preorder traversal
of C F E A D B .
Do these traversals generate a unique tree and, if so,
what is that tree's
inorder traversal?
 yes, but the correct answer is not listed
 yes, F A E C B D
 yes, F A E C B D
 yes, F E A C D B
 no
Concept: insertion and deletion

T or F:
Suppose you are given an inorder traversal of
an unbalanced BST.
If you were to insert those values into an empty BST
in the order given,
would the result be a balanced tree?

T or F:
Suppose you are given a preorder traversal of
an unbalanced BST.
If you were to insert those values into an empty BST
in the order given,
would the result be a balanced tree?

T or F:
Suppose you are given an inorder traversal of
a balanced BST.
If you were to insert those values into an empty BST
in the order given,
would the result be a balanced tree?

T or F:
Suppose you are given a preorder traversal of
a balanced BST.
If you were to insert those values into an empty BST
in the order given,
would the result be a balanced tree?

Suppose 10 values are inserted inserted into an empty BST.
What is the minimum and maximum resulting heights of the tree?
The height is the number of steps from the root to the furthest leaf.
 4 and 10
 3 and 9
 3 and 10
 4 and 9
 5 and 10
 5 and 9

Which, if any, of these deletion strategies for nonleaf nodes reliably preserve BST ordering?

Swap the values of the node to be deleted and the smallest leaf node with a larger value, then remove the leaf.

Swap the values of the node to be deleted with its predecessor or successor. If the predecessor or successor is a leaf, remove it. Otherwise, repeat the process.

If the node to be deleted does not have two children, simply connect the parent's child pointer to the node to the node's child pointer, otherwise, use a correct deletion strategy for nodes with two children.
 all
 iii
 i and iii
 i
 none
 ii and iii
 ii
 i and ii
Concept: heap shapes

In a heap, the upper bound on the number of leaves is:
 $O\left(1\right)$
 $O\left(n\right)$
 $O\left(\mathrm{log}n\right)$
 $O\left(n\mathrm{log}n\right)$

In a heap, the distance from the root to the furthest leaf is:
 $\theta \left(1\right)$
 $\theta \left(n\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(\mathrm{log}n\right)$

In a heap, let ${d}_{f}$ be the distance of the furthest leaf from the root
and let ${d}_{c}$ be the analogous distance of the closest leaf. What is
${d}_{f}{d}_{c}$, at most?
 $\theta \left(\mathrm{log}n\right)$
 2
 0
 1

What is the most number of nodes in a heap
with a single child?
 0
 2
 1
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$

What is the fewest number of nodes in a heap
with a single child?
 0
 one per level
 1
 2

T or F:
There can be two or more nodes in a heap with exactly one child.

T or F:
A heap can have no nodes with exactly one child.

T or F:
All heaps are perfect trees.

T or F:
No heaps are perfect trees.

T or F:
All heaps are complete trees.

T or F:
No heaps are complete trees.

T or F:
A binary tree with one node must be a heap.

T or F:
A binary tree with two nodes and with the root having
the smallest value must be a minheap.

T or F:
If a node in a heap is a right child and has two children,
then its sibling must also have two children.

T or F:
If a node in a heap is a right child and has one child,
then its sibling must also have one child.
Concept: heap ordering

In a minheap, what is the relationship between a parent
and its left child?
 there is no relationship between their values
 the parent has a smaller value
 the parent has a larger value
 the parent has the same value

In a minheap, what is the relationship between a left
child and its sibling?
 the right child has a larger value
 there is no relationship between their values
 the left child has a smaller value
 both children cannot have the same value

T or F:
A binary tree with three nodes and with the root having
the smallest value and two children must be a min heap.

T or F:
The largest value in a maxheap can be found
at the root.

T or F:
The largest value in a minheap can be found
at the root.

T or F:
The largest value in a minheap can be found
at a leaf.
Concept: heaps stored in arrays

How would this heap be stored in an array?

[2,10,4,11,13,5,15,21,12]

[2,4,5,10,11,12,13,15,21]

[2,10,11,21,12,13,4,5,15]

[21,11,12,10,13,2,5,4,15]

Printing out the values in the array yield what kind of traversal of
the heap?
 preorder
 postorder
 inorder
 levelorder

Suppose the heap has n values. The root of the heap can be
found at which index?
 n
 1
 n1
 0

Suppose the heap has n values. The left child of the
root can be found at which index?
 1
 n2
 2
 0
 n
 n1

Left children in a heap are stored at what kind of indices?
 all even but one
 all odd
 a roughly equal mix of odd and even
 all odd but one
 all even

Right children in a heap are stored at what kind of indices?
 all even but one
 a roughly equal mix of odd and even
 all even
 all odd
 all odd but one

The formula for finding the left child of a node stored at index i is:
 $i*2$
 $i*2+1$
 $i*21$
 $i*2+2$

The formula for finding the right child of a node stored at index i is:
 $i*2$
 $i*2+2$
 $i*2+1$
 $i*21$

The formula for finding the parent of a node stored at index i is:
 $(i+2)/2$
 $(i+1)/2$
 $(i1)/2$
 $i/2$

If the array uses onebased indexing, the formula for finding
the left child of a node stored at index i is:
 $i*21$
 $i*2+2$
 $i*2$
 $i*2+1$

If the array uses onebased indexing, the formula for finding
the right child of a node stored at index i is:
 $i*2+2$
 $i*2+1$
 $i*2$
 $i*21$

If the array uses onebased indexing, the formula for finding
the parent of a node stored at index i is:
 $(i+2)/2$
 $(i1)/2$
 $(i+1)/2$
 $i/2$

Consider a trinary heap stored in
an array.
The formula for finding the left child of a node stored at index i is:
 $i*3+1$
 $i*32$
 $i*3+3$
 $i*31$
 $i*3$
 $i*3+2$

Consider a trinary heap stored in
an array.
The formula for finding the middle child of a node stored at index i is:
 $i*3+1$
 $i*32$
 $i*3+3$
 $i*3+2$
 $i*3$
 $i*31$

Consider a trinary heap stored in
an array.
The formula for finding the right child of a node stored at index i is:
 $i*3$
 $i*32$
 $i*31$
 $i*3+1$
 $i*3+3$
 $i*3+2$

Consider a trinary heap stored in
an array.
The formula for finding the parent of a node stored at index i is:
 $(i2)/3$
 $(i+2)/3$
 $i/3+1$
 $(i1)/3$
 $(i+1)/3$
 $i/31$
Concept: heap operations

In a maxheap with no knowledge of
the minimum value, the minimum value can be found
in time:
 $\theta \left(n\right)$
 $\theta \left(1\right)$
 $\theta \left(\mathrm{log}n\right)$
 $\theta \left(n\mathrm{log}n\right)$

Suppose a minheap with n values is stored in an array a. In the
extractMin operation, which element immediatelyreplaces the root element
(prior to this new root being sifted down).

a[2]
 the minimum of
a[1]
and
a[2]

a[n1]

a[1]

The findMin operation in a minheap takes how much time?
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(n\right)$

The extractMin operation in a minheap takes how much time?
 $\Theta \left(1\right)$
 $\Theta \left(n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$

Merging two heaps of size n and m, m < n takes
how much time?
 $\Theta (n*m)$
 $\Theta \left(n\mathrm{log}m\right)$
 $\Theta (\mathrm{log}n+\mathrm{log}m)$
 $\Theta (n+m)$
 $\Theta (\mathrm{log}n*\mathrm{log}m)$
 $\Theta \left(m\mathrm{log}n\right)$

The insert operation takes how much time?
 $\Theta \left(n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$

Turning an unordered array into a heap takes how much time?
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$

Suppose the
values 21, 15, 14, 10, 8, 5, and 2
are inserted, one after the other, into an empty minheap. What does
the resulting heap look like?
Heap properties are maintained after every insertion.
 w
 y
 z
 x

Using the standard buildHeap operation to turn an unordered array
into a maxheap, how many parentchild swaps are made if the
initial unordered array
is
[5,21,8,15,25,3,9]
?
 2
 4
 7
 5
 3
 6