Algorithm Study Guide

What is a root node?

• The bottommost node in a tree data structure.

• The topmost node in a tree data structure.

• A node that has no children in a tree data structure.

• A node that connects two branches in a tree data structure.

What is the time complexity of linear search?

• O(1) (constant)

• O(log n) (logarithmic)

• O(n) (linear)

• O(n^2) (quadratic)

What data structure does DFS use?

• A queue (FIFO - First-In, First-Out)

• A stack (LIFO - Last-In, First-Out)

• A linked list

• An array

What is the order of nodes in post-order traversal?

• Node, Left, Right

• Left, Node, Right

• Right, Left, Node

• Left, Right, Node

What is a tree?

• A linear data structure with a single path of nodes.

• A hierarchical data structure consisting of nodes connected by edges, with a root node and no cycles.

• A collection of unordered elements without any relationships.

• A type of graph that contains cycles and no root node.

What are the two main graph traversal algorithms?

• Breadth-First Search (BFS) and Depth-First Search (DFS)

• Dijkstra's Algorithm and Prim's Algorithm

• A* Search and Bellman-Ford Algorithm

• Kruskal's Algorithm and Floyd-Warshall Algorithm

What data structure does BFS use?

• A stack (LIFO - Last-In, First-Out)

• A queue (FIFO - First-In, First-Out)

• A linked list

• An array

What are the three types of tree traversal algorithms?

• Pre-order, in-order, and post-order traversal.

• Level-order, depth-first, and breadth-first traversal.

• In-order, reverse-order, and random-order traversal.

• Pre-order, post-order, and breadth-first traversal.

What is a key limitation of Dijkstra’s algorithm?

• It doesn't work with negative edge weights.

• It cannot find the shortest path in a graph with cycles.

• It requires all edge weights to be positive.

• It is only applicable to directed graphs.

What is a leaf node?

• A node in a tree that has no children.

• A node that has at least one child.

• A node that is the root of the tree.

• A node that connects two branches.