Back to Subject

Unit 6: Backtracking - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main idea of backtracking?

General method Easy
A. Store every solution in a queue
B. Sort all choices before searching
C. Explore choices and undo invalid ones
D. Combine solutions without checking constraints

2 Which structure is commonly used to represent the choices explored by a backtracking algorithm?

General method Easy
A. Hash table
B. State-space tree
C. Adjacency matrix
D. Circular queue

3 What does pruning mean in backtracking?

General method Easy
A. Skipping branches that cannot succeed
B. Arranging choices in sorted order
C. Removing duplicate input values
D. Joining two partial solutions

4 Backtracking most commonly uses which search strategy?

General method Easy
A. Breadth-first search
B. Binary search
C. Depth-first search
D. Linear search

5 When does a backtracking algorithm undo its most recent choice?

General method Easy
A. When the input becomes sorted
B. When every branch has equal cost
C. When the partial solution becomes invalid
D. When the search reaches the root

6 What is the goal of the 8-queens problem?

The 8-queens problem Easy
A. Place eight queens so none attack
B. Cover the board using eight queens
C. Place eight queens in one row
D. Move one queen across eight squares

7 Which board size is used in the standard 8-queens problem?

The 8-queens problem Easy
A.
B.
C.
D.

8 In a valid 8-queens solution, how many queens may occupy the same row?

The 8-queens problem Easy
A. At most eight queens
B. At most one queen
C. At most two queens
D. At most four queens

9 Which three relationships must be checked to prevent two queens from attacking each other?

The 8-queens problem Easy
A. Columns, edges, and centers
B. Rows, corners, and centers
C. Rows, columns, and diagonals
D. Diagonals, corners, and edges

10 What should a backtracking algorithm do after placing a queen causes a conflict?

The 8-queens problem Easy
A. Accept the board as complete
B. Add another queen to the same square
C. Remove the queen and try another position
D. Restart without preserving earlier choices

11 What is assigned to each vertex in the graph coloring problem?

Graph coloring Easy
A. A distance
B. A direction
C. A weight
D. A color

12 In a proper vertex coloring, adjacent vertices must have what property?

Graph coloring Easy
A. They have different colors
B. They have equal weights
C. They have different labels
D. They have equal degrees

13 What does the chromatic number of a graph represent?

Graph coloring Easy
A. The number of connected parts
B. The minimum required colors
C. The maximum vertex degree
D. The total number of edges

14 How many colors are sufficient to properly color a graph containing no edges?

Graph coloring Easy
A. Four colors
B. Two colors
C. Three colors
D. One color

15 When should backtracking reject a color assigned to a vertex?

Graph coloring Easy
A. When a neighboring vertex has that color
B. When a distant vertex has that color
C. When the vertex has an even label
D. When the graph contains several edges

16 What is a Hamiltonian cycle?

Hamiltonian cycles Easy
A. A cycle that visits every vertex once
B. A cycle that uses every edge once
C. A path that repeats every vertex
D. A path that avoids the starting vertex

17 What must happen at the end of a Hamiltonian cycle?

Hamiltonian cycles Easy
A. The path reaches a new vertex
B. The path returns to its start
C. The path uses every edge
D. The path removes its last edge

18 How many times is each vertex visited in a Hamiltonian cycle, apart from repeating the start to close the cycle?

Hamiltonian cycles Easy
A. Exactly twice
B. Exactly once
C. Any number of times
D. At least twice

19 When extending a partial Hamiltonian cycle, which vertex may be added next?

Hamiltonian cycles Easy
A. An unvisited nonadjacent vertex
B. Any previously visited vertex
C. Any vertex with an even label
D. An unvisited adjacent vertex

20 What is the key difference between a Hamiltonian cycle and an Euler cycle?

Hamiltonian cycles Easy
A. Hamiltonian focuses on vertices; Euler focuses on edges
B. Hamiltonian allows paths; Euler allows only trees
C. Hamiltonian uses colors; Euler uses vertex weights
D. Hamiltonian focuses on edges; Euler focuses on vertices

21 A backtracking algorithm has a maximum of candidates at each of decision levels. If no branches are pruned, what is its worst-case time complexity?

General method Medium
A.
B.
C.
D.

22 Which sequence correctly describes how a typical backtracking algorithm processes a candidate?

General method Medium
A. Test, undo, choose, and recurse
B. Recurse, choose, test, and undo
C. Choose, recurse, undo, and test
D. Choose, test, recurse, and undo

23 For a pruning rule to preserve the correctness of a backtracking algorithm, which condition must hold?

General method Medium
A. Every accepted node has one child
B. Every search level uses equal branching
C. Every candidate is examined in sorted order
D. Every pruned node has no valid completion

24 A backtracking procedure currently stops when it finds its first valid solution. What change is needed to enumerate all valid solutions?

General method Medium
A. Record the solution and restart from the root
B. Reject the solution and increase the depth limit
C. Record the solution and continue exploring siblings
D. Accept the solution and disable all pruning

25 A depth-first backtracking algorithm has maximum recursion depth . Ignoring stored output, what is its typical auxiliary space usage when each stack frame has constant size?

General method Medium
A.
B.
C.
D.

26 In an 8-queens representation where is the column of the queen in row , when do queens in rows and attack each other?

The 8-queens problem Medium
A. or
B. or
C. or
D. or

27 Queens have been placed in columns for rows . Which column is safe for the queen in row ?

The 8-queens problem Medium
A. Column
B. Column
C. Column
D. Column

28 A backtracking formulation places exactly one queen in each row. Which conflicts must its promising function explicitly test?

The 8-queens problem Medium
A. Row and column conflicts
B. Column and diagonal conflicts
C. Row and diagonal conflicts
D. Only diagonal conflicts

29 In the standard row-by-row state-space tree for 8-queens, what does a promising node at depth represent?

The 8-queens problem Medium
A. A complete board containing five solutions
B. Five queens using exactly five diagonals
C. Five nonattacking queens in five rows
D. Eight queens with five conflicts removed

30 If an 8-queens solution has its row- queen in column , where is that queen after reflecting the board across its vertical axis?

The 8-queens problem Medium
A. Column
B. Column
C. Column
D. Column

31 What is the minimum number of colors required to properly color the cycle graph ?

Graph coloring Medium
A.
B.
C.
D.

32 A backtracking algorithm attempts to color using three colors. What happens after three mutually adjacent vertices receive distinct colors?

Graph coloring Medium
A. The fourth vertex has no legal color
B. The first vertex must be left uncolored
C. The graph becomes properly two-colored
D. The fourth vertex may reuse any color

33 Vertices , , and form a triangle. If is red and is blue, which color can be assigned to in a proper coloring using red, blue, and green?

Graph coloring Medium
A. Red or blue
B. Red only
C. Green only
D. Blue only

34 Which vertex-ordering heuristic often reduces the search performed by a graph-coloring backtracking algorithm?

Graph coloring Medium
A. Color high-degree vertices first
B. Color vertices randomly once
C. Color isolated vertices first
D. Color low-degree vertices first

35 For a graph with vertices and available colors, what is the maximum number of complete color assignments before constraint-based pruning?

Graph coloring Medium
A.
B.
C.
D.

36 During a Hamiltonian-cycle search, which conditions make an unvisited vertex a valid next candidate on the current path?

Hamiltonian cycles Medium
A. It is nonadjacent to the last vertex and unvisited
B. It is adjacent to the last vertex and unvisited
C. It has the largest degree and is unvisited
D. It is adjacent to the first vertex and visited

37 After a backtracking algorithm places all vertices in a candidate Hamiltonian path, what final condition must it verify?

Hamiltonian cycles Medium
A. The last vertex has maximum graph degree
B. The first vertex is adjacent to every vertex
C. The last vertex is adjacent to the first
D. The path contains every graph edge

38 A connected graph with more than two vertices contains a vertex of degree . What can be concluded about Hamiltonian cycles in the graph?

Hamiltonian cycles Medium
A. A Hamiltonian cycle exists if the graph is connected
B. A Hamiltonian cycle must use that edge twice
C. Exactly one Hamiltonian cycle exists
D. No Hamiltonian cycle can exist

39 How many distinct undirected Hamiltonian cycles does the complete graph have when rotations and reversals are considered identical?

Hamiltonian cycles Medium
A.
B.
C.
D.

40 Two triangles share exactly one common vertex and have no other connecting edges. Why does the resulting graph have no Hamiltonian cycle?

Hamiltonian cycles Medium
A. The graph requires exactly three vertex colors
B. The shared vertex would need to be visited twice
C. Each triangle contains too many graph edges
D. The shared vertex has an odd degree

41 A backtracking algorithm prunes a node whenever a predicate on the current partial state is false. Which property of is sufficient to guarantee that pruning preserves completeness?

General method Hard
A. is true for every internal search-tree node
B. Every state satisfying extends to a solution
C. Every complete solution extending implies
D. implies that has exactly one solution

42 At depth , each surviving node generates at most children, and testing a node at depth costs . With no pruning, which expression is the tightest general upper bound on total testing cost through depth ?

General method Hard
A.
B.
C.
D.

43 A constraint solver dynamically chooses the unassigned variable with the fewest legal values rather than using a fixed variable order. Under which condition does this preserve completeness?

General method Hard
A. It chooses only variables whose domains have equal cardinality
B. It permanently removes every value rejected in one sibling branch
C. It always selects the same variable after returning to a depth
D. It explores every legal value and reverses each state change correctly

44 Two different partial assignments reach states with the same proposed memoization signature. When is merging those states sound for an optimization backtracking algorithm?

General method Hard
A. Their search-tree depths and most recent decisions are identical
B. Their feasible completions and incremental completion values are identical
C. Their branching factors and variable orders are identical
D. Their current objective values have the same numerical parity

45 In a minimization search seeking one optimal solution, an incumbent has value . A valid lower bound applies to every completion of state . Which pruning rule is sound?

General method Hard
A. Prune whenever its current cost is below
B. Prune whenever
C. Prune whenever
D. Prune whenever one completion may exceed

46 In a bit-mask solver, , , and mark columns and diagonals attacked in the current row, and . After choosing a one-bit position , which update correctly prepares the masks for the next row?

The 8-queens problem Hard
A. , ,
B. , ,
C. , ,
D. , ,

47 The standard 8-queens problem has 92 solutions when board orientations are distinguished. How many fundamental solutions remain when rotations and reflections are considered equivalent?

The 8-queens problem Hard
A. fundamental solutions
B. fundamental solutions
C. fundamental solutions
D. fundamental solutions

48 Queens have been legally placed in rows through at columns . Which set contains exactly the legal columns for the queen in row ?

The 8-queens problem Hard
A.
B.
C.
D.

49 A solver restricts the first-row queen to columns through to break left-right reflection symmetry. What is the precise effect on the 92 oriented solutions?

The 8-queens problem Hard
A. It retains 23 solutions because four rotations are eliminated
B. It retains 12 solutions representing all symmetry equivalence classes
C. It retains 4 solutions because only corner-column starts survive
D. It retains 46 solutions but does not remove all rotational symmetries

50 A generalized queens solver may choose any unassigned row next and applies the minimum-remaining-values heuristic. Which statement best characterizes this modification?

The 8-queens problem Hard
A. It eliminates the need to track occupied diagonal directions
B. It preserves only solutions compatible with increasing row order
C. It preserves all solutions and may expose dead ends earlier
D. It guarantees polynomial running time on every board size

51 Using the chromatic polynomial of a cycle, how many proper colorings of the labeled vertices of exist with three labeled colors?

Graph coloring Hard
A.
B.
C.
D.

52 A graph is -degenerate, meaning every nonempty subgraph has a vertex of degree at most . Which procedure is guaranteed to construct a proper coloring using at most colors?

Graph coloring Hard
A. Color minimum-degree vertices immediately without removing their incident edges
B. Remove minimum-degree vertices repeatedly, then greedily color in reverse order
C. Remove maximum-degree vertices repeatedly, then greedily color in removal order
D. Color maximum-degree vertices first while reserving one color for each component

53 For vertices ordered as , a coloring search enforces and . What symmetry does this restriction remove?

Graph coloring Hard
A. It restricts the search to greedy colorings of the chosen vertex order
B. It chooses one canonical representative for each permutation of color labels
C. It identifies colorings related by arbitrary permutations of graph vertices
D. It removes every coloring related by a nontrivial graph automorphism

54 During -coloring backtracking, each uncolored vertex has a residual list of permitted colors. For an uncolored clique , which condition is a sound reason to prune?

Graph coloring Hard
A. At least two vertices in have lists of equal size
B. Some satisfies
C. Some satisfies
D. Every satisfies

55 An uncolored graph has vertices with saturation degrees and uncolored degrees , respectively. Under standard DSATUR selection with uncolored degree as the tie-breaker, which vertex is selected?

Graph coloring Hard
A. Vertex
B. Vertex
C. Vertex
D. Vertex

56 A bipartite graph has parts and with and . Which conclusion about Hamiltonian cycles is valid regardless of its edge set?

Hamiltonian cycles Hard
A. It has a Hamiltonian cycle if every vertex has degree at least
B. It has no Hamiltonian cycle because the part sizes differ
C. It has a Hamiltonian cycle whenever the graph is connected
D. It has no Hamiltonian path because its order is odd

57 Let mean that a path starts at fixed vertex , visits exactly the vertices in , and ends at . Which recurrence supports a Hamiltonian-cycle algorithm?

Hamiltonian cycles Hard
A.
B.
C.
D.

58 A Hamiltonian-cycle backtracking search has a partial path from start vertex to current endpoint , with unvisited set . Which condition is a sound pruning test?

Hamiltonian cycles Hard
A. Prune if the subgraph induced only by contains any cycle
B. Prune if the subgraph induced by is disconnected
C. Prune if some two vertices of have the same graph degree
D. Prune if and are not adjacent in the current partial path

59 For a simple graph with vertices, which statement correctly applies Dirac's theorem?

Hamiltonian cycles Hard
A. If , then is Hamiltonian
B. If , then is Hamiltonian
C. If , then is Hamiltonian
D. If is Hamiltonian, then

60 How many distinct undirected Hamiltonian cycles does the complete labeled graph contain when cycles differing only by starting vertex or traversal direction are identified?

Hamiltonian cycles Hard
A.
B.
C.
D.
Previous MCQ
Unit 5
Next MCQ
Unit 7