Mastering Data Structures

What is the primary difference between an array and a linked list?

• The primary difference is that arrays use contiguous memory for storage, while linked lists use nodes with pointers to connect elements.

• Linked lists store elements in a single block of memory, while arrays use multiple blocks.

• Arrays allow for faster access to elements than linked lists due to their structure.

• Arrays can grow dynamically in size, while linked lists have a fixed size.

Answer explanation

The correct choice highlights that arrays store elements in contiguous memory, allowing for direct access, while linked lists consist of nodes connected by pointers, which can lead to slower access times.

How do you implement a stack using an array?

• A stack requires a fixed size and cannot grow dynamically.

• A stack can be implemented using an array by maintaining an index for the top element and providing push, pop, and peek operations.

• A stack can only be implemented using linked lists.

• You can only perform enqueue and dequeue operations on a stack.

Answer explanation

A stack can be implemented using an array by keeping track of the top index. This allows for efficient push (add), pop (remove), and peek (view top) operations, making it a suitable structure for stack functionality.

What is the time complexity of accessing an element in a linked list?

• O(n^2)

• O(n)

• O(log n)

• O(1)

Answer explanation

Accessing an element in a linked list requires traversing from the head to the desired node, which takes O(n) time in the worst case. Therefore, the correct time complexity is O(n).

Explain the difference between a queue and a stack.

• A queue is LIFO; a stack is FIFO.

• A queue allows random access; a stack does not.

• A queue is a linear data structure; a stack is a non-linear data structure.

• A queue is FIFO; a stack is LIFO.

Answer explanation

A queue operates on a FIFO (First In, First Out) basis, meaning the first element added is the first to be removed. In contrast, a stack uses LIFO (Last In, First Out), where the last element added is the first to be removed.

What is a binary tree and how does it differ from a binary search tree?

• A binary tree is a type of graph; a binary search tree is a linear structure.

• A binary tree can have any number of children; a binary search tree can have only one.

• A binary tree is a tree structure with nodes having at most two children; a binary search tree is a binary tree with ordered nodes.

• A binary tree is always balanced; a binary search tree can be unbalanced.

Answer explanation

A binary tree allows each node to have at most two children. In contrast, a binary search tree is a specific type of binary tree where the nodes are arranged in a way that maintains a sorted order, facilitating efficient searching.

How do you perform a breadth-first search on a graph?

• Use a stack to explore nodes randomly, ignoring visited nodes.

• Use a queue to explore nodes level by level, marking them as visited.

• Explore nodes in reverse order, starting from the last added node.

• Visit all nodes in a single pass without using any data structure.

Answer explanation

Breadth-first search (BFS) uses a queue to explore nodes level by level. This ensures that all nodes at the current depth are visited before moving on to the next level, while marking nodes as visited to avoid cycles.

What is the purpose of a hash table and how does it work?

• To create a backup of data in a database.

• To store data in a linear array format.

• The purpose of a hash table is to provide efficient data storage and retrieval using key-value pairs.

• To encrypt sensitive information using keys.

Answer explanation

A hash table uses key-value pairs to store data, allowing for efficient retrieval and storage. This structure enables quick access to values based on their unique keys, making it ideal for scenarios requiring fast lookups.

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

• 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 its sorted structure.

• Binary search trees can only store integer values.

• Regular binary trees have better memory efficiency than binary search trees.

Answer explanation

The correct choice highlights that binary search trees (BSTs) allow for efficient searching, insertion, and deletion due to their sorted structure, unlike regular binary trees which do not maintain order.

Describe how to insert an element into a binary search tree.

• Always place the new value to the left of the current node.

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

• Insert the new value at the appropriate null position based on comparisons.

• Delete the smallest value in the tree before inserting the new value.

Answer explanation

To insert an element into a binary search tree, compare the new value with the current node. If it's smaller, move left; if larger, move right. Place the new value in the first available null position based on these comparisons.

What is the time complexity for searching an element in a hash table?

• O(log n) on average, O(n) in the worst case

• O(1) in all cases

• O(1) on average, O(n) in the worst case

• O(n) on average, O(1) in the worst case

Answer explanation

In a hash table, searching for an element typically takes O(1) time on average due to direct indexing. However, in the worst case, if many elements hash to the same index, it can take O(n) time to search through them.