Advanced Data Structures Challenge

What is the time complexity of in-order traversal of a binary tree?

• O(log n)

• O(n^2)

• O(1)

• O(n)

Describe the difference between pre-order and post-order traversal in binary trees.

• Pre-order traversal processes the root after its children, while post-order processes the root before its children.

• Pre-order traversal only processes leaf nodes, while post-order processes all nodes.

• Pre-order traversal processes the root before its children, while post-order processes the root after its children.

• Both pre-order and post-order traversals process the root at the same time.

What is the purpose of a depth-first search (DFS) in graph traversal?

• To identify cycles in a directed graph.

• To find the shortest path between two vertices.

• To calculate the total weight of all edges in a graph.

• The purpose of DFS in graph traversal is to explore all vertices and edges of a graph by going as deep as possible along each branch before backtracking.

Explain how breadth-first search (BFS) works in graph traversal.

• Breadth-first search (BFS) explores a graph level by level using a queue to track nodes.

• BFS uses a stack to explore nodes in depth-first order.

• BFS only visits nodes that are directly connected to the starting node.

• BFS requires a binary tree structure to function properly.

What is the time complexity of BFS and DFS in terms of vertices and edges?

• O(V)

• O(V + E)

• O(E)

• O(V * E)

What is a hash table and how does it work?

• A hash table is a physical table used in restaurants for serving food.

• A hash table is a programming language used for web development.

• A hash table is a data structure that uses a hash function to map keys to values for efficient data retrieval.

• A hash table is a type of database used for storing large amounts of data.

Describe the chaining method for collision resolution in hash tables.

• Chaining method uses linked lists to handle collisions by storing multiple entries at the same index.

• Chaining method resolves collisions by deleting the older entry.

• Chaining method requires a fixed size for the hash table.

• Chaining method uses arrays to store entries at the same index.

What is open addressing in hash tables and how does it resolve collisions?

• Open addressing uses linked lists to handle collisions.

• Open addressing resolves collisions by finding the next available slot in the hash table using a probing sequence.

• Collisions are resolved by doubling the size of the hash table.

• Open addressing requires a separate array for each key in the hash table.

What are the advantages of using a binary search tree over a regular binary tree?

• Binary search trees can only store integer values.

• Regular binary trees allow for more efficient searching than binary search trees.

• Binary trees are always balanced, making them faster.

• The advantages of using a binary search tree over a regular binary tree include efficient searching, insertion, and deletion operations due to the sorted order of elements.

How can you determine if a binary tree is balanced?

• A binary tree is balanced if it is a complete binary tree.

• A binary tree is balanced if the height difference between left and right subtrees is at most 1 for all nodes.

• A binary tree is balanced if all nodes have the same number of children.

• A binary tree is balanced if it has a maximum depth of 3.