Exploring Data Structures and Algorithms

What is a Binary Search Tree and how does it differ from a regular binary tree?

• A Binary Search Tree allows for unordered node placement, making it less efficient than a regular binary tree.

• A Binary Search Tree is a binary tree that only allows for left child nodes.

• A Binary Search Tree is a type of graph structure used for network routing.

• A Binary Search Tree is a binary tree with ordered nodes, allowing efficient search, insertion, and deletion, unlike a regular binary tree.

Explain the balancing mechanism of an AVL Tree.

• The balancing mechanism of an AVL Tree involves maintaining a balance factor for each node and performing rotations to ensure the tree remains balanced after insertions or deletions.

• An AVL Tree uses a single rotation to maintain balance after every insertion.

• The balancing mechanism relies solely on the height of the tree without considering node values.

• AVL Trees do not require any balancing operations after deletions.

What are the key properties of a binary tree?

• A binary tree is always balanced and complete.

• A binary tree does not have a hierarchical structure.

• A binary tree has nodes with at most two children, a hierarchical structure, and properties related to node values and height.

• A binary tree can have any number of children per node.

Define a directed graph and provide an example.

• An example of a directed graph is: A -> B, B -> C, A -> C.

• A -> B, C -> A, B -> A

• A <-> B, B <-> C, A <-> C

• A -> B, B -> C, C -> A

What distinguishes an undirected graph from a directed graph?

• A directed graph has no edges connecting its vertices.

• An undirected graph has bidirectional edges, while a directed graph has edges with a specific direction.

• An undirected graph can only have one vertex connected to another.

• An undirected graph has edges that can only be traversed in one direction.

How do weighted graphs differ from unweighted graphs?

• Weighted graphs have more vertices than unweighted graphs.

• Weighted graphs have edges with values (weights), while unweighted graphs do not.

• Weighted graphs are always directed while unweighted graphs are undirected.

• Unweighted graphs can only represent linear relationships.

What is an adjacency matrix and how is it used to represent graphs?

• An adjacency matrix is a list of all vertices in a graph.

• An adjacency matrix is a square matrix used to represent a graph, indicating the presence or absence of edges between vertices.

• An adjacency matrix is a circular array used to store graph weights.

• An adjacency matrix is a tree structure that represents hierarchical data.

Describe the time complexity of searching in a Binary Search Tree.

• O(n^2) for searching in any Binary Search Tree.

• O(log n) on average for balanced trees, O(n) in the worst case for unbalanced trees.

• O(log n) for all cases regardless of tree balance.

• O(n) on average for balanced trees, O(log n) in the worst case for unbalanced trees.

What are the advantages of using an AVL Tree over a regular Binary Search Tree?

• AVL Trees are slower for search operations compared to regular Binary Search Trees.

• The advantages of using an AVL Tree over a regular Binary Search Tree include guaranteed O(log n) time complexity for search, insert, and delete operations due to self-balancing, which prevents the tree from becoming unbalanced.

• AVL Trees require more memory than regular Binary Search Trees due to additional pointers.

• Regular Binary Search Trees guarantee O(log n) time complexity for all operations.

How can you convert a weighted graph into an adjacency matrix?

• An adjacency matrix is formed by connecting vertices with lines without considering weights.

• An adjacency matrix is created by initializing a square matrix and filling it with edge weights.

• An adjacency matrix is created by listing all vertices in a single row.

• You can convert a weighted graph by drawing it on paper instead of using a matrix.