set-1

1. What is the difference between a primitive data type and an abstract data type in programming?

1. Primitive data types are basic and cannot be changed, while abstract data types can be modified.

2. Primitive data types are simple, while abstract data types are complex.

3. Primitive data types are defined by the programming language, while abstract data types are defined by the programmer.

4. Primitive data types are stored in memory, while abstract data types are stored on disk.

Show me the answer

Answer: 3. Primitive data types are defined by the programming language, while abstract data types are defined by the programmer.

Explanation:

• Primitive Data Types: These are the basic data types provided by the programming language itself, such as int, float, char, etc. They are predefined and cannot be broken down into simpler data types.

• Abstract Data Types (ADTs): These are data types that are defined by the programmer. They are more complex and can be composed of primitive data types or other ADTs. Examples include stacks, queues, and lists. ADTs are defined by their behavior (operations) rather than their implementation.

• Conclusion: The key difference is that primitive data types are built into the language, while ADTs are user-defined and can encapsulate both data and operations.

2. Which of the following is a linear data structure?

1. Graph

2. Queue

3. Tree

4. Hash Table

Show me the answer

Answer: 2. Queue

Explanation:

• Linear Data Structure: A linear data structure is one where elements are arranged in a sequential manner, and each element is connected to its previous and next element. Examples include arrays, linked lists, stacks, and queues.

• Queue: A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where the first element added is the first one to be removed.

• Graph and Tree: These are non-linear data structures where elements are connected in a hierarchical or networked manner.

• Hash Table: This is a data structure that uses a hash function to map keys to values, and it is not linear.

• Conclusion: The queue is the only linear data structure among the options.

3. In the big O notation, $O(1)$ represents:

1. A constant time algorithm

2. A linear time algorithm

3. A logarithmic time algorithm

4. An exponential time algorithm

Show me the answer

Answer: 1. A constant time algorithm

Explanation:

• Big O Notation: Big O notation is used to describe the time complexity of an algorithm, i.e., how the runtime of an algorithm grows as the input size increases.

• $O(1)$: This represents constant time complexity, meaning the algorithm takes the same amount of time to execute regardless of the input size. For example, accessing an element in an array by index is an $O(1)$ operation.

• Conclusion: $O(1)$ indicates that the algorithm's runtime is constant and does not depend on the input size.

4. What does big O notation represent in algorithm analysis?

1. The worst-case time complexity of an algorithm

2. The best-case time complexity of an algorithm

3. The average time complexity of an algorithm

4. The exact time complexity of an algorithm

Show me the answer

Answer: 1. The worst-case time complexity of an algorithm

Explanation:

• Big O Notation: Big O notation is used to describe the upper bound of an algorithm's runtime, i.e., the worst-case scenario. It provides an upper limit on the time an algorithm takes to complete as a function of the input size.

• Worst-Case Scenario: It represents the maximum amount of time an algorithm could take to complete, assuming the worst possible input.

• Conclusion: Big O notation is primarily used to describe the worst-case time complexity of an algorithm.

5. What does a big O notation of $O(n)$ indicate about an algorithm?

1. The algorithm takes a constant amount of time regardless of the size of the input.

2. The algorithm takes a linear amount of time proportional to the size of the input.

3. The algorithm takes a logarithmic amount of time relative to the size of the input.

4. The algorithm takes an exponential amount of time based on the size of the input.

Show me the answer

Answer: 2. The algorithm takes a linear amount of time proportional to the size of the input.

Explanation:

• $O(n)$: This represents linear time complexity, meaning the runtime of the algorithm grows linearly with the size of the input. For example, iterating through an array of size $n$ takes $O(n)$ time.

• Linear Growth: If the input size doubles, the runtime also doubles.

• Conclusion: $O(n)$ indicates that the algorithm's runtime is directly proportional to the input size.

6. What is the big O notation for a binary search algorithm?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 3. $O(\log n)$

Explanation:

• Binary Search: Binary search is an efficient algorithm for finding an item in a sorted list. It works by repeatedly dividing the search interval in half.

• Time Complexity: The time complexity of binary search is $O(\log n)$, where $n$ is the number of elements in the list. This is because the search space is halved with each step.

• Mathematical Explanation: If the list has $n$ elements, the maximum number of steps required to find the target is $\log_2 n$.

• Conclusion: Binary search has a logarithmic time complexity, making it very efficient for large datasets.

7. Which of the following algorithms has a big O notation of $O(n^2)$?

1. Binary search

2. Quick sort

3. Bubble sort

4. Linear search

Show me the answer

Answer: 3. Bubble sort

Explanation:

• Bubble Sort: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

• Time Complexity: The worst-case time complexity of bubble sort is $O(n^2)$, where $n$ is the number of elements in the list. This is because, in the worst case, the algorithm may need to make $n \times n$ comparisons.

• Conclusion: Bubble sort is an example of an algorithm with quadratic time complexity, making it inefficient for large datasets.

8. What does big O notation tell us about the efficiency of an algorithm?

1. It gives us an exact measurement of the time complexity of an algorithm.

2. It gives us an approximation of the time complexity of an algorithm, taking into account the worst-case scenario.

3. It gives us an estimate of the space complexity of an algorithm.

4. It gives us a comparison of the time complexity of different algorithms.

Show me the answer

Answer: 2. It gives us an approximation of the time complexity of an algorithm, taking into account the worst-case scenario.

Explanation:

• Big O Notation: Big O notation provides an upper bound on the growth rate of an algorithm's runtime as a function of the input size. It describes the worst-case scenario, i.e., the maximum amount of time an algorithm could take.

• Approximation: It does not give an exact measurement but rather an approximation of how the runtime scales with input size.

• Conclusion: Big O notation is used to describe the worst-case time complexity of an algorithm, helping us understand its efficiency.

9. What is a linear data structure?

1. A data structure that stores data in a sequential manner

2. A data structure that stores data in a hierarchical manner

3. A data structure that stores data randomly

4. A data structure that stores data in a circular manner

Show me the answer

Answer: 1. A data structure that stores data in a sequential manner

Explanation:

• Linear Data Structure: A linear data structure is one where elements are arranged in a sequential order, and each element is connected to its previous and next element. Examples include arrays, linked lists, stacks, and queues.

• Sequential Storage: In a linear data structure, elements are stored one after another in memory, making it easy to traverse the structure in a linear fashion.

• Conclusion: Linear data structures store data in a sequential manner, making them suitable for applications where elements need to be accessed in a specific order.

10. Which of the following is an example of a linear data structure?

1. Tree

2. Stack

3. Graph

4. Hash Table

Show me the answer

Answer: 2. Stack

Explanation:

• Stack: A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed.

• Linear Structure: Elements in a stack are stored in a sequential manner, and operations like push and pop are performed at one end of the stack.

• Conclusion: The stack is an example of a linear data structure, as it stores elements in a sequential order.

11. What is the difference between a stack and a queue in terms of data storage and retrieval?

1. A stack stores and retrieves data in a first-in, first-out (FIFO) manner, while a queue stores and retrieves data in a last-in, first-out (LIFO) manner.

2. A stack stores and retrieves data in a last-in, first-out (LIFO) manner, while a queue stores and retrieves data in a first-in, first-out (FIFO) manner.

3. A stack stores and retrieves data randomly, while a queue stores and retrieves data in a sequential manner.

4. A stack stores and retrieves data in a hierarchical manner, while a queue stores and retrieves data in a circular manner.

Show me the answer

Answer: 2. A stack stores and retrieves data in a last-in, first-out (LIFO) manner, while a queue stores and retrieves data in a first-in, first-out (FIFO) manner.

Explanation:

• Stack: A stack follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Operations like push (add) and pop (remove) are performed at the top of the stack.

• Queue: A queue follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue is the first one to be removed. Operations like enqueue (add) and dequeue (remove) are performed at the front and rear of the queue.

• Conclusion: The key difference between a stack and a queue is the order in which elements are stored and retrieved: LIFO for stacks and FIFO for queues.

12. What is the time complexity of inserting or deleting an element from the beginning of a singly linked list?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 2. $O(n)$

Explanation:

• Singly Linked List: In a singly linked list, each node points to the next node in the sequence. To insert or delete an element at the beginning of the list, you need to update the head pointer, which takes $O(1)$ time.

• Insertion/Deletion at the Beginning: However, if you need to insert or delete an element at the beginning of the list, you must traverse the entire list to update the pointers, which takes $O(n)$ time in the worst case.

• Conclusion: The time complexity of inserting or deleting an element from the beginning of a singly linked list is $O(n)$.

13. What is the time complexity of inserting or deleting an element from the end of a linked list?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 2. $O(n)$

Explanation:

• Linked List: In a linked list, each node points to the next node in the sequence. To insert or delete an element at the end of the list, you need to traverse the entire list to reach the last node.

• Traversal: Traversing the list to reach the last node takes $O(n)$ time, where $n$ is the number of elements in the list.

• Conclusion: The time complexity of inserting or deleting an element from the end of a linked list is $O(n)$.

14. What is a data structure?

1. A collection of related data values

2. A collection of algorithms

3. A way of organizing and storing data in a computer so that it can be accessed and manipulated efficiently

4. A way of organizing and storing data in a database

Show me the answer

Answer: 3. A way of organizing and storing data in a computer so that it can be accessed and manipulated efficiently

Explanation:

• Data Structure: A data structure is a way of organizing and storing data in a computer so that it can be accessed and manipulated efficiently. It provides a means to manage large amounts of data effectively.

• Efficiency: The choice of data structure affects the efficiency of operations like insertion, deletion, and search.

• Conclusion: Data structures are essential for efficient data management and manipulation in computer programs.

15. What are the two main types of data structures?

1. Linear and non-linear

2. Hierarchical and non-hierarchical

3. Primitive and non-primitive

4. Structured and unstructured

Show me the answer

Answer: 1. Linear and non-linear

Explanation:

• Linear Data Structures: These are data structures where elements are arranged in a sequential manner, such as arrays, linked lists, stacks, and queues.

• Non-linear Data Structures: These are data structures where elements are not arranged sequentially, such as trees, graphs, and hash tables.

• Conclusion: The two main types of data structures are linear and non-linear, depending on how the elements are organized.

16. What is an array in data structures?

1. A collection of data elements stored in a sequential manner

2. A collection of data elements stored in a random manner

3. A collection of data elements stored in a hierarchical manner

4. A collection of data elements stored in a circular manner

Show me the answer

Answer: 1. A collection of data elements stored in a sequential manner

Explanation:

• Array: An array is a collection of data elements stored in a sequential manner. Each element in the array is accessed using an index, and the elements are stored in contiguous memory locations.

• Sequential Storage: Arrays allow for efficient access to elements using their indices, making them suitable for applications where random access is required.

• Conclusion: Arrays are a fundamental linear data structure that stores elements in a sequential manner.

17. What is a linked list in data structures?

1. A collection of data elements stored in a sequential manner

2. A collection of data elements stored in a random manner

3. A collection of data elements stored in a hierarchical manner

4. A linked list consists of nodes where each node contains a data field and a reference (link) to the next node in the list

Show me the answer

Answer: 4. A linked list consists of nodes where each node contains a data field and a reference (link) to the next node in the list

Explanation:

• Linked List: A linked list is a linear data structure where each element (called a node) contains two parts: the data and a reference (or link) to the next node in the sequence.

• Node Structure: Each node stores the data and a pointer to the next node, allowing dynamic memory allocation and efficient insertion/deletion operations.

• Conclusion: A linked list is a dynamic data structure where elements are connected via pointers, making it flexible for various operations.

18. What is a stack in data structures?

1. A collection of data elements stored in a sequential manner

2. A collection of data elements stored in a random manner

3. A collection of data elements stored in a hierarchical manner

4. A collection of data elements stored in a last-in, first-out (LIFO) manner

Show me the answer

Answer: 4. A collection of data elements stored in a last-in, first-out (LIFO) manner

Explanation:

• Stack: A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added to the stack is the first one to be removed.

• Operations: The two main operations on a stack are push (to add an element) and pop (to remove the top element).

• Conclusion: A stack is a LIFO data structure, making it suitable for applications like function call management and expression evaluation.

19. Which of the following is/are the application of stack?

1. Backtracking

2. Evaluation of arithmetic expression

3. Function calls

4. All of the above

Show me the answer

Answer: 4. All of the above

Explanation:

• Backtracking: Stacks are used in backtracking algorithms to store the state of the problem at each step.

• Evaluation of Arithmetic Expressions: Stacks are used to evaluate arithmetic expressions, especially in converting infix expressions to postfix or prefix notation.

• Function Calls: Stacks are used to manage function calls in programming languages, storing the return address and local variables.

• Conclusion: Stacks have a wide range of applications, including backtracking, expression evaluation, and function call management.

20. What is the time complexity of pushing an element onto a stack?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 1. $O(1)$

Explanation:

• Push Operation: The push operation in a stack involves adding an element to the top of the stack. This operation takes constant time because it only requires updating the top pointer.

• Time Complexity: Since no traversal or additional processing is needed, the time complexity is $O(1)$.

• Conclusion: Pushing an element onto a stack is an $O(1)$ operation.

21. What is the time complexity of popping an element from a stack?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 1. $O(1)$

Explanation:

• Pop Operation: The pop operation in a stack involves removing the top element from the stack. This operation takes constant time because it only requires updating the top pointer.

• Time Complexity: Since no traversal or additional processing is needed, the time complexity is $O(1)$.

• Conclusion: Popping an element from a stack is an $O(1)$ operation.

22. What is the use of a stack in computer science?

1. To store and retrieve data in a first-in, first-out (FIFO) manner

2. To store and retrieve data in a last-in, first-out (LIFO) manner

3. To store and retrieve data randomly

4. To store and retrieve data in a circular manner

Show me the answer

Answer: 2. To store and retrieve data in a last-in, first-out (LIFO) manner

Explanation:

• LIFO Principle: A stack follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

• Applications: Stacks are used in various applications such as function call management, expression evaluation, and backtracking.

• Conclusion: The primary use of a stack is to store and retrieve data in a LIFO manner.

23. What is an example of a problem that can be solved using a stack?

1. Sorting a list of numbers

2. Finding the shortest path between two points

3. Balancing parentheses in a mathematical expression

4. Searching for a specific element in a list

Show me the answer

Answer: 3. Balancing parentheses in a mathematical expression

Explanation:

• Balancing Parentheses: A stack can be used to check if the parentheses in a mathematical expression are balanced. For every opening parenthesis, it is pushed onto the stack, and for every closing parenthesis, the top element is popped and checked for a match.

• Conclusion: Balancing parentheses is a classic problem that can be efficiently solved using a stack.

24. What is the difference between a stack and a queue?

1. A stack stores and retrieves data in a last-in, first-out (LIFO) manner, while a queue stores and retrieves data in a first-in, first-out (FIFO) manner.

2. A stack stores and retrieves data randomly, while a queue stores and retrieves data in a sequential manner.

3. A stack is a linear data structure, while a queue is a non-linear data structure.

4. A stack is a dynamic data structure, while a queue is a static data structure.

Show me the answer

Answer: 1. A stack stores and retrieves data in a last-in, first-out (LIFO) manner, while a queue stores and retrieves data in a first-in, first-out (FIFO) manner.

Explanation:

• Stack: A stack follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

• Queue: A queue follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed.

• Conclusion: The key difference between a stack and a queue is the order in which elements are stored and retrieved: LIFO for stacks and FIFO for queues.

25. What is the advantage of using a stack over other data structures to solve certain problems?

1. Stacks are more efficient in terms of time and space complexity.

2. Stacks are easier to implement and use than other data structures.

3. Stacks allow for efficient retrieval of data in a last-in, first-out (LIFO) manner, making them well-suited for certain problems.

4. Stacks provide better performance in terms of memory usage compared to other data structures.

Show me the answer

Answer: 3. Stacks allow for efficient retrieval of data in a last-in, first-out (LIFO) manner, making them well-suited for certain problems.

Explanation:

• LIFO Principle: The LIFO nature of stacks makes them ideal for problems where the most recently added element needs to be accessed first, such as backtracking, expression evaluation, and function call management.

• Conclusion: The primary advantage of using a stack is its ability to efficiently handle problems that require LIFO data retrieval.

26. What is a stack overflow error in computer programming?

1. An error that occurs when a stack exceeds its maximum size.

2. An error that occurs when a stack is not properly initialized.

3. An error that occurs when a stack is not properly deallocated.

4. An error that occurs when a stack is not properly aligned in memory.

Show me the answer

Answer: 1. An error that occurs when a stack exceeds its maximum size.

Explanation:

• Stack Overflow: A stack overflow occurs when the stack grows beyond its allocated memory limit, typically due to excessive recursion or deep nesting of function calls.

• Conclusion: A stack overflow error is caused by exceeding the stack's maximum size, leading to program termination or undefined behavior.

27. What is the difference between a stack and a heap in computer programming?

1. A stack stores data in a last-in, first-out (LIFO) manner, while a heap stores data in a random manner.

2. A stack is a static data structure, while a heap is a dynamic data structure.

3. A stack is used for short-term storage of data, while a heap is used for long-term storage of data.

4. A stack is used for program execution, while a heap is used for memory allocation.

Show me the answer

Answer: 4. A stack is used for program execution, while a heap is used for memory allocation.

Explanation:

• Stack: The stack is used for managing function calls, local variables, and control flow during program execution. It follows the LIFO principle.

• Heap: The heap is used for dynamic memory allocation, where memory is allocated and deallocated as needed during runtime.

• Conclusion: The stack is used for program execution, while the heap is used for dynamic memory management.

28. What is a stack frame in computer programming?

1. A unit of memory that stores data for a single function call in a stack.

2. A unit of memory that stores data for a single data structure in a stack.

3. A unit of memory that stores data for multiple function calls in a stack.

4. A unit of memory that stores data for multiple data structures in a stack.

Show me the answer

Answer: 1. A unit of memory that stores data for a single function call in a stack.

Explanation:

• Stack Frame: A stack frame is a block of memory that stores data related to a single function call, including local variables, return addresses, and parameters.

• Function Execution: Each time a function is called, a new stack frame is created and pushed onto the stack. When the function returns, the stack frame is popped.

• Conclusion: A stack frame is used to manage data for individual function calls during program execution.

29. What is the push operation in a stack data structure?

1. An operation to remove an element from the top of the stack

2. An operation to add an element to the bottom of the stack

3. An operation to add an element to the top of the stack

4. An operation to remove an element from the bottom of the stack

Show me the answer

Answer: 3. An operation to add an element to the top of the stack

Explanation:

• Push Operation: The push operation adds an element to the top of the stack. It updates the top pointer to point to the newly added element.

• Conclusion: The push operation is used to add elements to the top of the stack.

30. What is the pop operation in a stack data structure?

1. An operation to remove an element from the top of the stack

2. An operation to add an element to the bottom of the stack

3. An operation to add an element to the top of the stack

4. An operation to remove an element from the bottom of the stack

Show me the answer

Answer: 1. An operation to remove an element from the top of the stack

Explanation:

• Pop Operation: The pop operation removes the top element from the stack. It updates the top pointer to point to the next element in the stack.

• Conclusion: The pop operation is used to remove elements from the top of the stack.

31. What is stack overflow in a stack data structure?

1. An error that occurs when a stack exceeds its maximum size

2. An error that occurs when a stack is not properly initialized

3. An error that occurs when a stack is not properly deallocated

4. An error that occurs when a stack is not properly aligned in memory

Show me the answer

Answer: 1. An error that occurs when a stack exceeds its maximum size

Explanation:

• Stack Overflow: A stack overflow occurs when the stack grows beyond its allocated memory limit, typically due to excessive recursion or deep nesting of function calls.

• Conclusion: A stack overflow error is caused by exceeding the stack's maximum size, leading to program termination or undefined behavior.

32. What is stack underflow in a stack data structure?

1. An error that occurs when a stack is empty and an attempt is made to remove an element from it

2. An error that occurs when a stack is full and an attempt is made to add an element to it

3. An error that occurs when a stack is improperly aligned in memory

4. An error that occurs when a stack is not properly initialized

Show me the answer

Answer: 1. An error that occurs when a stack is empty and an attempt is made to remove an element from it

Explanation:

• Stack Underflow: A stack underflow occurs when an attempt is made to pop an element from an empty stack. This is an invalid operation and results in an error.

• Conclusion: Stack underflow is an error that occurs when trying to remove an element from an empty stack.

33. What is a queue in data structures?

1. Sequential collection with insertion at one end and deletion at the other end

2. Random collection

3. Hierarchical collection

4. Circular collection with pointers

Show me the answer

Answer: 1. Sequential collection with insertion at one end and deletion at the other end

Explanation:

• Queue: A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are inserted at the rear and removed from the front.

• Operations: The two main operations on a queue are enqueue (to add an element) and dequeue (to remove an element).

• Conclusion: A queue is a sequential collection where insertion and deletion occur at opposite ends.

34. What is the time complexity of inserting an element into a queue?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 1. $O(1)$

Explanation:

• Enqueue Operation: The enqueue operation in a queue involves adding an element to the rear of the queue. This operation takes constant time because it only requires updating the rear pointer.

• Time Complexity: Since no traversal or additional processing is needed, the time complexity is $O(1)$.

• Conclusion: Inserting an element into a queue is an $O(1)$ operation.

35. What is the time complexity of removing an element from a queue?

1. $O(1)$

2. $O(n)$

3. $O(\log n)$

4. $O(n \log n)$

Show me the answer

Answer: 1. $O(1)$

Explanation:

• Dequeue Operation: The dequeue operation in a queue involves removing an element from the front of the queue. This operation takes constant time because it only requires updating the front pointer.

• Time Complexity: Since no traversal or additional processing is needed, the time complexity is $O(1)$.

• Conclusion: Removing an element from a queue is an $O(1)$ operation.

36. What is the use of a queue in computer science?

1. To store and retrieve data in a last-in, first-out (LIFO) manner

2. To store and retrieve data in a first-in, first-out (FIFO) manner

3. To store and retrieve data randomly

4. To store and retrieve data in a circular manner

Show me the answer

Answer: 2. To store and retrieve data in a first-in, first-out (FIFO) manner

Explanation:

• FIFO Principle: A queue follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed.

• Applications: Queues are used in various applications such as task scheduling, print spooling, and breadth-first search (BFS) in graphs.

• Conclusion: The primary use of a queue is to store and retrieve data in a FIFO manner.

37. What is an example of a problem that can be solved using a queue?

1. Sorting a list of numbers

2. Breadth-first search in a graph

3. Balancing parentheses in a mathematical expression

4. Searching for a specific element in a list

Show me the answer

Answer: 2. Breadth-first search in a graph

Explanation:

• Queue: A queue is a data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed.

• Breadth-First Search (BFS): BFS is a graph traversal algorithm that explores all the nodes at the present depth level before moving on to nodes at the next depth level. It uses a queue to keep track of the nodes to be explored.

• Conclusion: Queues are essential for implementing BFS, making them suitable for solving graph traversal problems.

38. What is the minimum number of fields in each node of a doubly linked list?

1. 2

2. 3

3. 4

4. None of the above

Show me the answer

Answer: 2. 3

Explanation:

• Doubly Linked List: In a doubly linked list, each node contains three fields:

  1. Data Field: Stores the actual data.

  2. Next Pointer: Points to the next node in the list.

  3. Previous Pointer: Points to the previous node in the list.

• Conclusion: The minimum number of fields in each node of a doubly linked list is 3.

39. What is a graph referred to as when all vertices have equal degree?

1. Complete graph

2. Regular graph

3. Multi graph

4. Simple graph

Show me the answer

Answer: 2. Regular graph

Explanation:

• Regular Graph: A graph is called a regular graph if all its vertices have the same degree. For example, in a 3-regular graph, every vertex has a degree of 3.

• Conclusion: A graph where all vertices have equal degree is referred to as a regular graph.

40. What is a vertex with in-degree zero in a directed graph called?

1. Root vertex

2. Isolated vertex

3. Sink

4. Articulation point

Show me the answer

Answer: 3. Sink

Explanation:

• Sink: In a directed graph, a sink is a vertex with an in-degree of zero, meaning no edges are directed into it.

• Conclusion: A vertex with in-degree zero in a directed graph is called a sink.

41. What conditions must a graph meet to be considered a tree?

1. It must be a directed graph

2. It must contain no cycles

3. It must be planar

4. It must be completely connected

Show me the answer

Answer: 2. It must contain no cycles

Explanation:

• Tree: A tree is a type of graph that must satisfy the following conditions:

  1. No Cycles: A tree must be acyclic, meaning it contains no cycles.

  2. Connected: A tree must be connected, meaning there is a path between any two vertices.

• Conclusion: A graph must be acyclic and connected to be considered a tree.

42. Where are the elements of a linked list stored?

1. In a structure

2. In an array

3. Anywhere the computer has space for them

4. In contiguous memory locations

Show me the answer

Answer: 3. Anywhere the computer has space for them

Explanation:

• Linked List: In a linked list, elements (nodes) are not stored in contiguous memory locations. Instead, each node contains a data field and a pointer to the next node, allowing the elements to be stored anywhere in memory.

• Conclusion: The elements of a linked list can be stored anywhere in memory, as long as each node points to the next node.

43. What data structure would be best suited for implementing a parentheses checker program?

1. List

2. Queue

3. Stack

4. Any of the above

Show me the answer

Answer: 3. Stack

Explanation:

• Parentheses Checker: A stack is ideal for checking balanced parentheses because it follows the Last-In-First-Out (LIFO) principle. When an opening parenthesis is encountered, it is pushed onto the stack. When a closing parenthesis is encountered, it is matched with the top element of the stack.

• Conclusion: A stack is the best data structure for implementing a parentheses checker program.

44. What data structure is required to perform level-order traversal on a binary tree?

1. Hash table

2. Queue

3. Binary search tree

4. Stack

Show me the answer

Answer: 2. Queue

Explanation:

• Level-Order Traversal: Level-order traversal visits nodes level by level, starting from the root. A queue is used to keep track of the nodes at the current level and their children.

• Conclusion: A queue is required to perform level-order traversal on a binary tree.

45. What data structure is required to convert an arithmetic expression in infix to its equivalent postfix notation?

1. Queue

2. Linked list

3. Binary search tree

4. None of above

Show me the answer

Answer: 4. None of above

Explanation:

• Infix to Postfix Conversion: The conversion of an infix expression to postfix notation typically requires a stack. The stack is used to keep track of operators and parentheses during the conversion process.

• Conclusion: A stack is the data structure required for converting an infix expression to postfix notation.

46. What type of binary tree has all levels except the last filled with the maximum number of nodes and all nodes in the last level having only one child, which is its left child?

1. Threaded tree

2. Complete binary tree

3. M-way search tree

4. Full binary tree

Show me the answer

Answer: 2. Complete binary tree

Explanation:

• Complete Binary Tree: A complete binary tree is a binary tree in which all levels except possibly the last are completely filled, and all nodes are as far left as possible.

• Conclusion: A complete binary tree satisfies the given conditions.

47. What data structure is most appropriate for implementing quick sort iteratively?

1. Deque

2. Queue

3. Stack

4. Priority queue

Show me the answer

Answer: 3. Stack

Explanation:

• Quick Sort Iteratively: Quick sort can be implemented iteratively using a stack to simulate the recursive calls. The stack is used to keep track of the subarrays that need to be sorted.

• Conclusion: A stack is the most appropriate data structure for implementing quick sort iteratively.

48. What is the number of edges in a complete graph of $n$ vertices?

1. $\frac{n(n+1)}{2}$

2. $\frac{n(n-1)}{2}$

3. $\frac{n^2}{2}$

4. $n$

Show me the answer

Answer: 2. $\frac{n(n-1)}{2}$

Explanation:

• Complete Graph: In a complete graph, every pair of distinct vertices is connected by a unique edge. The number of edges in a complete graph with $n$ vertices is given by the formula:

  $$\frac{n(n-1)}{2}$$
• Conclusion: The number of edges in a complete graph of $n$ vertices is $\frac{n(n-1)}{2}$.

49. What is the space complexity of bubble sort?

1. $O(1)$

2. $O(n^2)$

3. $O(2)$

4. None of the above

Show me the answer

Answer: 1. $O(1)$

Explanation:

• Bubble Sort: Bubble sort is an in-place sorting algorithm, meaning it does not require additional memory proportional to the input size. It sorts the array by swapping adjacent elements.

• Space Complexity: The space complexity of bubble sort is $O(1)$ because it uses a constant amount of extra space.

• Conclusion: The space complexity of bubble sort is $O(1)$.

50. What are two trees called if they have the same structure and node content?

1. Synonyms trees

2. Joint trees

3. Equivalent trees

4. Similar trees

Show me the answer

Answer: 3. Equivalent trees

Explanation:

• Equivalent Trees: Two trees are called equivalent if they have the same structure and the same content in corresponding nodes.

• Conclusion: Trees with the same structure and node content are called equivalent trees.