Quick recall · 290 cards
Short MCQ-style retrieval prompts. Tap a card to reveal the answer.
PYQ
Tap to reveal →
Which of the following is true about circular linked lists? (A) Last node points to first node (B) Can traverse only forward (C) Requires extra memory than singly linked list (D) Both A and C
D · Both A and C
PYQ
Tap to reveal →
Two stacks are implemented using a single array of size MAXSIZE. One stack grows from the left end (top1) and the other from the right end (top2). Which condition correctly checks if both stacks are full?
D · (d) top1 = top2 - 1
PYQ
Tap to reveal →
A queue is defined as a linear data structure that operates on which principle?
B · First In First Out (FIFO)
PYQ
Tap to reveal →
What is the time complexity of the dequeue operation in a basic array-based queue implementation where elements need to shift?
C · O(n)
PYQ
Tap to reveal →
Which of the following data structure implementations can achieve O(1) time complexity for all queue operations?
B · Circular queue using modular arithmetic
PYQ
Tap to reveal →
What is the formula for calculating the index after 'last' in a circular array queue of CAPACITY elements?
B · (last + 1) % CAPACITY
PYQ
Tap to reveal →
Which algorithm commonly uses a queue data structure for graph traversal?
B · Breadth-First Search (BFS)
PYQ
Tap to reveal →
What is the primary advantage of using a circular queue over a simple array-based queue?
B · It achieves O(1) dequeue operations without element shifting
PYQ
Tap to reveal →
With what data structure can a priority queue be implemented?
C · Heap
PYQ
Tap to reveal →
Which of the following is not an application of priority queue?
B · Undo operation
PYQ
Tap to reveal →
What is the time complexity to insert a node based on key in a priority queue implemented using a heap?
B · O(log n)
PYQ
Tap to reveal →
Which of the following is not an advantage of a priority queue?
D · Easy to delete elements in any case
Question bank
Tap to reveal →
Which of the following best defines an array?
B · A collection of elements of the same data type stored in contiguous memory locations
An array is a collection of elements of the same data type stored in contiguous memory locations, allowing efficient indexing.
Question bank
Tap to reveal →
Which characteristic is NOT true about arrays?
B · Array size can be changed dynamically during runtime in static arrays
Static arrays have a fixed size that cannot be changed during runtime; dynamic arrays allow resizing.
Question bank
Tap to reveal →
Which of the following is a key characteristic of arrays?
C · Elements can be accessed in constant time using an index
Arrays allow constant time access to elements via their index due to contiguous memory allocation.
Question bank
Tap to reveal →
Which of the following is NOT a type of array?
C · Linked array
Linked array is not a standard type of array; arrays are classified by their dimensions such as 1D, 2D, and multi-dimensional.
Question bank
Tap to reveal →
Refer to the diagram below showing a 2D array. What is the index of the element containing value 15?
A · [1][2]
In the given 2D array diagram, the element 15 is located at row 1, column 2 (0-based indexing).
Question bank
Tap to reveal →
Which of the following correctly describes a multi-dimensional array?
B · An array with multiple rows and columns, possibly more than two dimensions
Multi-dimensional arrays have multiple rows and columns and can extend beyond two dimensions.
Question bank
Tap to reveal →
Which of the following is the correct way to declare a 3D array in C?
B · int arr[3][4][5];
A 3D array declaration requires three dimensions specified, e.g., int arr[3][4][5];
Question bank
Tap to reveal →
Refer to the diagram below representing a 1D array in memory. What is the memory address of the element at index 3 if the base address is 1000 and each element occupies 4 bytes?
A · 1012
Address of element at index i = base_address + i * size_of_element = 1000 + 3*4 = 1012. But since 0-based indexing, index 3 means 4th element, so 1000 + 3*4 = 1012.
Question bank
Tap to reveal →
How are elements of a 2D array stored in row-major order in memory?
B · Elements of each row are stored contiguously
In row-major order, elements of each row are stored contiguously in memory.
Question bank
Tap to reveal →
Refer to the diagram below showing memory layout of a 2D array stored in column-major order. Which element is stored immediately after element at position [0][1]?
A · Element at [1][1]
In column-major order, elements in the same column are stored contiguously. So after [0][1], [1][1] is stored.
Question bank
Tap to reveal →
What is the formula to calculate the address of element \( A[i] \) in a 1D array stored at base address \( B \) where each element occupies \( s \) bytes?
B · \( B + i \times s \)
The address of element \( A[i] \) is calculated as \( B + i \times s \), where \( i \) is the index and \( s \) is the size of each element.
Question bank
Tap to reveal →
Which of the following operations is NOT typically efficient in arrays?
D · Insertion at the beginning
Insertion at the beginning requires shifting all elements, making it inefficient in arrays.
Question bank
Tap to reveal →
Which array operation has a time complexity of \( O(n) \) in the worst case?
B · Searching for an element in an unsorted array
Searching for an element in an unsorted array requires scanning all elements, resulting in \( O(n) \) time complexity.
Question bank
Tap to reveal →
Refer to the diagram below showing an array before and after insertion at index 2. Which element is shifted to index 3 after insertion?
B · Element originally at index 2
Insertion at index 2 shifts the element originally at index 2 to index 3 to make space for the new element.
Question bank
Tap to reveal →
Which searching algorithm is most efficient for a sorted array?
B · Binary Search
Binary Search is most efficient for sorted arrays with \( O(\log n) \) complexity.
Question bank
Tap to reveal →
Which of the following is a limitation of arrays?
B · Fixed size in static arrays
Static arrays have a fixed size which cannot be changed after allocation, limiting flexibility.
Question bank
Tap to reveal →
Which of the following is NOT a limitation of arrays?
D · Dynamic resizing without overhead
Dynamic resizing without overhead is not a limitation; arrays typically do not support dynamic resizing without overhead.
Question bank
Tap to reveal →
Which limitation of arrays affects their use in applications requiring frequent insertions and deletions?
B · Contiguous memory allocation
Contiguous memory allocation makes insertion and deletion expensive as elements need to be shifted.
Question bank
Tap to reveal →
Which of the following is a common application of arrays?
B · Storing fixed-size collections of elements
Arrays are commonly used to store fixed-size collections of homogeneous elements.
Question bank
Tap to reveal →
Arrays are widely used in which of the following applications?
A · Implementing stacks and queues
Arrays are used to implement linear data structures like stacks and queues due to their contiguous memory layout.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of arrays?
C · Dynamic memory management
Dynamic memory management is not typically implemented using arrays; arrays have fixed or semi-fixed sizes.
Question bank
Tap to reveal →
Refer to the diagram below illustrating array indexing. What is the index of the element with value 8?
A · 3
The element with value 8 is at index 3 (0-based indexing) as shown in the diagram.
Question bank
Tap to reveal →
What is the address calculation formula for element \( A[i][j] \) in a 2D array stored in row-major order with base address \( B \), number of columns \( n \), and element size \( s \)?
B · \( B + (i \times n + j) \times s \)
In row-major order, address = \( B + (i \times n + j) \times s \), where \( i \) is row and \( j \) is column index.
Question bank
Tap to reveal →
Refer to the diagram below showing address calculation flowchart for a 1D array. Which step calculates the offset for element \( i \)?
A · Multiply index by element size
The offset is calculated by multiplying the index \( i \) by the element size.
Question bank
Tap to reveal →
Which of the following correctly describes static arrays?
B · Size is fixed at compile time
Static arrays have a fixed size determined at compile time and cannot be resized during runtime.
Question bank
Tap to reveal →
Which of the following is a key advantage of dynamic arrays over static arrays?
B · Ability to resize during runtime
Dynamic arrays can resize during runtime, allowing flexibility in the number of elements stored.
Question bank
Tap to reveal →
Refer to the diagram below comparing static and dynamic arrays. Which array type allows resizing after initial allocation?
B · Dynamic array
Dynamic arrays allow resizing after initial allocation, unlike static arrays.
Question bank
Tap to reveal →
Which of the following is a challenge when implementing dynamic arrays?
B · Overhead of resizing and copying elements
Dynamic arrays require resizing which involves allocating new memory and copying existing elements, causing overhead.
Question bank
Tap to reveal →
Refer to the diagram below showing address calculation for a 2D array. If base address is 2000, element size is 4 bytes, number of columns is 5, what is the address of element \( A[2][3] \)?
D · 2052
Address = 2000 + (2*5 + 3)*4 = 2000 + (10 + 3)*4 = 2000 + 52 = 2052. The correct answer should be 2052, option D.
Question bank
Tap to reveal →
Which of the following best defines an array?
B · A collection of elements of the same data type stored at contiguous memory locations
An array is a collection of elements of the same data type stored at contiguous memory locations, allowing efficient indexing.
Question bank
Tap to reveal →
Which characteristic is NOT true for arrays?
B · Array size can be changed dynamically without reallocation
Arrays have a fixed size once declared; their size cannot be changed dynamically without creating a new array.
Question bank
Tap to reveal →
What is the index of the first element in a typical array in most programming languages?
A · 0
Most programming languages use zero-based indexing, so the first element is at index 0.
Question bank
Tap to reveal →
Which of the following is a key characteristic of arrays?
D · Elements are stored contiguously and accessed via indices
Arrays store elements contiguously in memory and allow direct access using indices.
Question bank
Tap to reveal →
Which of the following is NOT a valid type of array?
C · Linked array
Linked array is not a standard type; arrays are typically one-dimensional, two-dimensional, or multi-dimensional.
Question bank
Tap to reveal →
How is a two-dimensional array typically represented in memory?
B · As a contiguous block of memory with row-major or column-major ordering
Two-dimensional arrays are stored as a contiguous block of memory either in row-major or column-major order.
Question bank
Tap to reveal →
Consider a 3D array declared as int arr[3][4][5]. How many total elements does it contain?
B · 60
Total elements = 3 * 4 * 5 = 60.
Question bank
Tap to reveal →
Which of the following statements about multi-dimensional arrays is true?
C · They are stored in memory as a linear sequence
Multi-dimensional arrays are stored as a linear sequence in memory using row-major or column-major order.
Question bank
Tap to reveal →
Refer to the diagram below showing a 3x3 array stored in row-major order. What is the memory address of element \( arr[2][1] \) if the base address is 1000 and each element occupies 4 bytes?
B · 1016
Question bank
Tap to reveal →
Which memory layout accesses elements in column-major order?
B · Elements of each column are stored contiguously
Column-major order stores elements of each column contiguously in memory.
Question bank
Tap to reveal →
Refer to the diagram below showing row-major and column-major storage of a 2x3 array. Which of the following is the correct sequence of elements in memory for column-major order?
B · a[0][0], a[1][0], a[0][1], a[1][1], a[0][2], a[1][2]
In column-major order, elements are stored column-wise: first all elements of column 0, then column 1, and so on.
Question bank
Tap to reveal →
Which of the following operations on arrays has the highest time complexity in the worst case?
C · Searching for an element
Searching an element in an unsorted array requires checking each element, resulting in O(n) time complexity.
Question bank
Tap to reveal →
Which operation is most costly in terms of time complexity when performed on an array?
B · Inserting an element at the beginning
Inserting at the beginning requires shifting all elements, resulting in O(n) time complexity.
Question bank
Tap to reveal →
Which of the following is the correct sequence of steps to delete an element at index \( i \) in an array?
A · Shift elements from \( i+1 \) to end one position left, then reduce size
Deleting an element requires shifting subsequent elements left to fill the gap, then reducing the logical size.
Question bank
Tap to reveal →
Which of the following is true about searching an element in an unsorted array?
B · Linear search is required with O(n) time complexity
In an unsorted array, linear search is required, which has O(n) time complexity.
Question bank
Tap to reveal →
Refer to the diagram below showing an array before and after insertion at index 2. What is the new element at index 3 after insertion?
A · Original element at index 2
Elements from index 2 onwards are shifted right; the original element at index 2 moves to index 3.
Question bank
Tap to reveal →
Which of the following is a major limitation of arrays?
B · Fixed size leading to inefficient memory usage
Arrays have a fixed size which cannot be changed dynamically, leading to potential memory wastage or overflow.
Question bank
Tap to reveal →
Which of the following is NOT a limitation of arrays?
C · Supports dynamic resizing automatically
Arrays do not support automatic dynamic resizing; this is a limitation.
Question bank
Tap to reveal →
Which of the following is a limitation when using arrays for data storage?
B · Fixed size leading to overflow or underutilization
Fixed size arrays can cause overflow if size is underestimated or waste memory if overestimated.
Question bank
Tap to reveal →
Which of the following is a common application of arrays?
B · Storing fixed-size collections of homogeneous data
Arrays are used to store fixed-size collections of elements of the same type.
Question bank
Tap to reveal →
Arrays are commonly used in which of the following scenarios?
A · Implementing stacks and queues
Stacks and queues can be efficiently implemented using arrays due to their linear structure.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of arrays?
D · Representing hierarchical data
Hierarchical data is better represented by trees, not arrays.
Question bank
Tap to reveal →
Refer to the diagram below showing an array with base address 2000 and element size 4 bytes. What is the address of \( arr[5] \)?
A · 2020
Address = base + index * element_size = 2000 + 5*4 = 2020.
Question bank
Tap to reveal →
Given a one-dimensional array with base address \( B \), element size \( s \), and index \( i \), which formula correctly calculates the address of \( arr[i] \)?
A · \( B + i \times s \)
Address calculation for arrays uses the formula \( B + i \times s \) where \( i \) is the index.
Question bank
Tap to reveal →
Refer to the diagram below illustrating a 2D array stored in row-major order. What is the address of element \( arr[1][2] \) if base address is 5000, each element size is 2 bytes, and the array dimensions are 3x4?
B · 5012
Address = base + ((row * number_of_columns) + column) * element_size = 5000 + ((1*4)+2)*2 = 5000 + (4+2)*2 = 5000 + 12 = 5012. Correct answer is 5012, option B.
Question bank
Tap to reveal →
Which of the following is a key difference between static and dynamic arrays?
C · Static arrays have fixed size determined at compile time, dynamic arrays can resize at runtime
Static arrays have fixed sizes determined at compile time, while dynamic arrays can resize during execution.
Question bank
Tap to reveal →
Which of the following is true about dynamic arrays compared to static arrays?
B · Dynamic arrays allow resizing and can grow or shrink during runtime
Dynamic arrays can resize during runtime, allowing flexible memory usage.
Question bank
Tap to reveal →
Which of the following is NOT an advantage of dynamic arrays over static arrays?
C · Faster access time due to contiguous memory
Both static and dynamic arrays have similar access times; dynamic arrays do not have faster access.
Question bank
Tap to reveal →
Refer to the diagram below showing static and dynamic arrays. Which statement correctly describes the memory allocation shown?
B · Static array size is fixed, dynamic array size can change as shown
Static arrays have fixed size allocated at compile time, dynamic arrays can resize during runtime as shown.
Question bank
Tap to reveal →
Which of the following best describes the address calculation for a two-dimensional array stored in row-major order?
B · \( Address = Base + (Row \times NumberOfColumns + Column) \times ElementSize \)
In row-major order, address is calculated as \( Base + (Row \times NumberOfColumns + Column) \times ElementSize \).
Question bank
Tap to reveal →
Which of the following operations on arrays typically requires shifting elements and thus has \( O(n) \) time complexity?
C · Insertion at the beginning
Insertion at the beginning requires shifting all elements to the right, resulting in \( O(n) \) time complexity.
Question bank
Tap to reveal →
Which of the following is NOT a characteristic of static arrays?
C · Can grow or shrink dynamically
Static arrays cannot grow or shrink dynamically; their size is fixed.
Question bank
Tap to reveal →
Which of the following best explains why arrays have limitations in insertion and deletion operations?
B · Because arrays require shifting elements to maintain order
Insertion and deletion require shifting elements to maintain contiguous order, making these operations costly.
Question bank
Tap to reveal →
Which of the following best defines a linked list?
B · A linear data structure where each element points to the next element
A linked list is a linear data structure where each element (node) contains data and a pointer to the next element, allowing dynamic memory allocation and non-contiguous storage.
Question bank
Tap to reveal →
What is the primary difference between a linked list and an array?
C · Linked lists use pointers to connect elements, arrays use indices
Linked lists use pointers to link nodes, allowing non-contiguous memory allocation, whereas arrays use indices and require contiguous memory.
Question bank
Tap to reveal →
Refer to the diagram below showing a linked list node structure. Which part of the node stores the address of the next node?
B · Pointer field
In a linked list node, the pointer field stores the address/reference to the next node in the list.
Question bank
Tap to reveal →
Which of the following is TRUE about the structure of a singly linked list?
B · Each node contains a pointer only to the next node
In a singly linked list, each node contains data and a pointer to the next node only.
Question bank
Tap to reveal →
What is the time complexity of searching for an element in a singly linked list of \( n \) nodes?
C · O(n)
Searching in a singly linked list requires traversing nodes sequentially, resulting in linear time complexity O(n).
Question bank
Tap to reveal →
In a singly linked list, which operation is more efficient compared to arrays?
B · Insertion at the beginning
Insertion at the beginning of a singly linked list is efficient (O(1)) as it requires updating only the head pointer, unlike arrays which may require shifting elements.
Question bank
Tap to reveal →
Which of the following is a disadvantage of singly linked lists compared to doubly linked lists?
C · No backward traversal
Singly linked lists do not have backward pointers, so backward traversal is not possible, unlike doubly linked lists.
Question bank
Tap to reveal →
Refer to the diagram below of a doubly linked list node. Which pointer points to the previous node?
B · Prev pointer
In a doubly linked list node, the 'Prev' pointer stores the address of the previous node.
Question bank
Tap to reveal →
Which of the following is NOT an advantage of doubly linked lists over singly linked lists?
C · Uses less memory per node
Doubly linked lists use more memory per node due to the extra pointer to the previous node.
Question bank
Tap to reveal →
In a doubly linked list, what is the time complexity of inserting a new node after a given node?
A · O(1)
Insertion after a given node in a doubly linked list is O(1) because it involves updating a fixed number of pointers.
Question bank
Tap to reveal →
Refer to the diagram below showing a doubly linked list with three nodes. Which pointer(s) need to be updated when inserting a new node between the second and third nodes?
A · Next pointer of second node and Prev pointer of third node
When inserting between two nodes, the next pointer of the preceding node and the prev pointer of the succeeding node must be updated to point to the new node.
Question bank
Tap to reveal →
Which of the following statements about circular linked lists is TRUE?
B · The last node points back to the first node
In circular linked lists, the last node points back to the first node, forming a loop.
Question bank
Tap to reveal →
Refer to the diagram below of a circular singly linked list with four nodes. Which node does the pointer of the last node point to?
C · First node
In a circular singly linked list, the last node's pointer points back to the first node, completing the circle.
Question bank
Tap to reveal →
Which of the following is an advantage of circular linked lists over singly linked lists?
B · Traversal can start at any node and continue indefinitely
Circular linked lists allow traversal from any node and can continue indefinitely due to the circular link.
Question bank
Tap to reveal →
In a circular doubly linked list, what is the pointer of the first node's previous pointer pointing to?
B · The last node
In a circular doubly linked list, the first node's previous pointer points to the last node, maintaining the circular connection.
Question bank
Tap to reveal →
Which operation on a singly linked list requires updating the head pointer?
B · Insertion at the beginning
Insertion at the beginning requires updating the head pointer to the new node.
Question bank
Tap to reveal →
What is the worst-case time complexity of deleting a node from a singly linked list when only the key value is given?
B · O(n)
In the worst case, the list must be traversed to find the node to delete, resulting in O(n) time complexity.
Question bank
Tap to reveal →
Refer to the diagram below of a singly linked list. Which pointer should be updated to insert a new node after the node labeled 'B'?
B · Pointer of node 'B'
To insert after node 'B', the pointer in node 'B' must be updated to point to the new node.
Question bank
Tap to reveal →
Which traversal method is used to visit all nodes in a circular linked list without repetition?
B · Traverse until the head node is reached again
In circular linked lists, traversal continues until the starting (head) node is reached again to avoid infinite loops.
Question bank
Tap to reveal →
Which of the following operations on a linked list has a time complexity of O(1)?
B · Insertion at the beginning
Insertion at the beginning of a linked list is O(1) because it involves updating the head pointer and the new node's pointer.
Question bank
Tap to reveal →
Which of the following is a disadvantage of linked lists compared to arrays?
C · Random access to elements is not possible
Linked lists do not support random access; elements must be accessed sequentially.
Question bank
Tap to reveal →
Which of the following is an advantage of linked lists over arrays?
C · Ease of dynamic memory allocation
Linked lists allow dynamic memory allocation and can grow or shrink during runtime, unlike arrays which have fixed size.
Question bank
Tap to reveal →
Which of the following is a disadvantage of linked lists?
A · Extra memory for storing pointers
Linked lists require extra memory for storing pointer(s) in each node.
Question bank
Tap to reveal →
Which of the following memory representations correctly depicts a singly linked list node?
C · Data field and one pointer
A singly linked list node contains a data field and a single pointer to the next node.
Question bank
Tap to reveal →
In memory representation, what does the pointer field in a linked list node store?
B · Memory address of the next node
The pointer field stores the memory address of the next node in the list.
Question bank
Tap to reveal →
Which pointer type is typically used in linked lists to refer to the next node?
C · Node pointer
A node pointer is used to point to the next node in the linked list.
Question bank
Tap to reveal →
Refer to the diagram below showing pointer manipulation during insertion in a singly linked list. Which pointer is updated last to complete the insertion?
B · Previous node's next pointer
The previous node's next pointer is updated last to point to the new node, completing the insertion.
Question bank
Tap to reveal →
Which of the following is a key difference between arrays and linked lists in terms of memory representation?
B · Arrays store elements in contiguous memory, linked lists store nodes non-contiguously
Arrays store elements in contiguous memory locations, whereas linked lists store nodes in non-contiguous memory connected by pointers.
Question bank
Tap to reveal →
Which of the following operations is generally faster in arrays compared to linked lists?
B · Random access to elements
Arrays provide O(1) time random access using indices, whereas linked lists require traversal.
Question bank
Tap to reveal →
Refer to the table below comparing arrays and linked lists. Which property is correctly matched for linked lists?
C · Dynamic size allocation
Linked lists support dynamic size allocation, unlike arrays which have fixed size.
Question bank
Tap to reveal →
Which of the following is a common application of linked lists?
B · Implementing stacks and queues
Linked lists are commonly used to implement dynamic data structures like stacks and queues.
Question bank
Tap to reveal →
Which of the following applications benefits most from circular linked lists?
B · Round robin scheduling
Circular linked lists are ideal for round robin scheduling as they allow continuous cycling through processes.
Question bank
Tap to reveal →
Which of the following linked list types is most suitable for implementing a browser's forward and backward navigation?
B · Doubly linked list
Doubly linked lists allow traversal in both directions, making them suitable for forward and backward navigation.
Question bank
Tap to reveal →
What is the time complexity of accessing the \( k^{th} \) element in a singly linked list of size \( n \)?
B · O(k)
Accessing the \( k^{th} \) element requires traversing from the head node, resulting in O(k) time complexity.
Question bank
Tap to reveal →
Which linked list operation has a time complexity of O(n) in the worst case?
C · Searching for an element
Searching requires traversing the list, which takes O(n) time in the worst case.
Question bank
Tap to reveal →
Refer to the diagram below showing a singly linked list with nodes labeled 1 to 4. What is the time complexity to insert a new node at the end if the tail pointer is NOT maintained?
B · O(n)
Without a tail pointer, insertion at the end requires traversal of all nodes, resulting in O(n) time complexity.
Question bank
Tap to reveal →
Which of the following operations on a doubly linked list has a worst-case time complexity of O(1)?
B · Insertion at the beginning
Insertion at the beginning requires only pointer updates and is done in O(1) time.
Question bank
Tap to reveal →
Which of the following operations on a circular linked list can lead to an infinite loop if not handled properly?
B · Traversal without checking for the head node again
Traversal in circular linked lists must check for the head node to avoid infinite loops.
Question bank
Tap to reveal →
Refer to the diagram below of a doubly linked list. What is the time complexity of deleting a node when a pointer to that node is given?
A · O(1)
Deletion with a pointer to the node is O(1) because only adjacent pointers need updating.
Question bank
Tap to reveal →
Which of the following best describes a linked list?
B · A linear data structure where each element points to the next
A linked list is a linear data structure where each element (node) contains data and a pointer/reference to the next node, allowing dynamic memory allocation.
Question bank
Tap to reveal →
In a singly linked list, what does the last node's pointer typically contain?
C · Null or None indicating end of list
In a singly linked list, the last node's pointer is set to null or None to indicate the end of the list.
Question bank
Tap to reveal →
Which of the following correctly represents the structure of a node in a linked list?
C · Data field and pointer to next node
A node in a linked list contains a data field and a pointer/reference to the next node (in singly linked lists).
Question bank
Tap to reveal →
Refer to the diagram below showing a linked list node. What does the green box represent?
B · Pointer to the next node
In the diagram, the green box represents the pointer/reference to the next node in the linked list.
Question bank
Tap to reveal →
Which type of linked list allows traversal in both forward and backward directions?
B · Doubly linked list
A doubly linked list contains two pointers per node, one pointing to the next node and another to the previous node, allowing bidirectional traversal.
Question bank
Tap to reveal →
Which of the following is a characteristic of a circular linked list?
B · Last node points to the first node
In a circular linked list, the last node's pointer points back to the first node, forming a circle.
Question bank
Tap to reveal →
Which linked list type requires extra memory per node for an additional pointer?
B · Doubly linked list
Doubly linked lists have two pointers per node (next and previous), requiring extra memory compared to singly linked lists.
Question bank
Tap to reveal →
Refer to the diagram below showing a doubly linked list node. What does the left pointer represent?
B · Pointer to the previous node
In a doubly linked list node, the left pointer points to the previous node, enabling backward traversal.
Question bank
Tap to reveal →
In a singly linked list, which operation has the worst-case time complexity of \( O(n) \)?
B · Insertion at the end without tail pointer
Insertion at the end without a tail pointer requires traversal of the entire list, resulting in \( O(n) \) time complexity.
Question bank
Tap to reveal →
Which of the following correctly describes the traversal operation in a circular linked list?
B · Traverse until the first node is reached again
In a circular linked list, traversal continues until the starting node is encountered again, completing a full cycle.
Question bank
Tap to reveal →
Which operation is generally the most complex to implement in a singly linked list?
B · Deletion of a node given only the pointer to that node
Deletion of a node given only the pointer to that node is complex because singly linked lists do not have backward pointers to access the previous node easily.
Question bank
Tap to reveal →
Refer to the diagram below of a singly linked list. What will be the new head after inserting a node with value 10 at the beginning?
A · Node with value 10
Inserting at the beginning makes the new node the head of the list.
Question bank
Tap to reveal →
Which of the following is an advantage of linked lists over arrays?
B · Dynamic memory allocation and ease of insertion/deletion
Linked lists allow dynamic memory allocation and efficient insertion/deletion without shifting elements, unlike arrays.
Question bank
Tap to reveal →
Which of the following is a disadvantage of linked lists compared to arrays?
B · Random access to elements is slow
Linked lists do not support efficient random access; accessing an element requires traversal from the head.
Question bank
Tap to reveal →
Which scenario favors the use of linked lists over arrays?
C · When frequent insertions and deletions occur
Linked lists are preferred when frequent insertions and deletions are required, as they avoid shifting elements.
Question bank
Tap to reveal →
Which memory allocation method is used for linked lists?
B · Dynamic memory allocation
Linked lists use dynamic memory allocation, allowing nodes to be created and linked at runtime.
Question bank
Tap to reveal →
Which of the following statements about dynamic memory allocation in linked lists is true?
B · Memory is allocated only when a new node is inserted
In linked lists, memory for nodes is allocated dynamically at runtime when new nodes are inserted.
Question bank
Tap to reveal →
Refer to the diagram below showing memory allocation for linked list nodes. Which statement is correct about the memory layout?
B · Nodes can be scattered in memory with pointers linking them
Linked list nodes can be located anywhere in memory; pointers link them logically, not physically.
Question bank
Tap to reveal →
Which of the following is a common application of linked lists?
B · Implementing stacks and queues
Linked lists are commonly used to implement dynamic data structures like stacks and queues.
Question bank
Tap to reveal →
Which application of linked lists benefits most from their dynamic size and ease of insertion/deletion?
B · Implementing undo functionality in software
Undo functionality often uses linked lists to dynamically track changes and easily insert or remove states.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of linked lists?
C · Implementing recursion
Recursion is a programming technique and does not require linked lists for its implementation.
Question bank
Tap to reveal →
What is the time complexity of searching for an element in a singly linked list of size \( n \)?
C · \( O(n) \)
Searching requires traversing the list sequentially, resulting in linear time complexity \( O(n) \).
Question bank
Tap to reveal →
Which operation on a doubly linked list has \( O(1) \) time complexity assuming you have a pointer to the node?
B · Deletion of a given node
Deletion of a given node in a doubly linked list can be done in constant time if the pointer to the node is known.
Question bank
Tap to reveal →
Refer to the diagram below of a singly linked list. What is the time complexity to insert a node at the end if no tail pointer is maintained?
B · \( O(n) \)
Without a tail pointer, insertion at the end requires traversing the entire list, which is \( O(n) \).
Question bank
Tap to reveal →
Which of the following edge cases must be handled when implementing deletion in a linked list?
A · Empty list, single node list, deleting head node
Deletion operations must handle empty lists, single node lists, and deleting the head node to avoid errors.
Question bank
Tap to reveal →
Refer to the diagram below of a circular linked list with one node pointing to itself. What special case does this represent?
B · Single node circular list
A circular linked list with a single node points to itself, representing the single node circular list edge case.
Question bank
Tap to reveal →
What problem can occur if a circular linked list is traversed without a proper stopping condition?
B · Infinite loop causing program to hang
Without a stopping condition, traversal in a circular linked list can cause an infinite loop.
Question bank
Tap to reveal →
In an empty linked list, which of the following is true?
A · Head pointer points to null
In an empty linked list, the head pointer is set to null indicating no nodes are present.
Question bank
Tap to reveal →
Which of the following is true about deleting the only node in a singly linked list?
A · Head pointer should be set to null after deletion
After deleting the only node, the head pointer must be set to null to indicate the list is empty.
Question bank
Tap to reveal →
In a singly linked list of 39 nodes, a function rotates the list to the right by 11 nodes, then reverses the first 20 nodes. After these operations, what is the position of the node originally at position 5?
D · Position 10
Question bank
Tap to reveal →
Which of the following best defines a stack data structure?
B · A linear data structure that follows LIFO (Last In First Out) principle
A stack is a linear data structure which follows the Last In First Out (LIFO) principle, meaning the last element inserted is the first to be removed.
Question bank
Tap to reveal →
Which property is NOT true for a stack?
B · Elements are accessed in the order they were inserted
Stacks do not access elements in the order they were inserted (FIFO). Instead, they follow LIFO, so the last inserted element is accessed first.
Question bank
Tap to reveal →
Which of the following is NOT a standard operation of a stack?
C · enqueue
Enqueue is an operation of a queue, not a stack. Stack operations include push (insert), pop (remove), and peek (view top element).
Question bank
Tap to reveal →
What will be the result of the following sequence of stack operations on an empty stack? push(5), push(10), pop(), push(7), peek()
B · 7
After push(5) and push(10), top is 10. pop() removes 10, top becomes 5. push(7) adds 7 on top. peek() returns 7.
Question bank
Tap to reveal →
Which condition indicates stack overflow in an array-based stack implementation?
B · When top == size - 1
In array-based stack, overflow occurs when the top pointer reaches the last index (size - 1), meaning no more elements can be pushed.
Question bank
Tap to reveal →
Refer to the diagram below showing an array-based stack implementation.
What is the value of the top pointer after pushing elements 3, 7, and 9 onto an empty stack of size 5?
C · 2
Initially top = -1. After pushing 3, top = 0; after 7, top = 1; after 9, top = 2.
Question bank
Tap to reveal →
Which of the following is an advantage of linked list-based stack implementation over array-based stack?
B · No overflow unless memory is exhausted
Linked list-based stacks can grow dynamically and do not suffer from overflow unless system memory is exhausted, unlike fixed-size arrays.
Question bank
Tap to reveal →
In a linked list-based stack, which pointer typically points to the top element?
C · Top pointer
The top pointer points to the node at the top of the stack in a linked list implementation.
Question bank
Tap to reveal →
Refer to the diagram below illustrating a linked list-based stack.
What will be the top element after popping one element from the stack shown?
B · 30
The current top is 40. Popping removes 40, so the new top is 30.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of stacks?
D · Binary search on sorted arrays
Binary search is performed on sorted arrays and does not require a stack. Stacks are used in expression evaluation, backtracking, and recursion simulation.
Question bank
Tap to reveal →
Which of the following expressions can be evaluated using a stack?
C · Both infix and postfix expressions
Stacks are used to evaluate both infix (with operator precedence) and postfix expressions efficiently.
Question bank
Tap to reveal →
In backtracking algorithms, how is a stack primarily used?
B · To keep track of previous states for possible rollback
Stacks store previous states or choices so the algorithm can backtrack (rollback) when a path fails.
Question bank
Tap to reveal →
Refer to the diagram below showing postfix expression evaluation using a stack.
What is the final result after evaluating the postfix expression "5 3 2 * +"?
A · 11
Postfix evaluation steps:Push 5Push 3Push 2Pop 2 and 3, multiply: 6, push 6Pop 6 and 5, add: 11Final result is 11.
Question bank
Tap to reveal →
Which of the following best describes stack overflow?
B · Attempting to push onto a full stack
Stack overflow occurs when a push operation is attempted on a stack that is already full.
Question bank
Tap to reveal →
Which of the following is a cause of stack underflow?
B · Popping an element when stack is empty
Stack underflow occurs when a pop operation is attempted on an empty stack.
Question bank
Tap to reveal →
Refer to the memory layout diagram below of a stack in memory.
What does the stack pointer indicate in this layout?
B · The next free position for push operation
The stack pointer points to the top element or the next free position where the next push will insert an element.
Question bank
Tap to reveal →
Which of the following is true about static and dynamic stacks?
C · Static stacks have fixed size, dynamic stacks can grow or shrink during runtime
Static stacks have fixed size (usually array-based), while dynamic stacks (usually linked list-based) can grow or shrink as needed.
Question bank
Tap to reveal →
Which of the following is a disadvantage of static stacks compared to dynamic stacks?
B · Risk of stack overflow due to fixed size
Static stacks have fixed size, so if the stack exceeds this size, overflow occurs. Dynamic stacks avoid this by dynamic memory allocation.
Question bank
Tap to reveal →
Which of the following is true about dynamic stacks implemented using linked lists?
C · They can grow and shrink at runtime
Dynamic stacks implemented with linked lists allocate memory as needed, allowing them to grow and shrink dynamically.
Question bank
Tap to reveal →
What is the time complexity of push and pop operations in a stack implemented using arrays or linked lists?
C · O(1) for both push and pop
Both push and pop operations in stack implementations (array or linked list) are performed in constant time O(1).
Question bank
Tap to reveal →
Which of the following operations on a stack has the worst-case time complexity of O(n)?
D · None of the above
All basic stack operations (push, pop, peek) have O(1) time complexity. None have O(n) in standard implementations.
Question bank
Tap to reveal →
In which scenario can the time complexity of stack operations degrade from O(1) to O(n)?
A · When implemented using arrays with resizing
In dynamic array implementations, resizing the array during push can cause O(n) time in that operation, though amortized complexity remains O(1).
Question bank
Tap to reveal →
Which of the following problems can be efficiently solved using a stack?
A · Balanced parentheses checking
Balanced parentheses checking is a classic problem solved efficiently using stacks by matching opening and closing brackets.
Question bank
Tap to reveal →
What does the 'Next Greater Element' problem involve?
A · Finding the next element greater than the current element in an array
The Next Greater Element problem requires finding, for each element, the next element to the right that is greater than it.
Question bank
Tap to reveal →
Refer to the diagram below illustrating the stock span problem.
What is the span of the stock price on day 5 with price 70?
C · 4
The span is the number of consecutive days before day 5 where stock price was less or equal to 70. Days 2 (60), 3 (65), 4 (55), and 5 (70) count, so span = 4.
Question bank
Tap to reveal →
Which of the following algorithms uses stack to simulate recursion?
A · Iterative inorder traversal of a binary tree
Iterative inorder traversal uses an explicit stack to simulate the function call stack of recursive traversal.
Question bank
Tap to reveal →
Which of the following is NOT a variation of the stack problem?
D · Binary search tree traversal
Binary search tree traversal is not a stack variation problem, though stacks can be used for traversal, it is not considered a classic stack problem variation.
Question bank
Tap to reveal →
Which of the following best describes the stack data structure?
B · A linear data structure that follows LIFO order
A stack is a linear data structure that follows Last In First Out (LIFO) order, meaning the last element added is the first to be removed.
Question bank
Tap to reveal →
Which property is NOT true for a stack?
B · It allows random access to elements
Stacks do not allow random access; elements can only be accessed from the top. Random access is a property of arrays, not stacks.
Question bank
Tap to reveal →
Which of the following is a key property of a stack that differentiates it from a queue?
B · LIFO order of element removal
Stacks follow Last In First Out (LIFO) order, whereas queues follow First In First Out (FIFO) order.
Question bank
Tap to reveal →
Which stack operation removes the top element from the stack?
B · Pop
The pop operation removes and returns the top element of the stack.
Question bank
Tap to reveal →
What will be the result of performing a peek operation on an empty stack?
C · Returns null or error
Peek operation returns the top element without removing it. If the stack is empty, it typically returns null or an error indicating underflow.
Question bank
Tap to reveal →
Which of the following sequences of operations on an initially empty stack will cause a stack overflow in an array-based implementation of size 3?
B · Push, Push, Push, Push
Pushing 4 elements into a stack of size 3 causes overflow since the array cannot accommodate more than 3 elements.
Question bank
Tap to reveal →
In an array-based stack implementation, which condition indicates that the stack is full?
B · Top == size - 1
In array-based stacks, the stack is full when the top index reaches size - 1 (last valid index).
Question bank
Tap to reveal →
Refer to the diagram below showing a linked list representation of a stack. Which pointer indicates the top of the stack?
A · Head pointer
In a linked list implementation of a stack, the head pointer points to the top element of the stack.
Question bank
Tap to reveal →
Which of the following is an advantage of linked list implementation of a stack over array implementation?
B · Dynamic size allocation
Linked list implementation allows dynamic memory allocation, so the stack size can grow or shrink as needed, unlike fixed size arrays.
Question bank
Tap to reveal →
Consider the following code snippet for a stack implemented using an array of size 5. Which condition should be checked before pushing an element to avoid overflow?
C · top == size - 1
Before pushing, we check if top == size - 1 to ensure the stack is not full and avoid overflow.
Question bank
Tap to reveal →
Refer to the diagram below illustrating an expression evaluation tree using stack. Which traversal order is used to evaluate the expression?
C · Postorder traversal
Postorder traversal is used to evaluate expression trees because it ensures operands are processed before operators.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of stacks?
D · Sorting large datasets efficiently
Stacks are not primarily used for sorting large datasets efficiently; other algorithms and data structures are better suited for that.
Question bank
Tap to reveal →
In backtracking algorithms, how does a stack help in exploring different solution paths?
B · By storing the current state and reverting to previous states
Stacks store the current state, allowing the algorithm to backtrack by popping states and exploring alternative paths.
Question bank
Tap to reveal →
Which stack operation is primarily used to manage function calls in programming languages?
A · Push to save return address and local variables
When a function is called, the return address and local variables are pushed onto the stack to manage the call and return process.
Question bank
Tap to reveal →
Which of the following scenarios causes stack underflow?
B · Popping an element from an empty stack
Stack underflow occurs when attempting to pop from an empty stack, i.e., no elements to remove.
Question bank
Tap to reveal →
Which condition indicates a stack overflow in an array-based stack implementation?
B · Attempting to push when top == size - 1
Stack overflow occurs when pushing an element into a full stack, i.e., when top == size - 1 in array implementation.
Question bank
Tap to reveal →
Which of the following is a common cause of stack overflow in recursive function calls?
A · Base case is never reached
If the base case is never reached, recursive calls keep adding stack frames, causing stack overflow.
Question bank
Tap to reveal →
Refer to the diagram below showing the stack frame layout in memory during a function call. Which part of the stack frame stores the return address?
C · Return address section
The return address section stores the address to return to after the function completes execution.
Question bank
Tap to reveal →
What is the role of the stack pointer (SP) in stack memory management?
B · It points to the next free location for push operation
The stack pointer points to the top element or the next free location where the next push will occur.
Question bank
Tap to reveal →
In the context of stack frames, which of the following is NOT typically stored in the stack frame during a function call?
C · Global variables
Global variables are stored in a separate data segment, not in the stack frame.
Question bank
Tap to reveal →
What is the time complexity of push and pop operations in a stack implemented using an array?
C · O(1) for both push and pop
Both push and pop operations in an array-based stack are performed in constant time O(1).
Question bank
Tap to reveal →
Which of the following statements about the time complexity of stack operations is correct?
B · Push and pop operations are O(1)
Push, pop, peek, and isEmpty operations in a stack are all performed in constant time O(1).
Question bank
Tap to reveal →
Refer to the flowchart below representing the push operation on a stack. What is the first condition checked before inserting a new element?
B · If stack is full
Before pushing, the algorithm checks if the stack is full to avoid overflow.
Question bank
Tap to reveal →
Which of the following best defines a Deque (Double-Ended Queue)?
B · A linear data structure where insertion and deletion are allowed at both ends
A Deque allows insertion and deletion operations at both front and rear ends, unlike stacks or queues which restrict operations to one end.
Question bank
Tap to reveal →
Which characteristic is NOT true about a Deque?
C · Follows strict FIFO order
Deques do not follow strict FIFO order since elements can be inserted and deleted from both ends, unlike queues which strictly follow FIFO.
Question bank
Tap to reveal →
Which of the following statements correctly describes the main feature of a Deque?
C · Insertion and deletion are allowed at both ends
Deques allow insertion and deletion operations at both the front and rear ends, providing more flexibility than stacks or queues.
Question bank
Tap to reveal →
In an input-restricted deque, which operation is restricted?
B · Insertion at only one end
In an input-restricted deque, insertion is allowed at only one end but deletion is allowed at both ends.
Question bank
Tap to reveal →
Which of the following is true for an output-restricted deque?
A · Insertion is allowed at both ends but deletion is allowed at only one end
In an output-restricted deque, insertion can be done at both ends but deletion is restricted to only one end.
Question bank
Tap to reveal →
Which of the following correctly describes the difference between input-restricted and output-restricted deques?
B · Input-restricted allows insertion at one end only, output-restricted allows deletion at one end only
Input-restricted deques restrict insertion to one end but allow deletion at both ends; output-restricted deques allow insertion at both ends but restrict deletion to one end.
Question bank
Tap to reveal →
Refer to the diagram below showing an array-based deque implementation.
Which index represents the front of the deque after inserting elements at both ends?
B · Index 1
In array-based deque, front and rear indices move towards each other. After inserting at both ends, front typically moves to the next index (1) from initial position (0).
Question bank
Tap to reveal →
Which of the following is an advantage of linked list-based deque implementation over array-based?
B · No need to shift elements during insertion/deletion
Linked list-based deque allows insertion and deletion without shifting elements, unlike arrays which may require shifting to maintain order.
Question bank
Tap to reveal →
Refer to the linked list diagram below representing a deque.
Which pointer indicates the rear end of the deque?
C · Pointer at node with value 20
In the linked list representation of a deque, the rear pointer points to the last node (with value 20 in the diagram).
Question bank
Tap to reveal →
Which of the following operations is NOT possible in a deque?
C · Insertion at middle
Deques allow insertion and deletion only at the front and rear ends, not at the middle.
Question bank
Tap to reveal →
Which operation sequence is valid for a deque?
C · InsertFront, DeleteRear, InsertRear
Deques support insertion and deletion at both front and rear ends, but not in the middle.
Question bank
Tap to reveal →
Refer to the operation flow diagram below for deque insertion.
Which step comes immediately after checking if the deque is full?
A · Insert element at front or rear
After confirming the deque is not full, the insertion operation proceeds to insert the element at the specified end.
Question bank
Tap to reveal →
Which of the following sequences correctly represents deletion operations on a deque?
B · DeleteRear, DeleteFront, DeleteRear
Deques allow deletion only at front and rear ends, so deleting from the middle is invalid.
Question bank
Tap to reveal →
Which of the following is the time complexity of insertion and deletion operations at both ends in a deque implemented using a doubly linked list?
A · O(1) for both insertion and deletion
Doubly linked list implementation of deque allows insertion and deletion at both ends in constant time O(1).
Question bank
Tap to reveal →
Which of the following is a common application of deques?
B · Undo functionality in text editors
Deques are used in undo operations where elements can be added or removed from both ends efficiently.
Question bank
Tap to reveal →
Which of the following applications best utilizes a deque data structure?
C · Palindrome checking
Palindrome checking can be efficiently done using a deque by comparing characters from both ends.
Question bank
Tap to reveal →
Which of the following is NOT a typical application of deques?
D · Implementing priority queues
Priority queues require a different data structure (like heaps), not deques, which are linear and allow insertion/deletion at ends only.
Question bank
Tap to reveal →
What is the average time complexity of insertion and deletion operations at both ends in an array-based deque implementation?
A · O(1) amortized
Array-based deque implementations can achieve O(1) amortized time for insertion and deletion at both ends using circular arrays.
Question bank
Tap to reveal →
Which of the following operations in a deque has worst-case time complexity O(n) in an array-based implementation?
A · Insertion at front when array is full
When the array is full, insertion at front may require resizing and copying elements, leading to O(n) worst-case time complexity.
Question bank
Tap to reveal →
Consider a deque implemented using a circular array of size \( n \). What is the time complexity of checking if the deque is empty?
A · O(1)
Checking if the deque is empty involves comparing front and rear indices, which is done in constant time O(1).
Question bank
Tap to reveal →
Refer to the comparison chart below between Stack, Queue, and Deque.
Which data structure supports insertion and deletion at both ends?
C · Deque
Only Deque supports insertion and deletion at both front and rear ends, unlike Stack and Queue which restrict operations to one end.
Question bank
Tap to reveal →
Which of the following statements correctly compares a deque with a stack?
B · Deque allows insertion and deletion at both ends, stack only at one end
Deque supports insertion and deletion at both ends, while stack restricts these operations to only one end (top).
Question bank
Tap to reveal →
Which data structure would be more efficient for implementing a deque?
B · Doubly linked list
Doubly linked list allows efficient insertion and deletion at both ends, making it suitable for deque implementation.
Question bank
Tap to reveal →
Which of the following problems can be efficiently solved using a deque?
A · Finding the maximum in a sliding window
Deques are used in sliding window maximum problems to maintain candidates for maximum efficiently.
Question bank
Tap to reveal →
Refer to the problem-solving flow diagram below using a deque.
What is the primary purpose of using a deque in this algorithm?
B · To allow insertion and deletion from both ends for efficient window management
The deque is used to efficiently manage elements at both ends, which is essential in sliding window or similar algorithms.
Question bank
Tap to reveal →
Which of the following is a limitation when using array-based deque implementation compared to linked list-based?
A · Fixed size leading to overflow
Array-based deque has fixed size which can lead to overflow, whereas linked list-based deque can dynamically grow.
Question bank
Tap to reveal →
Which of the following sequences correctly demonstrates the use of a deque to check if a string is a palindrome?
A · Insert characters at rear, delete characters from front and rear for comparison
For palindrome checking, characters are inserted and deleted from both ends to compare front and rear characters.
Question bank
Tap to reveal →
Which of the following best describes the amortized time complexity of resizing an array-based deque when it becomes full?
B · O(n)
Resizing involves copying all elements to a new array, which takes O(n) time, but amortized over many insertions this cost is spread out.
Question bank
Tap to reveal →
Which of the following best defines a deque?
B · A linear data structure allowing insertion and deletion at both ends
A deque (double-ended queue) allows insertion and deletion operations at both the front and rear ends.
Question bank
Tap to reveal →
Which characteristic distinguishes a deque from a queue?
C · Insertion and deletion are allowed at both ends
Unlike a queue, a deque allows insertion and deletion at both front and rear ends.
Question bank
Tap to reveal →
Which of the following is NOT a characteristic of a deque?
C · Supports random access to elements
Deques do not support random access; elements are accessed only from ends.
Question bank
Tap to reveal →
In an input-restricted deque, which operation is restricted?
B · Insertion at one end only
An input-restricted deque allows insertion at only one end but deletion at both ends.
Question bank
Tap to reveal →
Which of the following correctly describes an output-restricted deque?
A · Insertion allowed at both ends; deletion allowed at one end only
In an output-restricted deque, insertion can be done at both ends but deletion is allowed at only one end.
Question bank
Tap to reveal →
Which of the following scenarios best illustrates the use of an input-restricted deque?
A · A system where data can be added only at the rear but removed from both ends
Input-restricted deque allows insertion at one end (rear) and deletion at both ends.
Question bank
Tap to reveal →
Which deque operation is performed when an element is inserted at the front end?
B · EnqueueFront
Insertion at the front end of a deque is called EnqueueFront operation.
Question bank
Tap to reveal →
Refer to the diagram below showing a deque with elements [10, 20, 30] (front to rear). If an element 5 is inserted at the front and 40 is deleted from the rear, what will be the resulting deque?
A · [5, 10, 20]
Inserting 5 at front results in [5, 10, 20, 30], then deleting 40 from rear removes 30 (since 40 is not present, assuming 40 was at rear), so final deque is [5, 10, 20].
Question bank
Tap to reveal →
Which deque operation has the highest time complexity in a linked list implementation?
D · All operations have the same time complexity
In a doubly linked list implementation of deque, insertion and deletion at both ends take O(1) time.
Question bank
Tap to reveal →
Which of the following is a disadvantage of array-based deque implementation compared to linked list-based implementation?
D · Both A and C
Array-based deque has fixed size and deletion at front requires shifting elements, making both dynamic resizing and deletion inefficient.
Question bank
Tap to reveal →
Refer to the diagram below showing a doubly linked list representing a deque with nodes containing values 15, 25, 35 (front to rear). Which pointer changes are required to insert a node with value 10 at the front?
A · New node's next points to 15; 15's prev points to new node
Inserting at front requires new node's next pointing to current front (15) and 15's prev pointing back to new node.
Question bank
Tap to reveal →
Which of the following statements is TRUE about array-based deque implementation?
B · It uses circular array to efficiently utilize space
Array-based deque typically uses a circular array to avoid shifting elements and efficiently use space.
Question bank
Tap to reveal →
Which of the following is a common application of deques?
B · Managing undo operations in software
Deques are used in undo operations where elements can be added or removed from both ends.
Question bank
Tap to reveal →
Which application best utilizes a deque to maintain a sliding window maximum in an array?
C · Real-time data stream processing
Deques efficiently maintain candidates for sliding window maximum in real-time data streams.
Question bank
Tap to reveal →
Which of the following applications cannot be efficiently implemented using a deque?
B · Job scheduling with priority
Job scheduling with priority is better suited to priority queues, not deques.
Question bank
Tap to reveal →
What is the average time complexity of insertion and deletion operations in a deque implemented using a doubly linked list?
C · O(1) for both insertion and deletion
Doubly linked list implementation allows O(1) time insertion and deletion at both ends.
Question bank
Tap to reveal →
What is the time complexity of deleting an element from the front end in an array-based deque with circular array implementation?
A · O(1)
Circular array implementation allows deletion at front in O(1) time without shifting elements.
Question bank
Tap to reveal →
Which of the following is the worst-case time complexity for resizing an array-based deque when it becomes full?
B · O(n)
Resizing an array-based deque requires copying all elements to a new array, taking O(n) time.
Question bank
Tap to reveal →
Which of the following correctly compares a deque with a stack?
B · Deque allows insertion and deletion at both ends; stack only at one end
A deque supports insertion and deletion at both ends, while a stack supports these operations only at one end (top).
Question bank
Tap to reveal →
Which of the following is a key difference between a queue and a deque?
B · Deque allows insertion and deletion at both ends; queue only at front and rear respectively
Queue allows insertion at rear and deletion at front only; deque allows these operations at both ends.
Question bank
Tap to reveal →
Refer to the table below comparing Stack, Queue, and Deque operations. Which operation is supported only by deque but not by stack or queue?
C · Insertion at front
Only deque supports insertion at front; stack and queue do not.
Question bank
Tap to reveal →
Which of the following best defines a priority queue?
B · A data structure where each element has a priority and the element with the highest priority is dequeued first
A priority queue is a data structure where each element has a priority, and the element with the highest priority is removed first, unlike a regular queue which follows FIFO order.
Question bank
Tap to reveal →
Which characteristic is NOT true about a priority queue?
C · It always dequeues elements in FIFO order
Priority queues do not dequeue elements in FIFO order; instead, elements with the highest priority are dequeued first.
Question bank
Tap to reveal →
Which of the following is a key characteristic of a priority queue?
B · Elements are processed based on their priority rather than insertion order
Priority queues process elements based on their priority, not the order of insertion.
Question bank
Tap to reveal →
Which of the following is NOT a common method to implement a priority queue?
D · Hash table-based implementation
Hash tables are not typically used to implement priority queues because they do not efficiently support priority-based ordering.
Question bank
Tap to reveal →
Refer to the diagram below showing a max-heap implementation of a priority queue. Which element will be dequeued first?
D · 70
In a max-heap, the root node contains the maximum element, which has the highest priority and will be dequeued first.
Question bank
Tap to reveal →
Which of the following is the worst-case time complexity for inserting an element into a binary heap based priority queue?
B · O(log n)
Insertion in a binary heap requires placing the element at the end and then 'heapifying' up, which takes O(log n) time in the worst case.
Question bank
Tap to reveal →
Which operation is NOT typically supported by a priority queue?
C · Search for an element by value in O(1) time
Priority queues do not support searching for an element by value in O(1) time; searching is generally O(n).
Question bank
Tap to reveal →
Refer to the flowchart below illustrating the 'extract-max' operation on a max-heap based priority queue. What is the next step after removing the root element?
A · Replace root with last element and heapify down
After removing the root (maximum element), the last element is moved to the root and then heapify-down is performed to restore heap property.
Question bank
Tap to reveal →
What is the time complexity of the 'peek' operation (accessing the highest priority element) in a heap-based priority queue?
A · O(1)
The highest priority element is always at the root of the heap, so peek operation takes O(1) time.
Question bank
Tap to reveal →
Which of the following is a common application of priority queues?
B · Job scheduling in operating systems
Priority queues are widely used in job scheduling where processes with higher priority are executed first.
Question bank
Tap to reveal →
Which of the following applications uses priority queues internally?
B · Dijkstra's shortest path algorithm
Dijkstra's algorithm uses a priority queue to select the next vertex with the smallest tentative distance.
Question bank
Tap to reveal →
In which scenario is a priority queue most useful?
B · When elements must be processed based on their priority levels
Priority queues are designed to process elements based on priority rather than arrival order or sorting.
Question bank
Tap to reveal →
What is the average time complexity for extracting the highest priority element from a binary heap based priority queue?
B · O(log n)
Extracting the highest priority element requires removing the root and heapifying down, which takes O(log n) time on average.
Question bank
Tap to reveal →
Which of the following operations on a priority queue implemented using a binary heap has the highest worst-case time complexity?
B · Extract-min or Extract-max
Extract-min or Extract-max operations require heapify-down which takes O(log n) time, same as insertion, but generally considered costlier due to restructuring.
Question bank
Tap to reveal →
Which of the following is the time complexity of building a heap from an unsorted array of size \( n \)?
B · O(n)
Building a heap from an unsorted array can be done in O(n) time using the bottom-up heap construction method.
Question bank
Tap to reveal →
Which of the following statements about the time complexity of priority queue operations is TRUE?
C · Building a heap takes O(n) time
Building a heap from an unsorted array takes O(n) time, while insertion and extraction take O(log n), and peek takes O(1).
Question bank
Tap to reveal →
Which linear data structure is most similar to a priority queue in terms of element ordering?
C · Sorted linked list
A sorted linked list maintains elements in order, similar to a priority queue which processes elements based on priority.
Question bank
Tap to reveal →
Compared to a simple queue, a priority queue differs in that it:
B · Removes elements based on priority rather than arrival order
Priority queues remove elements based on priority, unlike simple queues which follow FIFO order.
Question bank
Tap to reveal →
Which data structure provides more efficient priority queue operations for large datasets?
C · Binary heap
Binary heaps provide efficient O(log n) insertion and extraction, making them suitable for large datasets.
Question bank
Tap to reveal →
Which of the following is a variant of a priority queue?
B · Min-heap
Min-heap is a variant of a priority queue where the element with the minimum value has the highest priority.
Question bank
Tap to reveal →
Refer to the diagram below showing a min-heap. Which element will be extracted first from this priority queue?
B · 10
In a min-heap, the root node contains the smallest element, which will be extracted first.
Question bank
Tap to reveal →
Which of the following is TRUE about max-heap and min-heap variants of priority queues?
C · Max-heap extracts the maximum element first, min-heap extracts the minimum element first
Max-heap extracts the maximum element first, while min-heap extracts the minimum element first.
Question bank
Tap to reveal →
Which of the following operations is more complex in a Fibonacci heap compared to a binary heap?
B · Extract-min
Extract-min operation is more complex in Fibonacci heaps compared to binary heaps, but other operations like decrease-key are more efficient.
Question bank
Tap to reveal →
Which real-world application commonly uses priority queues?
B · Network packet scheduling
Network packet scheduling uses priority queues to process packets based on priority levels.
Question bank
Tap to reveal →
In which of the following scenarios is a priority queue NOT typically used?
C · Sorting an array
Sorting an array is not typically done using priority queues directly, although heapsort uses a heap internally.
Question bank
Tap to reveal →
Which of the following is a typical use case of priority queues in operating systems?
B · Process scheduling based on priority
Operating systems use priority queues to schedule processes based on their priority levels.
Question bank
Tap to reveal →
Refer to the flowchart below illustrating the insertion operation in a heap-based priority queue. What is the purpose of the 'heapify-up' step?
B · To restore the heap property by moving the element up if its priority is higher than its parent
Heapify-up restores the heap property by moving the newly inserted element up the tree if its priority is higher than its parent's.
Question bank
Tap to reveal →
Which of the following best describes a priority queue?
B · A linear data structure where each element has a priority and elements are served based on priority
A priority queue is a linear data structure where each element is associated with a priority and elements are dequeued based on their priority rather than their insertion order.
Question bank
Tap to reveal →
Which characteristic is NOT true for a priority queue?
C · Insertion order is strictly maintained
Insertion order is not strictly maintained in priority queues; elements are dequeued based on priority, not insertion order.
Question bank
Tap to reveal →
Which of the following statements about priority queues is TRUE?
B · Priority queues can be used to implement scheduling algorithms
Priority queues are commonly used in scheduling algorithms where tasks with higher priority are executed first.
Question bank
Tap to reveal →
Which of the following is NOT a common implementation technique for priority queues?
D · Hash table
Hash tables are not typically used to implement priority queues because they do not support efficient priority-based retrieval.
Question bank
Tap to reveal →
Refer to the diagram below showing a max-heap implementation of a priority queue. What is the maximum element in this heap?
D · 25
In a max-heap, the root node contains the maximum element. According to the diagram, the root node is 25.
Question bank
Tap to reveal →
Which operation on a priority queue typically has the highest time complexity when implemented using a binary heap?
C · Extract minimum/maximum
Extracting the minimum or maximum element requires removing the root and reheapifying, which takes \(O(\log n)\) time in a binary heap.
Question bank
Tap to reveal →
Which of the following sequences correctly represents the operations of a priority queue?
B · Insert, Extract-Min/Max, Peek
Priority queues typically support Insert, Extract-Min/Max (depending on min or max priority), and Peek operations.
Question bank
Tap to reveal →
Refer to the flowchart below representing the insertion operation in a priority queue implemented as a min-heap. What is the purpose of the 'heapify-up' step?
B · To maintain the heap property by moving the new element up if it has higher priority
Heapify-up restores the min-heap property by swapping the inserted element upwards if it has higher priority (lower value) than its parent.
Question bank
Tap to reveal →
Which of the following is a typical application of priority queues?
B · CPU task scheduling
Priority queues are widely used in CPU scheduling where tasks with higher priority are executed first.
Question bank
Tap to reveal →
Which of the following applications benefits from using a priority queue?
B · Dijkstra's shortest path algorithm
Dijkstra's algorithm uses a priority queue to select the next vertex with the smallest tentative distance efficiently.
Question bank
Tap to reveal →
In which scenario is a priority queue most useful?
B · When elements need to be processed based on their priority
Priority queues are designed to process elements based on priority rather than arrival order or random access.
Question bank
Tap to reveal →
What is the average time complexity of the extract-min operation in a priority queue implemented using a binary heap?
B · O(\log n)
Extract-min operation in a binary heap requires removing the root and heapifying down, which takes \(O(\log n)\) time.
Question bank
Tap to reveal →
Which priority queue operation has \(O(1)\) time complexity when implemented using a binary heap?
C · Peek (find-min)
Peek or find-min operation returns the root element in constant time \(O(1)\) in a binary heap.
Question bank
Tap to reveal →
Consider a priority queue implemented as a binary heap with \(n\) elements. What is the worst-case time complexity of inserting an element?
B · O(\log n)
Insertion requires adding the element at the bottom and heapifying up, which takes \(O(\log n)\) time in the worst case.
Question bank
Tap to reveal →
Which of the following statements correctly compares priority queues and stacks?
C · Priority queues dequeue elements based on priority, stacks follow LIFO order
Stacks follow Last-In-First-Out (LIFO) order, whereas priority queues dequeue elements based on their priority.
Question bank
Tap to reveal →
Refer to the table below comparing priority queues and queues. Which property is unique to priority queues?
B · Elements have associated priorities influencing dequeue order
Priority queues associate priorities with elements, affecting the order of removal, unlike regular queues which dequeue in FIFO order.
Question bank
Tap to reveal →
Which of the following linear data structures is most similar to a priority queue in terms of element access?
D · Sorted linked list
A sorted linked list maintains elements in order, similar to how priority queues access elements based on priority.
Question bank
Tap to reveal →
Which of the following is a characteristic of a min-heap variant of a priority queue?
B · Every parent node is less than or equal to its children
In a min-heap, the parent node is always less than or equal to its children, ensuring the minimum element is at the root.
Question bank
Tap to reveal →
Which of the following is TRUE about max-heap and min-heap variants of priority queues?
B · Both maintain the heap property but differ in priority ordering
Both max-heap and min-heap maintain the heap property; max-heap root is maximum, min-heap root is minimum, differing in priority ordering.
Question bank
Tap to reveal →
Refer to the diagram below showing a min-heap. Which element will be extracted first from this priority queue?
A · 5
In a min-heap, the root node contains the minimum element, which is 5 in the diagram.
Question bank
Tap to reveal →
Which variant of priority queue would be most suitable for implementing a task scheduler that always executes the highest priority task first?
B · Max-heap
A max-heap variant is suitable because it always allows extraction of the highest priority (maximum) element efficiently.
