DS&A

Question 1

Process of returning to a previous state in the algorithm’s execution path when a terminal condition is reached to explore alternative possibilities

Answer 1

backtrack step

Question 2

this list type stores each node’s outgoing neighbors in its value array

Answer 2

An adjacency list

Question 3

Technique used to eliminate unnecessary exploration of the state space / Like taking shortcuts in our search by avoiding paths we know won’t lead to a solution

Answer 3

Pruning

Question 4

L._. nodes do not have any children.

Answer 4

Leaf nodes do not have any children.

Question 5

Condition telling us when to stop exploring a particular path. Could be due to a solution or because we’ve reached a dead end

Answer 5

terminal condition

Question 6

Potential choice or element that we can add to current partial solution

Answer 6

candidate

Question 7

the height of “p_____” binary trees grows logarithmically.

Answer 7

the height of ->”perfect”<- binary trees grows logarithmically.

Question 8

On average, searching for an element in a balanced Binary Search Tree takes O(_ ? _ ) time, where N is the number of nodes

Answer 8

On average, searching for an element in a balanced BST takes O(log N) time, where N is the number of nodes

Question 9

Full Binary Trees: Every node has either_ or_ children

Answer 9

Full Binary Trees: Every node has either zero or two children

Question 10

Complete Binary Trees: All levels are completely filled with nodes, except possibly for the l____ level (nodes are filled from l____ to r____ on the last level)

Answer 10

Complete Binary Trees: All levels are completely filled with nodes, except possibly for the last level (nodes filled from left to right on last level)

Question 11

Represent hierarchical structures or processes with a clear direction and no repetition;
No loops; once you go down a path, there’s no way back up;

Answer 11

acyclic graph

Question 12

At least one loop where you can start and end at same vertex; Useful for modeling systems that can return to their initial state

Answer 12

cyclic graph

Question 13

Balanced Binary Trees: the height of left and right subtrees of any node differs by at most ._.

Answer 13

Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one

Question 14

Tree structure representing state space

Answer 14

state space tree

Question 15

B________ed Binary Trees: the height of left and right subtrees of any node differs by at most one

Answer 15

Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one

Question 16

the height of perfect binary trees grows l________y.

Answer 16

the height of perfect binary trees grows logarithmically.

Question 17

N____ branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization

Answer 17

Naive branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization

Question 18

Set of all possible states in problem / all possible configurations or situations that may be encountered

Answer 18

state space