Design and Analysis of Algorithms

What is a data structure?

• A data structure is a method for writing algorithms.

• A data structure is a programming language.

• A data structure is a type of software application.

• A data structure is a specialized format for organizing, processing, and storing data.

Explain the difference between an array and a linked list.

• An array has a fixed size and allows for fast access via indices, while a linked list is dynamic in size and allows for efficient insertions and deletions but has slower access times.

• A linked list uses contiguous memory while an array does not.

• Accessing elements in an array is slower than in a linked list.

• An array can grow dynamically while a linked list has a fixed size.

What is a stack and how does it work?

• A stack can only store integers and does not support other data types.

• A stack is a LIFO data structure that allows adding and removing items from the top.

• A stack is a type of queue that processes items in random order.

• A stack is a FIFO data structure that allows adding and removing items from the bottom.

Define a queue and its operations.

• A queue is a FIFO data structure with operations: enqueue (add), dequeue (remove), peek (view front), and isEmpty (check if empty).

• A queue is a LIFO data structure with operations: push (add), pop (remove), top (view top), and isFull (check if full).

• A queue is a circular data structure with operations: add (enqueue), remove (dequeue), last (view last), and isEmpty (check if empty).

• A queue is a data structure that allows random access with operations: insert (add), delete (remove), front (view any element), and isEmpty (check if empty).

What is the time complexity of binary search?

• O(n)

• O(log n)

• O(1)

• O(n log n)

Explain the concept of recursion with an example.

• Recursion is a technique used to optimize code by removing unnecessary function calls.

• Recursion is a method where a function runs in a loop until a condition is met.

• Recursion is when a function is executed multiple times without calling itself.

• Recursion is a method where a function calls itself to solve smaller instances of the same problem.

What is a hash table and how is it used?

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

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

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

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

Describe the difference between depth-first and breadth-first search.

• DFS goes deep into a branch first, while BFS explores all nodes at the current level before going deeper.

• DFS explores all nodes at the current level before going deeper, while BFS goes deep into a branch first.

• DFS and BFS are identical in their approach to searching through a graph.

• BFS is faster than DFS in all scenarios regardless of the graph structure.

What is a binary tree and its properties?

• A binary tree is a structure where each node can have any number of children.

• A binary tree is a tree data structure where each node has at most two children.

• A binary tree is a linear data structure with only one child per node.

• A binary tree is a type of graph that allows cycles between nodes.

What are the advantages of using a graph data structure?

• Slower than array structures

• Limited to linear data representation

• Efficiently represent relationships, quick traversal, support for complex algorithms.

• Only suitable for simple data relationships