Mastering Data Structures

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

• Linked lists allow random access while arrays require sequential access.

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

• The main difference is that arrays have a fixed size and allow random access, while linked lists are dynamic in size and allow sequential access.

• Arrays store elements in nodes while linked lists store elements in contiguous memory.

How do you implement a stack using an array?

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

• A stack can only be implemented using linked lists.

• You can only add elements to a stack, not remove them.

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

What are the key properties of a binary tree?

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

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

• A binary tree is a linear structure with nodes arranged in a single line.

• A binary tree is always balanced and has equal height on both sides.

Explain the difference between depth-first search and breadth-first search in graphs.

• Both DFS and BFS use a stack to explore nodes in the same manner.

• Depth-first search (DFS) uses a stack and explores deeply, while breadth-first search (BFS) uses a queue and explores widely.

• DFS uses a queue and explores widely, while BFS uses a stack and explores deeply.

• DFS explores all nodes at the present depth before moving on, while BFS explores one node at a time.

What is a hash table and how does it handle collisions?

• A hash table is a data structure that uses a hash function to map keys to values and handles collisions through methods like chaining or open addressing.

• A hash table is a type of database that stores data in rows and columns.

• A hash table uses a binary tree structure to manage data and collisions.

• A hash table is a simple list that does not require a hash function for data retrieval.

Describe the quicksort algorithm and its average time complexity.

• O(n log n)

• O(log n)

• O(n)

• O(n^2)

What is the purpose of a queue in data structures?

• To permanently delete data without processing.

• To store data in a LIFO manner for quick access.

• The purpose of a queue is to manage data in a FIFO manner, facilitating orderly processing of tasks.

• To allow random access to elements without order.

How can you determine the time complexity of a given algorithm?

• Use a debugger to step through the algorithm line by line.

• Count the number of lines in the code.

• Analyze the algorithm's structure and count basic operations as a function of input size.

• Run the algorithm multiple times and average the execution time.

What is a balanced tree and why is it important?

• A balanced tree is a data structure that maintains a balanced height for efficient operations, important for ensuring logarithmic time complexity in insertions, deletions, and lookups.

• A balanced tree is a type of fruit tree that grows evenly.

• A balanced tree is a structure that only allows for linear time complexity operations.

• A balanced tree is a data structure that prioritizes memory usage over speed.

Explain the concept of a priority queue and its applications.

• Priority queues are a type of data structure that only allows insertion of elements.

• Priority queues are used in applications such as scheduling tasks in operating systems, managing bandwidth in networks, and implementing algorithms like Dijkstra's and A* for pathfinding.

• Priority queues are primarily used for managing user interfaces in applications.

• Priority queues are only used for sorting data in arrays.