Free Practice Quiz Question List

12 Discrete Structures and Algorithms Online Quiz Questions

Use this free practice quiz with 20 questions to review 12 Discrete Structures and Algorithms, test your knowledge, and prepare for your next test or exam.

20 questions

Choose one

1 point

Which Boolean identity correctly simplifies the complement of an AND expression?

A
$\overline{A+B}=\overline A+\overline B$
B
$\overline{AB}=\overline A+\overline B$
C
$\overline{AB}=\overline A\,\overline B$
D
$A+\overline A=0$

Choose one

1 point

A propositional circuit has three independent Boolean input variables. How many rows are required for its complete truth table?

Choose one

1 point

Which precondition is essential for the usual binary-search step that discards half of the remaining array?

A
The array is sorted.
B
The array contains no duplicate values.
C
The target is at the first or last position.
D
The array has exactly $2^k$ elements.

True or false

1 point

True or false: Every problem in P is also in NP.

A
True
B
False

True or false

1 point

True or false: During linear search, the loop invariant proves before every iteration that the target is absent from the entire array.

A
True
B
False

Written response

1 point

What is the technical term for a condition that must be true before an algorithm executes?

Written response

1 point

Using Theta notation, classify the asymptotic growth of $3n^2+7n+4$ .

Fill in the blank

1 point

In a standard loop-invariant proof, the first step is , which shows the invariant holds initially. The second step is , which shows that one iteration preserves it.

Fill in the blank

1 point

In the definition of NP, a proposed yes-answer that can be checked in polynomial time is called a .

Choose all

1 point

Select all gate types that the material identifies as universal gates.

A
NAND
B
XOR
C
NOR
D
AND

Choose all

1 point

Select all statements that are consistent with the material’s distinction between algorithm correctness and complexity analysis.

A
Whether the algorithm produces the required result
B
How resource use grows with input size
C
Whether the algorithm uses a particular programming language
D
Whether machine-specific constants are being abstracted away when comparing asymptotic growth

Open ended

1 point

Compare linear search and binary search on an array of length $n$ . Explain the worst-case time bound of each algorithm and state the precondition that makes binary search’s bound valid.

Choose one

1 point

Suppose there is a polynomial-time reduction $A\le_p B$ . Which conclusion follows if problem $B$ has a polynomial-time algorithm?

A
If $A\le_p B$ , a fast algorithm for $A$ automatically solves $B$ .
B
If $A\le_p B$ and $B$ is solvable in polynomial time, then $A$ is solvable in polynomial time.
C
If $A\le_p B$ , then $A$ and $B$ must have identical inputs.
D
If $A\le_p B$ , then $B$ is necessarily in P regardless of the status of $A$ .

Choose one

1 point

Which Boolean expression is equivalent to $A+AB$ ?

A
$A+B$
B
$A$
C
$AB$
D
$B$

True or false

1 point

True or false: Binary search can correctly discard half of the remaining search interval after each comparison in an arbitrary unsorted array.

A
True
B
False

Choose one

1 point

For the circuit $f(A,B,C)=(A\land B)\lor\lnot C$ , what output is produced when $A=1$ , $B=0$ , and $C=0$ ?

A
0, because the AND gate receives a zero
B
0, because $\lnot C=0$
C
1, because $\lnot C=1$
D
1, because both $A$ and $B$ are true

Written response

1 point

What is the tight asymptotic classification of $3n^2+7n+4$ ? Enter your answer in standard Big-Theta notation.

Choose one

1 point

Which statement is a suitable loop invariant for linear search after positions $1$ through $i-1$ have been checked?

A
The target occurs at position $i$ .
B
Every position from $i$ through $n$ has already been checked.
C
The target does not occur in positions $1$ through $i-1$ , unless the algorithm has already returned.
D
The array is sorted through position $i-1$ .

Written response

1 point

How many rows are required for a complete truth table with five Boolean input variables?

Choose one

1 point

Ignoring constant factors and lower-order effects, which algorithm is generally more scalable for large inputs: one running in $O(n\log n)$ time or one running in $O(n^2)$ time?

A
An $O(n\log n)$ algorithm
B
An $O(n^2)$ algorithm
C
They must have identical running times
D
Neither bound gives any information about scalability