Exploring Data Structures

What is a Binary Search Tree (BST)?

• A Binary Search Tree (BST) allows nodes to have more than two children.

• A Binary Search Tree (BST) is a tree data structure where each node has at most two children, with the left child containing values less than the parent and the right child containing values greater than the parent.

• A Binary Search Tree (BST) is a linear data structure with nodes arranged in a single line.

• A Binary Search Tree (BST) is a type of graph where all nodes are connected in a cycle.

How do you insert a node in a Binary Search Tree?

• Insert the new node at the root regardless of its value.

• Delete the node with the smallest value before inserting.

• Insert the new node in the correct position based on its value.

• Always insert the new node as a left child.

What is the time complexity of searching in a balanced BST?

• O(n log n)

• O(1)

• O(n)

• O(log n)

Explain the concept of a Hash Table.

• A hash table is a graphical representation of data relationships.

• A hash table is a data structure that maps keys to values using a hash function to compute an index.

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

• A hash table is a linear data structure that stores elements in a sequential manner.

What is a hash function and why is it important?

• A hash function is a type of encryption used to secure passwords.

• A hash function is an algorithm that converts input data into a fixed-size string, important for data integrity and security.

• A hash function is a method for compressing files into smaller sizes.

• A hash function is a programming language used for data analysis.

How do collisions occur in a Hash Table?

• Collisions occur when different keys hash to the same index in a hash table.

• Collisions are caused by using a linear probing method.

• Collisions occur when keys are of different data types.

• Collisions happen when the hash table is full.

What are the common methods to resolve collisions in Hash Tables?

• Rehashing and bucket sorting

• Chaining and open addressing

• Double hashing and cuckoo hashing

• Linear probing and quadratic probing

Describe the Depth-First Search (DFS) algorithm.

• Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures by exploring as far as possible along each branch before backtracking.

• Depth-First Search (DFS) is a technique used to find the shortest path between two nodes in a graph.

• Depth-First Search (DFS) is a method for sorting data in ascending order by comparing elements sequentially.

• Depth-First Search (DFS) is an algorithm that visits all nodes at the present depth level before moving on to the nodes at the next depth level.

What are the different types of Depth-First Search?

• Binary Search

• Types of Depth-First Search include Recursive DFS, Iterative DFS, Pre-order, In-order, Post-order, and variations for graph traversal.

• Linear Search

• Breadth-First Search

How does Depth-First Search differ from Breadth-First Search?

• DFS explores all neighbors before going deeper, while BFS goes deeper first.

• DFS uses a stack for exploration, while BFS uses a queue.

• DFS guarantees the shortest path, whereas BFS does not.

• BFS uses a stack for exploration, while DFS uses a queue.