CCDSALG Practice Questions

Given: sum = 0 for i = 0 to n: for j = 0 to i: sum += j What is the time complexity?

• O(n)

• O(n log n)

• O(n²)

• O(n³)

Answer explanation

The inner loop runs i times for each i, leading to 1 + 2 + 3 + ... + n = O(n²) operations.

Let f(n) = 4n² + 6n + 1, g(n) = n². Which is true?

• f(n) = O(g(n))

• f(n) = Ω(g(n))

• f(n) = Θ(g(n))

• All of the above

Answer explanation

Since both upper and lower bounds are tightly n2n^2n2, it's Θ. Hence, also O and Ω.

Which function has the slowest growth rate?

• log²n

• √n

• n log n

• n²

Answer explanation

Logarithmic growth is slower than root or linear-log.

Let f(n) = 10n + 50, and g(n) = n. Which constants satisfy f(n) ≤ cg(n)?

• c = 60, n₀ = 1

• c = 10, n₀ = 5

• c = 12, n₀ = 10

• c = 5, n₀ = 20

Answer explanation

f(n)=10n+50≤60n is true for n≥1.

Convert (3 + 6) * (4 - 2) into prefix:

• * + 3 6 - 4 2

• + 3 6 * - 4 2

• + * 3 6 4 2

• * 3 6 - 4 2

Answer explanation

Prefix = operator before operands: * + 3 6 - 4 2.

Quadratic probing, collision at index 2.

What is the probing sequence?

• 3, 6, 11

• 3, 7, 2

• 3, 4, 5

• 3, 5, 8

Answer explanation

Quadratic probing: i² offset. 2+1²=3, 2+2²=6, 2+3²=11→mod size if needed.

Data structure for infix to postfix conversion?

• Queue

• Stack

• Tree

• Graph

Binary tree with height 3, full binary tree. Leaf nodes?

• 2

• 4

• 6

• 8

Answer explanation

A full binary tree of height h has 2^h leaf nodes. Here, 2^3=8.

Which is FALSE about trees?

• A tree is a connected acyclic graph.

• A tree with n nodes has n edges

• A full binary tree has every node with 0 or 2 children.

• The number of leaves in a perfect binary tree is 2^h, where h is the height.

Answer explanation

tree with n nodes has n - 1 edges — not n.

Hash table with h(k) = k mod 11. Keys 1, 2, 3 are taken. Where does 45 go?

• 1

• 2

• 4

• 5

Answer explanation

45 mod 11 = 1 → occupied → probe: 2 → 3 → 4 → empty.