1Which of the following data structures is considered a non-linear data structure?
A.Stack
B.Queue
C.Linked List
D.Tree
Correct Answer: Tree
Explanation:Stacks, Queues, and Linked Lists are linear data structures where elements are arranged sequentially. A Tree is a hierarchical, non-linear data structure.
Incorrect! Try again.
2In the context of algorithm analysis, which notation represents the asymptotic upper bound of the time requirement?
A.Big Omega ()
B.Big Theta ()
C.Big Oh ()
D.Little oh ()
Correct Answer: Big Oh ()
Explanation:Big Oh () notation is used to describe the asymptotic upper bound, representing the worst-case scenario for time complexity.
Incorrect! Try again.
3What is the primary advantage of a Linked List over an Array?
A.Random access to elements
B.Dynamic size and efficient insertion/deletion
C.Memory locality
D.Lower memory overhead per element
Correct Answer: Dynamic size and efficient insertion/deletion
Explanation:Linked lists can grow dynamically and allow insertion or deletion (given a pointer to the location), whereas arrays have fixed size and require shifting elements for insertion/deletion.
Incorrect! Try again.
4In a Singly Linked List, what is the time complexity to access the element?
A.
B.
C.
D.
Correct Answer:
Explanation:Linked lists do not support random access. To find the node, you must traverse from the head through nodes, resulting in linear time complexity.
Incorrect! Try again.
5Which type of Linked List allows traversal in both forward and backward directions?
A.Singly Linked List
B.Circular Singly Linked List
C.Doubly Linked List
D.Priority List
Correct Answer: Doubly Linked List
Explanation:A Doubly Linked List contains nodes with two pointers: one pointing to the next node and one pointing to the previous node, allowing bidirectional traversal.
Incorrect! Try again.
6A pointer in a linked list that does not point to any valid memory location is generally referred to as:
A.Void pointer
B.Null pointer
C.Dangling pointer
D.Wild pointer
Correct Answer: Null pointer
Explanation:In linked lists, the next pointer of the last node is typically set to NULL to indicate the end of the list.
Incorrect! Try again.
7If a circular linked list has a pointer to the last node, what is the time complexity to insert a node at the beginning of the list?
A.
B.
C.
D.
Correct Answer:
Explanation:If you have a pointer to the last node (tail), tail->next points to the head. You can insert a new node, update pointers, and update tail in constant time.
Incorrect! Try again.
8Which data structure follows the LIFO (Last In, First Out) principle?
A.Queue
B.Stack
C.Tree
D.Graph
Correct Answer: Stack
Explanation:A Stack adds and removes elements from the same end (the top), adhering to the Last In, First Out principle.
Incorrect! Try again.
9What is the result of evaluating the postfix expression: ?
10Which data structure is implicitly used by the system to handle function calls and recursion?
A.Queue
B.Heap
C.Stack
D.Hash Table
Correct Answer: Stack
Explanation:The system call stack is used to store stack frames (local variables, return addresses) for active function calls, supporting recursion.
Incorrect! Try again.
11In a Queue implemented using a circular array of size , the condition for the queue being full is:
A.front == rear
B.rear == N - 1
C.(rear + 1) % N == front
D.(front + 1) % N == rear
Correct Answer: (rear + 1) % N == front
Explanation:In a circular queue, to distinguish between full and empty states, we typically leave one space unused or maintain a count. Using the pointer method, full is defined when the next position of rear wraps around to front.
Incorrect! Try again.
12Which operation removes an element from the front of a Queue?
A.Push
B.Pop
C.Dequeue
D.Enqueue
Correct Answer: Dequeue
Explanation:Enqueue adds to the rear, and Dequeue removes from the front of a Queue.
Incorrect! Try again.
13A double-ended queue (Deque) allows insertion and deletion at:
A.Only the front
B.Only the rear
C.Both the front and the rear
D. The middle
Correct Answer: Both the front and the rear
Explanation:A Deque (Double Ended Queue) is a generalized version of a queue that allows insertion and deletion at both ends.
Incorrect! Try again.
14Implementing a Queue using two Stacks requires how many stacks?
A.1
B.2
C.3
D.4
Correct Answer: 2
Explanation:One stack is used for enqueue operations, and the second stack is used to reverse the order for dequeue operations to maintain FIFO order.
Incorrect! Try again.
15What is the maximum number of nodes in a binary tree of height (where the root is at height 0)?
A.
B.
C.
D.
Correct Answer:
Explanation:A perfect binary tree of height has nodes, which sums to a geometric series totaling .
Incorrect! Try again.
16Which tree traversal visits the root node, then the left subtree, and finally the right subtree?
A.Inorder
B.Preorder
C.Postorder
D.Level Order
Correct Answer: Preorder
Explanation:Preorder traversal follows the order: Root Left Right.
Incorrect! Try again.
17In a Binary Search Tree (BST), the Inorder traversal produces:
A.Nodes in sorted non-decreasing order
B.Nodes in sorted non-increasing order
C.Random order
D.Nodes based on their level
Correct Answer: Nodes in sorted non-decreasing order
Explanation:Inorder traversal (Left, Root, Right) on a BST visits smaller values, then the value itself, then larger values, resulting in a sorted sequence.
Incorrect! Try again.
18What is the worst-case time complexity for searching in an unbalanced Binary Search Tree?
A.
B.
C.
D.
Correct Answer:
Explanation:In the worst case (a skewed tree behaving like a linked list), the height becomes , so the search takes linear time .
Incorrect! Try again.
19An AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than:
A.0
B.1
C.2
D.Any value
Correct Answer: 1
Explanation:The balance factor in an AVL tree (Height of Left - Height of Right) must be .
Incorrect! Try again.
20The number of edges in a tree with nodes is always:
A.
B.
C.
D.
Correct Answer:
Explanation:A tree is a connected acyclic graph. To connect nodes without cycles, exactly edges are required.
Incorrect! Try again.
21Which data structure is commonly used to implement Breadth-First Search (BFS) in a graph?
A.Stack
B.Queue
C.Heap
D.Hash Map
Correct Answer: Queue
Explanation:BFS explores neighbors level by level, which requires a Queue (FIFO) to manage the order of visitation.
Incorrect! Try again.
22Which data structure is commonly used to implement Depth-First Search (DFS) in a graph?
A.Queue
B.Stack
C.Priority Queue
D.Tree
Correct Answer: Stack
Explanation:DFS explores as deep as possible along each branch before backtracking, which corresponds to LIFO behavior (Stack). Recursion also implicitly uses a stack.
Incorrect! Try again.
23In a graph represented by an Adjacency Matrix , if there is an edge between vertex and vertex , then:
A.
B. (or weight)
C.
D.
Correct Answer: (or weight)
Explanation:In an adjacency matrix, a non-zero value (typically 1 for unweighted graphs) at index indicates the existence of an edge from to .
Incorrect! Try again.
24What is the space complexity of an Adjacency List representation for a graph with vertices and edges?
A.
B.
C.
D.
Correct Answer:
Explanation:An adjacency list stores a list for each vertex. The total storage is the number of vertices plus the total number of edges stored in those lists.
Incorrect! Try again.
25Dijkstra's algorithm is used for:
A.Finding the Minimum Spanning Tree
B.Finding the Shortest Path from a source node to all other nodes
C.Topological Sorting
D.Detecting cycles in a graph
Correct Answer: Finding the Shortest Path from a source node to all other nodes
Explanation:Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights.
Incorrect! Try again.
26Which algorithm is used to find the Minimum Spanning Tree (MST) of a graph?
A.DFS
B.Floyd-Warshall
C.Kruskal's Algorithm
D.Binary Search
Correct Answer: Kruskal's Algorithm
Explanation:Kruskal's algorithm and Prim's algorithm are standard greedy algorithms used to find the MST of a weighted undirected graph.
Incorrect! Try again.
27Topological Sort is applicable to which type of graph?
A.Undirected Cyclic Graph
B.Directed Acyclic Graph (DAG)
C.Undirected Acyclic Graph
D.Any Directed Graph
Correct Answer: Directed Acyclic Graph (DAG)
Explanation:Topological sorting is a linear ordering of vertices such that for every directed edge , vertex comes before . This is only possible if there are no cycles (DAG).
Incorrect! Try again.
28In an undirected graph, the sum of the degrees of all vertices is equal to:
A.The number of edges
B.
C.
D.
Correct Answer:
Explanation:This is the Handshaking Lemma. Every edge contributes to the degree of two vertices, so the sum of degrees is twice the number of edges.
Incorrect! Try again.
29A complete binary tree has a property that it is filled:
A.From right to left
B.From left to right on the last level
C.Randomly
D.Only on the left side
Correct Answer: From left to right on the last level
Explanation:In a complete binary tree, all levels are fully filled except possibly the last, which is filled from left to right.
Incorrect! Try again.
30How many different binary trees can be constructed with distinct nodes?
A.
B.
C.
D.
Correct Answer:
Explanation:The number of tree shapes is the Catalan number . Since the nodes are distinct (labeled), we multiply by for the permutations.
Incorrect! Try again.
31Which data structure is best suited for implementing a Priority Queue?
A.Array
B.Linked List
C.Heap
D.Stack
Correct Answer: Heap
Explanation:Heaps (Min-Heap or Max-Heap) allow efficient access to the highest/lowest priority element () and efficient insertion/deletion ().
Incorrect! Try again.
32In a Max-Heap, the value of a parent node is always:
A.Less than or equal to its children
B.Greater than or equal to its children
C.Equal to the sum of its children
D.Half of the left child
Correct Answer: Greater than or equal to its children
Explanation:The max-heap property ensures the root contains the maximum element and every parent is greater than or equal to its children.
Incorrect! Try again.
33If a binary heap is stored in an array (0-indexed), the left child of the node at index is located at:
A.
B.
C.
D.
Correct Answer:
Explanation:In a 0-indexed array representation of a binary heap, the left child is at and the right child is at .
Incorrect! Try again.
34What is the time complexity to insert a new element into a binary heap with elements?
A.
B.
C.
D.
Correct Answer:
Explanation:Insertion involves adding the element to the end and 'bubbling up' (heapify up) to restore the heap property, which takes time proportional to the height of the tree ().
Incorrect! Try again.
35Heap Sort has a worst-case time complexity of:
A.
B.
C.
D.
Correct Answer:
Explanation:Heap sort involves building a heap () and then extracting the max element times (), resulting in .
Incorrect! Try again.
36A situation where two different keys map to the same index in a Hash Table is called:
A.Rehashing
B.Collision
C.Overflow
D.Clustering
Correct Answer: Collision
Explanation:A collision occurs when the hash function generates the same index for two distinct keys.
Incorrect! Try again.
37Which of the following is a technique to resolve hash collisions?
A.Binary Search
B.Chaining
C.Merge Sort
D.Heapify
Correct Answer: Chaining
Explanation:Chaining resolves collisions by maintaining a linked list (or other structure) at each hash bucket to store multiple elements.
Incorrect! Try again.
38In Open Addressing, which probing method calculates the interval between probes using a second hash function?
A.Linear Probing
B.Quadratic Probing
C.Double Hashing
D.Separate Chaining
Correct Answer: Double Hashing
Explanation:Double Hashing uses a second hash function to determine the step size when a collision occurs, reducing clustering.
Incorrect! Try again.
39The Load Factor () of a hash table is defined as:
A.Number of buckets / Number of elements
B.Number of elements / Number of buckets
C.Number of collisions / Number of buckets
D.Size of largest chain
Correct Answer: Number of elements / Number of buckets
Explanation:The load factor is the ratio of stored elements to the table size, indicating how full the hash table is.
Incorrect! Try again.
40What is the average time complexity for Search, Insert, and Delete operations in a well-implemented Hash Table?
A.
B.
C.
D.
Correct Answer:
Explanation:With a good hash function and low load factor, average case operations are constant time.
Incorrect! Try again.
41Which traversal of a Binary Search Tree (BST) sorts the elements?
A.Preorder
B.Inorder
C.Postorder
D.Level Order
Correct Answer: Inorder
Explanation:Inorder traversal of a BST visits the nodes in ascending sorted order.
Incorrect! Try again.
42What is the height of a balanced binary search tree with nodes?
A.
B.
C.
D.
Correct Answer:
Explanation:Balanced trees (like AVL or Red-Black) maintain a height of to ensure efficient operations.
Incorrect! Try again.
43Converting a general tree to a binary tree typically involves the representation:
A.Left-Child, Right-Sibling
B.Parent Pointer
C.Adjacency Matrix
D.Heap Array
Correct Answer: Left-Child, Right-Sibling
Explanation:The Left-Child, Right-Sibling representation allows any general tree (nodes with arbitrary number of children) to be represented as a binary tree.
Incorrect! Try again.
44Which of the following data structures is most appropriate for a dictionary implementation (looking up definitions by words)?
A.Stack
B.Linked List
C.Hash Table
D.Queue
Correct Answer: Hash Table
Explanation:Dictionaries require fast lookups based on a key (the word), which Hash Tables provide ( average).
Incorrect! Try again.
45A graph is considered connected if:
A.There is a path between every pair of vertices
B.There are no cycles
C.Every vertex has degree 1
D.It is a complete graph
Correct Answer: There is a path between every pair of vertices
Explanation:Connectivity implies that you can travel from any node to any other node via edges.
Incorrect! Try again.
46In a binary heap, the 'Heapify' operation usually takes time proportional to:
A.The number of nodes
B.The height of the tree
C.Constant time
D.
Correct Answer: The height of the tree
Explanation:Heapify fixes a violation of the heap property at a specific node by trickling it down (or up) the height of the tree.
Incorrect! Try again.
47The post-fix form of the expression is:
A.
B.
C.
D.
Correct Answer:
Explanation:Multiplication and Division have higher precedence. . . Then add: .
Incorrect! Try again.
48Which data structure is used to check for balanced parentheses in an expression?
A.Queue
B.Stack
C.Linked List
D.Binary Tree
Correct Answer: Stack
Explanation:A stack is used to push opening brackets and pop when a matching closing bracket is found.
Incorrect! Try again.
49Deletion of a node from a Doubly Linked List involves changing how many pointers (assuming the node is not head/tail)?
A.1
B.2
C.3
D.4
Correct Answer: 2
Explanation:You must update the next pointer of the previous node and the prev pointer of the next node. (Technically 2 nodes are updated, modifying 2 pointers within the list structure).
Incorrect! Try again.
50In the context of Hashing, what is a 'Perfect Hash Function'?
A.A function that is very fast to compute
B.A function that maps every key to a distinct integer with no collisions
C.A function that uses cryptographic security
D.A function with load factor 1.0
Correct Answer: A function that maps every key to a distinct integer with no collisions
Explanation:A perfect hash function maps a static set of keys to a table with no collisions.