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. Explore choices and undo invalid ones
B. Sort all choices before searching
C. Combine solutions without checking constraints
D. Store every solution in a queue

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

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

3 What does pruning mean in backtracking?

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

4 Backtracking most commonly uses which search strategy?

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

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

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

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

The 8-queens problem Easy
A. Place eight queens in one row
B. Cover the board using eight queens
C. Place eight queens so none attack
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 two queens
B. At most eight queens
C. At most four queens
D. At most one queen

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. Diagonals, corners, and edges
C. Rows, columns, and diagonals
D. Rows, corners, and centers

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

The 8-queens problem Easy
A. Add another queen to the same square
B. Accept the board as complete
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 direction
B. A weight
C. A color
D. A distance

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

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

13 What does the chromatic number of a graph represent?

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

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

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

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

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

16 What is a Hamiltonian cycle?

Hamiltonian cycles Easy
A. A path that repeats every vertex
B. A cycle that uses every edge once
C. A cycle that visits every vertex once
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 returns to its start
B. The path uses every edge
C. The path removes its last edge
D. The path reaches a new vertex

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. Any number of times
B. Exactly once
C. At least twice
D. Exactly twice

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

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

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 uses colors; Euler uses vertex weights
C. Hamiltonian focuses on edges; Euler focuses on vertices
D. Hamiltonian allows paths; Euler allows only trees

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 candidate is examined in sorted order
C. Every search level uses equal branching
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. Accept the solution and disable all pruning
D. Record the solution and continue exploring siblings

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. Row and diagonal conflicts
C. Column 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. Eight queens with five conflicts removed
B. A complete board containing five solutions
C. Five nonattacking queens in five rows
D. Five queens using exactly five diagonals

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 graph becomes properly two-colored
B. The fourth vertex has no legal color
C. The first vertex must be left uncolored
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. Blue only
B. Red only
C. Red or blue
D. Green 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 low-degree vertices first
C. Color vertices randomly once
D. Color isolated 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 adjacent to the first vertex and visited
B. It is nonadjacent to the last vertex and unvisited
C. It has the largest degree and is unvisited
D. It is adjacent to the last vertex and unvisited

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. No Hamiltonian cycle can exist
B. A Hamiltonian cycle exists if the graph is connected
C. A Hamiltonian cycle must use that edge twice
D. Exactly one Hamiltonian cycle exists

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 shared vertex has an odd degree
B. The graph requires exactly three vertex colors
C. Each triangle contains too many graph edges
D. The shared vertex would need to be visited twice

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. implies that has exactly one solution
C. Every state satisfying extends to a solution
D. Every complete solution extending implies

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 explores every legal value and reverses each state change correctly
D. It always selects the same variable after returning to a depth

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 branching factors and variable orders are identical
B. Their feasible completions and incremental completion values are identical
C. Their current objective values have the same numerical parity
D. Their search-tree depths and most recent decisions are identical

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
B. Prune whenever
C. Prune whenever its current cost is below
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 46 solutions but does not remove all rotational symmetries
C. It retains 4 solutions because only corner-column starts survive
D. It retains 12 solutions representing all symmetry equivalence classes

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 maximum-degree vertices first while reserving one color for each component
B. Remove maximum-degree vertices repeatedly, then greedily color in removal order
C. Remove minimum-degree vertices repeatedly, then greedily color in reverse order
D. Color minimum-degree vertices immediately without removing their incident edges

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 removes every coloring related by a nontrivial graph automorphism
C. It chooses one canonical representative for each permutation of color labels
D. It identifies colorings related by arbitrary permutations of graph vertices

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. Every satisfies
C. Some satisfies
D. Some 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 whenever the graph is connected
B. It has a Hamiltonian cycle if every vertex has degree at least
C. It has no Hamiltonian cycle because the part sizes differ
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 and are not adjacent in the current partial path
B. Prune if the subgraph induced only by contains any cycle
C. Prune if some two vertices of have the same graph degree
D. Prune if the subgraph induced by is disconnected

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

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

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