Question 1: Which of the following properties hold for a B-Tree of order m?
A. Every node has at most m children.
B. Every non-root node has at least m/2 children.
C. The root has at least two children if it’s not a leaf node.
D. All of the above.
Answer: D
Explanation: These properties are the defining characteristics of a B-Tree. An internal node can have between ceil(m/2) and m child nodes, inclusive. The root must have at least two children if it is not a leaf node.
Question 2: In a B-Tree of order m, what is the maximum number of keys a node can hold?
A. m
B. m-1
C. 2m
D. 2m-1
Answer: B
Explanation: In a B-Tree of order m, every node can contain between 1 and m-1 keys.
Question 3: What is the worst-case time complexity of search, insert and delete operations in a B-tree?
A. O(log n)
B. O(n log n)
C. O(n)
D. O(1)
Answer: A
Explanation: The B-tree is height-balanced, so all leaves are at the same depth. Operations like search, insert, and delete require us to descend from the root to a leaf, which takes O(log n) time.
Question 4: What is the primary operation of Prim’s Algorithm?
A. Find the minimum spanning tree
B. Find the shortest path in the graph
C. Find all connected components in the graph
D. Find the maximum flow in the graph
Answer: A
Explanation: Prim’s Algorithm is used to find the minimum spanning tree of a connected, undirected graph.
Question 5: What is the worst-case time complexity of Prim’s Algorithm using binary heap?
A. O(V^2)
B. O(V+E)
C. O(E log V)
D. O(E + V log V)
Answer: D
Explanation: When implemented with a binary heap or priority queue, the time complexity of Prim’s Algorithm is O(E + V log V), where V is the number of vertices and E is the number of edges.
Question 6: What is the fundamental difference between Prim’s and Kruskal’s algorithms?
A. Prim’s constructs a minimum spanning tree, Kruskal’s doesn’t
B. Kruskal’s constructs a minimum spanning tree, Prim’s doesn’t
C. Prim’s starts from a given node, Kruskal’s starts from the smallest edge
D. Prim’s algorithm is faster than Kruskal’s
Answer: C
Explanation: Both Prim’s and Kruskal’s algorithms are used to find the minimum spanning tree. The main difference is in their approach: Prim’s algorithm starts from a specific vertex and keeps adding the minimum cost edge that connects a vertex in the tree to a vertex not in the tree, while Kruskal’s algorithm sorts all the edges and adds them one by one, provided that the addition of the edge doesn’t form a cycle.
Question 7: What is the worst-case time complexity of Kruskal’s algorithm?
A. O(V^2)
B. O(E log E)
C. O(E log V)
D. O(EV)
Answer: B
Explanation: The most time-consuming part of Kruskal’s algorithm is sorting the edges, which has a time complexity of O(E log E).
Question 8: In a simple graph with n vertices, what is the maximum number of edges?
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
Answer: C
Explanation: A simple graph is a graph in which no two edges connect the same pair of vertices and no edge connects a vertex to itself. Hence, for ‘n’ vertices, each vertex can connect to ‘n-1’ other vertices. Since each edge has been counted twice (once for each vertex), we divide by 2 to avoid double counting.
Question 9: In a directed acyclic graph (DAG), what is the time complexity of finding all the ancestors of a node?
A. O(V+E)
B. O(V^2)
C. O(E)
D. O(V)
Answer: A
Explanation: This operation can be completed by conducting a depth-first search (DFS) starting from the given node, which takes O(V+E) time, where V is the number of vertices and E is the number of edges.
Question 10: Which of the following graph traversal methods is used to perform a topological sort?
A. Breadth-First Search
B. Depth-First Search
C. Both Breadth-First and Depth-First Search
D. Neither Breadth-First nor Depth-First Search
Answer: B
Explanation: Topological sort can be performed using Depth-First Search (DFS).
Question 11: What is the time complexity of a topological sort?
A. O(V+E)
B. O(V^2)
C. O(E)
D. O(V)
Answer: A
Explanation: A topological sort can be performed in O(V+E) time using a depth-first search.
Question 12: In graph theory, a planar graph can be defined as:
A. A graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
B. A graph that can be drawn on a plane in such a way that no edges cross each other.
C. Both A and B
D. None of the above
Answer: C
Explanation: Both statements A and B define what a planar graph is. It is a graph that can be drawn on a plane in such a way that no edges cross each other except at their endpoints.
Question 13: What is the time complexity of the Bellman-Ford algorithm?
A. O(V+E)
B. O(VE)
C. O(E log V)
D. O(V log V)
Answer: B
Explanation: The Bellman-Ford algorithm has a time complexity of O(VE) as it relaxes all E edges V-1 times.
Question 14: What does the Euler’s formula state about a connected planar graph?
A. Vertices + Edges = Faces + 2
B. Vertices – Edges = Faces + 2
C. Vertices + Edges = Faces – 2
D. Vertices – Edges = Faces – 2
Answer: B
Explanation: Euler’s formula, applied to a connected planar graph, states that the number of vertices (V) minus the number of edges (E) plus the number of faces (F) is equal to 2: V – E + F = 2.
Question 15: What is the time complexity of the Floyd Warshall algorithm?
A. O(V+E)
B. O(VE)
C. O(V^3)
D. O(V^2 log V)
Answer: C
Explanation: The Floyd Warshall algorithm has a time complexity of O(V^3) as it uses three nested loops each iterating through V vertices.
Question 16: What is the time complexity of the Dijkstra’s algorithm using Fibonacci Heap?
A. O(V+E)
B. O(E + V log V)
C. O(V^3)
D. O(V^2)
Answer: B
Explanation: The Dijkstra’s algorithm has a time complexity of O(E + V log V) when implemented with Fibonacci Heap as priority queue, where V is the number of vertices and E is the number of edges.
Question 17: The adjacency matrix representation of a graph consumes memory in the order of:
A. O(V+E)
B. O(VE)
C. O(V^3)
D. O(V^2)
Answer: D
Explanation: The adjacency matrix representation of a graph consumes O(V^2) memory because it maintains a V x V matrix, where V is the number of vertices in the graph.
Question 18: What does the Handshaking Theorem state?
A. Every vertex has the same degree.
B. Sum of degrees of all vertices is twice the number of edges.
C. Sum of degrees of all vertices is equal to the number of edges.
D. Every vertex has a unique degree.
Answer: B
Explanation: The Handshaking Theorem states that the sum of the degrees of all the vertices of the graph is twice the number of edges.
Question 19: What is the space complexity of a Depth-First Search (DFS) traversal of a graph represented using adjacency list?
A. O(V)
B. O(E)
C. O(V + E)
D. O(V^2)
Answer: C
Explanation: In the worst-case scenario, the space complexity of DFS using an adjacency list is O(V + E), as all vertices and edges could be stored on the call stack during the traversal.
Question 20: What is the time complexity of checking whether a graph is Bipartite using Depth-First Search?
A. O(V)
B. O(E)
C. O(V + E)
D. O(V^2)
Answer: C
Explanation: The time complexity to check if a graph is bipartite using DFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph, as each vertex and each edge is explored exactly once.
Question 21: A stack follows which of the following data structures?
A. LIFO (Last In First Out)
B. FIFO (First In First Out)
C. Both A and B
D. None of the above
Answer: A
Explanation: Stack is a LIFO (Last In First Out) data structure, which means the last item inserted is the first one to get out.
Question 22: What is the maximum number of parentheses that will be on the stack at any one time for the expression a/(b+c)d-e(f+g)?
A. 1
B. 2
C. 3
D. 4
Answer: B
Explanation: The given expression has two pairs of parentheses. The maximum depth of nested parentheses is 1, so there will never be more than 2 parentheses on the stack at any one time.
Question 23: Which of the following is not a type of queue?
A. Simple Queue
B. Priority Queue
C. Circular Queue
D. Sorted Queue
Answer: D
Explanation: There is no specific data structure known as a ‘Sorted Queue’. The types of queue include Simple Queue, Priority Queue, and Circular Queue.
Question 24: The initial configuration of a queue is a, b, c, d (a is in the front). To get the configuration d, c, b, a, one needs a minimum of how many deletions and insertions?
A. 3 deletions and 3 insertions
B. 4 deletions and 4 insertions
C. 2 deletions and 2 insertions
D. 1 deletion and 1 insertion
Answer: B
Explanation: All 4 elements need to be removed and then re-inserted in reverse order.
Question 25: In a queue, the initial position is (F:5, R:5). What will be the position after performing the following operations: insert(10), insert(20), delete(), insert(30), delete()?
A. (F:7, R:7)
B. (F:7, R:8)
C. (F:6, R:7)
D. (F:6, R:8)
Answer: C
Explanation: Here F represents front and R represents rear. After performing all the operations, the front would have moved 2 places (due to two deletes), and the rear would have moved 3 places (due to three inserts). Hence, (F:6, R:7).
Question 26: Which of the following algorithms is NOT a use of stacks?
A. Backtracking
B. Parsing
C. Breadth First Search
D. Function call simulation
Answer: C
Explanation: Breadth First Search uses queues, not stacks. Backtracking, parsing and function call simulation use stacks.
Question 27: What is the worst-case time complexity of a push operation in a stack implemented as a linked list?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Answer: A
Explanation: The push operation in a stack implemented using a linked list takes constant time, O(1), as it always inserts the new element at the head of the list.
Question 28: What is the worst-case time complexity of a pop operation in a queue implemented as an array?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Answer: B
Explanation: The pop operation in a queue implemented using an array takes O(n) time in worst case as we remove an element from the front of the array and shift all other elements to fill up the space.
Question 29: What is the primary difference between a stack and a queue?
A. Stack follows LIFO, while Queue follows FIFO
B. Stack follows FIFO, while Queue follows LIFO
C. Stack is a linear data structure, while Queue is not
D. There is no difference
Answer: A
Explanation: A stack follows the LIFO (Last In First Out) principle, i.e., the element that is pushed last is the first one to be popped. On the other hand, a queue follows the FIFO (First In First Out) principle, i.e., the element that is added first is the first one to be removed.
Question 30: In a queue, if the elements are enqueued in the order A, B, C and D and dequeued twice, what is the next element to be dequeued?
A. A
B. B
C. C
D. D
Answer: C
Explanation: In a queue, the order of elements is FIFO (First In First Out). After enqueuing A, B, C and D in order, and performing dequeue operation twice, elements A and B are removed. Thus, the next element to be dequeued is C.
Question 31: Which data structure is used in Breadth-First Search (BFS) of a graph?
A. Stack
B. Queue
C. Tree
D. Graph
Answer: B
Explanation: In BFS traversal of a graph, we use a queue data structure. It helps to traverse all the vertices of a graph at the current level before moving to the next level.
Question 32: Which of the following is a real-life example of a queue?
A. Plates stacked over one another
B. People standing in a line to get a movie ticket
C. Both A and B
D. None of the above
Answer: B
Explanation: People standing in a line to get a movie ticket follow the FIFO (First In First Out) property of a queue, where the person who comes first gets the ticket first. The plates stacked over one another follow the LIFO (Last In First Out) property of a stack.
Question 33: What operation is used to add an element to a stack?
A. Enqueue
B. Dequeue
C. Push
D. Pop
Answer: C
Explanation: In the context of a stack, the operation of adding an element is referred to as a “push”.
Question 34: What operation is used to remove an element from a queue?
A. Enqueue
B. Dequeue
C. Push
D. Pop
Answer: B
Explanation: In the context of a queue, the operation of removing an element is referred to as a “dequeue”.
Question 35: What is the time complexity of the enqueue operation in a queue implemented as a linked list?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Answer: A
Explanation: The enqueue operation in a queue implemented using a linked list takes constant time, O(1), as it always inserts the new element at the end of the list.
Question 36: What is the time complexity of the pop operation in a stack implemented as an array?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)
Answer: A
Explanation: The pop operation in a stack implemented using an array takes constant time, O(1), as it always removes the element at the top of the stack.
Question 37: If the stack is implemented with a linked list, in what position are the push and pop operations performed?
A. At the beginning of the list
B. At the end of the list
C. Anywhere in the list
D. None of the above
Answer: A
Explanation: If the stack is implemented with a linked list, the push and pop operations are performed at the beginning of the list. This is done to achieve constant time complexity for these operations.
Question 38: What is underflow condition in data structures?
A. When a new element is inserted into a full stack or queue
B. When a new element is removed from an empty stack or queue
C. When there are no elements in a stack or queue
D. When a stack or queue is full
Answer: B
Explanation: The underflow condition is a state that occurs when we try to remove (pop or dequeue) an element from an empty stack or queue.
Question 39: In a stack, suppose we push the elements 1, 2, 3, 4 and then perform pop operations, what will be the order of elements which are popped out?
A. 1, 2, 3, 4
B. 4, 3, 2, 1
C. 4, 1, 3, 2
D. 2, 3, 1, 4
Answer: B
Explanation: As stack follows LIFO (Last In First Out) property, the elements will be popped out in the order: 4, 3, 2, 1.
Question 40: Which of the following applications may not be able to use queue data structure efficiently?
A. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
B. When a resource is shared among multiple consumers.
C. As a temporary storage for a running program.
D. In recursion mechanism.
Answer: D
Explanation: In recursion, stack is the appropriate data structure to keep track of function calls and returns. Queues are not efficient for this purpose because they follow the FIFO order, which is not suitable for the way recursion operates.
Question 41: Which of the following is not an advantage of linked lists over arrays?
A. Linked lists can grow and shrink during execution
B. Linked lists have constant time complexity for insertions and deletions
C. Linked lists do not need to be defined with an initial size
D. Linked lists allow for efficient use of memory
Answer: B
Explanation: Insertion and deletion operations in linked lists do not have constant time complexity. They can depend on the size of the list, and the position where the operations are performed.
Question 42: In a singly linked list, each node contains:
A. Data and a reference to the next node
B. Data and a reference to the previous node
C. Data and references to both the next and previous nodes
D. Data only
Answer: A
Explanation: Each node in a singly linked list contains the data and a reference (link) to the next node in the sequence.
Question 43: Which of the following is a characteristic of dynamic memory allocation?
A. Memory is allocated at compile time
B. Memory is allocated at runtime
C. Memory size has to be known beforehand
D. All of the above
Answer: B
Explanation: In dynamic memory allocation, memory is allocated during runtime, not at compile time. The size of memory does not need to be known beforehand.
Question 44: What is the time complexity of inserting a node at the beginning of a linked list?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
Answer: A
Explanation: Inserting a node at the beginning of a linked list can be done in constant time, O(1), as it does not depend on the size of the list.
Question 45: Which of the following functions is used to allocate memory dynamically in C++?
A. malloc()
B. calloc()
C. free()
D. new()
Answer: D
Explanation: In C++, the new operator is used for dynamic memory allocation.
Question 46: Which of the following functions is used to release dynamically allocated memory in C?
A. delete
B. free
C. remove
D. erase
Answer: B
Explanation: In C, the free function is used to release (or free up) dynamically allocated memory.
Question 47: What is the main disadvantage of a singly linked list?
A. It requires more memory than an array
B. It does not allow direct access to elements
C. It cannot be traversed in reverse
D. All of the above
Answer: D
Explanation: All listed options are disadvantages of a singly linked list. It requires more memory due to the storage of additional pointers, does not allow direct access to elements (only sequential access), and it cannot be traversed in reverse.
Question 48: Which of the following is not a type of linked list?
A. Singly Linked List
B. Doubly Linked List
C. Sorted Linked List
D. Circular Linked List
Answer: C
Explanation: Singly Linked List, Doubly Linked List, and Circular Linked List are types of linked lists. There is no specific ‘Sorted Linked List’ type. However, a linked list can be sorted by rearranging its nodes.
Question 49: What is the main advantage of using dynamic memory allocation?
A. Memory is more efficiently used
B. Programs using it run faster
C. Memory can be allocated whenever needed
D. All of the above
Answer: A, C
Explanation: Dynamic memory allocation allows for more efficient use of memory, as memory can be allocated when needed and deallocated when no longer needed.
Question 50: In a doubly linked list, which of the following scenarios takes O(1) time?
A. Inserting a node at the beginning
B. Deleting a node from the end
C. Searching for a node
D. Both A and B
Answer: D
Explanation: In a doubly linked list, both inserting a node at the beginning and deleting a node from the end can be done in constant time, O(1). Searching for a node is an O(n) operation as it could, in the worst case, involve traversing the whole list.
Question 51: Which of the following is true about the nodes in a linked list?
A. They must be stored in contiguous memory locations
B. They can be stored anywhere in memory
C. The starting node should always be the smallest node
D. None of the above
Answer: B
Explanation: In a linked list, nodes do not need to be stored in contiguous memory locations. They can be stored anywhere in memory, with each node pointing to the location of the next node.
Question 52: In dynamic memory allocation, what does the malloc() function return in C if it fails to allocate memory?
A. An error message
B. A NULL pointer
C. The memory address 0
D. It does not return anything
Answer: B
Explanation: If malloc() fails to allocate memory, it returns a NULL pointer.
Question 53: In C++, which operator is used to deallocate dynamically allocated memory?
A. free()
B. delete
C. clear()
D. None of the above
Answer: B
Explanation: In C++, the delete operator is used to deallocate memory that was previously allocated by new.
Question 54: Which of the following is a type of linked list that allows traversal in both directions?
A. Singly Linked List
B. Doubly Linked List
C. Circular Linked List
D. None of the above
Answer: B
Explanation: A Doubly Linked List allows for bidirectional traversal as each node has a pointer to the next node and a pointer to the previous node.
Question 55: Which function in C++ is used to find out the size of memory allocated dynamically?
A. sizeof()
B. length()
C. size()
D. None of the above
Answer: A
Explanation: The sizeof() function is used in C++ to find out the size of the memory (in bytes) allocated for any datatype, including dynamically allocated memory.
Question 56: What is the time complexity to add a node at the end of the linked list if we have a tail pointer?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
Answer: A
Explanation: If we maintain a tail pointer in the linked list, we can add a node at the end of the linked list in O(1) time complexity.
Question 57: Which of the following scenarios can cause memory leak in a program?
A. Allocating memory and not freeing it
B. Trying to access memory that has already been freed
C. Both A and B
D. None of the above
Answer: C
Explanation: Both allocating memory and not freeing it, and trying to access memory that has already been freed, can cause memory leaks in a program.
Question 58: In a circular linked list, the next pointer of the last node points to:
A. NULL
B. The first node
C. The last node itself
D. None of the above
Answer: B
Explanation: In a circular linked list, the next pointer of the last node points back to the first node.
Question 59: What is the main disadvantage of dynamic memory allocation?
A. It uses more memory than static allocation
B. It is slower than static allocation
C. It can lead to fragmentation
D. All of the above
Answer: D
Explanation: Dynamic memory allocation has all the mentioned disadvantages: It uses more memory than static allocation due to metadata and fragmentation, it is slower than static allocation, and it can lead to fragmentation if not managed correctly.
Question 60: In a linked list, the element which does not have a predecessor is:
A. Middle element
B. Last element
C. First element
D. Any random element
Answer: C
Explanation: In a linked list, the first element does not have a predecessor as it is the start of the list.
Question 61: What is the height of an AVL tree with a single node?
A. -1
B. 0
C. 1
D. 2
Answer: B
Explanation: The height of a tree is the longest path from the root to a leaf. For a single-node tree (just the root), the height is considered 0.
Question 62: After an element is inserted into an AVL tree, what is the maximum difference in height between the left and right subtrees of any node?
A. 0
B. 1
C. 2
D. 3
Answer: B
Explanation: By definition, AVL trees are self-balancing binary search trees where the difference in height between the left and right subtrees (the balance factor) of any node is at most 1.
Question 63: In a B-tree of order m, what is the maximum number of children a node can have?
A. m
B. m – 1
C. m + 1
D. 2m
Answer: A
Explanation: In a B-tree of order m, each node can have at most m children.
Question 64: In a pre-order tree traversal, which of the following actions is performed first?
A. Visit the root
B. Traverse the left subtree
C. Traverse the right subtree
D. All operations are performed simultaneously
Answer: A
Explanation: In a pre-order tree traversal (root-left-right), the root is visited first, followed by the left subtree, and then the right subtree.
Question 65: What is the minimum number of keys in a non-root node of a B-tree of order m?
A. m
B. m – 1
C. ceil(m/2) – 1
D. floor(m/2)
Answer: D
Explanation: In a B-tree of order m, each internal node (other than the root) must contain at least ceil(m/2) – 1 keys, which is equivalent to floor(m/2).
Question 66: In an in-order tree traversal, which of the following actions is performed last?
A. Visit the root
B. Traverse the left subtree
C. Traverse the right subtree
D. All operations are performed simultaneously
Answer: C
Explanation: In an in-order tree traversal (left-root-right), the traversal of the right subtree is performed last.
Question 67: Which of the following sequences could be the result of a post-order traversal of a binary search tree?
A. 5, 7, 6, 9, 11, 10, 8
B. 8, 10, 11, 9, 6, 7, 5
C. 5, 6, 7, 8, 9, 10, 11
D. 11, 10, 9, 8, 7, 6, 5
Answer: B
Explanation: A post-order traversal of a binary tree visits the left subtree, the right subtree, and the root node at the last. So, the highest value (root in this case) should be at the end of the traversal which is in option B.
Question 68: An AVL tree is:
A. Always a full binary tree
B. Always a complete binary tree
C. Always a binary search tree
D. None of the above
Answer: C
Explanation: An AVL tree is always a binary search tree, but it’s not always full or complete.
Question 69: What is the time complexity of AVL tree insertion?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: B
Explanation: AVL trees are balanced, so insertions take O(log n) time.
Question 70: What is the time complexity of B-tree insertion?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: B
Explanation: Like AVL trees, B-trees are also balanced, so insertions take O(log n) time.
Question 71: In a post-order traversal, the left and right subtrees are explored _______ the root.
A. before
B. after
C. before and after
D. either before or after
Answer: A
Explanation: In a post-order traversal (left-right-root), both the left and right subtrees are explored before the root.
Question 72: In an AVL tree, the balance factor of any node is:
A. Only 1
B. Only -1
C. Either 1, 0, or -1
D. None of the above
Answer: C
Explanation: In an AVL tree, the balance factor of any node is either 1, 0, or -1.
Question 73: Which of the following is not a property of a B-tree?
A. All leaves are at the same depth
B. All non-leaf nodes (except root) contain between ceil(m/2) – 1 and m – 1 keys
C. The root has at least two children if it is not a leaf node
D. The keys in each node are sorted in ascending order
Answer: B
Explanation: All non-leaf nodes (except for the root) in a B-tree contain at least ceil(m/2) keys and at most m – 1 keys.
Question 74: What rotation is used in AVL tree if the balance factor becomes 2 and the right child has a balance factor of -1?
A. Right rotation
B. Left rotation
C. Left-right rotation
D. Right-left rotation
Answer: C
Explanation: If the balance factor of a node in an AVL tree is 2 and its right child has a balance factor of -1, a left-right rotation is needed.
Question 75: Which of the following tree traversal methods is depth-first?
A. In-order
B. Pre-order
C. Post-order
D. All of the above
Answer: D
Explanation: All the listed traversal methods (in-order, pre-order, and post-order) are depth-first traversals.
Question 76: What is the worst-case space complexity of an AVL tree?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: C
Explanation: The worst-case space complexity of an AVL tree is O(n) as each node uses a constant amount of space, and there are n nodes in the tree.
Question 77: What is the minimum number of nodes in a B-tree of height h and order m?
A. m^h
B. m^(h-1)
C. h^m
D. (m-1)^h
Answer: A
Explanation: The minimum number of nodes in a B-tree of height h and order m is m^h.
