Which data structure is typically used to implement breadth-first search (BFS) in a graph?
A Array
B Stack
C Queue
D Linked List
BFS uses a queue to store the nodes to be visited. The algorithm explores the graph level by level, starting from a source node, processing all its neighbors before moving to the next level.
Which of the following is a characteristic of a binary search tree (BST)?
A Nodes have at most two children
B Each node stores multiple values
C Unordered structure
D Allows cycles
A binary search tree is a type of binary tree where each node has at most two children. The left child is smaller, and the right child is larger than the parent node, ensuring an ordered structure for efficient search.
Which tree type maintains a balance by enforcing constraints on its nodes?
A B-Tree
B AVL Tree
C Red-Black Tree
D Binary Tree
An AVL tree is a self-balancing binary search tree. It maintains a balance factor for each node to ensure that the height difference between the left and right subtrees is at most 1, ensuring O(log n) time complexity for search, insertion, and deletion.
What is the primary purpose of a hash table in computer science?
A To represent hierarchical relationships
B To store data dynamically
C To store data in an unordered manner for fast access
D To store elements in order
A hash table stores data using a hash function, allowing for fast data retrieval by mapping keys to specific indices in an array. This provides average time complexity of O(1) for search, insertion, and deletion.
Which of these is not an example of a balanced binary search tree?
A Binary Tree
B AVL Tree
C Red-Black Tree
D B-Tree
A standard binary tree does not necessarily maintain balance. In contrast, AVL trees and Red-Black trees are balanced to ensure efficient search and update operations. B-Trees are balanced but are more suitable for databases.
In which of the following scenarios would a priority queue be useful?
A Sorting a list of items
B Handling elements based on priority
C Managing function calls in recursion
D Storing large datasets
A priority queue is used to store elements with a priority, ensuring that the element with the highest (or lowest) priority is dequeued first. It is commonly used in scheduling algorithms and algorithms like Dijkstra’s shortest path.
What is the worst-case time complexity of quicksort?
A O(n)
B O(n log n)
C O(log n)
D O(n²)
In the worst-case scenario, where the pivot selection results in unbalanced partitions (such as when the input array is already sorted), quicksort can degrade to O(n²) time complexity. However, its average case is O(n log n).
What does a min-heap property ensure?
A The root contains the minimum element
B Each node is larger than its children
C The tree is perfectly balanced
D The root contains the maximum element
A min-heap is a binary tree where each parent node has a value smaller than or equal to its children, ensuring that the root node always contains the minimum element. It is used for efficient priority queue implementation.
What is the main feature of a circular linked list?
A Elements are sorted
B Last node points to the first node
C Nodes have two pointers
D List has a fixed size
A circular linked list is a variation of a linked list where the last node points back to the first node, forming a loop. This allows for continuous traversal of the list without a defined end.
What is the purpose of the depth-first search (DFS) algorithm in graph theory?
A To find the shortest path
B To check for cycles
C To visit all nodes by exploring as deep as possible
D To find the maximum node value
DFS explores a graph by starting at the root (or any arbitrary node) and exploring as deep as possible along each branch before backtracking. It is useful for pathfinding and topological sorting in directed acyclic graphs.
Which data structure is used for efficient dynamic memory allocation?
A Linked List
B Hash Table
C Queue
D Stack
A linked list is used for dynamic memory allocation because its nodes can be created or deleted at runtime without needing to resize a structure, unlike arrays. It allows for efficient allocation of memory as needed.
Which of the following sorting algorithms is in-place?
A Bubble Sort
B Quick Sort
C Merge Sort
D Radix Sort
Quick Sort is an in-place sorting algorithm, meaning it sorts the array without needing extra space for another array. It sorts by partitioning the array and recursively sorting the sub-arrays.
Which type of data structure is used to implement recursion?
A Array
B Tree
C Stack
D Linked List
A stack is used to implement recursion. When a function is called recursively, each call is pushed onto the stack with its local variables and return address, and popped when the function call completes.
Which of the following trees allows for efficient insertion, deletion, and search operations with a logarithmic time complexity?
A AVL Tree
B Red-Black Tree
C B-Tree
D All of the above
AVL trees, Red-Black trees, and B-Trees all provide efficient insertion, deletion, and search operations with O(log n) time complexity. They are self-balancing and ensure that operations are performed efficiently even with large datasets.
Which of the following graph traversal algorithms uses a queue?
A Dijkstra’s Algorithm
B Depth-First Search
C Bellman-Ford Algorithm
D Breadth-First Search
Breadth-First Search (BFS) uses a queue to store nodes that need to be explored. It explores the graph level by level, ensuring that all nodes at a given depth are processed before moving on to the next level.