Computer Science Exit Exam Study Guide · 271 questions
Read the question first. Select the eye beside the reading hint, study the cited module section, then reveal the answer. Each eye controls only its own block. All hints and answers start closed whenever this page opens.
Read the linked study-guide sections before revealing the answer. PDF page references count from the first page of the document.
271 of 271 questions
Question 1
When we use a hash table data structure, our hash function should map the expected inputs (keys) as evenly as possible over its output range(indexes). This property of good hash function is known as______.
A. Uniformity
B. Determinism
C. Continuity
D. Data normalization
Hint / Module Reference (Where to Read)
Trace the initial state and each executed operation in order, preserving the requested output layout.
DSA25 defines uniformity as spreading expected keys evenly among addresses. That directly matches the question’s wording. Determinism is a different obligation: repeated equal keys receive the same address for the chosen function. Continuity and data normalization do not name this distribution property, so only Uniformity answers the literal stem.
Evidence in the complete study note
Determinism means repeated equal keys get the same address for the chosen function. Uniformity means expected keys spread evenly. Universal hashing chooses one function randomly from a suitable family for the table, independently of a fixed key set; it does not choose a fresh unrelated function for each lookup. Random choice controls collision probability, not a promise of zero collisions.DSA25
Choice by choice
A · correct — Uniformity describes spreading expected input keys evenly across the output address range, exactly as the stem requires.
B · incorrect — Determinism requires repeated equal keys to map identically; it does not require an even address distribution.
C · incorrect — Continuity is not the key-distribution property defined for hash functions in DSA25.
D · incorrect — Data normalization does not name the even-distribution requirement of a hash function.
Question 2
In a one-based array representation of a binary heap, the root is at index 1. If a node at index i has a right child, at which index is that child stored?
A. 2*i+1
B. i/2
C. (i+1)/2
D. 2*i
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Heap child formulas depend on whether indexing begins at zero or one. With the explicitly stated one-based convention, the two children of node i occupy positions 2i and 2i+1. The latter is the right child. Integer division by two instead identifies a parent in this convention. The existence condition matters because an index computed beyond the current heap size does not designate an actual child.
Evidence in the complete study note
Zero-based array representation: root index 0, left=2i+1, right=2i+2, parent=floor((i-1)/2) for i>0. One-based representation uses children 2i,2i+1 and parent floor(i/2). A child exists only if its index is inside the current heap size.DSA23
Choice by choice
A · correct — 2i+1 is the one-based right-child index.
B · incorrect — floor(i/2) computes the parent for nonroot nodes.
C · incorrect — (i+1)/2 does not compute the right child.
D · incorrect — 2i is the one-based left child.
Question 3
Use iterative sequential search and iterative binary search on random-access arrays, with constant-size indices. For binary search, reverse comparisons on descending arrays. Compare tight asymptotic auxiliary space and worst-case element probes as n grows. Which statement is false?
A. Binary searching algorithm can work on list of data which is stored in descending order
B. Sequential and binary searching algorithm are not equal in terms of memory efficiency
C. Sequential searching algorithm can work on sorted and unsorted list of data
D. Binary search has a smaller tight worst-case probe order than sequential search on sorted random-access arrays.
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answer: B — B. Sequential and binary searching algorithm are not equal in terms of memory efficiency
Both iterative algorithms keep only a fixed number of indices and temporary values, giving constant auxiliary space. Their worst-case probe counts differ: sequential search can inspect every element, whereas binary search halves the ordered interval each time. Binary search can also handle descending order with reversed comparisons, and sequential search does not require sorted input. Under these specified implementations, the unequal-memory claim is the false statement.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Choice by choice
A · incorrect — Descending binary search works with reversed comparisons.
B · correct — Both iterative implementations use constant auxiliary space, so this inequality claim is false.
C · incorrect — A sequential scan works with either input ordering.
D · incorrect — Binary search has logarithmic rather than linear worst-case probes.
Question 4
For ordinary array sorting implementations, which listed algorithm uses a temporary element buffer proportional to n rather than only a fixed number of saved elements? Count recursive call frames separately from auxiliary element storage.
A. Insertion sort
B. Selection sort
C. Merge sort
D. Quick sort
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Ordinary array mergesort merges two sorted halves through a temporary buffer that can hold a number of elements proportional to n. Insertion sort retains one item while shifting, and selection sort needs fixed temporary storage for a minimum position and an exchange. Ordinary quicksort partitions inside the original array. Its recursive stack is counted separately here, so the linear element-buffer requirement uniquely identifies mergesort.
Evidence in the complete study note
Ordinary array merging needs a linear auxiliary buffer.DSA37
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
At position i, scan the remaining suffix for its minimum, then exchange it with A[i].DSA33
Quicksort normally rearranges in the same array but recursive storage can be linear in the worst case.DSA36
Choice by choice
A · incorrect — Insertion saves one item and shifts within the same array.
B · incorrect — Selection retains a minimum position and a fixed-size swap temporary.
C · correct — Ordinary array merging needs a linear auxiliary element buffer.
D · incorrect — In-array partitioning needs no full merge buffer; recursive frames are excluded by the stated convention.
Question 5
Which data structure is the most appropriate for sharing a printer in a network environment?
A. Stack
B. Binary search tree
C. Full binary tree
D. Queue
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The module explicitly identifies print-server jobs as a queue application. FIFO preserves arrival order among pending jobs. Evidence: assigned PDF pages 8, 6, 9.
Evidence in the complete study note
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — A stack would give the most recent print request priority. See assigned PDF 8, 6, 9.
B · incorrect — BST ordering by key is not arrival-order service. See assigned PDF 8, 6, 9.
C · incorrect — A full tree shape does not specify job service order. See assigned PDF 8, 6, 9.
D · correct — The print server maintains a queue of print jobs. See assigned PDF 8, 6, 9.
Question 6
Which one of the following is true about Queue data structure?
A. Queue data structure applies first come first served policy
B. Queue data structure uses last in first out rule
C. Queue data structure does not have efficient basic operations
D. Queue data structure cannot be implemented using linked list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — Queue data structure applies first come first served policy
FIFO serves the first arrival first; the module also explicitly gives linked-list enqueue and dequeue. Therefore A is true and the supplied D key contradicts page 8. Evidence: assigned PDF pages 7, 8.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · correct — First come first served is stated under queue applications. See assigned PDF 7, 8, 8.
B · incorrect — LIFO describes the stack, whereas queue deletion is at the front. See assigned PDF 7, 8, 8.
C · incorrect — A blanket inefficiency claim is unsupported; front removal and rear insertion can use fixed pointer updates. See assigned PDF 7, 8, 8.
D · incorrect — The module expressly implements the queue as a linked list. See assigned PDF 7, 8, 8.
Question 7
An unsorted singly linked list maintains only its head pointer. Which option gives the complete set of listed operations with tight worst-case constant time? There is no cached tail, predecessor index or positional index.
A. Insertion at the front of the linked list
B. Insertion at the end of the linked list
C. Deletion of the front node of the linked list
D. Deletion of the last node of the linked list
E. A&C
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Inserting at the head links the new node to the old head and updates head. Deleting the head advances head and releases one node. Both use constant work. Appending requires traversal to find the tail, and deleting the tail requires its predecessor, also found by traversal. The complete constant-time set is therefore insertion at the front together with deletion of the front, which is option E.
Evidence in the complete study note
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++.DSA09
Deleting the tail of a singly linked list requires its predecessor, even when tail itself is known. Handle empty and single-node lists separately; after removing the only node, set both head and tail to null. To remove a known successor, bypass it before deallocation. Clearing an owned n-node chain visits and releases every node.DSA09
Choice by choice
A · incorrect — Front insertion is constant, but this alone omits the also-constant front deletion.
B · incorrect — Head-only append traverses the list to find its tail.
C · incorrect — Front deletion is constant, but this alone omits the also-constant front insertion.
D · incorrect — Tail deletion must locate its predecessor by traversal.
E · correct — This combines exactly the two listed constant-time operations.
Question 8
Which of the following data structure is more appropriate to represent a heap tree?
A. Two dimensional array
B. Doubly linked list
C. Linear array
D. Single linked list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The heap algorithm directly maps tree nodes to Data indices and uses arithmetic child indices, establishing the linear array representation. Evidence: assigned PDF pages 11.
Evidence in the complete study note
Zero-based array representation: root index 0, left=2i+1, right=2i+2, parent=floor((i-1)/2) for i>0. One-based representation uses children 2i,2i+1 and parent floor(i/2). A child exists only if its index is inside the current heap size.DSA23
Choice by choice
A · incorrect — A second array dimension is unnecessary for one index per node. See assigned PDF 11.
B · incorrect — A doubly linked list lacks the given direct child-index arithmetic. See assigned PDF 11.
C · correct — Data[0] and children 2*i+1, 2*i+2 use a one-dimensional array. See assigned PDF 11.
D · incorrect — A singly linked chain does not directly represent the two children by these indices. See assigned PDF 11.
Question 9
Linear search is highly inefficient compare to binary search when dealing with_____?
A. Small, unsorted arrays
B. Large, sorted arrays
C. Small, sorted arrays
D. Large, unsorted arrays
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The comparison n versus log2 n becomes substantial for large n, and binary searching requires ordering. Thus both size and sortedness matter. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Choice by choice
A · incorrect — Unsorted input does not satisfy binary-search prerequisites. See assigned PDF 3, 3.
B · correct — Large sorted arrays provide both the prerequisite and the asymptotic advantage. See assigned PDF 3, 3.
C · incorrect — Sorting permits binary search, but small size does not produce the large growth-rate difference requested. See assigned PDF 3, 3.
D · incorrect — Large unsorted arrays still cannot be binary-searched without preprocessing. See assigned PDF 3, 3.
Question 10
Considering the array elements (independently for this question):
int a[6]={11,13,15,17,19,21}
Implementing stack, the elements after pop(); push(9); are:
A. 9, 11, 13, 15, 17, 19
B. 13, 15, 17, 19, 21, 9
C. 11, 13, 15, 17, 19, 9
D. 9, 13, 15, 17, 19, 21
Hint / Module Reference (Where to Read)
Trace the initial state and each executed operation in order, preserving the requested output layout.
Take the listed array in bottom-to-top order, with 21 at top. Pop removes 21; push appends 9 at the same top slot, leaving 11,13,15,17,19,9. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — This puts 9 at the bottom and shifts surviving data. See assigned PDF 6, 6.
B · incorrect — This removes 11, which is a queue-style front removal. See assigned PDF 6, 6.
C · correct — Only the final top entry changes from 21 to 9. See assigned PDF 6, 6.
D · incorrect — This replaces the bottom entry 11 rather than the top. See assigned PDF 6, 6.
Question 11
A capacity-six circular queue uses all six slots with front=0 and size=6. Its physical array is [11,13,15,17,19,21]. After dequeue() and enqueue(9), what is the logical front-to-rear sequence?
A. 9, 11, 13, 15, 17, 19
B. 13, 15, 17, 19, 21, 9
C. 11, 13, 15, 17, 19, 9
D. Queue overflow
Hint / Module Reference (Where to Read)
Trace the initial state and each executed operation in order, preserving the requested output layout.
The initial front element is 11, so dequeue removes it and advances front to the slot containing 13. The queue now has five items. Circular insertion reuses the freed physical slot zero for 9 and restores size six. Reading from the new front around to the rear gives 13,15,17,19,21,9. Physical slot order differs from this requested logical service order.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Choice by choice
A · incorrect — This would remove 21 and prepend 9 rather than remove the front.
B · correct — This is the front-to-rear order after removing 11 and appending 9.
C · incorrect — This incorrectly retains 11 and removes the rear 21.
D · incorrect — Circular reuse makes room for the insertion after the removal.
Question 12
A circular queue has capacity six, front=0 and size=6, using physical slots [11,13,15,17,19,21]. It can use all six slots. After dequeue() and enqueue(9), list the physical array in index order 0 through 5.
A. 9, 11, 13, 15, 17, 19
B. 13, 15, 17, 19, 21, 9
C. 11, 13, 15, 17, 19, 9
D. 9, 13, 15, 17, 19, 21
Hint / Module Reference (Where to Read)
Trace the initial state and each executed operation in order, preserving the requested output layout.
Dequeue reads 11 at index zero, advances front to index one and reduces size to five. The count-based insertion formula then gives (front+size)%6=(1+5)%6=0. Enqueue therefore writes 9 into the freed slot zero. All other physical slots retain their old values. The logical service order begins at 13, but the requested physical index order begins at the newly stored 9.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Dequeue reads A[front], sets front=(front+1)%C and decreases size. An alternative reserves one unused slot and uses next(rear)==front for full; its empty test and capacity differ. State the convention before tracing.DSA15
Choice by choice
A · incorrect — This drops 21 and retains the removed 11.
B · incorrect — This is logical front-to-rear order, not physical index order.
C · incorrect — This overwrites 21 instead of reusing slot zero.
D · correct — Slot zero receives 9 and slots 1–5 remain unchanged.
Question 13
The data structure used in the standard implementation of Breadth First Search is ?
A. Stack
B. Array
C. Linked List
D. Queue
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Breadth-first search repeatedly dequeues a vertex and enqueues its undiscovered neighbors. FIFO ordering ensures earlier distance layers are processed before later ones. Arrays or linked nodes can store this frontier, but Queue names its required access discipline. A stack instead serves latest pending work.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
Choice by choice
A · incorrect — A stack serves the latest pending vertex first and does not preserve BFS distance-layer order.
B · incorrect — An array can store a queue, but an array alone specifies no FIFO frontier discipline.
C · incorrect — Linked nodes can represent a queue, but Linked List alone does not specify breadth-first processing.
D · correct — A FIFO queue processes discovered vertices by distance layer, the standard BFS frontier rule.
Question 14
Suppose we define a static method totalEvenLoc() that returns the total for even-index items of an integer list as shown, on the right, below. What is the Big O running time of the method if lst is a LinkedList of size N?
public static int totalEvenLoc(List<Integer> lst) {
int sum = 0;
for(int i = 0; i < lst.size(); i += 2)
sum += lst.get(i);
return sum;
}
A. O(N)
B. O(1)
C. O(N^2)
D. O(logN)
E. O(NlogN)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
The loop visits about N/2 even indices, but LinkedList.get(i) walks from the nearer endpoint. A linear number of those indices lie near the middle, each requiring linear traversal. DSA07 analyzes exactly this access pattern and obtains Θ(N²) total work. Incrementing by two changes a constant factor, not the quadratic order.
Evidence in the complete study note
Indexed access is not constant for every List implementation. Java LinkedList.get(i) walks from the nearer endpoint. Summing get(0), get(2), get(4), … over a length-N list still gives Theta(N²), because a linear number of middle indices each require linear traversal. An iterator scans once in linear time. An exact executable runtime requires valid code and an explicit cost convention.DSA07
Choice by choice
A · incorrect — O(N) would require constant-cost indexed access; LinkedList.get(i) instead traverses nodes.
B · incorrect — A growing number of accesses and additions prevents a constant bound on total work.
C · correct — A linear number of middle-index accesses each traverse a linear number of nodes, yielding quadratic time.
D · incorrect — Neither the iteration count nor the accumulated linked-node traversal has logarithmic growth.
E · incorrect — Quadratic traversal grows faster than N log N, so this is not a valid upper bound.
Question 15
The array 10, 8, 6, 2, 1, 4, 5 is organized into a full heap (heap and full BT). Which array represents the heap after the first and second biggest elements are removed?
A. 6 5 4 2 1
B. 6 4 5 2 1
C. 6 4 5 1 2
D. 6 5 4 1 2
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Remove 10 by moving 5 to root and adjusting: [8,5,6,2,1,4]. Remove 8 by moving 4 to root and adjusting through child 6: [6,5,4,2,1]. These are standard root-last swaps and downward heap restoration. Evidence: assigned PDF pages 11.
Evidence in the complete study note
Insert at the next complete-tree position and swap upward while parent order is violated. To remove the root, move the final element to root, reduce heap size, then swap downward with the more dominant child until order holds. Each path has logarithmic length. Building bottom-up by sinking internal nodes takes linear total time; repeated independent insertions give an O(n log n) construction bound.DSA24
Max-heap [10,8,6,2,1,4,5]: remove 10, move 5 to root and sink, giving [8,5,6,2,1,4]. Remove 8, move 4 up then exchange with 6: [6,5,4,2,1].DSA24
Choice by choice
A · correct — Matches both root deletions and adjustment steps. See assigned PDF 11.
B · incorrect — A valid max heap, but not the result of these root-last adjustments. See assigned PDF 11.
C · incorrect — Changes the lower pair 2,1 as well as giving a different adjustment history. See assigned PDF 11.
D · incorrect — Reverses the unchanged lower pair 2,1. See assigned PDF 11.
Question 16
Think of a reference implementation of a classical queue with front and rear pointing to the appropriate locations in the queue. Which of these references will change during an insertion into a possibly empty queue?
A. Neither change
B. Only front changes
C. None of the choices is correct
D. Both may change.
E. Only rear changes
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Insertion into an empty linked queue makes the new node both front and rear. Insertion into a nonempty queue changes rear while front remains. Consequently both references may change across the allowed cases. Evidence: assigned PDF pages 7, 8, 5.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — Insertion must update at least rear to include the new node. See assigned PDF 7, 8, 5.
B · incorrect — Rear changes too; front alone is insufficient. See assigned PDF 7, 8, 5.
C · incorrect — D describes the empty-queue case correctly. See assigned PDF 7, 8, 5.
D · correct — Both change when the first node is inserted. See assigned PDF 7, 8, 5.
E · incorrect — Rear alone changes only in the nonempty case. See assigned PDF 7, 8, 5.
Question 17
Binary search is to operate on an already ordered sequence of comparable keys through an indexed-access interface. Which listed property is required of its search domain, rather than being a particular physical array representation or allocation policy?
A. The array must hold elements of the same data type.
B. All are additional requirements.
C. The array must be contiguous.
D. The search interval must have valid finite bounds.
E. The array must fix its size a prior to population.
F. None is an additional requirement.
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: D — D. The search interval must have valid finite bounds.
Binary search maintains an interval of candidate indices and repeatedly shrinks it until a match or an empty interval is obtained. That operation requires valid finite bounds. Homogeneous physical storage and contiguity are properties of ordinary array representations, rather than requirements of the abstract interval-halving procedure. Fixing capacity before population is unnecessary: a resizable sequence can be populated first and searched afterward. Hence not all listed properties are requirements.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Choice by choice
A · incorrect — Comparable keys are assumed; identical physical data types are not the abstract domain requirement.
B · incorrect — All fails because prior fixed allocation is unnecessary.
C · incorrect — Contiguity is a representation choice rather than the abstract search-domain requirement.
D · correct — The candidate index domain needs valid finite bounds.
E · incorrect — A resizable sequence may be populated before searching.
F · incorrect — Valid finite bounds are a required condition among these choices.
Question 18
What will be the content of the queue (shown from queue front on the left to queue rear on the right), after the given sequence of operations shown below?
Queue q = new Queue();
q.enqueue(4);
q.enqueue(8);
if(q.peek() > 5)
q.dequeue();
q.enqueue(1);
q.enqueue(6);
q.dequeue();
A. 4, 6
B. 4, 8, 1
C. 8, 1, 6
D. 8, 6
E. 4, 1
Hint / Module Reference (Where to Read)
Trace the initial state and each executed operation in order, preserving the requested output layout.
After enqueues the queue is [4,8]. Peek examines the front 4, so 4>5 is false and the conditional dequeue does not execute. Enqueues give [4,8,1,6]; the final dequeue removes 4, leaving [8,1,6]. Evidence: assigned PDF pages 7, 6.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — Drops 8 and 1 without corresponding deletions. See assigned PDF 7, 6.
B · incorrect — Leaves the removed 4 and omits the enqueued 6. See assigned PDF 7, 6.
C · correct — Matches the final FIFO sequence. See assigned PDF 7, 6.
D · incorrect — Incorrectly removes 1 as well as 4. See assigned PDF 7, 6.
E · incorrect — Drops 8 and 6 and retains the removed 4. See assigned PDF 7, 6.
Question 19
What is the tightest listed worst-case time bound for constructing an optimal binary search tree using the standard interval dynamic program that tries every key as root of every interval?
A. O(n)
B. O(n³)
C. O(logn)
D. O (n!)
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
This asks about constructing an optimal BST, rather than searching a tree after construction. The standard dynamic program considers quadratically many key intervals. For each interval it tries up to a linear number of candidate roots, combining the relevant subproblem costs. Multiplying those counts gives cubic construction time. The cubic option states that bound; the linear, logarithmic and factorial alternatives do not give the tight construction order.
Evidence in the complete study note
Standard optimal-BST dynamic programming tries each possible root for each key interval: O(n²) intervals times O(n) roots gives O(n³) construction.DSA19
Choice by choice
A · incorrect — Linear time does not cover all intervals and root candidates.
B · correct — Quadratic intervals times linear root trials give cubic time.
C · incorrect — Logarithmic time concerns balanced search paths, not this construction.
D · incorrect — Factorial is a loose upper bound rather than the tight listed order.
Question 20
Which of the following is the best case time complexity of linear search algorithm?
A. O(n'2)
B. O(n)
C. O(1)
D. O(log n)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
A match at the very first inspected element ends scanning after one comparison, independent of n. Interpret the options as tight growth orders rather than arbitrary loose Big-O upper bounds. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Choice by choice
A · incorrect — Quadratic is not the tight best-case count. See assigned PDF 3.
B · incorrect — Linear is the complete-scan bound, not the immediate-match cost. See assigned PDF 3.
C · correct — One first-element comparison is constant. See assigned PDF 3.
D · incorrect — Logarithmic describes halving, not immediate linear-search success. See assigned PDF 3.
Question 21
If the elements '1', '2', '3' and '4' are inserted in a queue, what would be order for the removal?
A. 4321
B. 3241
C. 1234
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
FIFO removes the four insertions in their original order: 1 then 2 then 3 then 4. Evidence: assigned PDF pages 7.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — 4321 reverses arrival order. See assigned PDF 7.
B · incorrect — 3241 puts later arrivals before 1 and 2. See assigned PDF 7.
C · correct — 1234 preserves insertion order. See assigned PDF 7.
D · incorrect — C already supplies the FIFO result. See assigned PDF 7.
Question 22
What is the disadvantage of array data structure?
A. The amount of memory to be allocated should be known beforehand.
B. Elements of an array can be accessed in constant time.
C. Elements are stored in contiguous memory blocks.
D. Multiple other data structures can be implemented using arrays.
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — The amount of memory to be allocated should be known beforehand.
The module calls array storage static and contrasts it with dynamically allocated nodes. A fixed array requires a capacity in advance; constant access and reuse as a storage implementation are benefits, while contiguous storage alone is not the capacity drawback. Evidence: assigned PDF pages 6, 7, 5.
Evidence in the complete study note
A fixed array has a chosen capacity; the choice need not occur at compile time. A resizable array allocates a larger block and copies when needed. Inserting in the middle shifts later elements, so it costs linear time. Appending into spare capacity is constant; a resizing append can be linear, though repeated geometric growth gives amortized constant append cost.DSA02
Choice by choice
A · correct — Preallocated fixed capacity is the disadvantage illustrated by static array implementations. See assigned PDF 6, 7, 5.
B · incorrect — Constant indexed access is an advantage, not a disadvantage. See assigned PDF 6, 7, 5.
C · incorrect — Contiguity itself does not state the capacity limitation. See assigned PDF 6, 7, 5.
D · incorrect — Supporting other structures is useful rather than a disadvantage. See assigned PDF 6, 7, 5.
Question 23
For selection sort on n elements, n>=2, count only exchanges between distinct positions and omit the final one-element suffix. What is the maximum number of swaps?
A. n - 1
B. 1
C. n
D. n - 2
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Selection sort places the minimum remaining element into each successive position. After n-1 such placements, the last position is determined automatically. Each placement needs at most one exchange between distinct positions, so the maximum is n-1. This count excludes self-swaps and the redundant final-position call that some implementations include. The choice of input can require an exchange on every one of those meaningful passes.
Evidence in the complete study note
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls.DSA33
Choice by choice
A · correct — There are n-1 meaningful placements, each requiring at most one exchange.
B · incorrect — More than one exchange can be needed for larger n.
C · incorrect — n counts an extra redundant final swap call under another convention.
D · incorrect — n-2 omits a possible exchange on a meaningful pass.
Question 24
In an infix-to-prefix conversion algorithm that temporarily holds pending operators and parentheses using last-in, first-out access, which abstract data type supplies that access discipline?
A. Stack
B. Queue
C. Binary tree
D. Linked list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Pending operators must be retrieved in reverse order when grouping or precedence requires them to be emitted. A stack provides that last-in, first-out discipline. An expression tree is another possible representation for conversion, but it is not the requested pending-operator ADT in this specified algorithm. A queue retrieves the oldest entry first, while a linked list alone describes storage links without prescribing the needed access policy.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
To evaluate postfix, push operands. At a binary operator, pop right operand first, then left, and push left op right. Build an expression tree for either prefix (preorder) or postfix (postorder); a stack is useful but is not the only possible conversion representation.DSA13
Choice by choice
A · correct — A stack retrieves the latest pending operator first.
B · incorrect — A queue uses first-in, first-out access.
C · incorrect — An expression tree can support another conversion method but is not this pending-operator ADT.
D · incorrect — A linked list can implement storage but alone does not specify LIFO behavior.
Question 25
Which one of the following is the process of inserting an element in the stack?
A. Insert
B. Add
C. Push
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The stack terminology explicitly names adding an element Push. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — Insert is a generic action rather than the given operation name. See assigned PDF 6.
B · incorrect — Add is descriptive rather than the module stack name. See assigned PDF 6.
C · correct — Push is defined as adding an element to the stack. See assigned PDF 6.
D · incorrect — C is explicitly defined, so none is false. See assigned PDF 6.
Question 26
How many cases are there, which are used to compare various data structure's execution time in a relative manner?
A. 2
B. 3
C. 4
D. 5
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
DSA05 names best, average, and worst as the ordinary cases for comparing costs on inputs of equal size. Average additionally needs an input distribution. Counting these cases gives three. This is a classification of input cases, rather than a count of resources, data structures, or asymptotic bound notations.
Evidence in the complete study note
Fix the input size before comparing cases. Best-case cost is the minimum resource use over legal inputs of that size; worst-case cost is the maximum. Average-case cost averages costs using a stated input distribution. These three input-case functions can each be described using upper, lower or tight asymptotic bounds; the case name does not select the bound notation.DSA-S01
Choice by choice
A · incorrect — Two omits one of the three named categories: best, average, and worst case.
B · correct — The note lists three ordinary fixed-size input cases: best, average, and worst.
C · incorrect — Four does not match the three ordinary input-case categories listed in DSA05.
D · incorrect — Five adds categories outside the stated best, average, and worst input-case classification.
Question 27
Which case of data structure operation takes maximum time?
A. Worst Case
B. Average Case
C. Best Case
D. None of the above
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
DSA05 distinguishes best, average, and worst over inputs of the same size. Worst selects the largest runtime; best selects the smallest, while average takes an expectation under a distribution. Therefore Worst Case directly matches maximum time. This input-case distinction is independent of whether the resulting cost function is described with O, Ω, or Θ notation.
Evidence in the complete study note
Fix the input size before comparing cases. Best-case cost is the minimum resource use over legal inputs of that size; worst-case cost is the maximum. Average-case cost averages costs using a stated input distribution. These three input-case functions can each be described using upper, lower or tight asymptotic bounds; the case name does not select the bound notation.DSA-S01
Choice by choice
A · correct — Worst case takes the maximum operation cost over valid inputs of the same size.
B · incorrect — Average case computes an expected cost under a distribution instead of selecting the maximum.
C · incorrect — Best case selects the minimum cost, the opposite extremum from the question.
D · incorrect — Worst Case is offered and directly identifies the requested maximum-time input case.
Question 28
Which listed characteristic is a binary-tree shape condition rather than a general functional-correctness or resource-cost criterion for arbitrary data-structure operations? Interpret completeness as the complete-tree shape property.
A. Completeness
B. Correctness
C. Time Complexity
D. Space Complexity
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correctness asks whether operations produce their specified results. Time and space complexity measure operation counts and memory use under a resource model. Completeness, under the explicit meaning supplied here, instead describes how a binary tree’s levels are filled: earlier levels are full and the last fills from the left. It is a particular shape condition, rather than a universal assessment criterion for every data structure.
Evidence in the complete study note
Binary means at most two children. Full means each node has zero or two children. Complete means all earlier levels are filled and the last fills from left. Perfect means all leaves share a level and every internal node has two children. Balanced means height stays logarithmic under a stated rule; it does not require a perfect shape.DSA18
Finiteness means termination after finitely many steps for every valid input. Definiteness means each instruction has one interpretation; effectiveness means each step is executable. Correctness means meeting the stated result for every valid input. A finite program can still return the wrong answer.DSA04
Time counts chosen operations; space counts memory, including live recursive frames.DSA05
Choice by choice
A · correct — Completeness describes a particular binary-tree shape.
B · incorrect — Correctness assesses whether an operation meets its specification.
C · incorrect — Time complexity assesses operation cost.
D · incorrect — Space complexity assesses memory cost.
Question 29
Which abstract data types permit deleting an element at the front and inserting an element at the rear? Include types that also permit additional endpoint operations. Select all that apply.
A. Stacks
B. Queues
C. Deques
D. Binary search tree
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): B, C — B. Queues; C. Deques
An ordinary queue supplies exactly the stated FIFO operations: insertion at the rear and removal at the front. A deque allows insertion and removal at both ends, which includes those same two operations as a subset. The question explicitly includes types with additional endpoint capabilities, so both qualify. A stack exposes a single LIFO top, and a BST organizes access by keys rather than front and rear.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure.DSA16
Choice by choice
A · incorrect — A stack exposes a single LIFO top rather than these FIFO endpoints.
B · correct — A queue enqueues at rear and dequeues at front.
C · correct — A deque includes both requested operations among its endpoint capabilities.
D · incorrect — A BST uses key-based tree operations rather than front/rear endpoints.
Question 30
Which algorithms have tight worst-case time Theta(n²)? Use ordinary array comparison-sort implementations; radix sort uses counting-based passes with fixed digit count and fixed radix. Select all that apply.
A. Merge sort
B. Insertion sort
C. Quick sort
D. Radix sort
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answers (select all): B, C — B. Insertion sort; C. Quick sort
Insertion sort on reverse input shifts a growing sorted prefix, totaling quadratic work. Quicksort repeatedly choosing an extreme pivot also accumulates quadratic partition work. Ordinary merge sort instead performs linear work at logarithmically many levels. Under the explicitly fixed digit count and radix, radix sorting is linear in n. Tight bounds distinguish these actual growth rates from the looser quadratic upper bounds that faster algorithms also satisfy.
Evidence in the complete study note
Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work.DSA36
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage.DSA39
Choice by choice
A · incorrect — Ordinary merge sort has tight n log n worst time.
B · correct — Reverse-order insertion gives quadratic shifts.
C · correct — Repeated extreme quicksort pivots give quadratic work.
D · incorrect — Fixed-width, fixed-radix counting passes give linear time.
Question 31
In which sorting algorithm does the largest element "bubble" to the end of the list at each pass?
A. Bubble sort
B. Selection sort
C. Insertion sort
D. Heap sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Repeated adjacent out-of-order swaps push the largest item toward the final position in a left-to-right pass. This is exactly the bubble-sort mechanism. Evidence: assigned PDF pages 4, 3, 11.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
At position i, scan the remaining suffix for its minimum, then exchange it with A[i].DSA33
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
Choice by choice
A · correct — Adjacent comparisons bubble the largest to its proper end. See assigned PDF 4, 3, 3, 11.
B · incorrect — Selection finds a minimum and swaps it into position rather than bubbling through adjacent pairs. See assigned PDF 4, 3, 3, 11.
C · incorrect — Insertion inserts each new element into a sorted prefix. See assigned PDF 4, 3, 3, 11.
D · incorrect — Heap sort removes a root maximum using tree adjustment. See assigned PDF 4, 3, 3, 11.
Question 32
Which algorithms have tight best-case time Theta(n)? Use early-exit bubble sort, ordinary quicksort, ordinary array mergesort without merge-skipping, and standard insertion sort. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Alternative version 1
Which algorithms have tight best-case time Theta(n)? Use early-exit bubble sort, standard selection sort, ordinary array mergesort without merge-skipping, and standard insertion sort. Select all that apply.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answers (select all): A, D — A. Bubble sort; D. Insertion sort
Early-exit bubble sort terminates after one complete no-swap pass on already sorted input, so its best case is linear. Insertion sort also checks each new item once without shifting it on sorted input. Ordinary quicksort still partitions across logarithmically many balanced levels in its best case, and ordinary mergesort still performs its merges. Thus exactly the bubble and insertion implementations have the requested linear best case.
Evidence in the complete study note
Early stopping makes a sorted input linear: one no-swap pass finishes.DSA32
On sorted input each pass needs one ordering check and no shifts: linear time.DSA34
Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work.DSA36
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Choice by choice
A · correct — The no-swap early exit gives a linear sorted-input pass.
B · incorrect — Ordinary quicksort has n log n best growth.
C · incorrect — Without merge-skipping, mergesort still uses n log n work.
D · correct — Sorted input needs one ordering check per insertion pass.
Alternative version 1
Correct answers (select all): A, D — A. Bubble sort; D. Insertion sort
Early-exit bubble sort needs one no-swap pass on sorted input, while insertion sort performs one successful ordering check per new item with no shifts. Both have linear best time. Selection sort still scans every remaining suffix and makes quadratic comparisons, even on sorted input. Ordinary mergesort retains logarithmically many levels of merging. Consequently A and D are the complete selection for this variant.
Early stopping makes a sorted input linear: one no-swap pass finishes.DSA32
On sorted input each pass needs one ordering check and no shifts: linear time.DSA34
There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order.DSA33
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
A · correct — An early-exit no-swap pass makes optimized bubble sort linear on sorted input.
B · incorrect — Selection sort still scans each suffix and makes quadratic comparisons even when sorted.
C · incorrect — Ordinary merge sorting does n log n work across input orders.
D · correct — Insertion sort is linear on sorted input because each pass needs no shifts.
Question 33
Which ordinary iterative array sorting implementations use constant auxiliary element storage? Use buffered mergesort for C. Select all that apply.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Apply the naming, type and syntax rules before deciding whether an option can be used as stated.
Correct answers (select all): A, B, D — A. Bubble sort; B. Selection sort; D. Insertion sort
Bubble sort reuses one temporary element for each adjacent swap. Selection sort retains the minimum position while scanning, then exchanges elements using the same fixed-size temporary storage. Insertion sort saves one item and shifts preceding entries within the original array before filling the gap. The indices and saved elements stay fixed in number as n grows, giving constant auxiliary storage for A, B and D. Buffered mergesort instead needs a linear auxiliary buffer.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
At position i, scan the remaining suffix for its minimum, then exchange it with A[i].DSA33
Ordinary array merging needs a linear auxiliary buffer.DSA37
Choice by choice
A · correct — Adjacent swaps reuse a single temporary element and a fixed number of indices.
B · correct — The suffix scan retains a minimum index; the exchange needs only fixed-size temporary storage.
C · incorrect — The specified buffered array mergesort allocates a linear auxiliary merge buffer.
D · correct — One saved item and fixed-size indices suffice while larger entries shift within the original array.
Question 34
Which sorting algorithm uses a pivot element to partition the list into two sublists?
A. Bubble sort
B. Selection sort
C. Quick sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The source quicksort procedure chooses a pivot and partitions around it before recursively sorting both sides. Evidence: assigned PDF pages 11, 4, 3.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
Begin with the first element already sorted.DSA34
Choice by choice
A · incorrect — Bubble uses adjacent exchanges without a pivot partition. See assigned PDF 11, 4, 3, 3.
B · incorrect — Selection chooses the minimum for its next position. See assigned PDF 11, 4, 3, 3.
C · correct — Quicksort explicitly chooses and positions a pivot. See assigned PDF 11, 4, 3, 3.
D · incorrect — Insertion extends a sorted prefix rather than partitioning by a pivot. See assigned PDF 11, 4, 3, 3.
Question 35
Which sorting implementations preserve the relative input order of equal keys? Use bubble sort with strict adjacent swaps, standard exchange-based selection sort, ordinary in-place quicksort, and mergesort with left-first tie handling. Select all that apply.
A. Bubble sort
B. Selection sort
C. Quick sort
D. Merge sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): A, D — A. Bubble sort; D. Merge sort
Strict bubble swaps never exchange equal adjacent keys, so equal records retain their input order. Left-first handling during merging likewise preserves the order of ties from the left and right runs. Standard selection sort can reverse ties through a distant minimum exchange, and ordinary quicksort partitioning does not guarantee stable order. The specified implementation details therefore make bubble and merge the two stable choices.
Evidence in the complete study note
Strict swaps preserve equal-key order.DSA32
With left-first tie handling, equal keys retain order.DSA37
Selection suits expensive record moves with cheap key comparisons, not every large dataset. It is unstable: exchanging first 2a with 1 in [2a,2b,1] gives [1,2b,2a]. Constant extra element storage is shared by several sorts.DSA33
stack usually log n average, n worst; unstableDSA31
Choice by choice
A · correct — Strict adjacent swaps preserve equal-key order.
B · incorrect — A distant minimum exchange can reverse equal records.
C · incorrect — Ordinary in-place partitioning does not guarantee stability.
D · correct — Taking the left run first on ties preserves equal-key order.
Question 36
Which algorithm has tight Theta(n log n) time in both the average and worst cases? Use ordinary array implementations; radix sort uses fixed digit count and fixed radix.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Radix sort
Alternative version 1
Under ordinary array comparison-sort implementations, which algorithm has tight Theta(n log n) time in every input case? Exclude optimizations that skip work on already ordered input.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Ordinary mergesort performs linear merging at each of logarithmically many levels, giving n log n work regardless of input order. Bubble and selection have quadratic average and worst time. Fixed-width, fixed-radix counting passes instead give radix sort linear time, so radix does not have the requested tight n log n growth. Specifying tight bounds excludes faster methods that would also satisfy the looser Big-O upper bound.
Evidence in the complete study note
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage.DSA39
Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order.DSA33
Choice by choice
A · incorrect — Bubble has quadratic average and worst time.
B · incorrect — Selection makes quadratic comparisons in every order.
C · correct — Ordinary mergesort has tight n log n average and worst time.
D · incorrect — With fixed digits and radix, radix sorting has tight linear time.
Alternative version 1
Correct answer: C — C. Merge sort
Buffered mergesort has linear merge work at logarithmically many levels in every input case, giving tight n log n average and worst growth. Bubble, selection and insertion have quadratic worst time, and their usual average time is also quadratic. Quicksort’s extreme partitions can violate the requested worst-case bound, whereas buffered mergesort meets it.
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order.DSA33
Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
A · incorrect — Bubble has quadratic average and worst time.
B · incorrect — Selection always makes quadratic comparisons.
C · correct — Mergesort has the required tight average and worst bounds.
D · incorrect — Insertion has quadratic average and worst time.
Question 37
For a large array of nonnegative integer keys with fixed digit count and fixed radix, which listed ordinary algorithm can achieve linear time using counting-based digit passes and O(n+r) auxiliary storage?
A. Bubble sort
B. Selection sort
C. Radix sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
With digit count d and radix r fixed, the radix cost O(d(n+r)) reduces to linear growth in n. Its counting-based stable passes use auxiliary storage for output and digit counts. The key assumptions make this an eligible radix-sorting workload rather than an unspecified large-list claim. Bubble, selection and insertion use constant extra element storage in their ordinary forms and can require quadratic work.
Evidence in the complete study note
With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage.DSA39
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
At position i, scan the remaining suffix for its minimum, then exchange it with A[i].DSA33
Choice by choice
A · incorrect — Bubble uses adjacent comparisons and can require quadratic work.
B · incorrect — Selection uses quadratic comparisons and constant extra element storage.
C · correct — Radix uses the stated digit passes and auxiliary storage.
D · incorrect — Insertion uses prefix shifts and can require quadratic work.
Question 38
Which listed sorting algorithm orders fixed-length strings by stably processing individual character positions, without using whole-string comparison operations? Assume an ordered finite character alphabet and LSD passes.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Radix sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Strings can be compared lexicographically, but the stated question asks for a digit-based mechanism rather than whole-key comparisons. LSD radix sorting treats each character position as a digit, stably sorting from the last position toward the first. Stability retains the ordering established by earlier passes. Bubble, selection and merge use comparisons between keys in their ordinary forms, so they do not implement this specified character-pass mechanism.
Evidence in the complete study note
LSD radix sorting handles fixed-width digit keys by stably sorting least-significant digit first, then moving left. Stable intermediate passes preserve the ordering already established by less-significant digits. With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage.DSA39
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
At position i, scan the remaining suffix for its minimum, then exchange it with A[i].DSA33
Split into halves, sort them, then merge by advancing the smaller current front.DSA37
The first element is already a sorted prefix. Each of the remaining N-1 elements is inserted once: the source starts with the first two, then adds the third, and so on. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap. That gives n-1 insertion passes. On sorted input each pass needs one ordering check and no shifts: linear time. Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Choice by choice
A · incorrect — N counts the initial singleton as an insertion pass. See assigned PDF 3.
B · correct — There is one insertion for each position 2 through N. See assigned PDF 3.
C · incorrect — N+1 adds two passes with no corresponding elements. See assigned PDF 3.
D · incorrect — N squared is a work bound, not the count of outer passes. See assigned PDF 3.
Question 40
What is the running time of an insertion sort algorithm if the input is pre-sorted?
A. O(N2)
B. O(N log N)
C. O(N)
D. O(M log N)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
For sorted input every new item already belongs after its predecessor. Each of N-1 prefix extensions needs constant comparison work and no shifts, giving Theta(N). Big-O choices are interpreted as tight orders. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap. That gives n-1 insertion passes. On sorted input each pass needs one ordering check and no shifts: linear time. Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Choice by choice
A · incorrect — Quadratic is the adverse-input bound, not the tight sorted-input cost. See assigned PDF 3.
B · incorrect — N log N adds work not performed by this insertion process. See assigned PDF 3.
C · correct — One constant check per extension gives linear work. See assigned PDF 3.
D · incorrect — M is undefined and no M-dependent process is given. See assigned PDF 3.
Question 41
Which of the following examples represent the worst case input for an insertion sort?
A. array in sorted order
B. array sorted in reverse order
C. normal unsorted array
D. large array
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Reverse order forces each inserted item to move through the whole preceding prefix. The movement total 1+2+...+(n-1)=n(n-1)/2 is quadratic. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap. That gives n-1 insertion passes. On sorted input each pass needs one ordering check and no shifts: linear time. Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Choice by choice
A · incorrect — Sorted input needs no shifts. See assigned PDF 3.
B · correct — Each next element is smaller than every element in the prefix. See assigned PDF 3.
C · incorrect — An arbitrary unsorted array need not maximize all insertion distances. See assigned PDF 3.
D · incorrect — Large size alone does not determine relative ordering or maximal shifts. See assigned PDF 3.
Question 42
Which scenario specifically favors selection sort’s small number of record exchanges, when records themselves are moved and comparisons are cheap? Interpret large values as large records and small keys as inexpensive comparison keys.
A. The input is already sorted
B. A large file has to be sorted
C. Large values need to be sorted with small keys
D. Small values need to be sorted with large keys
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: C — C. Large values need to be sorted with small keys
Selection sort scans suffixes and makes quadratic comparisons regardless of the initial order, but it performs at most one meaningful exchange per placement. That tradeoff can be useful when physically moving a large record is expensive while comparing its small key is cheap. A large file or sorted input alone does not offer this advantage. Expensive large-key comparisons instead make selection’s many comparisons less attractive.
Evidence in the complete study note
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls.DSA33
Choice by choice
A · incorrect — Sorted order does not reduce selection’s quadratic comparison count.
B · incorrect — Large file size alone does not identify the expensive-move advantage.
C · correct — Large records with cheap keys match the many-comparisons/few-exchanges tradeoff.
D · incorrect — Expensive comparisons with cheap moves do not favor that tradeoff.
Question 43
What is the advantage of selection sort over other sorting techniques?
A. It requires no additional storage space
B. It is scalable
C. It works best for inputs which are already sorted
D. It is faster than any other sorting technique
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — Constant extra element storage, conventionally called in-place sorting.
DSA33 says selection uses constant extra element storage, which is the conventional meaning of A’s no-additional-storage phrasing. It still needs a few temporary values, so literally zero bytes would be inaccurate. Its quadratic comparisons do not improve on already sorted input, and the note gives no universal scalability or fastest-algorithm claim. A names the valid conventional benefit.
Evidence in the complete study note
Selection suits expensive record moves with cheap key comparisons, not every large dataset. It is unstable: exchanging first 2a with 1 in [2a,2b,1] gives [1,2b,2a]. Constant extra element storage is shared by several sorts.DSA33
There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order.DSA33
Choice by choice
A · correct — Interpreted conventionally as in-place, selection uses constant extra element storage rather than an auxiliary array.
B · incorrect — Quadratic comparisons do not provide an unqualified scalability advantage for growing datasets.
C · incorrect — Selection makes the same quadratic comparisons even on already sorted input.
D · incorrect — No universal fastest claim follows; selection trades few moves for many comparisons.
Question 44
What is an external sorting algorithm?
A. Algorithm that uses tape or disk during the sort
B. Algorithm that uses main memory during the sort
C. Algorithm that involves swapping
D. Algorithm that are considered 'in place'
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — Sorting using external storage such as disk or tape.
DSA37 defines external sorting through datasets beyond main memory and buffered disk runs. Option A captures this distinguishing external-storage use. Main memory may still hold buffers, but using it alone does not define external sorting. Swapping and being in place are separate implementation properties and do not identify whether the working dataset resides externally.
Evidence in the complete study note
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively. In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant. Internal sorting fits the working dataset in memory. External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.DSA37
Choice by choice
A · correct — Tape or disk stores external runs when the working dataset does not fit wholly in main memory.
B · incorrect — Main-memory use alone does not distinguish external sorting; external algorithms also use memory for buffers.
C · incorrect — Swapping is an operation used by many sorts and does not define external storage use.
D · incorrect — In-place concerns auxiliary element storage, independently of whether sorting accesses an external dataset.
Question 45
What is the worst case complexity of bubble sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
An adversarial input requires repeated passes over adjacent pairs; the total comparisons and swaps are quadratic as stated in the module. Evidence: assigned PDF pages 4.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Choice by choice
A · incorrect — n log n understates the tight adverse-input work. See assigned PDF 4.
B · incorrect — Logarithmic growth cannot account for repeated full passes. See assigned PDF 4.
C · incorrect — Linear describes at most a single pass. See assigned PDF 4.
D · correct — The source explicitly gives O(n2) comparisons and swaps. See assigned PDF 4.
Question 46
What is the average case complexity of bubble sort?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answer: D — O(n²) under the usual average-case model.
DSA32 identifies quadratic average and worst work from repeated adjacent comparisons. Under the usual random-permutation average model, bubble sort therefore takes Θ(n²), which implies O(n²). Early stopping makes an already sorted input linear, but that is the optimized best case rather than the ordinary average over input arrangements.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Fix the input size before comparing cases. Best-case cost is the minimum resource use over legal inputs of that size; worst-case cost is the maximum. Average-case cost averages costs using a stated input distribution. These three input-case functions can each be described using upper, lower or tight asymptotic bounds; the case name does not select the bound notation.DSA-S01
Choice by choice
A · incorrect — Quadratic average work grows faster than n log n, so this bound is too small.
B · incorrect — Repeated adjacent passes do not have logarithmic average growth under the usual input model.
C · incorrect — Linear work is the optimized sorted-input best case, not ordinary average-case bubble sorting.
D · correct — Quadratic average work is bounded by O(n²), matching the adjacent-pass analysis in DSA32.
Question 47
What is the auxiliary space complexity of merge sort?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Merging both halves needs an auxiliary array holding up to n elements. Recursion contributes O(log n) frames, dominated by O(n) temporary element storage in the ordinary implementation. Evidence: assigned PDF pages 11.
Evidence in the complete study note
Ordinary array merging needs a linear auxiliary buffer.DSA37
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
An n-level ordinary recursion with constant live storage per level needs Theta(n) stack space.DSA07
Choice by choice
A · incorrect — Constant space contradicts the full merge array. See assigned PDF 11.
B · incorrect — Logarithmic describes recursion depth alone. See assigned PDF 11.
C · correct — A merge buffer proportional to n dominates auxiliary storage. See assigned PDF 11.
D · incorrect — n log n counts cumulative work across levels, not simultaneously live storage when buffers are reused. See assigned PDF 11.
Question 48
What is the tightest listed worst-case time bound for ordinary array mergesort that performs all merges and does not skip already ordered runs? Interpret logarithms explicitly as parenthesized in the options.
A. O(n log n)
B. O(n²)
C. O(n² log n)
D. O(n (log n)²)
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Ordinary mergesort splits the array into logarithmically many levels and performs linear total merging work per level. It therefore has n log n worst-case growth under the specified implementation. Sorted input does not skip any merges here. The quadratic and n² log n choices are looser upper bounds, while n(log n)² grows faster than n log n. Asking for the tightest listed bound selects A uniquely.
Evidence in the complete study note
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · correct — This matches the actual n log n growth.
B · incorrect — Quadratic is a valid but looser upper bound.
C · incorrect — n² log n is a valid but looser upper bound.
D · incorrect — n(log n)² grows faster and is a looser upper bound.
Question 49
What is the tightest listed best-case time bound for ordinary array mergesort that performs all merges and does not skip already ordered runs? Interpret logarithms explicitly as parenthesized in the options.
A. O(n log n)
B. O(n²)
C. O(n² log n)
D. O(n (log n)²)
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Ordinary mergesort splits the array into logarithmically many levels and performs linear total merging work per level. It therefore has n log n best-case growth under the specified implementation. Sorted input does not skip any merges here. The quadratic and n² log n choices are looser upper bounds, while n(log n)² grows faster than n log n. Asking for the tightest listed bound selects A uniquely.
Evidence in the complete study note
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · correct — This matches the actual n log n growth.
B · incorrect — Quadratic is a valid but looser upper bound.
C · incorrect — n² log n is a valid but looser upper bound.
D · incorrect — n(log n)² grows faster and is a looser upper bound.
Question 50
Using the terminology of the course note, which listed phrase names the combining operation rather than a recognized organization or storage variant of mergesort?
A. in-place merge sort
B. bottom up merge sort
C. top down merge sort
D. linear merge sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Top-down mergesort recursively divides the sequence, while bottom-up mergesort iteratively combines runs of increasing widths. In-place variants change the storage tradeoff used while merging. Under the note’s stated terminology, linear merge names the combining operation itself rather than a separate standardized sort variant. This is a distinction within the supplied naming convention, not a claim that no author could ever use that phrase differently.
Evidence in the complete study note
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively. In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant. Internal sorting fits the working dataset in memory. External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.DSA37
Choice by choice
A · incorrect — In-place merging is a recognized storage variant.
B · incorrect — Bottom-up mergesort is the iterative run-merging organization.
C · incorrect — Top-down mergesort is the recursive organization.
D · correct — Linear merge names the combining operation under the stated terminology.
Question 51
Which of the following is not in place sorting algorithm by default?
A. merge sort
B. quick sort
C. heap sort
D. insertion sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The default merge algorithm explicitly uses an auxiliary array. The described partition, heap swaps and insertion can use the original array; recursion-stack use is distinct from requiring a second element array. Evidence: assigned PDF pages 11, 3.
Evidence in the complete study note
Ordinary array merging needs a linear auxiliary buffer.DSA37
Quicksort normally rearranges in the same array but recursive storage can be linear in the worst case.DSA36
Building with bottom-up sinking is linear; repeated extraction gives O(n log n) worst time. Iterative sinking needs constant auxiliary storage. The method is generally unstable because long root-to-end exchanges can reorder equal keys. It is not uniquely the method for sorting by priorities: any comparison sort can compare a priority field. Heap extraction is its distinctive mechanism.DSA38
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
Choice by choice
A · correct — Merge expressly allocates auxiliary array storage. See assigned PDF 11, 11, 11, 3.
B · incorrect — Quicksort partitions in the existing array in its conventional form. See assigned PDF 11, 11, 11, 3.
C · incorrect — Heap sorts by exchanging root and last within the array. See assigned PDF 11, 11, 11, 3.
D · incorrect — Insertion rearranges the list in its existing slots. See assigned PDF 11, 11, 11, 3.
Question 52
Which of the following is not a stable sorting algorithm?
A. Quick sort
B. Cocktail sort
C. Bubble sort
D. Merge sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — Standard quicksort is unstable.
The DSA31 sorting table identifies quicksort as unstable. Cocktail and bubble sorts preserve equal-key order when swapping only strict adjacent inversions. Ordinary merge sort preserves equal-key order when ties are taken from the left run first. Under these usual implementations, quicksort is the single listed algorithm that does not guarantee stability.
Evidence in the complete study note
Early stopping makes a sorted input linear: one no-swap pass finishes. A fixed pass schedule stays quadratic. Strict swaps preserve equal-key order. Cocktail sort runs bubble passes in both directions and is stable with strict swaps.DSA32
With left-first tie handling, equal keys retain order.DSA37
stack usually log n average, n worst; unstableDSA31
Choice by choice
A · correct — Standard quicksort partition exchanges can move equal keys past one another and do not guarantee stability.
B · incorrect — Cocktail sort is stable with strict adjacent swaps, as described in DSA32.
C · incorrect — Bubble sort preserves equal-key order when it swaps only strict adjacent inversions.
D · incorrect — Merge sort preserves equal-key order by taking equal elements from the left run first.
Question 53
Which specified sorting implementations avoid recursion? A is ordinary recursive quicksort; B is top-down recursive mergesort; C uses iterative heap sinking; D is bottom-up mergesort. Select all that apply.
A. quick sort
B. top-down merge sort
C. heap sort with iterative sinking
D. bottom up merge sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): C, D — C. heap sort with iterative sinking; D. bottom up merge sort
Bottom-up mergesort processes run widths 1, 2, 4 and so on in loops, without recursive splitting. Heapsort can also restore heap order with iterative sinking, making the specified C implementation nonrecursive. A and B are explicitly the recursive forms described in the note. The question fixes implementations because algorithm names alone do not force either recursive or iterative control flow.
Evidence in the complete study note
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively.DSA37
The source states O(n^2) in the worst case. Repeated extreme pivots leave subproblems n-1,n-2,..., whose partition work sums quadratically. Evidence: assigned PDF pages 11.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Choice by choice
A · incorrect — Linear does not include repeated near-full partitions. See assigned PDF 11.
B · incorrect — n log n is the expected, not worst, cost. See assigned PDF 11.
C · correct — Unbalanced partitions give quadratic work. See assigned PDF 11.
D · incorrect — Logarithmic describes neither partition scans nor their total. See assigned PDF 11.
Question 55
For a strictly increasing array of at least five distinct keys, which listed pivot rule is deterministic and avoids choosing an extreme key on the first partition? Interpret median-of-three as the median of the first, middle and last keys.
A. first element
B. last element
C. median-of-three partitioning
D. random element
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: C — C. median-of-three partitioning
On a strictly increasing array, the first key is the minimum and the last key is the maximum, so those deterministic endpoint rules choose extremes. The median of the first, middle and last keys is the middle-position value, which is neither extreme for the stated size. A random element is not a deterministic rule and can choose an endpoint. This criterion selects C without claiming a universally best practical pivot strategy.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Choice by choice
A · incorrect — The first key is the minimum on this input.
B · incorrect — The last key is the maximum on this input.
C · correct — The sample median is the middle-position value and is not extreme.
D · incorrect — Random selection is not deterministic and may choose an extreme.
Question 56
What is the average running time of a quick sort algorithm?
A. O(N2)
B. O(N)
C. O(N log N)
D. O(log N)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Expected O(n log n) is explicitly given. Under ordinary nonadversarial/random-pivot assumptions this is the average runtime intended by the question. Evidence: assigned PDF pages 11.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Fix the input size before comparing cases. Best-case cost is the minimum resource use over legal inputs of that size; worst-case cost is the maximum. Average-case cost averages costs using a stated input distribution. These three input-case functions can each be described using upper, lower or tight asymptotic bounds; the case name does not select the bound notation.DSA-S01
Choice by choice
A · incorrect — Quadratic is the stated worst case. See assigned PDF 11.
B · incorrect — Linear omits recursive partition levels. See assigned PDF 11.
C · correct — Matches the stated expected n log n growth. See assigned PDF 11.
D · incorrect — Logarithmic omits linear partition work. See assigned PDF 11.
Question 57
Which option gives the most complete set of the listed situations in which linear search can be an appropriate direct method? Select the combined answer rather than only one valid situation.
A. When the list has only a few elements
B. When performing a single search in an unordered list
C. Used all the time
D. When the list has only a few elements and When performing a single search in an unordered list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: D — Both short lists and a single unsorted-list query favor scanning.
Linear scanning can suit a short list because setup costs may dominate, and it can answer a single unsorted query without first building an ordered index or sorting the data. These are two supported use cases, not conditions that must occur simultaneously. A and B each give one true but incomplete situation. D combines both, while the universal claim that scanning should be used all the time is false.
Evidence in the complete study note
For a single unsorted query, sorting first is rarely justified. Small lists may favour scanning because setup matters. Sorting does not avoid examining all values for mean, variance or arbitrary parity counts.DSA28
Choice by choice
A · incorrect — True but incomplete: a short list is one supported case, but this omits the single unsorted query.
B · incorrect — True but incomplete: a single unsorted query is supported, but this omits the short-list case.
C · incorrect — Linear search is not preferable for every workload or available representation.
D · correct — The combined answer includes both supported situations.
Question 58
What is the best case for linear search?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(1)
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
An immediate match at the first list element takes one comparison. Treat complexity options as the tight order. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Choice by choice
A · incorrect — n log n is not the immediate-match cost. See assigned PDF 3.
B · incorrect — Logarithmic is not needed for the first inspected item. See assigned PDF 3.
C · incorrect — Linear is the complete-scan order. See assigned PDF 3.
D · correct — The first-item match requires constant work. See assigned PDF 3.
Question 59
What is the worst case for linear search?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(1)
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
An absent target or a match at the final position requires inspecting n elements, giving tight linear worst-case growth. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Choice by choice
A · incorrect — n log n is a loose bound, not the scan order. See assigned PDF 3.
B · incorrect — Logarithmic cannot inspect all n elements. See assigned PDF 3.
C · correct — A full scan is proportional to n. See assigned PDF 3.
D · incorrect — Constant work describes immediate success, not worst case. See assigned PDF 3.
Question 60
What is the worst case complexity of binary search using recursion?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Each recursive step halves the candidate interval; after k steps its size is at most n/2^k. Reaching size one requires about log2 n steps. Evidence: assigned PDF pages 3.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Choice by choice
A · incorrect — n log n overcounts a single search path. See assigned PDF 3.
B · correct — Repeated halving gives logarithmic search depth. See assigned PDF 3.
C · incorrect — Linear ignores the discarded half at every step. See assigned PDF 3.
D · incorrect — Quadratic has no corresponding nested scan. See assigned PDF 3.
Question 61
For recursive binary search on a sorted random-access array of n distinct keys, each stored key is equally likely to be the successful target. With constant-time comparisons, what is the tightest listed average-time upper bound?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Binary search repeatedly halves the remaining interval. Under equally likely successful keys, only a limited number can be found at shallow decision-tree levels, while a constant fraction require logarithmic depth. Together with the logarithmic upper bound, this gives Theta(log n) average probes. The larger displayed upper bounds are valid but loose; the requested tightest listed bound is therefore O(log n).
Evidence in the complete study note
For successful binary search with all stored positions equally likely, average probes have order Theta(log n). The probe decisions form a binary tree: only a bounded number of positions occur in shallow levels, while a constant fraction require logarithmic depth. Interval halving also gives the logarithmic upper bound. A distribution concentrating on an immediate midpoint hit would give a different average.DSA-S01
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Choice by choice
A · incorrect — n log n is a looser upper bound on logarithmic average work.
B · correct — log n is the tight average order under the stated successful-target distribution.
C · incorrect — Linear is a valid but looser upper bound.
D · incorrect — Quadratic is a valid but much looser upper bound.
Question 62
Which task cannot directly use ordinary binary interval elimination under its stated conditions? The interval-union subtask in B uses a sorted array of interval endpoints; C has an ordered monotone good/bad boundary.
A. To find the lower/upper bound in an ordered sequence
B. Finding endpoint bounds in a sorted endpoint array while forming an interval union
C. Finding a monotone good/bad boundary during debugging
D. Directly searching an unordered list without sorting or an ordered index
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: D — D. Directly searching an unordered list without sorting or an ordered index
Binary search needs ordering that justifies rejecting one half of its candidate interval. Lower and upper bounds in an ordered sequence have that property. Searching sorted interval endpoints during an interval-union task also supplies an ordered subproblem, and a monotone debugging boundary permits the same halving logic. Direct searching in an unordered list supplies no such invariant, so a midpoint comparison cannot safely discard a half.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Binary debugging needs an ordered good/bad boundary, not arbitrary fault locations.DSA29
Choice by choice
A · incorrect — Boundary variants operate on the ordered candidate sequence.
B · incorrect — The specified endpoint lookup is an ordered binary-search subtask.
C · incorrect — The specified monotone good/bad boundary supports binary elimination.
D · correct — An unordered list lacks the order needed to safely discard half after comparison.
Question 63
Which standard linear structure is defined by a chain of nodes, each containing a payload and one successor link, with a null successor ending an ordinary noncircular chain?
A. linked list
B. Array
C. Binary tree
D. None of these
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The payload stores an item and the successor link connects its node to the next item’s node. Following those links produces a linear sequence ending at null, which is the ordinary singly linked-list representation. An array instead reaches equal-sized positions by address arithmetic, and a binary tree has a branching parent/child contract rather than this one-successor sequence contract. The linked-list option is therefore the matching standard name.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain.DSA08
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing.DSA02
Binary means at most two children.DSA18
Choice by choice
A · correct — A linked list represents its sequence through payload-plus-successor nodes.
B · incorrect — An array uses indexed positions rather than this successor-chain representation.
C · incorrect — A binary tree specifies up to two child branches rather than the stated linear successor contract.
D · incorrect — The linked-list option supplies the matching structure.
Question 64
What is the time complexity to count the number of elements in the linked list?
A. O(1)
B. O(n)
C. O(logn)
D. None of the mentioned
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Without a stored count, follow next pointers from start to NULL and increment once per visited node. Exactly n node visits are needed. Evidence: assigned PDF pages 5.
Evidence in the complete study note
To display or count nodes, follow next from head until null, processing each node. Counting is Theta(n) unless size is maintained. An array-linked list still follows links unless separately position-indexed.DSA08
Choice by choice
A · incorrect — Constant time requires an additional maintained count. See assigned PDF 5.
B · correct — Traversal visits every node once. See assigned PDF 5.
C · incorrect — No halving shortcut exists in the next-pointer chain. See assigned PDF 5.
D · incorrect — B supplies the traversal order. See assigned PDF 5.
Question 65
Linked lists are not suitable to for the implementation of?
A. Insertion sort
B. Radix sort
C. Polynomial manipulation
D. Binary search
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: D — Binary search loses its usual advantage on linked lists.
DSA29 explains that linked midpoint traversal loses logarithmic total time. That makes an ordinary linked list unsuitable for the usual efficient binary-search implementation, although an algorithm can still be written. The other tasks do not require constant-time midpoint access: insertion sort can relink nodes, polynomial terms can occupy nodes, and radix digit buckets can retain stable node sequences.
Evidence in the complete study note
Linked midpoint traversal loses logarithmic total time.DSA29
Few inversions mean few shifts, favouring insertion for nearly sorted or small arrays. Shift only strictly larger keys for stability. A linked implementation saves array shifts but still must locate each insertion position.DSA34
Lists suit changing sequences when references to insertion positions are already available. Finding a position is still linear. Lists can hold polynomial terms (coefficient, exponent), directory or block links, child lists in nonbinary trees, and hash chains. Browser history can use a doubly linked cursor. A playlist may be circular; airline seat lookup requires a specified seat-record model, not an automatic linked-list answer.DSA10
Stable intermediate passes preserve the ordering already established by less-significant digits.DSA39
Choice by choice
A · incorrect — Insertion sorting can find an insertion location and relink nodes without requiring constant-time midpoint access.
B · incorrect — Radix digit buckets can preserve node order across passes without a random-access midpoint operation.
C · incorrect — Polynomial terms are explicitly listed as a linked-list application in DSA10.
D · correct — Traversing to linked-list midpoints defeats the standard logarithmic total-time advantage of binary search.
Question 66
Which of these is an application of linked lists?
A. To implement file systems
B. For separate chaining in hash-tables
C. To implement non-binary trees
D. All of the mentioned
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
DSA10 explicitly lists directory or block links, hash chains, and nonbinary-tree child lists as applications of linked nodes. These correspond to the three preceding options. Therefore All of the mentioned is the complete answer. The statement says linked lists can implement these components; it does not require every file system or tree representation to use them.
Evidence in the complete study note
Lists suit changing sequences when references to insertion positions are already available. Finding a position is still linear. Lists can hold polynomial terms (coefficient, exponent), directory or block links, child lists in nonbinary trees, and hash chains. Browser history can use a doubly linked cursor. A playlist may be circular; airline seat lookup requires a specified seat-record model, not an automatic linked-list answer.DSA10
Choice by choice
A · incorrect — File-system directory or block links are valid uses, but this option omits the other supported applications.
B · incorrect — Separate chaining uses linked bucket entries, but this is only one of the supported applications.
C · incorrect — Child lists can represent nonbinary-tree children, alongside the other listed uses.
D · correct — All three preceding options correspond to linked-record applications explicitly listed in DSA10.
Question 67
In linked list each node contain minimum of two fields. One field is data field to store the data second field is?
A. Pointer to character
B. Pointer to integer
C. Pointer to node
D. Node
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The second minimum field points to the next node of the same node structure, alongside the payload. Evidence: assigned PDF pages 4.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · incorrect — A character pointer is not the next-node link unless the entire node type were a character, which it is not. See assigned PDF 4.
B · incorrect — An integer pointer cannot stand for the described structured node link. See assigned PDF 4.
C · correct — The link points to a node of the list. See assigned PDF 4.
D · incorrect — The field is a pointer to a node, not a nested node stored by value. See assigned PDF 4.
Question 68
For repeated queries for the item at logical position k, which listed representation gives constant-time lookup? A–C maintain ordinary links and endpoints only; D additionally maintains a random-access array mapping each logical position to its node. Ignore the cost of maintaining this index during updates.
A. Singly linked list
B. Doubly linked list
C. Circular linked list
D. Array implementation with a separate logical-position-to-node index
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answer: D — D. Array implementation with a separate logical-position-to-node index
Ordinary singly, doubly and circular linked lists must follow links to reach a logical position, giving linear worst-case positional access. Storing nodes in an array alone does not change that. The explicit extra index in D is different: it maps each logical position directly to the corresponding node, so a random-access array lookup answers the query in constant time. Update costs are excluded by the stated workload.
Evidence in the complete study note
To display or count nodes, follow next from head until null, processing each node. Counting is Theta(n) unless size is maintained. An array-linked list still follows links unless separately position-indexed.DSA08
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing. This arithmetic gives constant-time positional access in the usual RAM cost model. A row-major rectangular matrix uses base + (row × columns + column) × element_size.DSA02
Choice by choice
A · incorrect — Ordinary next-link traversal is linear in the worst case.
B · incorrect — Using either endpoint still requires linear worst-case traversal.
C · incorrect — Circular links do not supply a direct logical-position index.
D · correct — The maintained position-to-node array permits direct indexed lookup.
Question 69
Linked list is considered as an example of ___________ type of memory allocation.
A. Dynamic
B. Static
C. Compile time
D. None of the mentioned
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Nodes are allocated with new as they are needed; the source explicitly calls linked-list stack memory dynamic. Evidence: assigned PDF pages 5, 6.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
In C++, match new with delete and new[] with delete[].DSA03
Choice by choice
A · correct — Node allocation occurs during execution. See assigned PDF 5, 6.
B · incorrect — Static allocation is the contrasting array implementation. See assigned PDF 5, 6.
C · incorrect — Compile-time allocation does not describe new-node creation. See assigned PDF 5, 6.
D · incorrect — Dynamic is explicitly supported. See assigned PDF 5, 6.
Question 70
In Linked List implementation, a node carries information regarding
A. Data
B. Link
C. Data and Link
D. None of the mentioned
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
A node combines its payload with a next-node pointer. Neither field alone represents the complete linked-list node. Evidence: assigned PDF pages 4.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · incorrect — Data alone omits the next link. See assigned PDF 4.
B · incorrect — A link alone omits the payload. See assigned PDF 4.
C · correct — Both data and link are explicitly required. See assigned PDF 4.
D · incorrect — C matches the stated two-field structure. See assigned PDF 4.
Question 71
Process of inserting an element in stack is called ____________.
A. Create
B. Push
C. Evaluation
D. Pop
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The module defines push as adding an element to the stack top. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — Create would initialize a structure, not name its insertion operation. See assigned PDF 6.
B · correct — Push adds an element. See assigned PDF 6.
C · incorrect — Evaluation is an application rather than insertion. See assigned PDF 6.
D · incorrect — Pop removes an element. See assigned PDF 6.
Question 72
In a stack, if a user tries to remove an element from empty stack it is called _________.
A. Underflow
B. Empty collection
C. Overflow
D. Garbage Collection
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The stack pop code first tests empty at top==0. Removing from an empty structure is the underflow condition, explicitly named for dequeue and applied here to the same empty-removal failure. Evidence: assigned PDF pages 6, 7.
Evidence in the complete study note
Overflow is an attempted insertion into full storage; underflow is an attempted removal from empty storage. Merely checking isEmpty does not underflow.DSA11
Choice by choice
A · correct — Underflow denotes attempting removal without an available element. See assigned PDF 6, 7.
B · incorrect — Empty collection describes the state rather than the operation failure. See assigned PDF 6, 7.
C · incorrect — Overflow concerns adding to a full structure. See assigned PDF 6, 7.
D · incorrect — Garbage collection concerns reclaiming storage, not empty pop. See assigned PDF 6, 7.
Question 73
Process of removing an element from stack is called __________
A. Create
B. Push
C. Evaluation
D. Pop
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The source names removing an element Pop and adding one Push. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — Create does not remove the stack top. See assigned PDF 6.
B · incorrect — Push adds rather than removes. See assigned PDF 6.
C · incorrect — Evaluation uses stack operations but is not their deletion name. See assigned PDF 6.
D · correct — Pop removes the current top. See assigned PDF 6.
Question 74
A serial-storage interface restricts insertion and removal to the same current end: an item must be removed before any item stored earlier beneath it can be removed. Which ADT matches this restricted access policy?
A. Heap
B. Binary Tree
C. Array
D. Stack
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The restriction makes the latest inserted item the next removable item. That is the stack’s LIFO policy, with both push and pop acting at the top. Serial access alone would not establish this rule, so the same-end removal restriction is stated explicitly. A heap selects by priority, a binary tree supplies branching relationships, and an ordinary array permits indexed access rather than imposing this removal policy.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
ADTs do not force one representation, and serial-access memory is not inherently LIFO.DSA45
Choice by choice
A · incorrect — A heap selects an extreme priority rather than the latest insertion.
B · incorrect — A binary tree supplies hierarchy rather than this same-end policy.
C · incorrect — An array does not inherently impose this removal order.
D · correct — A stack’s push/pop policy matches the specified LIFO restriction.
Question 75
A singly linked queue maintains only its front pointer and owns all its nodes. Emptying means immediately visiting and freeing every node. Which option gives the complete set of listed operations with tight worst-case linear time for n nodes?
A. Insertion
B. Deletion
C. To empty a queue
D. Both Insertion and To empty a queue
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
Correct answer: D — D. Both Insertion and To empty a queue
Enqueue must traverse from the front to find the tail because no rear pointer is maintained. Emptying the owned queue must also visit and release all n nodes under the specified reclamation contract. Deleting one front node requires only a constant number of link and deallocation operations. Therefore both insertion and complete emptying are linear, and the aggregate option D is the complete selection.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Deleting the tail of a singly linked list requires its predecessor, even when tail itself is known. Handle empty and single-node lists separately; after removing the only node, set both head and tail to null. To remove a known successor, bypass it before deallocation. Clearing an owned n-node chain visits and releases every node.DSA09
Choice by choice
A · incorrect — Insertion is linear, but this omits the also-linear emptying operation.
B · incorrect — A single front deletion is constant time.
C · incorrect — Emptying is linear, but this omits insertion.
D · correct — Both insertion and immediate full-node cleanup are linear.
Question 76
A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a ?
A. Queue
B. Stack
C. Tree
D. Linked list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The queue definition makes insertion rear-only and deletion front-only. A linked list can implement that policy, but does not by itself impose the two restrictions. Evidence: assigned PDF pages 7, 6, 4.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · correct — Matches the defined queue interface. See assigned PDF 7, 6, 4.
B · incorrect — Stack uses one common endpoint for both operations. See assigned PDF 7, 6, 4.
C · incorrect — Tree operations are not front/rear list operations. See assigned PDF 7, 6, 4.
D · incorrect — A generic linked list permits operations beyond queue restrictions. See assigned PDF 7, 6, 4.
Question 77
In Breadth First Search of Graph, which of the following data structure is used?
A. Stack
B. Queue
C. Linked list
D. None of the mentioned
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
DSA41 repeatedly dequeues a vertex and enqueues undiscovered neighbors. FIFO service preserves the order of distance layers. Queue is therefore the standard BFS frontier structure. A linked list may store the queue but does not alone define this ordering; a stack chooses latest pending work and instead supports the depth-first discipline.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
Choice by choice
A · incorrect — A stack selects the latest pending vertex and does not maintain breadth-first distance layers.
B · correct — A FIFO queue processes earlier discoveries before later layers, matching standard breadth-first search.
C · incorrect — Linked nodes can store a queue, but linked-list structure alone specifies no BFS frontier policy.
D · incorrect — Queue is offered and directly matches the algorithm given in DSA41.
Question 78
A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?
A. Queue
B. Circular queue
C. Dequeue
D. Priority queue
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Interpret the option spelling Dequeue as deque, the double-ended queue defined on page 8. That structure allows insertion and deletion at either end. Evidence: assigned PDF pages 8, 7.
Evidence in the complete study note
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure.DSA16
Choice by choice
A · incorrect — An ordinary queue restricts insertion and deletion to different fixed ends. See assigned PDF 8, 7.
B · incorrect — Circular storage changes reuse, not the ordinary queue interface. See assigned PDF 8, 7.
C · correct — Deque is explicitly double-ended; the option has a terminology typo. See assigned PDF 8, 7.
D · incorrect — Priority queue chooses service by key, not arbitrary endpoint operations. See assigned PDF 8, 7.
Question 79
Queues serve major role in
A. Simulation of recursion
B. Simulation of arbitrary linked list
C. Simulation of limited resource allocation
D. All of the mentioned
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: C — Simulation of limited resource allocation
The module lists print jobs, disk requests and waiting lines: all allocate a limited resource among waiting requests. Recursion is expressly a stack use, so all is false. Evidence: assigned PDF pages 8, 6.
Evidence in the complete study note
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · incorrect — Recursion is listed under stack applications. See assigned PDF 8, 6.
B · incorrect — Arbitrary linked-list simulation is not a stated queue role. See assigned PDF 8, 6.
C · correct — Waiting requests for shared resources fit the listed applications. See assigned PDF 8, 6.
D · incorrect — A is false, so the conjunction cannot hold. See assigned PDF 8, 6.
Question 80
Which listed service discipline is a stack policy rather than FIFO, a circular FIFO representation, or priority-based queue service? Interpret B as insertion and removal at the same top end.
A. Ordinary queue
B. Single-ended insertion and removal at the same top (LIFO)
C. Circular queue
D. Priority queue
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: B — B. Single-ended insertion and removal at the same top (LIFO)
An ordinary queue serves front elements after rear insertion, while a circular queue changes how its FIFO storage slots are reused. A priority queue chooses according to a priority key. Inserting and removing at the same top end instead gives LIFO stack service. Explicitly defining the formerly vague single-ended phrase makes this a policy distinction rather than an unsupported claim that a particular phrase is forbidden terminology.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
A priority queue returns the smallest or largest priority key under its convention. Urgent patients may precede earlier arrivals. Insertions and extractions can interleave. Binary heaps support constant peek and logarithmic insert/extract.DSA17
Choice by choice
A · incorrect — Ordinary queue service is FIFO.
B · correct — Same-top insertion/removal is LIFO stack service.
C · incorrect — Circular storage can implement FIFO queue service.
D · incorrect — Priority queue service selects by an extreme priority key.
Question 81
Which claims contradict the ordinary unique-key map contract? Select all that apply.
A. Allow duplicate keys
B. Cannot be traversed
C. Allow duplicate values
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): A, B — A. Allow duplicate keys; B. Cannot be traversed
A map associates each unique key with a value. Different keys may share the same value, and its entries can be traversed even when a particular iteration order is not promised. Thus allowing duplicate keys and forbidding all traversal both contradict the contract. Allowing duplicate values does not contradict it. Since contradictory claims exist, the none-of-the-above option is not selected.
Evidence in the complete study note
A map associates unique keys with values; different keys may share values, and entries can be traversed. A set forbids duplicate elements. Null and iteration-order policies depend on implementation. Lists preserve positions and generally allow duplicates; Java LinkedList also permits null.DSA27
Choice by choice
A · correct — Duplicate keys contradict the unique-key map contract.
B · correct — Map entries can be traversed, so this prohibition is false.
C · incorrect — Different keys may share values, making this a valid property.
D · incorrect — A and B do contradict the contract.
Question 82
Consider a set implementation that permits one null element and does not promise an iteration order. Which statement about this implementation is incorrect?
A. Unordered collection
B. Duplicates are not allowed
C. null is not allowed
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
All sets forbid duplicate elements, but null acceptance and iteration order depend on the implementation. The implementation explicitly permits null and promises no iteration order. Under those policies, calling its collection unordered is consistent and rejecting duplicates remains correct. The claim that null is not allowed is the one contradiction. The none-of-the-above alternative fails because that contradictory claim is present.
Evidence in the complete study note
A map associates unique keys with values; different keys may share values, and entries can be traversed. A set forbids duplicate elements. Null and iteration-order policies depend on implementation. Lists preserve positions and generally allow duplicates; Java LinkedList also permits null.DSA27
Choice by choice
A · incorrect — No iteration order is promised under the specified policy.
B · incorrect — Rejecting duplicate elements is the set contract.
C · correct — The stated implementation permits null, contradicting this prohibition.
D · incorrect — C is incorrect, so none-of-the-above fails.
Question 83
Which one of the following is correct about list data structure?
A. Unordered collection
B. Duplicates are not allowed
C. null is not allowed
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: D — None of the above under the ordinary list contract.
DSA27 says lists preserve positions and generally allow duplicates; it also gives Java LinkedList as a list permitting null. Therefore Unordered collection and Duplicates are not allowed misdescribe the ordinary list contract. The universal null prohibition is refuted by the supplied example. None of those statements is a generally correct list property, so D is supported.
Evidence in the complete study note
A map associates unique keys with values; different keys may share values, and entries can be traversed. A set forbids duplicate elements. Null and iteration-order policies depend on implementation. Lists preserve positions and generally allow duplicates; Java LinkedList also permits null.DSA27
Choice by choice
A · incorrect — Lists preserve positions, so calling the ordinary list contract unordered confuses positional order with sortedness.
B · incorrect — Ordinary lists allow repeated elements; duplicate rejection belongs to sets rather than the general list contract.
C · incorrect — Java LinkedList explicitly permits null, refuting a universal null prohibition for list structures.
D · correct — None of the preceding statements describes a generally valid property of the ordinary list contract.
Question 84
In a binary search tree that stores distinct keys with strict left-smaller/right-larger ordering, which statements are true? Select all that apply.
A. Every node has at most two children.
B. The value on left sub tree of the binary search tree can be equal to the root node value.
C. Every node stores a unique key value.
D. All of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): A, C — A. Every node has at most two children.; C. Every node stores a unique key value.
Binary limits a node to at most two children; it does not require every node to have exactly two. The specified distinct-key model also requires uniqueness. Strict subtree ordering places every left-subtree key below its ancestor, so an equal key cannot appear there. A and C consequently hold under the stated model, while B and the all-of-the-above aggregate do not.
Evidence in the complete study note
Binary means at most two children. Full means each node has zero or two children. Complete means all earlier levels are filled and the last fills from left. Perfect means all leaves share a level and every internal node has two children. Balanced means height stays logarithmic under a stated rule; it does not require a perfect shape.DSA18
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
Choice by choice
A · correct — Binary means at most two children per node.
B · incorrect — An equal key violates the specified strict left-subtree ordering.
C · correct — Distinct keys mean every stored key value is unique.
D · incorrect — B is false, so not all preceding statements hold.
Question 85
The operation for adding an item to a stack is named to be___.
A. Push
B. Insert
C. Add
D. enqueue
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The module names the stack addition operation Push. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · correct — Push is the defined stack insertion term. See assigned PDF 6.
B · incorrect — Insert is a generic verb, not the given operation name. See assigned PDF 6.
C · incorrect — Add is descriptive, not the stack-specific name. See assigned PDF 6.
D · incorrect — Enqueue is the queue insertion name. See assigned PDF 6.
Question 86
_____Which operation in stack could result underflow?
A. Push();
B. Is_empty();
C. Pop();
D. B and C
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Only an attempted pop removes an element. When top==0 no element exists, so this removal attempt underflows; checking emptiness does not consume an element. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Overflow is an attempted insertion into full storage; underflow is an attempted removal from empty storage. Merely checking isEmpty does not underflow.DSA11
Choice by choice
A · incorrect — Push can encounter a full stack, not empty-removal underflow. See assigned PDF 6, 6.
B · incorrect — Is_empty only checks state. See assigned PDF 6, 6.
C · correct — Pop attempts removal and can find the stack empty. See assigned PDF 6, 6.
D · incorrect — B does not underflow, so B and C is false. See assigned PDF 6, 6.
Question 87
During ordinary lookup in a binary search tree with distinct keys and strict left-smaller/right-larger ordering, which rule correctly chooses the next subtree or recognizes a match?
A. If the searched key is less than the root, go to left.
B. If the searched key is larger than the root, go to left.
C. If the searched key is equal to the root, go to left.
D. None.
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: A — A. If the searched key is less than the root, go to left.
The BST invariant puts every key in the current node’s left subtree below that node’s key and every right-subtree key above it. A target smaller than the current key must therefore be sought on the left. A larger target belongs on the right, while equality finishes the lookup at the current node. This directional rule relies on BST ordering, not merely on having a binary shape.
Evidence in the complete study note
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
Choice by choice
A · correct — A smaller target follows the left subtree under the BST invariant.
B · incorrect — A larger target follows right, not left.
C · incorrect — Equality is a successful match rather than a reason to continue left.
D · incorrect — A supplies a valid search rule.
Question 88
Which key word is used to de-allocate the space taken by a node?
A. delete
B. alloc()
C. del()
D. A and B
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The deletion section explicitly uses delete temp to release node storage. Evidence: assigned PDF pages 5.
Evidence in the complete study note
A C struct groups named fields, including arrays and pointers. A singly linked node needs payload plus a same-type link. C fields cannot have initializers inside the type declaration; modern C++ permits default member initializers. In C++, match new with delete and new[] with delete[]. Repair links before freeing a node; never dereference it afterwards.DSA03
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++.DSA09
Choice by choice
A · correct — delete releases the pointed-to memory. See assigned PDF 5.
B · incorrect — alloc is not the given C++ deallocation keyword. See assigned PDF 5.
C · incorrect — del is not the module keyword. See assigned PDF 5.
D · incorrect — B is not the prescribed deallocation instruction. See assigned PDF 5.
Question 89
Which one is easier to perform?
A. Deleting a leaf node
B. Deleting internal node
C. deleting root node
D. A and B
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The module calls leaf deletion simple and straightforward: detach its parent link. Internal and root deletion can need child promotion or copying. Evidence: assigned PDF pages 10.
Evidence in the complete study note
A leaf can be detached by clearing its parent link. For one child, make the parent bypass the node and point to the child. For two children, copy the inorder predecessor (left-subtree maximum) or successor (right-subtree minimum), then delete that replacement from its original location. That second deletion has at most one child.DSA21
Choice by choice
A · correct — A leaf has no descendant subtree to reconnect. See assigned PDF 10.
B · incorrect — An internal node can require preserving one or two child subtrees. See assigned PDF 10.
C · incorrect — Root deletion may require choosing and reconnecting a replacement. See assigned PDF 10.
D · incorrect — Internal deletion is not always as simple as leaf deletion. See assigned PDF 10.
Question 90
Algorithms must terminate after a finite number of steps; What is this characteristics
called__
A. Unambiguous
B. Feasibility
C. Finiteness
D. Independent
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The algorithm criteria expressly name termination after a finite number of steps Finiteness. Evidence: assigned PDF pages 2.
Evidence in the complete study note
Finiteness means termination after finitely many steps for every valid input. Definiteness means each instruction has one interpretation; effectiveness means each step is executable. Correctness means meeting the stated result for every valid input. A finite program can still return the wrong answer.DSA04
Choice by choice
A · incorrect — Unambiguous describes definiteness of each instruction. See assigned PDF 2.
B · incorrect — Feasibility is not the term attached to termination here. See assigned PDF 2.
C · correct — Finiteness is the named finite-termination criterion. See assigned PDF 2.
D · incorrect — Independent does not name finite termination. See assigned PDF 2.
Question 91
Which listed structures are linear data structures in the course classification? Select all that apply.
A. Tree
B. Array
C. Queue
D. Linked list
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): B, C, D — B. Array; C. Queue; D. Linked list
Arrays, queues and linked lists arrange their items as linear sequences in this classification. A tree instead models hierarchical branching and is classified as nonlinear. Thus three offered structures meet the question’s category. The stray extraction characters before Queue are removed so the option states the structure’s name clearly, and the select-all instruction accounts for every valid member of the category.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · incorrect — A tree is hierarchical rather than linear.
B · correct — An array is a linear structure.
C · correct — A queue is a linear structure.
D · correct — A linked list is a linear structure.
Question 92
Which abbreviations describe stack service order? Select all that apply.
A. LIFO
B. FIFO
C. FILO
D. FCFS
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answers (select all): A, C — A. LIFO; C. FILO
A stack removes the latest inserted item first, described as last in, first out or LIFO. The equivalent view says that the first inserted item leaves last, described as first in, last out or FILO. Both abbreviations name the same policy. FIFO and FCFS instead serve earlier arrivals before later ones and describe the ordinary queue discipline rather than the stack discipline.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
This is FIFO or first-come, first-served.DSA14
Choice by choice
A · correct — LIFO means last in, first out.
B · incorrect — FIFO is the ordinary queue discipline.
C · correct — FILO is equivalent to LIFO.
D · incorrect — FCFS serves arrivals in queue order.
Question 93
In singly linked list, the node contains
A. Data and index
B. Data and one pointer ( the next node)
C. Only data
D. Data and two pointers
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: B — Data and one pointer ( the next node)
The singly linked node contains a data payload and a single pointer to the next node. Evidence: assigned PDF pages 4.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · incorrect — An index is not the described next-pointer field. See assigned PDF 4.
B · correct — Both required components are present. See assigned PDF 4.
C · incorrect — Payload alone cannot connect the chain. See assigned PDF 4.
D · incorrect — Two pointers describe a different representation, not the supplied single-link node. See assigned PDF 4.
Question 94
Which data structure follows LIFO principle?
A. Graphs
B. Queues
C. Stacks
D. Trees
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Stack removes its most recently inserted top, exactly LIFO. Evidence: assigned PDF pages 6, 7, 2.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — A graph structure does not prescribe a last-in deletion order. See assigned PDF 6, 7, 2.
B · incorrect — Queue is FIFO. See assigned PDF 6, 7, 2.
C · correct — Stack is expressly LIFO. See assigned PDF 6, 7, 2.
D · incorrect — A tree hierarchy does not impose stack order. See assigned PDF 6, 7, 2.
Question 95
The time complexity for binary search is
A. O(n*log(n )2)
B. O(n2)
C. ¢.
O(n)
D. O(logn)
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
The source states search time proportional to log2 n; repeated midpoint selection halves the remaining ordered interval. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · incorrect — n times a logarithmic factor is not the tight single-search bound. See assigned PDF 3.
B · incorrect — Quadratic does not describe a halving path. See assigned PDF 3.
C · incorrect — Linear is sequential-search growth. See assigned PDF 3.
D · correct — Logarithmic matches the binary-search statement. See assigned PDF 3.
Question 96
Which sorting algorithm compares each pair of adjacent elements from the beginning of
an array and, if they are in reversed order, swaps them; if at least one swaps has been
done, repeat step 1.
A. Insertion sort
B. Bubble sort
C. .
Selection sort
D. Shell sort
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The stem describes complete adjacent-pair passes and repeats if swaps occur. That is bubble sort with a no-swap stopping test. Evidence: assigned PDF pages 4, 3.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Choice by choice
A · incorrect — Insertion places a new item in the sorted prefix. See assigned PDF 4, 3, 3.
B · correct — Bubble compares and exchanges adjacent out-of-order entries across passes. See assigned PDF 4, 3, 3.
C · incorrect — Selection searches for a minimum rather than exchanging every reversed adjacent pair. See assigned PDF 4, 3, 3.
D · incorrect — Shell first uses gap-separated subsequences, unlike these adjacent passes. See assigned PDF 4, 3, 3.
Question 97
Among the following one is NOT the application of queue in the real world.
A. It is used in operating systems for handling interrupts.
B. It is used to maintain the play list in media players in order
C. .
It is used in Depth First search
D. It is widely used as waiting lists for a single shared resource
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Correct answer: C — Depth-first search uses a stack rather than the ordinary FIFO queue.
DSA14 gives FIFO waiting, asynchronous buffers, and play sequences as queue uses. DSA42 explicitly contrasts DFS stack or recursion with a queue, which would change the discipline. Pending interrupts can be buffered for processing; this does not mean every interrupt policy must be FIFO. Standard depth-first search is the listed application that requires latest-pending-work service instead.
Evidence in the complete study note
An interrupt service routine may need to record work quickly and defer its completion. Operating systems can queue that deferred work for later processing; Windows deferred procedure calls are one concrete example. This is a queue application, but it does not imply that every interrupt system uses a single FIFO service policy.DSA-S02
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · incorrect — Pending interrupt work can be queued for handling; the claim does not require every interrupt policy to be FIFO.
B · incorrect — A queue can preserve a play sequence in arrival order, as noted in DSA14.
C · correct — Standard DFS uses a stack or recursion to finish a branch before returning, not a FIFO frontier.
D · incorrect — First-come shared-resource waiting is a direct FIFO queue application described in DSA14.
Question 98
An airline has a fixed finite seat layout, and each seat number maps directly to a dense integer position. Which listed representation gives constant-time lookup of that seat’s reservation record under the usual RAM model?
A. Array
B. Linked List
C. Queue
D. Stack
Hint / Module Reference (Where to Read)
Fix the input case and cost model, then count dominant work or simultaneously live storage.
The explicit seat-number mapping turns each lookup into an indexed-position query over a fixed finite layout. An array can compute the corresponding element address directly, giving constant-time access in the note’s RAM model. An ordinary linked list must traverse to a position, while queues and stacks expose service endpoints rather than arbitrary seat lookup. This models seat records themselves, rather than a queue of waiting reservation requests.
Evidence in the complete study note
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing. This arithmetic gives constant-time positional access in the usual RAM cost model. A row-major rectangular matrix uses base + (row × columns + column) × element_size.DSA02
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · correct — Direct seat-position indexing gives constant-time array lookup.
B · incorrect — An ordinary linked list needs positional traversal.
C · incorrect — A queue exposes front/rear service, not direct seat lookup.
D · incorrect — A stack exposes its top rather than arbitrary seat positions.
Question 99
Which notation writes binary arithmetic operators between their operands and uses precedence and parentheses, as in ordinary written arithmetic?
A. Infix notation
B. Prefix notation
C. Postfix notation
D. None of the above
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
Infix notation places each binary operator between its two operands, using precedence rules and parentheses to establish grouping. Prefix puts the operator before its operands, and postfix puts it after them. The criterion asks for that objective familiar arithmetic layout rather than a universal claim about personal comfort. Since A names the between-operands form, the none-of-the-above alternative does not apply.
Evidence in the complete study note
Infix places an operator between operands and uses precedence and parentheses. Prefix places it first; postfix places it last. Their fixed operator arity determines grouping. To convert infix to postfix, output operands immediately and hold operators on a stack. Pop higher-precedence operators before pushing a new operator; also pop equal precedence for left-associative operators. Parentheses temporarily override this order.DSA13
Choice by choice
A · correct — Infix places the operator between operands.
B · incorrect — Prefix puts the operator before its operands.
C · incorrect — Postfix puts the operator after its operands.
D · incorrect — Infix satisfies the specified layout.
Question 100
Which option is outside the three standard named depth-first visitation orders for binary trees in this course? This asks about those standard order names, not whether other traversal algorithms can exist.
A. Randomized traversal
B. Preorder traversal
C. Postorder traversal
D. Inorder traversal
Hint / Module Reference (Where to Read)
Compare the required access order and representation constraints with the defining operations of each option.
The three standard named orders are preorder, inorder and postorder, determined respectively by visiting the node before, between or after its two child subtrees. Randomized visitation can be implemented, but it is not one of these three conventional names. Thus Randomized traversal is the correct exclusion under the explicit classification. The question no longer claims that such a traversal is impossible or never used.
Evidence in the complete study note
Preorder visits node,left,right; inorder left,node,right; postorder left,right,node. Apply recursively; null children do nothing. Inorder returns sorted keys only for a BST. Preorder supports copying, postorder supports deleting children before parents, and level order uses a FIFO queue.DSA20
Choice by choice
A · correct — Randomized visitation is possible but is not one of the three standard named orders being classified.
B · incorrect — Preorder is one of the standard orders.
C · incorrect — Postorder is one of the standard orders.
D · incorrect — Inorder is one of the standard orders.
Question 101
Which of the following principles does Queue use?
A. LIFO principle
B. FIFO principle
C. Linear tree
D. Ordered array
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Insertion at rear and deletion at front preserve arrival order, which the source calls FIFO. Evidence: assigned PDF pages 7.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — LIFO is the stack policy. See assigned PDF 7.
B · correct — FIFO is explicitly named for queues. See assigned PDF 7.
C · incorrect — Linear tree is not an ordering policy. See assigned PDF 7.
D · incorrect — Ordered array describes neither the queue service rule nor all its representations. See assigned PDF 7.
Question 102
In this course’s standard ADT vocabulary, which structure calls insertion at its top push and removal from that same top pop?
A. Queue
B. Stack
C. Both
D. None
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The stack contract inserts and removes at one top. Its standard operations are push for insertion and pop for removal, with peek observing the top without removing it. The ordinary queue contract instead enqueues at the rear and dequeues at the front. The question fixes this conceptual vocabulary rather than comparing method names chosen by particular programming libraries, making Stack the definite selection.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
An ordinary queue enqueues at rear, dequeues at front, and peeks at front.DSA14
Choice by choice
A · incorrect — The standard queue vocabulary is enqueue/dequeue at different endpoints.
B · correct — Push and pop name the standard stack-top operations.
C · incorrect — Both would incorrectly include the queue under the specified vocabulary.
D · incorrect — Stack is present and matches the stated operations.
Question 103
Which task requires FIFO service rather than the LIFO service of a stack used as the sole pending-item ADT? In D, asynchronous transfer must deliver buffered items in arrival order.
A. String reversal
B. Recursion
C. Backtracking
D. Asynchronous buffered transfer with mandatory arrival-order delivery
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: D — D. Asynchronous buffered transfer with mandatory arrival-order delivery
Stacks support reversal by popping items in reverse insertion order. They also manage nested recursive calls and backtracking through the most recent pending context or choice. The stated asynchronous-transfer contract instead requires older buffered items to be delivered before newer arrivals. That is FIFO service, so an ordinary queue supplies the needed ordering. A single stack’s LIFO removal rule does not meet this explicitly ordered buffering contract.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Choice by choice
A · incorrect — Reversal uses the stack’s reverse insertion order.
B · incorrect — Nested recursive calls return most-recent-first.
C · incorrect — Backtracking resumes the latest pending choice.
D · correct — Arrival-order delivery requires FIFO rather than a single stack’s LIFO.
Question 104
For an unordered symbol table with no range queries, assume suitable hashing and bounded load factor. Which listed ordinary representation offers expected constant-time lookup, compared with linear list search and logarithmic balanced-tree search?
A. Self-organizing list
B. Hash table
C. Balanced search tree
D. Linear list scan
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Symbol tables can use hashing for expected constant lookup when hashing spreads keys suitably and load remains bounded. Balanced search trees supply logarithmic lookup and ordering, while list search can require a linear scan. The comparison concerns the expected lookup growth under those assumptions, not an unconditional worst-case minimum. Collision-heavy hash inputs can still take linear time outside that expected analysis.
Evidence in the complete study note
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.DSA27
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
Choice by choice
A · incorrect — Ordinary self-organizing list search does not guarantee the stated general expected bound.
B · correct — Suitable hashing with bounded load provides expected constant lookup.
C · incorrect — A balanced search tree has logarithmic lookup.
D · incorrect — A linear list scan takes linear worst-case lookup.
Question 105
In the linked list implementation of a queue, where will the new element be
inserted?
A. At the middle position of the linked list.
B. At the head position of the linked list.
C. At the tail position of the linked list.
D. None of the above.
Hint / Module Reference (Where to Read)
Trace the initial state and update only the fields affected by each permitted operation.
Correct answer: C — At the tail position of the linked list.
The linked queue implementation expressly inserts a node at the end and removes the first node. End means tail. Evidence: assigned PDF pages 8.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — Middle insertion would break the specified FIFO insertion rule. See assigned PDF 8.
B · incorrect — Head insertion is the removal end in this representation. See assigned PDF 8.
C · correct — New nodes are inserted at the linked-list end/tail. See assigned PDF 8.
D · incorrect — C matches the implementation. See assigned PDF 8.
Question 106
What is the maximum number of children that a node can have in a binary
tree?
A. 3
B. 1
C. 4
D. 2
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
A binary tree has at most two children per node, named left and right. Maximum is therefore two. Evidence: assigned PDF pages 9.
Evidence in the complete study note
Binary means at most two children. Full means each node has zero or two children. Complete means all earlier levels are filled and the last fills from left. Perfect means all leaves share a level and every internal node has two children. Balanced means height stays logarithmic under a stated rule; it does not require a perfect shape.DSA18
Choice by choice
A · incorrect — Three exceeds the binary limit. See assigned PDF 9.
B · incorrect — One is permitted but is not the maximum. See assigned PDF 9.
C · incorrect — Four exceeds the binary limit. See assigned PDF 9.
D · correct — Two equals the specified maximum. See assigned PDF 9.
Question 107
DAG is an abbreviation of?
A. Detecting Acyclic Graph
B. Data Acyclic Graph
C. Dynamic Acyclic Graph
D. Directed Acyclic Graph
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
DSA40 directly expands DAG to directed acyclic graph. Directed specifies that each edge has an orientation, and acyclic excludes directed cycles. Detecting, Data, and Dynamic do not supply the defined first word. This is a vocabulary question and does not depend on graph representation or a particular traversal algorithm.
Evidence in the complete study note
A graph has vertices V and edges E. Directed edges distinguish u→v from v→u; undirected edges represent two-way relationships. Following accounts is directed; a mutual friendship relation is undirected. Weighted edges carry costs; unweighted shortest-path questions count edges. DAG expands to directed acyclic graph. Trees are connected acyclic graphs, although graph data structures may also contain cycles.DSA40
Choice by choice
A · incorrect — Detecting is not the first word in the defined expansion of DAG.
B · incorrect — Data is not the first word in the defined graph-theoretic abbreviation DAG.
C · incorrect — Dynamic is not the first word of DAG as defined in DSA40.
D · correct — Directed Acyclic Graph is the exact expansion explicitly given in the complete note.
Question 108
A binary search tree was built by inserting the following numbers in the given order: 40, 20, 50, 10, 30, 60. Which of the following statements are true?
A. 30 is the left child of 40
B. the tree is a heap
C. height of the tree is 3
D. 50 is the right child of 40
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Insertions give root 40; its children 20 and 50; 20 has children 10 and 30; 50 has right child 60. The deepest depth is two edges. A max heap is impossible because child 50 exceeds root 40. Evidence: assigned PDF pages 9, 11.
Evidence in the complete study note
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
Choice by choice
A · incorrect — 30 is the right child of 20, not the left child of 40. See assigned PDF 9, 9, 9, 11.
B · incorrect — 50 exceeds its parent 40, violating the module max-heap rule. See assigned PDF 9, 9, 9, 11.
C · incorrect — Height is depth two, not the three-level count. See assigned PDF 9, 9, 9, 11.
D · correct — 50 is larger than 40 and becomes its right child. See assigned PDF 9, 9, 9, 11.
Question 109
Certain operations on lists can be performed faster when the list is sorted than not. Which of the following could be an example of such an operation?
A. Searching for an element of a list
B. Computing the variance of a list
C. Computing the average of a list
D. All can be performed faster when the list is sorted.
E. Counting for the number of odd numbers in a list
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: A — Searching for an element of a list
Sortedness permits logarithmic binary search instead of a linear scan. Sorting alone does not remove the need to inspect all values for mean, variance or arbitrary parity counts. Evidence: assigned PDF pages 3.
Evidence in the complete study note
For a single unsorted query, sorting first is rarely justified. Small lists may favour scanning because setup matters. Sorting does not avoid examining all values for mean, variance or arbitrary parity counts.DSA28
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Choice by choice
A · correct — Binary searching uses sorted order to discard half the list at each step. See assigned PDF 3, 3.
B · incorrect — Variance still depends on all values, without extra aggregates. See assigned PDF 3, 3.
C · incorrect — Average still depends on all values, without a stored sum. See assigned PDF 3, 3.
D · incorrect — The statistical computations are not accelerated solely by ordering. See assigned PDF 3, 3.
E · incorrect — Odd and even values are not a monotone split in numeric sorted order. See assigned PDF 3, 3.
Question 110
For the values 5 3 8 9 1 7 0 2 6 4, which offered arrays satisfy the final-pivot partition condition for pivot 5: all smaller values precede it and all larger values follow it? Do not require a particular partition algorithm or internal ordering. Select all that apply.
A. 3 1 0 2 4 5 8 9 7 6
B. None of the choices are correct
C. 4 2 3 0 1 5 7 9 6 8
D. 0 3 4 2 1 5 7 9 6 8
E. 3 1 0 2 4 5 8 9 6 7
F. 5 3 4 2 1 0 7 9 6 8
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, C, D, E — A. 3 1 0 2 4 5 8 9 7 6; C. 4 2 3 0 1 5 7 9 6 8; D. 0 3 4 2 1 5 7 9 6 8; E. 3 1 0 2 4 5 8 9 6 7
There are five values below 5 and four values above it, so a final-position pivot must occupy index five in zero-based order. A, C, D and E each place precisely the smaller group before that pivot and the larger group after it. Their internal subgroup orders need not agree because only the partition invariant is requested. F leaves smaller values after an initial pivot and fails the condition.
Evidence in the complete study note
In the ten-distinct-value example, a final pivot 5 has five smaller values before it and four larger after it. Internal orders depend on the partition algorithm; several candidate arrays can satisfy the invariant. State the algorithm before predicting one exact array. Quicksort normally rearranges in the same array but recursive storage can be linear in the worst case.DSA36
Choice by choice
A · correct — All five smaller values precede 5 and all larger ones follow.
B · incorrect — Several offered arrays satisfy the condition.
C · correct — This array satisfies the smaller/pivot/larger grouping.
D · correct — This array also satisfies the grouping despite different internal order.
E · correct — The right-side permutation does not violate the grouping.
F · incorrect — Smaller values after the leading 5 violate its final-position condition.
Question 111
An owning dynamically allocated linked-list API must provide item search, insertion and removal. Removal unlinks and frees its node before returning; it returns any needed payload by value. Which additional function is unnecessary and would violate the contract if its result were dereferenced?
A. A function that returns a pointer to an already freed node for later dereferencing
B. A function that searches for an item from the list
C. A function that inserts an item in the list
D. A function that removes an item from the list
E. None of the choices is correct
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: A — A. A function that returns a pointer to an already freed node for later dereferencing
The API explicitly requires search, insertion and removal, so those operations belong in its interface. Its removal contract frees the node before returning, leaving that node’s storage unavailable for later dereference. An additional function promising a usable pointer to the freed node is therefore inappropriate. Returning a copied payload is different and remains allowed; the distinction concerns storage lifetime rather than whether deletion may report a value.
Evidence in the complete study note
A C struct groups named fields, including arrays and pointers. A singly linked node needs payload plus a same-type link. C fields cannot have initializers inside the type declaration; modern C++ permits default member initializers. In C++, match new with delete and new[] with delete[]. Repair links before freeing a node; never dereference it afterwards.DSA03
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++.DSA09
Choice by choice
A · correct — A usable pointer to a freed node violates the stated lifetime contract.
B · incorrect — Item search is explicitly required by this API.
C · incorrect — Item insertion is explicitly required by this API.
D · incorrect — Item removal is explicitly required by this API.
E · incorrect — A identifies an inappropriate extra function.
Question 112
Consider a max-heap of n>=3 distinct keys, stored in ordinary level-order array form. Its binary tree is full: every internal node has two children. Which statement is false?
A. The root is the biggest element.
B. The second biggest element is necessarily found at depth 1 (root is at depth 0)
C. The search for the smallest element can be accomplished in O(log n) time (worst case)
D. The last element of the array is necessarily the right most child on the lowest level.
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: C — C is false: finding the minimum can require Theta(n) time.
The root contains the maximum key. With distinct keys, the second largest must be one of its children, since a deeper key has a larger ancestor above it. Completeness places the final occupied array slot at the rightmost occupied position of the lowest level. The minimum can occur at any leaf, however, so finding it may require a linear scan rather than logarithmic worst-case time. C is therefore false.
Evidence in the complete study note
A binary max-heap is complete with each parent at least its children; a min-heap reverses this order. Unlike BSTs, heaps do not order entire subtrees. The root is maximum. If all keys are distinct, the second largest is a root child. With duplicate maxima, the second largest distinct value may be deeper: [9,9,9,8,7,6,5] is a valid max-heap and that value is 8 at index 3. The minimum may be any leaf, requiring linear worst-case scanning.DSA23
Complete means all earlier levels are filled and the last fills from left.DSA18
Choice by choice
A · incorrect — The max-heap order makes the root the largest key, so this is true rather than the requested false statement.
B · incorrect — Distinct keys ensure the second largest is a root child, so this is true.
C · correct — The minimum may require scanning linearly many leaves; the logarithmic worst-case claim is false.
D · incorrect — Level-order storage of a complete heap ends at the rightmost occupied position on the lowest level.
Question 113
For ordinary top-down array mergesort on n=8 items with left-first ties and no merge-skipping, which description alone guarantees the maximum possible number of key comparisons across the merges?
A. When the list is initially sorted in the "reverse" order
B. When the list is already sorted in the "right" order
C. When the list contains all similar elements
D. When the list contains all distinct elements
E. None of the choices is correct
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: E — E. None of the choices is correct
Maximum merge comparisons depend on the interleaving of the sorted runs, rather than merely on a broad input label. Sorted or reverse-sorted input produces separated runs, and equal keys let left-first merging exhaust a run early. Distinct keys permit a worst interleaving but do not force one; already sorted distinct keys are a counterexample. None of A–D therefore guarantees the requested exact maximum.
Evidence in the complete study note
Split into halves, sort them, then merge by advancing the smaller current front. With left-first tie handling, equal keys retain order. Ordinary array merging needs a linear auxiliary buffer. There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Reverse order alone does not characterize maximum merge comparisons.DSA37
Choice by choice
A · incorrect — Reverse order alone does not force worst interleavings.
B · incorrect — Sorted runs can be merged with an early exhaustion of one side.
C · incorrect — Left-first equal keys exhaust a run without maximum interleaving.
D · incorrect — Distinct keys can already be sorted, so distinctness is insufficient.
E · correct — No preceding description alone guarantees the exact maximum comparison count.
Question 114
If a sorted list contains 100 elements, what is the maximum number of comparisons to make to search for an element using binary searching algorithm?
A. None of the choices are correct
B. 100
C. 10
D. 7
E. 50
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
With one midpoint-key comparison per visited node, the maximum probes are floor(log2 100)+1=7, since 64<=100<128. Equivalently seven binary levels can distinguish up to 127 keys. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Choice by choice
A · incorrect — Seven is present as D. See assigned PDF 3.
B · incorrect — 100 is a complete linear scan. See assigned PDF 3.
C · incorrect — 10 exceeds the needed halving depth. See assigned PDF 3.
D · correct — Seven midpoint probes suffice in the worst case. See assigned PDF 3.
E · incorrect — 50 counts only the first halving, not the number of probes. See assigned PDF 3.
Question 115
For ordinary representations without an extra positional index, which listed structure guarantees O(1) worst-case access to an arbitrary valid logical position as its length grows? Use fixed-size elements and unit-cost address arithmetic.
A. Singly linked list
B. Doubly linked list
C. Every listed linked structure guarantees constant-time access to an arbitrary logical position.
D. Circular linked list
E. Array
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
An array computes an element address from its base address, the requested index and the fixed element size, giving constant-time access. Ordinary singly, doubly and circular linked lists instead follow links to reach a logical position; even starting from the nearer endpoint leaves linear worst-case traversal. The replacement aggregate claim is false because those linked structures lack a direct positional index. Array is therefore the unique matching choice.
Evidence in the complete study note
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing. This arithmetic gives constant-time positional access in the usual RAM cost model.DSA02
An array-linked list still follows links unless separately position-indexed.DSA08
Finding a position is still linear.DSA10
Choice by choice
A · incorrect — A singly linked list may traverse linearly many successor links.
B · incorrect — A doubly linked list still has linear worst-case access to middle positions.
C · incorrect — The listed linked structures do not all have constant-time arbitrary positional lookup.
D · incorrect — Circularity changes how a chain ends, not how a logical position is located.
E · correct — An array computes the address directly with fixed-size element arithmetic.
Question 116
Which listed representations guarantee O(log n) worst-case arbitrary-key lookup under these implementations? Use a height-balanced BST for A, an ordinary singly linked list for C, an ordinary binary heap for D, and a sorted random-access array with binary search for E. Select all that apply.
A. Height-balanced BST
B. A and C
C. Singly linked list
D. Heap
E. Sorted random-access array with binary search
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, E — A. Height-balanced BST; E. Sorted random-access array with binary search
A height-balanced BST has logarithmic height, so following its ordered search path takes logarithmic worst-case time. A sorted random-access array supports logarithmic binary-search probes. An ordinary singly linked list must traverse links, and a heap does not order entire subtrees by arbitrary search keys. Thus the combined A-and-C claim fails because C lacks the guarantee, while A and E independently meet it.
Evidence in the complete study note
Search compares at each node and follows one child until equality or null. Insertion uses that same path to attach a new leaf. Operations cost O(height): logarithmic for balanced trees, linear for a chain. Best-case successful search is Theta(1), a root hit. An optimal BST minimizes expected search cost using access probabilities; constructing it is a different problem from searching it.DSA19
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Unlike BSTs, heaps do not order entire subtrees.DSA23
Choice by choice
A · correct — Balance bounds the BST search path logarithmically.
B · incorrect — C lacks the logarithmic guarantee, so A and C is false.
C · incorrect — Singly linked lookup may scan all nodes.
D · incorrect — Heap order privileges the extreme but not arbitrary-key lookup.
E · correct — Binary search on a sorted random-access array is logarithmic.
Question 117
A queue is a ?
A. FIFO (First In First Out) list
B. LIFO (Last In First Out) list
C. Ordered array
D. Linear tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: A — FIFO (First In First Out) list
The source expressly calls queues First in First out lists. Evidence: assigned PDF pages 7.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · correct — FIFO preserves arrival order. See assigned PDF 7.
B · incorrect — LIFO names a stack. See assigned PDF 7.
C · incorrect — An ordered array is one possible storage form, not the abstract queue rule. See assigned PDF 7.
D · incorrect — Linear tree is not the source queue definition. See assigned PDF 7.
Question 118
What is an internal sorting algorithm?
A. Algorithm that uses tape or disk during the sort
B. Algorithm that uses main memory during the sort
C. Algorithm that involves swapping
D. Algorithm that are considered 'in place'
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: B — Sorting whose working dataset fits in main memory.
DSA37 defines internal sorting by fitting the working dataset in memory. Option B expresses that main-memory setting. In contrast, external sorting handles disk-backed runs when data exceeds memory. Swapping is an operation used by some algorithms, and in-place describes auxiliary storage; neither determines whether a sort is internal.
Evidence in the complete study note
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively. In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant. Internal sorting fits the working dataset in memory. External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.DSA37
Choice by choice
A · incorrect — Tape or disk working data characterizes external sorting rather than the main-memory internal setting.
B · correct — Internal sorting keeps its working dataset in main memory, matching the definition in DSA37.
C · incorrect — Swapping is an implementation operation and does not define the location of the working dataset.
D · incorrect — In-place concerns auxiliary element storage; an internal sort may still use a separate memory buffer.
Question 119
What is the time complexity order of binary searching algorithm?
A. O(n^3)
B. O(n)
C. O(log n)
D. O(1)
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The stated time is proportional to log2 n because each midpoint decision discards half the remaining ordered interval. Evidence: assigned PDF pages 3.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Choice by choice
A · incorrect — Cubic does not match repeated halving. See assigned PDF 3.
B · incorrect — Linear is the source sequential-search order. See assigned PDF 3.
C · correct — Logarithmic is the explicit binary-search order. See assigned PDF 3.
D · incorrect — Constant time occurs for an immediate match, not a general search bound. See assigned PDF 3.
Question 120
What is the tightest listed worst-case time bound for ordinary quicksort when each partition may choose an extreme pivot?
A. O(n)
B. O(n^2)
C. O(2^n)
D. O(n log n)
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
An extreme pivot leaves one empty part and one part with only a single element removed. Repeating that pattern makes partition work proportional to n+(n-1)+… rather than distributing it across balanced levels. The sum is quadratic. Balanced partitions explain the n log n alternative, but they are not guaranteed in this worst case. Exponential time is a looser upper bound, not the tightest listed one.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Choice by choice
A · incorrect — Linear time does not cover repeated partition scans.
B · correct — Repeated extreme pivots produce quadratic total work.
C · incorrect — Exponential is a much looser upper bound.
D · incorrect — n log n requires suitably balanced or expected partitions.
Question 121
Under universal hashing, one random family member is chosen for a table independently of a fixed key set. Which claims are false? Interpret C as an unconditional superiority claim. Select all that apply.
A. In universal hashing a hash function is selected randomly from a set of hash functions for each key
B. In universal hashing a hash function is selected from a set of hash functions independent of keys
C. A single fixed hash function is always better than universal hashing at reducing collisions.
D. Universal hashing controls collision probability without guaranteeing zero collisions.
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, C — A. In universal hashing a hash function is selected randomly from a set of hash functions for each key; C. A single fixed hash function is always better than universal hashing at reducing collisions.
Universal hashing chooses one random function for the table and then uses it consistently, rather than selecting an unrelated function afresh for each key. Its purpose is to control collision probability for a fixed key set. It does not establish that a single fixed function is always better for avoiding collisions. Thus A and C are false, while independent table-level choice and probability control are the valid principles.
Evidence in the complete study note
Determinism means repeated equal keys get the same address for the chosen function. Uniformity means expected keys spread evenly. Universal hashing chooses one function randomly from a suitable family for the table, independently of a fixed key set; it does not choose a fresh unrelated function for each lookup. Random choice controls collision probability, not a promise of zero collisions.DSA25
Choice by choice
A · correct — The chosen function is reused for the table rather than chosen afresh per key.
B · incorrect — Independence from the fixed key set is the stated selection principle.
C · correct — Unconditional fixed-function superiority does not follow and contradicts the randomized collision-control purpose.
D · incorrect — Universal choice controls collision probability without promising no collisions.
Question 122
In a tree data structure, if a node has no parent node, then the node is _______.
A. Parent node
B. Root node
C. External node
D. Internal node
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The module defines root as a node without a parent, whereas leaves have no child and internal nodes have children. Evidence: assigned PDF pages 9.
Evidence in the complete study note
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
Choice by choice
A · incorrect — Parent describes a relation to a child, not the absence of a parent. See assigned PDF 9.
B · correct — Root is explicitly the parentless node. See assigned PDF 9.
C · incorrect — External nodes are defined by having no child. See assigned PDF 9.
D · incorrect — Internal nodes have at least one child, which does not imply parentlessness. See assigned PDF 9.
Question 123
Linked list data structure is ____________ type of data structure.
A. Non-linear data structure
B. Fixed size data structure
C. Static data structure
D. Dynamic data structure
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Linked nodes are created using new and the module labels linked-list memory dynamic. The size is not fixed by a static array declaration. Evidence: assigned PDF pages 5, 6.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · incorrect — The supplied single linked list forms a linear chain. See assigned PDF 5, 6.
B · incorrect — New nodes can be added at runtime, so size is not intrinsically fixed. See assigned PDF 5, 6.
C · incorrect — Static describes the source array implementation. See assigned PDF 5, 6.
D · correct — Dynamic allocation is the linked representation given. See assigned PDF 5, 6.
Question 124
Assume there is a line of patients waiting for service from a clinic. Seriously sick patients
should get service first. Which data structure is the most appropriate for this real-world problem?
A. Tree
B. Queue
C. Stack
D. Priority Queue
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Give each patient a key representing medical urgency and serve by that priority. This adapts the module associated-key priority queue to the stated urgency rule. Evidence: assigned PDF pages 8, 7.
Evidence in the complete study note
A priority queue returns the smallest or largest priority key under its convention. Urgent patients may precede earlier arrivals. Insertions and extractions can interleave. Binary heaps support constant peek and logarithmic insert/extract.DSA17
Choice by choice
A · incorrect — A tree alone does not define urgency-based service. See assigned PDF 8, 7.
B · incorrect — A plain FIFO queue serves arrival order rather than illness severity. See assigned PDF 8, 7.
C · incorrect — A stack gives recent arrivals precedence, regardless of severity. See assigned PDF 8, 7.
D · correct — Associated priority keys represent how urgently each patient needs service. See assigned PDF 8, 7.
Question 125
For an input graph, Depth First Traversal (DFT) algorithm uses ________ data structure to
traverse.
A. Priority queue
B. Tree
C. Queue
D. Stack
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
DSA42 says DFS recursively explores an unvisited neighbor to completion before returning. The recursive call stack stores return points; an explicit stack can store pending work instead. Both implement latest-pending-work-first order. A queue would change that discipline, while a priority queue or tree alone does not encode the required depth-first frontier behavior.
Evidence in the complete study note
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · incorrect — Priority service follows priority keys and does not guarantee finishing the latest active branch first.
B · incorrect — A tree may represent traversal results, but it does not identify the standard DFS pending-work discipline.
C · incorrect — FIFO queue order produces breadth-first pending work rather than the required latest-pending-work behavior.
D · correct — A stack, explicit or supplied by recursion, preserves return points and latest-pending-work-first order.
Question 126
Which statement is true about the pop() operation of Stack data structures?
A. pop() returns the end/top element but it doesn't delete that element
B. pop() removes the end/top element from the stack
C. pop() inserts a new element at the middle of stack
D. pop() inserts a new element at the beginning/bottom of stack
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: B — pop() removes the end/top element from the stack
The pop pseudocode reads the current top and decrements top, so the element is logically removed. Merely inspecting without deletion is peek. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — This describes peek, not pop. See assigned PDF 6, 6.
B · correct — Pop removes the current top by decreasing top. See assigned PDF 6, 6.
C · incorrect — Pop does not insert, and stack insertion is only at top. See assigned PDF 6, 6.
D · incorrect — Pop is removal, not bottom insertion. See assigned PDF 6, 6.
Question 127
A singly linked list of n nodes maintains only its head; there is no tail pointer or index. Appending traverses to the last node before linking a new node. Which listed bounds hold for its worst-case time? Select all that apply.
A. O(n)
B. Theta(1)
C. Theta(n)
D. O(1)
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, C — A. O(n); C. Theta(n)
The append operation begins at the head and must follow the chain to locate its final node. That requires linear traversal, followed by a constant amount of link work. Its tight worst-case bound is therefore Theta(n), which also implies the upper bound O(n). Neither constant-time choice holds as the list grows. Maintaining a separate tail would change the operation cost, but that representation is explicitly excluded.
Evidence in the complete study note
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++.DSA09
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · correct — O(n) is a valid upper bound on the traversal.
B · incorrect — The growing traversal prevents a constant tight bound.
C · correct — Theta(n) is the tight traversal bound.
D · incorrect — O(1) does not bound arbitrary head-only append traversal.
Question 128
Which ordinary search method requires its input key sequence to be sorted before using comparisons to discard the half that cannot contain a target?
A. Hash search
B. Depth-first search
C. Binary search
D. Linear search
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Binary search compares a target with the midpoint of an ordered interval, then safely discards one half. That elimination depends on sorted order. Linear search can scan unsorted values, hashing selects addresses from keys rather than sorted positions, and depth-first search follows graph adjacency. The revised alternatives therefore have clear operational meanings, and Binary search uniquely matches the stated ordered-half-elimination requirement.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1.DSA29
Unsorted data is allowed; sorted data is allowed too.DSA28
A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity.DSA25
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours.DSA42
Choice by choice
A · incorrect — Hash lookup uses computed addresses rather than a sorted input interval.
B · incorrect — Depth-first search follows adjacency, not ordered-array halves.
C · correct — Binary search needs ordering to safely discard a comparison-selected half.
D · incorrect — Linear scanning permits unsorted input.
Question 129
Given a binary search tree, which traversal type would print the values in the nodes in sorted
order?
A. Pre-order
B. Pre-order and Post-order
C. In-order
D. Post-order
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
All left-subtree keys precede the root, and all right-subtree keys follow it. Recursively visiting left, parent, right therefore emits increasing keys. Evidence: assigned PDF pages 9.
Evidence in the complete study note
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
Preorder visits node,left,right; inorder left,node,right; postorder left,right,node. Apply recursively; null children do nothing. Inorder returns sorted keys only for a BST. Preorder supports copying, postorder supports deleting children before parents, and level order uses a FIFO queue.DSA20
Choice by choice
A · incorrect — Preorder prints root before smaller left keys. See assigned PDF 9, 9.
B · incorrect — Including preorder cannot guarantee increasing order. See assigned PDF 9, 9.
C · correct — Inorder matches left keys < root < right keys recursively. See assigned PDF 9, 9.
D · incorrect — Postorder prints the root after larger right keys. See assigned PDF 9, 9.
Question 130
If a sequence of operations: push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2),
pop are performed on a stack, the sequence of popped values is:
A. 2,1,2,2,1
B. 2,2,1,1,2
C. 2,1,2,2,2
D. 2,2,1,2,2
Hint / Module Reference (Where to Read)
Trace the initial state and update only the fields affected by each permitted operation.
Trace bottom-to-top: [1], [1,2], pop 2; [1,1], [1,1,2], pop 2; pop 1; pop 1; [2], pop 2. Popped sequence is 2,2,1,1,2. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Write the stack bottom-to-top after every instruction and record popped values separately. Push 1, push 2, pop emits 2 and leaves [1]. Push 1, push 2, pop, pop, pop then emits 2,1,1; push 2, pop emits 2. The complete output is 2,2,1,1,2.DSA12
Choice by choice
A · incorrect — The second pop is 2, not 1. See assigned PDF 6.
B · correct — Exactly matches all five top removals. See assigned PDF 6.
C · incorrect — The second pop is again 2, not 1. See assigned PDF 6.
D · incorrect — The fourth pop removes the original bottom 1, not 2. See assigned PDF 6.
Question 131
Which of the following is FALSE in Data Structures and Algorithms?
A. A tree contains a cycle
B. Tree is a non-linear data structure
C. A tree is a connected graph
D. A tree with n nodes contains (n-1) edges
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Unique root paths and one parent per nonroot node exclude cycles. The n-1 nonroot nodes each contribute one parent edge, making the rooted tree connected with n-1 edges. Evidence: assigned PDF pages 9, 2.
Evidence in the complete study note
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · correct — A cycle contradicts the source unique-path parent hierarchy. See assigned PDF 9, 2.
B · incorrect — Trees are explicitly classified as nonlinear. See assigned PDF 9, 2.
C · incorrect — Every node is reachable from the root along a unique path, so the tree is connected. See assigned PDF 9, 2.
D · incorrect — One parent edge for each nonroot node yields n-1 edges. See assigned PDF 9, 2.
Question 132
A fixed-capacity circular array queue uses front and size indices, modulo slot reuse, and no shifting or resizing. Under unit-cost index arithmetic, what is the tightest listed worst-case pair for enqueue and dequeue, including full/empty checks?
A. O(n), O(1)
B. O(1), O(n)
C. O(1), O(1)
D. O(n), O(n)
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Enqueue computes a slot from front and size, writes one item and updates the count. Dequeue reads the front slot, advances front modulo capacity and decreases the count. Full or empty checks also inspect only constant-size state. No operation shifts or resizes the array, so each uses constant work in the stated model. The linear alternatives are looser bounds rather than the requested tight pair.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Dequeue reads A[front], sets front=(front+1)%C and decreases size. An alternative reserves one unused slot and uses next(rear)==front for full; its empty test and capacity differ. State the convention before tracing.DSA15
Choice by choice
A · incorrect — Linear enqueue is looser than the constant cost of this implementation.
B · incorrect — Linear dequeue is looser than its constant index update cost.
C · correct — Both endpoint operations use constant work.
D · incorrect — Both linear bounds are looser than the requested tight pair.
Question 133
Depending on the organization of the elements which of the following approach Is a non-linear data structure?
A. Queues
B. Linked-list
C. Tree
D. Stack
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The module classifies trees as nonlinear, while queues and stacks are linear sequences and a linked list is a next-pointer chain. Evidence: assigned PDF pages 2, 4, 6.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · incorrect — Queue is an explicit linear example. See assigned PDF 2, 4, 6.
B · incorrect — A linked list is a chain with one next node, not branching hierarchy. See assigned PDF 2, 4, 6.
C · correct — Tree is an explicit nonlinear example. See assigned PDF 2, 4, 6.
D · incorrect — Stack is an explicit linear example. See assigned PDF 2, 4, 6.
Question 134
For this question, an indirect queue application means using FIFO as auxiliary storage inside a graph traversal algorithm, rather than directly modeling a waiting line or scheduling service. Which listed description fits?
A. Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a print queue).
B. Simulation of real-world queues such as lines at a ticket counter or any other first-come first-served scenario requires a queue.
C. Auxiliary data structure for algorithms
D. Multiprogramming
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: C — C. Auxiliary data structure for algorithms
The supplied convention distinguishes an algorithm’s internal work storage from a real-world waiting-line model. BFS uses a queue to hold its discovered but not yet explored vertices, so auxiliary algorithm storage is the matching category. Equal-priority job scheduling and ticket-line simulation directly model service waiting. Multiprogramming is a broader operating-system setting and does not specifically name the internal graph-traversal role requested here.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Choice by choice
A · incorrect — Arrival-order print scheduling directly models a service queue.
B · incorrect — Ticket-line simulation directly models real-world waiting.
C · correct — An algorithmic frontier queue is auxiliary storage inside graph traversal.
D · incorrect — Multiprogramming is a broad execution setting, not the specified internal traversal role.
Question 135
A queue in which the item most recently added is always the first one out refers to:
A. FIFO queue
B. Real time queue
C. Priority queue
D. LIFO queue
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Most recently added first removed is LIFO by definition. The name LIFO queue here describes stack discipline rather than the ordinary FIFO queue. Evidence: assigned PDF pages 6, 7, 8.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — FIFO removes the earliest insertion. See assigned PDF 6, 7, 8.
B · incorrect — Real time alone does not specify last-in removal. See assigned PDF 6, 7, 8.
C · incorrect — Priority depends on keys, not necessarily insertion recency. See assigned PDF 6, 7, 8.
D · correct — LIFO exactly names last-in-first-out service. See assigned PDF 6, 7, 8.
Question 136
Which data structure follows the LIFO (Last-In-First-Out) principle?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The stack top is both insertion and removal end, so the most recent unremoved insertion leaves first. Evidence: assigned PDF pages 6, 7, 4, 9.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · correct — Stack is explicitly LIFO. See assigned PDF 6, 7, 4, 9.
B · incorrect — Queue is FIFO. See assigned PDF 6, 7, 4, 9.
C · incorrect — A linked list is a representation with no mandatory service discipline. See assigned PDF 6, 7, 4, 9.
D · incorrect — A binary tree defines children, not insertion/removal chronology. See assigned PDF 6, 7, 4, 9.
Question 137
Which data structure follows the FIFO (First-In-First-Out) principle?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
FIFO is explicitly the queue policy: enqueue at rear and dequeue at front. Evidence: assigned PDF pages 7, 6.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — Stack is LIFO. See assigned PDF 7, 6.
B · correct — Queue preserves insertion order for removal. See assigned PDF 7, 6.
C · incorrect — A linked list can implement a queue but does not inherently impose FIFO. See assigned PDF 7, 6.
D · incorrect — Binary-tree structure does not impose FIFO. See assigned PDF 7, 6.
Question 138
Which listed representation permits insertion and removal at either endpoint in constant time? Use ordinary stack and FIFO queue interfaces, and interpret C as a doubly linked list maintaining both head and tail.
A. Stack
B. Queue
C. Doubly linked list with head and tail
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: C — C. Doubly linked list with head and tail
A doubly linked list stores predecessor and successor links, while head and tail provide direct access to both endpoints. Inserting or removing there updates a fixed number of links, including the empty and singleton cases. Ordinary stack and FIFO queue interfaces expose fewer endpoint operations, and a binary tree has no corresponding two-end sequence guarantee. The explicit linked-list variant is essential because singly linked tail deletion needs a predecessor traversal.
Evidence in the complete study note
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — A stack exposes insertion/removal at one top only.
B · incorrect — An ordinary FIFO queue does not permit all four endpoint operations.
C · correct — A doubly linked list with both endpoint pointers supports constant-time operations at each end.
D · incorrect — A binary tree has no two-end sequence-operation guarantee.
Question 139
Which data structure represents a hierarchical structure with nodes and edges?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
A tree is expressly an abstract model of a hierarchical structure, and a binary tree is its at-most-two-children specialization. Evidence: assigned PDF pages 9.
Evidence in the complete study note
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
Trees model hierarchies; graphs model general connections.DSA01
Choice by choice
A · incorrect — Stack is a one-ended linear list. See assigned PDF 9, 9.
B · incorrect — Queue is a FIFO linear list. See assigned PDF 9, 9.
C · incorrect — A singly linked list is a chain rather than a branching hierarchy. See assigned PDF 9, 9.
D · correct — Binary tree matches the hierarchy with nodes and edges. See assigned PDF 9, 9.
Question 140
Which data structure is best suited for implementing a backtracking algorithm?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Backtracking is explicitly listed as a stack application: the latest pending decision can be undone first using pop. Evidence: assigned PDF pages 7, 6.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · correct — LIFO naturally returns to the most recent unfinished decision. See assigned PDF 7, 6.
B · incorrect — FIFO would return to oldest pending work. See assigned PDF 7, 6.
C · incorrect — A generic linked list does not prescribe backtracking order. See assigned PDF 7, 6.
D · incorrect — A binary tree can represent choices but does not itself maintain a LIFO return path. See assigned PDF 7, 6.
Question 141
A dispatcher keeps pending jobs in a sequence. Urgent jobs are added at the front, ordinary jobs at the back; serving removes the front job, and cancellation removes the last job. Which listed representation supports every operation in worst-case constant time as the sequence grows? Use ordinary stack and FIFO queue interfaces, with no additional indexes or auxiliary structures.
A. Stack
B. Queue
C. Doubly linked list with head and tail
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answer: C — C. Doubly linked list with head and tail
Urgent arrival inserts at the head, ordinary arrival appends at the tail, service removes the head, and cancellation removes the tail. A doubly linked list with both endpoint pointers updates a fixed number of links for each action; its prev link identifies the predecessor needed for tail removal. A stack exposes only one top, a FIFO queue lacks last-job cancellation and front insertion, and a generic binary tree provides no such endpoint-cost guarantee.
Evidence in the complete study note
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — One stack top cannot directly supply both service-at-front and cancellation-at-back operations.
B · incorrect — An ordinary FIFO queue permits rear insertion and front removal, but not urgent front insertion or last-job removal.
C · correct — Head and tail permit direct endpoint access, and prev links make last-job removal constant time.
D · incorrect — A generic binary tree has no guarantee for all four ordered-sequence endpoint updates.
Question 142
Which listed structures admit both array-based and linked-node representations? Links may be array indices or pointers, and binary-tree representations include the complete binary-tree case. Select all that apply.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, B, C, D — A. Stack; B. Queue; C. Linked list; D. Binary tree
Stacks and queues have both array and linked-node implementations. A linked list can store its next links as indices into an array or as pointers between allocated nodes. A binary tree can use linked child references, while the complete binary-tree case has the indexed heap representation. The question concerns possible representations, so all four qualify without requiring one universal layout for every instance.
Evidence in the complete study note
Arrays or linked nodes can implement the same LIFO stack.DSA01
A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head.DSA14
A circular queue reuses slots with modulo arithmetic.DSA15
An array-linked list still follows links unless separately position-indexed.DSA08
Zero-based array representation: root index 0, left=2i+1, right=2i+2, parent=floor((i-1)/2) for i>0.DSA23
A linked binary-tree node stores a payload and two child pointers, one for the left child and one for the right child.DSA-S03
Choice by choice
A · correct — A stack can use an array top or a linked head.
B · correct — A queue can use circular slots or linked endpoint nodes.
C · correct — List links may be indices or node references.
D · correct — Binary trees have linked-node forms and indexed complete-tree forms.
Question 143
A character reader supplies a word from left to right. After reading finishes, an output routine must remove one character at a time from a single auxiliary ADT to display the word right to left. It may use only the ADT’s standard insertion/removal interface and must preserve the original input. Which ADT directly supplies the needed removal order?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Insert the characters in the order they are read. The required output starts with the last character inserted, then continues toward the earliest one, so a stack’s LIFO interface directly supplies the reversal. A queue would preserve the original order. A linked list could represent a stack, but its storage links alone do not prescribe LIFO; a generic tree likewise has no matching removal contract.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Stack policy is LIFO, equivalently FILO.DSA11
Linked stacks achieve constant time by inserting and deleting at the head; using a singly linked tail for pop would require a predecessor traversal.DSA11
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served.DSA14
Specify whether a question asks which structure can implement something or which is best under stated costs. ADTs do not force one representation, and serial-access memory is not inherently LIFO.DSA45
Choice by choice
A · correct — Repeated stack removals produce the characters in reverse insertion order.
B · incorrect — FIFO removal would reproduce the original character order.
C · incorrect — A list is a possible representation but does not itself prescribe the required removal policy.
D · incorrect — A generic tree does not define the requested reverse-insertion removal contract.
Question 144
Which data structure is commonly used for implementing function call stacks in
programming languages?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The source explicitly states that a memory stack is used in function calls including recursion, keeping the most recent active call on top. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · correct — Nested calls return in LIFO order through a stack. See assigned PDF 6, 6.
B · incorrect — Queue FIFO order would not reflect nested returns. See assigned PDF 6, 6.
C · incorrect — Linked nodes can store frames but the controlling ADT is still a stack. See assigned PDF 6, 6.
D · incorrect — A binary tree does not provide the specified call-return discipline. See assigned PDF 6, 6.
Question 145
A message buffer accepts new items at its rear and delivers the oldest waiting item from its front. Which service ADT can maintain this contract using either a circular array or linked head-and-tail nodes? Choose the ADT rather than an underlying storage container.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
The oldest waiting message must leave first, while new arrivals join the rear. This is the ordinary queue service contract. The note supplies both a circular-array representation that reuses slots and a linked representation that appends at the tail and removes at the head. A stack serves the newest item first; a generic linked list or tree does not independently specify this FIFO policy.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — A stack’s latest-first removal violates oldest-message-first delivery.
B · correct — A queue has the stated rear-insertion/front-removal contract and both cited implementations.
C · incorrect — Linked nodes can store the queue but do not by themselves define its service policy.
D · incorrect — A binary tree does not inherently define this FIFO message-buffer interface.
Question 146
Which data structure has a First-In-First-Out (FIFO) property?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
First-in-first-out is the explicit queue property. Inserting at rear and removing at front preserves the oldest pending element. Evidence: assigned PDF pages 7.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · incorrect — Stack is last-in-first-out. See assigned PDF 7.
B · correct — Queue has FIFO semantics. See assigned PDF 7.
C · incorrect — A linked-list representation alone imposes no FIFO restriction. See assigned PDF 7.
D · incorrect — A binary-tree hierarchy is not arrival-order access. See assigned PDF 7.
Question 147
Which data structure is suitable for implementing a breadth-first search algorithm?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
DSA41 enqueues discovered neighbors and dequeues the next pending vertex. This FIFO discipline preserves distance-layer ordering. A linked list can store the queue but does not by itself state the policy. Stack service is latest-first, while a binary tree is not the standard frontier discipline. Queue is therefore the specific suitable ADT among the choices.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
Choice by choice
A · incorrect — Stack order selects the latest pending vertex and does not preserve the BFS layer invariant.
B · correct — Queue FIFO ordering processes earlier distance layers before later discoveries, as BFS requires.
C · incorrect — A linked list may represent a queue, but linked-list links alone specify no BFS service order.
D · incorrect — A binary tree does not supply the standard FIFO pending-vertex discipline used by breadth-first search.
Question 148
Which listed structures can create nodes using dynamic memory allocation in a linked-node implementation? Select all that apply.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, B, C, D — A. Stack; B. Queue; C. Linked list; D. Binary tree
Dynamic node allocation is a representation choice rather than a property exclusive to one ADT. A linked stack can allocate a node for each push, a linked queue for each enqueue, and a linked list for insertion. A pointer-based binary tree can allocate a leaf when attaching it. Array implementations also exist, but their existence does not prevent any of these structures from using dynamically allocated nodes.
Evidence in the complete study note
A linked binary-tree node stores a payload and two child pointers, one for the left child and one for the right child. A null child pointer means that child is absent; a root pointer gives access to the whole tree. In a dynamically allocated version, insertion can allocate a node and attach it through the appropriate child link.DSA-S03
Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Linked stacks achieve constant time by inserting and deleting at the head;DSA11
A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head.DSA14
Choice by choice
A · correct — A linked stack can allocate each new head node.
B · correct — A linked queue can allocate each new rear node.
C · correct — A linked list can grow by allocating nodes as needed.
D · correct — A linked binary tree can allocate an inserted leaf.
Question 149
Which structures admit an array-based representation? Array slots may contain payloads and integer links; for binary trees include complete trees stored with child-index formulas. Select all that apply.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
Correct answers (select all): A, B, C, D — A. Stack; B. Queue; C. Linked list; D. Binary tree
An array stack uses a top index, while a circular queue uses front and size indices. A linked list can store its links as indices into an array rather than as pointers to separately allocated nodes. Complete binary trees also fit the indexed heap layout. Since the question asks whether representations exist and removes the subjective ease ranking, each of the four listed structures qualifies.
Evidence in the complete study note
With zero-based occupied slots, top=-1 is empty and top=C-1 is full.DSA11
insertion slot is (front+size)%C.DSA15
An array-linked list still follows links unless separately position-indexed.DSA08
Zero-based array representation: root index 0, left=2i+1, right=2i+2, parent=floor((i-1)/2) for i>0. One-based representation uses children 2i,2i+1 and parent floor(i/2). A child exists only if its index is inside the current heap size.DSA23
Choice by choice
A · correct — An array top index implements a stack.
B · correct — Modulo-indexed slots implement a circular queue.
C · correct — Array indices can encode list links.
D · correct — Complete binary trees use the indexed heap layout.
Question 150
Which listed representation provides direct next and previous links for walking a linear sequence forward and backward without retracing from its head? Use ordinary stack/queue interfaces and a binary tree without parent or traversal-thread links.
A. Stack
B. Queue
C. Doubly linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the required operations, access order and representation metadata with each option.
A doubly linked list retains the forward next link and adds a prev link to each node. Following the corresponding link moves directly to a neighboring node in either direction. Ordinary stack and queue interfaces do not expose this bidirectional traversal contract. A child-linked binary tree without parent or traversal threads also does not provide the specified previous/next linear-sequence links. The concrete list variant makes the guarantee precise.
Evidence in the complete study note
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Choice by choice
A · incorrect — A stack interface exposes its top, not a bidirectional traversal.
B · incorrect — A queue interface exposes FIFO endpoints, not neighboring prev/next traversal.
C · correct — Doubly linked nodes provide next and prev links.
D · incorrect — The specified child-only tree lacks the requested linear previous/next links.
Question 151
Which specified representations provide direct constant-time inspection of both first and last items in a nonempty sequence? A is a head-only linked stack, B a linked queue with front and rear pointers, C a linked list with head and tail, and D a child-linked binary tree with no cached endpoints. Select all that apply.
A. Head-only linked stack
B. Linked queue with front and rear
C. Linked list with head and tail
D. Child-linked binary tree without endpoint caches
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): B, C — B. Linked queue with front and rear; C. Linked list with head and tail
Maintaining references to both endpoints makes their items directly available without traversal. The specified linked queue retains front and rear, and the specified list retains head and tail, so both provide constant-time inspection. A head-only linked stack must follow links to reach its oldest item, and a generic child-linked tree without endpoint caches supplies no direct first/last guarantee. The answer follows the representations, not the generic names alone.
Evidence in the complete study note
A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head.DSA14
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends.DSA10
Linked stacks achieve constant time by inserting and deleting at the head;DSA11
A linked binary-tree node stores a payload and two child pointers, one for the left child and one for the right child.DSA-S03
Choice by choice
A · incorrect — A head-only stack lacks a direct reference to its oldest node.
B · correct — Front and rear pointers directly expose both endpoint items.
C · correct — Head and tail pointers directly expose both endpoint items.
D · incorrect — The unaugmented tree has no cached traversal endpoints.
Question 152
Which data structure can be efficiently used for implementing undo and redo functionality in
applications?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Undo reverses the most recent action first, matching the source stack backtracking/reversal uses. A second stack can retain undone actions and reverse them again for redo. Evidence: assigned PDF pages 7, 6.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · correct — Push records actions; pop undoes the most recent; a second LIFO stack supports redo. See assigned PDF 7, 6.
B · incorrect — FIFO would undo the oldest pending action first. See assigned PDF 7, 6.
C · incorrect — A generic linked list can implement a stack but supplies no undo discipline by itself. See assigned PDF 7, 6.
D · incorrect — A binary tree does not directly supply last-action-first reversal. See assigned PDF 7, 6.
Question 153
A forward-only input sequence must be emitted in reverse order after all input is read, using one auxiliary ADT through its standard insertion/removal interface. Which ADT directly reverses the order without modifying the input links or adding a separate reversal algorithm?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
A stack accepts the sequence in arrival order and then removes the most recently inserted item first. Repeated pops therefore emit the complete reverse sequence directly. A FIFO queue preserves the original order. A generic linked list or binary tree does not itself specify the required removal discipline; reversing existing links would be a separate algorithm excluded by this question. The contract identifies the auxiliary reversal ADT.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · correct — Push all items and then pop to emit reverse order directly.
B · incorrect — FIFO removal preserves input order.
C · incorrect — A generic list has no inherent reverse-removal contract without an added algorithm or stack policy.
D · incorrect — A generic tree supplies no required reverse-sequence service.
Question 154
Which abstract frontier service policy directly implements the latest-pending-work-first behavior of depth-first search? Choose the ADT, rather than a storage representation that could be given that policy.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DFS finishes the most recently entered unfinished branch before returning to older pending work. A stack directly supplies this latest-pending-work-first rule. A queue would instead remove older pending items first, producing a breadth-first discipline under ordinary graph traversal. A linked list may implement a stack, but its links alone do not prescribe the frontier policy. A binary tree describes possible input relationships rather than the required pending-work ADT.
Evidence in the complete study note
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · correct — A stack directly supplies latest-pending-work-first service.
B · incorrect — A FIFO queue retrieves older pending work first.
C · incorrect — Linked-list storage alone does not specify a frontier service policy.
D · incorrect — A binary tree is not the latest-pending-work service ADT.
Question 155
Which listed representations can implement a priority queue without retaining an unmodified LIFO or FIFO removal contract? Interpret D as a binary heap and C as an ordered or unordered list using extremum selection. Select all that apply.
A. Stack
B. Queue
C. Linked list
D. Binary tree organized as a binary heap
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): C, D — C. Linked list; D. Binary tree organized as a binary heap
A priority queue removes an item with an extreme priority key. An unordered list can scan for that extremum, while an ordered list maintains the relevant order during insertion. A binary heap supplies the same priority contract through heap order and logarithmic insertion/extraction. An unmodified stack or FIFO queue removes according to arrival position rather than priority. Thus the list and heap-shaped binary tree qualify under the stated algorithms.
Evidence in the complete study note
A priority queue returns the smallest or largest priority key under its convention. Urgent patients may precede earlier arrivals. Insertions and extractions can interleave. Binary heaps support constant peek and logarithmic insert/extract.DSA17
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff. Equal priorities have no inherent FIFO guarantee. If stable service is required, compare (priority, arrival_counter). Choose the priority direction and tie rule before tracing.DSA17
Choice by choice
A · incorrect — An unmodified stack removes by recency rather than priority.
B · incorrect — An unmodified FIFO queue removes by arrival order rather than priority.
C · correct — Ordered or scanned lists can select the extreme priority.
D · correct — A binary heap implements priority selection through heap order.
Question 156
Which ordinary ADT restricts insertion to the rear and removal or peek to the front, preserving arrival order? Assume standard ADT interfaces rather than additional traversal operations.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The ordinary queue inserts new items at its rear and removes or observes the front item. These restrictions produce FIFO service: earlier arrivals are removed before later arrivals. A stack uses a single top and LIFO order. A general linked list permits operations beyond these restricted endpoints, while a binary tree organizes hierarchical relationships. Specifying the exact operations resolves the original vague use of access.
Evidence in the complete study note
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · incorrect — A stack operates at one top using LIFO.
B · correct — A queue has rear insertion and front removal/peek.
C · incorrect — A general list does not restrict access to those two operations.
D · incorrect — A binary tree does not have this FIFO endpoint contract.
Question 157
Which structures can use nodes connected by pointers in a linked implementation? Do not require that every implementation use pointers. Select all that apply.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, B, C, D — A. Stack; B. Queue; C. Linked list; D. Binary tree
Pointer links can connect the nodes of several structures. A linked list uses next links, a linked stack operates at the chain head, and a linked queue maintains endpoint references around a chain. A pointer-based binary tree instead links child nodes along branches. All four therefore admit a node-and-pointer representation. Their alternative array layouts do not invalidate this existence claim about linked implementations.
Evidence in the complete study note
A linked binary-tree node stores a payload and two child pointers, one for the left child and one for the right child. A null child pointer means that child is absent; a root pointer gives access to the whole tree. In a dynamically allocated version, insertion can allocate a node and attach it through the appropriate child link.DSA-S03
Arrays or linked nodes can implement the same LIFO stack.DSA01
A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head.DSA14
A singly linked node contains data and next.DSA08
Choice by choice
A · correct — A linked stack connects nodes through head-chain links.
B · correct — A linked queue connects nodes and retains endpoint pointers.
C · correct — A linked list directly uses node links.
D · correct — A pointer-based tree links its child nodes.
Question 158
Which data structure allows elements to be inserted and removed from both ends?
A. Stack
B. Queue
C. Deque
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
A double-ended queue permits insertion and deletion at either end by definition. Evidence: assigned PDF pages 8.
Evidence in the complete study note
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure.DSA16
Choice by choice
A · incorrect — Stack restricts both operations to one top. See assigned PDF 8.
B · incorrect — Ordinary queue fixes insertion rear and deletion front. See assigned PDF 8.
C · correct — Deque is expressly defined by operations at both ends. See assigned PDF 8.
D · incorrect — A binary tree is a hierarchy, not a double-ended sequence. See assigned PDF 8.
Question 159
Which ADTs impose an item-removal order through their ordinary service contract? Use LIFO for stacks, FIFO for queues, and smallest-priority-first with FIFO ties for priority queues. A generic binary tree has no specified traversal. Select all that apply.
A. Stack
B. Queue
C. Priority queue
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, B, C — A. Stack; B. Queue; C. Priority queue
Stacks impose reverse arrival order and queues impose arrival order. A priority queue also imposes an order once the priority direction and tie rule are supplied; this version chooses the smallest priority and serves equal priorities FIFO. A generic binary tree supplies a shape with several possible traversals rather than a single inherent removal order. Consequently the three service ADTs qualify and the unspecified tree does not.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
This is FIFO or first-come, first-served.DSA14
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff. Equal priorities have no inherent FIFO guarantee. If stable service is required, compare (priority, arrival_counter). Choose the priority direction and tie rule before tracing.DSA17
Choice by choice
A · correct — A stack imposes LIFO removal.
B · correct — A queue imposes FIFO removal.
C · correct — The stated priority and tie rules define priority-queue removal order.
D · incorrect — A generic tree without a traversal has no single inherent removal order.
Question 160
Which is the most general listed binary-tree family defined by the following distinct-key invariant alone, without an additional balancing discipline: every key in a node’s left subtree is smaller, and every key in its right subtree is larger?
A. AVL tree
B. Binary search tree
C. Red-black tree
D. B-tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The global left-smaller/right-larger invariant defines the binary search tree family. It applies to every descendant in each subtree, not only immediate children. AVL and red-black trees satisfy that ordering but impose additional balancing disciplines, so they are more specialized than the family requested. The binary-tree restriction also excludes a general B-tree. Asking for the most general family prevents those BST subclasses from becoming competing selections.
Evidence in the complete study note
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
AVL balance factor is height(left)-height(right); every node must have factor -1,0 or 1. After insertion or deletion, update heights upward and rotate where necessary. LL imbalance needs a right rotation; RR needs left; LR rotates the left child left then the node right; RL is symmetric. Rotations preserve inorder key order.DSA22
A B-tree is a balanced multiway search tree. Its allowed branching factor can exceed two, so a general B-tree is not the binary-tree family. Balanced describes a height discipline; it does not by itself restrict every node to two children.DSA-S03
Choice by choice
A · incorrect — AVL adds balance requirements beyond the stated invariant.
B · correct — BST is the general family defined by the strict subtree ordering alone.
C · incorrect — Red-black trees add a balancing discipline beyond the stated invariant.
D · incorrect — A general B-tree is not the requested binary-tree family.
Question 161
Which data structure represents a hierarchical structure with a set of connected nodes?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The module defines trees as hierarchical structures consisting of nodes and connecting edges. Binary trees specialize that hierarchy to two possible children. Evidence: assigned PDF pages 9.
Evidence in the complete study note
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
Choice by choice
A · incorrect — Stack is a linear LIFO list. See assigned PDF 9, 9.
B · incorrect — Queue is a linear FIFO list. See assigned PDF 9, 9.
C · incorrect — Single linked list is a sequential chain. See assigned PDF 9, 9.
D · correct — Binary tree is the hierarchical option. See assigned PDF 9, 9.
Question 162
Which data structure allows efficient insertion and deletion at both ends?
A. Stack
B. Queue
C. Deque
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The source deque definition allows insertion and deletion at either end. With endpoint references these are local operations; no middle search is needed. Evidence: assigned PDF pages 8.
Evidence in the complete study note
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure.DSA16
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
Choice by choice
A · incorrect — Stack offers only the top endpoint. See assigned PDF 8.
B · incorrect — Queue fixes rear insertion and front deletion, not both operations at both ends. See assigned PDF 8.
C · correct — Deque supplies the requested two-ended operations. See assigned PDF 8.
D · incorrect — Binary trees do not define two list ends. See assigned PDF 8.
Question 163
Which data structure uses the concept of "first in, last out" to handle function calls and
recursion?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
FILO is explicitly equivalent to LIFO, and the source names stack memory for calls and recursion. The most recent call returns before the earlier waiting caller. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Stack policy is LIFO, equivalently FILO.DSA11
Choice by choice
A · correct — Stack supplies FILO nesting for function frames. See assigned PDF 6, 6.
B · incorrect — Queue is FIFO and would not match nested returns. See assigned PDF 6, 6.
C · incorrect — A linked list can store frames but does not itself impose call order. See assigned PDF 6, 6.
D · incorrect — A binary tree does not implement the stated endpoint discipline by its definition. See assigned PDF 6, 6.
Question 164
Which data structure is suitable for implementing depth-first search (DFS) algorithm?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA42 describes recursively finishing an unvisited neighbor before returning to the parent. Explicit stack storage or the runtime call stack preserves this latest-pending-work-first behavior. A FIFO queue changes the exploration order. Linked lists can store frames but do not themselves define stack order, and a binary tree alone is not a frontier policy.
Evidence in the complete study note
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · correct — A stack stores pending frames or vertices so the latest unfinished branch is resumed first.
B · incorrect — A queue serves the oldest pending work and changes the depth-first exploration discipline.
C · incorrect — A linked list may store a stack, but its name alone supplies no depth-first service order.
D · incorrect — A binary tree is not the standard pending-work ADT needed to preserve DFS return points.
Question 165
A capacity-limited cache evicts entries strictly in insertion order; cache hits do not change that order. Which ADT should maintain its eviction order? Ask for the service policy rather than a possible storage implementation.
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The earliest inserted resident entry must be evicted first, and hits do not move it. This is FIFO order, which a queue directly maintains through rear insertion and front removal. A linked list could be used to implement that queue but does not independently prescribe the eviction discipline. A stack reverses insertion order, and a generic binary tree provides no FIFO eviction contract.
Evidence in the complete study note
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.DSA27
Choice by choice
A · incorrect — LIFO would evict the most recent insertion rather than the oldest.
B · correct — FIFO queue service matches insertion-order eviction.
C · incorrect — A linked list is a possible representation but does not itself prescribe FIFO service.
D · incorrect — A generic binary tree does not prescribe insertion-order eviction.
Question 166
Which data structure is commonly used for implementing undo-redo functionality in text
editors?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Undo applies the inverse of the latest action, a LIFO operation. Keeping undone actions on another stack supports redo in the reverse order of undo. Evidence: assigned PDF pages 7, 6.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · correct — Two stacks implement the required action reversal and restoration ordering. See assigned PDF 7, 6.
B · incorrect — FIFO would undo actions in their original order. See assigned PDF 7, 6.
C · incorrect — A linked list can store history but needs an added stack discipline. See assigned PDF 7, 6.
D · incorrect — A binary tree does not intrinsically select the latest action. See assigned PDF 7, 6.
Question 167
Which data structure allows easy traversal in a Last-In-First-Out (LIFO) order?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Easy traversal here is interpreted as repeated access/removal by the defining ADT rule. A stack pops the most recently pushed remaining element first. Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Choice by choice
A · correct — Stack expressly enforces last-in-first-out. See assigned PDF 6.
B · incorrect — Queue expressly enforces first-in-first-out. See assigned PDF 6.
C · incorrect — A linked list can emulate LIFO only after choosing an endpoint policy. See assigned PDF 6.
D · incorrect — A binary tree traversal is determined by child order, not insertion recency. See assigned PDF 6.
Question 168
Which specified representation supports constant-time insertion/deletion at either endpoint and constant-time indexed access to the logical middle item? Assume fixed capacity, no shifting or resizing, spare space for insertion, and a nonempty sequence for access.
A. Stack
B. Queue
C. Fixed-capacity circular-array deque
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: C — C. Fixed-capacity circular-array deque
A circular-array deque maps logical position k to a slot by adding the front index and reducing modulo capacity. That makes the middle item directly indexable. Endpoint insertions and deletions change only a slot and constant-size indices when no resize or shift occurs. A linked deque would not provide this indexing guarantee, so the array representation is explicit. The other ordinary ADT interfaces lack the combined operation set.
Evidence in the complete study note
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure.DSA16
insertion slot is (front+size)%C.DSA15
This arithmetic gives constant-time positional access in the usual RAM cost model.DSA02
Choice by choice
A · incorrect — A stack does not expose both-end updates and middle indexing.
B · incorrect — An ordinary queue does not expose all four endpoint operations or arbitrary middle access.
C · correct — The fixed circular-array deque supplies endpoint updates and indexed middle access.
D · incorrect — A generic binary tree lacks constant-time access by middle sequence position.
Question 169
Which data structure is commonly used for implementing the undo operation in a text
editor?
A. Stack
B. Queue
C. Linked list
D. Binary tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The latest action must be reversed first, matching LIFO and the source backtracking application. Pushing action records and popping the latest implements that order. Evidence: assigned PDF pages 6, 7.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Choice by choice
A · correct — Top holds the latest pending action to undo. See assigned PDF 6, 7.
B · incorrect — FIFO selects the oldest pending action instead. See assigned PDF 6, 7.
C · incorrect — A generic linked list needs a chosen stack discipline to implement undo. See assigned PDF 6, 7.
D · incorrect — A binary tree alone does not impose reverse chronology. See assigned PDF 6, 7.
Question 170
A bounded FIFO buffer must reuse freed array slots by wrapping indices modulo its fixed capacity, without shifting items. New insertions are rejected while full. Which listed term specifically names this storage representation?
A. Stack
B. Queue
C. Linked list
D. Circular buffer
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
A circular buffer reuses its fixed slots by wrapping indices modulo capacity, so released positions can be used again without moving surviving items. The FIFO order is tracked logically rather than by requiring the front to remain at physical slot zero. Queue names the service ADT and can have other representations; it does not specifically identify this layout. Stack and linked list likewise do not name the stated circular-array representation.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Merging FIFO queues needs an explicit policy: append one sequence after another or alternate their fronts. Splitting by a predicate preserves each subgroup’s original order if each removed item is appended to its matching output queue. A fixed-capacity buffer also needs a full-policy choice: reject, block or overwrite. Capacity alone does not choose a policy.DSA16
Choice by choice
A · incorrect — A stack names LIFO service rather than the specified FIFO ring storage.
B · incorrect — Queue names the FIFO ADT but does not specifically identify its storage layout.
C · incorrect — A linked list does not name modulo-indexed circular array slots.
D · correct — Circular buffer specifically names the stated fixed-slot wraparound representation.
Question 171
Which ordinary array sorting algorithms have tight worst-case time Theta(n²)? Select all that apply. Use buffered mergesort, ordinary quicksort, standard insertion sort and iterative heapsort.
A. Merge sort
B. Quick sort
C. Insertion sort
D. Heap sort
Alternative version 1
Which ordinary array sorting algorithms have tight worst-case time Theta(n²)? Use strict-swap bubble sort, ordinary quicksort, buffered mergesort and standard insertion sort. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): B, C — B. Quick sort; C. Insertion sort
Repeated extreme partitions make ordinary quicksort accumulate quadratic work. Insertion sort on reverse input similarly accumulates quadratic prefix shifts. Buffered mergesort and iterative heapsort have n log n worst-case bounds instead, so they are not tightly quadratic even though quadratic is a valid looser upper bound. The explicit tight-bound question therefore selects quicksort and insertion alone in this primary option set.
Evidence in the complete study note
Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work.DSA36
Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Building with bottom-up sinking is linear; repeated extraction gives O(n log n) worst time.DSA38
Choice by choice
A · incorrect — Buffered mergesort has n log n worst growth.
B · correct — Extreme quicksort partitions give tight quadratic worst growth.
D · incorrect — Iterative heapsort has an n log n worst bound.
Alternative version 1
Correct answers (select all): A, B, D — A. Bubble sort; B. Quick sort; D. Insertion sort
Bubble sort can require quadratically many adjacent comparisons, quicksort can accumulate quadratic work through extreme pivots, and insertion sort can perform quadratic shifts on reversed input. Buffered mergesort has n log n growth instead. The variant has bubble, quick, merge and insertion in its own label order, so its complete tight-quadratic selection is A, B and D.
Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work.DSA36
Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
A · correct — Adjacent bubble passes can require quadratic work.
B · correct — Extreme quicksort partitions can require quadratic work.
C · incorrect — Buffered mergesort has n log n growth.
D · correct — Reverse input causes quadratic insertion shifts.
Question 172
Which sorting algorithm uses the divide-and-conquer strategy? Use ordinary array implementations, with radix sorting specifically meaning iterative least-significant-digit passes.
A. Bubble sort
B. Selection sort
C. Merge sort
D. Radix sort
Alternative version 1
Which ordinary sorting algorithms use divide and conquer by recursively sorting smaller subproblems? Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Mergesort divides the array into two halves, recursively sorts them and merges their results, so it uses divide and conquer. Ordinary bubble sort uses adjacent passes and selection sort repeatedly selects a suffix minimum. The explicitly specified LSD radix method performs stable digit passes rather than recursive subproblem decomposition. This convention removes the possible confusion with MSD radix grouping while retaining the original primary answer.
Evidence in the complete study note
Divide and conquer reduces a problem to smaller instances of the same kind, solves the required smaller instances and obtains the original result from them. Mergesort recursively sorts two halves and merges; quicksort partitions and recursively sorts the resulting ranges. This course also classifies binary search as divide and conquer: an ordered comparison selects the only half that can contain the target. This is different from simply repeating adjacent swaps, choosing successive minima, or making stable LSD digit passes.DSA-S04
LSD radix sorting handles fixed-width digit keys by stably sorting least-significant digit first, then moving left. Stable intermediate passes preserve the ordering already established by less-significant digits. With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage.DSA39
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
Choice by choice
A · incorrect — Ordinary bubble sort uses adjacent passes rather than recursive decomposition.
B · incorrect — Ordinary selection sort repeatedly places one suffix minimum.
C · correct — Mergesort recursively solves smaller halves and combines their results.
D · incorrect — The specified iterative LSD form uses digit passes rather than recursive divide and conquer.
Alternative version 1
Correct answers (select all): B, C — B. Quick sort; C. Merge sort
Quicksort partitions around a pivot and recursively sorts the smaller ranges. Top-down mergesort recursively sorts halves and merges their results. Both therefore apply divide and conquer. Bubble sort’s adjacent passes and ordinary insertion sort’s growing sorted prefix do not use this recursive subproblem decomposition. The complete answer is B and C; the question requires multiple selection.
Divide and conquer reduces a problem to smaller instances of the same kind, solves the required smaller instances and obtains the original result from them. Mergesort recursively sorts two halves and merges; quicksort partitions and recursively sorts the resulting ranges. This course also classifies binary search as divide and conquer: an ordered comparison selects the only half that can contain the target. This is different from simply repeating adjacent swaps, choosing successive minima, or making stable LSD digit passes.DSA-S04
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Split into halves, sort them, then merge by advancing the smaller current front. With left-first tie handling, equal keys retain order. Ordinary array merging needs a linear auxiliary buffer. There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
A · incorrect — Bubble sorting repeatedly swaps adjacent inversions instead of recursively decomposing subinstances.
B · correct — Quicksort partitions around a pivot and recursively sorts the smaller ranges.
C · correct — Merge sort recursively sorts halves and combines their sorted results.
D · incorrect — Ordinary insertion sort extends a sorted prefix instead of applying recursive divide and conquer.
Question 173
Which specified sorting implementations preserve the relative order of equal full keys? Use ordinary in-place quicksort, ordinary heapsort, LSD radix with stable digit passes, and mergesort with left-first ties. Select all that apply.
A. Quick sort
B. Heap sort
C. Radix sort
D. Merge sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): C, D — C. Radix sort; D. Merge sort
Stable LSD radix passes preserve the ordering already established by less significant digits. Equal full keys remain tied on every pass, so their relative order remains unchanged. Mergesort with left-first ties also preserves equal-key order while combining runs. Ordinary in-place quicksort and heapsort do not guarantee that stability because distant exchanges can reorder equal records. Hence both radix and merge qualify under the specified implementations.
Evidence in the complete study note
Stable intermediate passes preserve the ordering already established by less-significant digits.DSA39
With left-first tie handling, equal keys retain order.DSA37
The method is generally unstable because long root-to-end exchanges can reorder equal keys.DSA38
stack usually log n average, n worst; unstableDSA31
Choice by choice
A · incorrect — Ordinary quicksort does not guarantee equal-key stability.
B · incorrect — Long heap exchanges can reorder equal records.
C · correct — Stable digit passes preserve the order of equal full keys.
D · correct — Left-first merge ties preserve equal-key order.
Question 174
Which sorting algorithm uses a pivot element to partition the array into two subarrays?
A. Bubble sort
B. Selection sort
C. Quick sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The module quicksort explicitly selects a pivot and partitions values below/above it before recursion. Evidence: assigned PDF pages 11, 4, 3.
Evidence in the complete study note
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best.DSA36
Choice by choice
A · incorrect — Bubble uses adjacent comparisons and swaps. See assigned PDF 11, 4, 3, 3.
B · incorrect — Selection chooses the minimum for the next output slot. See assigned PDF 11, 4, 3, 3.
C · correct — Pivot partitioning is the stated quicksort procedure. See assigned PDF 11, 4, 3, 3.
D · incorrect — Insertion puts each item into a sorted prefix. See assigned PDF 11, 4, 3, 3.
Question 175
Which searching algorithm is based on comparing the target value with elements at
midpoints of the array?
A. Linear search
B. Binary search
C. Interpolation search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA29 computes the midpoint of the current ordered interval, compares it with the target, and discards the half that cannot contain the target. That is exactly the midpoint-based procedure in the stem. Linear search scans successive elements, interpolation estimates a position from values, and DFS follows graph branches rather than ordered-array midpoints.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Interpolation search estimates the index from numeric values: lo+(hi-lo)×(key-A[lo])/(A[hi]-A[lo]), rounded to a valid index. Guard equal endpoints and out-of-range targets. On sorted, suitably uniform data its expected probes can be O(log log n); pathological distributions can require linear time. Binary search gives a logarithmic worst bound without that distribution assumption.DSA30
Choice by choice
A · incorrect — Linear search compares successive elements rather than repeatedly choosing the midpoint of a shrinking ordered interval.
B · correct — Binary search explicitly compares the target with the current interval midpoint and keeps one half.
C · incorrect — Interpolation search estimates a probe from numeric values and their distribution, rather than always using the midpoint.
D · incorrect — Depth-first search explores graph neighbors and branches, not ordered-array midpoint intervals.
Question 176
Which ordinary array-search algorithms require sorted input? For interpolation search also assume comparable numeric values and appropriate endpoint guards. Select all that apply.
A. Linear search
B. Binary search
C. Interpolation search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): B, C — B. Binary search; C. Interpolation search
Binary search relies on order to discard half the remaining candidate interval after a comparison. Interpolation search also relies on sorted numeric values when estimating a candidate position from endpoint values. Both therefore require sorted input, although their further assumptions differ. Linear search simply scans and permits unsorted data. DFS follows graph adjacency rather than relying on a sorted array-search interval.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Interpolation search estimates the index from numeric values: lo+(hi-lo)×(key-A[lo])/(A[hi]-A[lo]), rounded to a valid index. Guard equal endpoints and out-of-range targets. On sorted, suitably uniform data its expected probes can be O(log log n); pathological distributions can require linear time. Binary search gives a logarithmic worst bound without that distribution assumption.DSA30
Unsorted data is allowed; sorted data is allowed too.DSA28
Choice by choice
A · incorrect — Linear scanning permits unsorted data.
B · correct — Binary interval elimination needs sorted order.
C · correct — Interpolation index estimation also needs sorted input.
D · incorrect — DFS follows graph connections and has no sorted-array requirement.
Question 177
Which searching algorithm works by comparing the target value with elements from the
beginning of the array until a match is found?
A. Linear search
B. Binary search
C. Interpolation search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Linear search starts at the beginning and compares successive elements until a match or exhaustion. Binary search instead chooses a midpoint of an ordered interval, and interpolation search estimates a position from endpoint key values. Depth-first search follows an unvisited graph branch before returning. These positive procedural differences classify the alternatives without any appeal to an old module’s omissions, so A remains the definite matching choice.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted.DSA28
Compute mid=lo+(hi-lo)//2.DSA29
Interpolation search estimates the index from numeric values: lo+(hi-lo)×(key-A[lo])/(A[hi]-A[lo]), rounded to a valid index.DSA30
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours.DSA42
Choice by choice
A · correct — Linear search compares successive elements from the beginning.
B · incorrect — Binary search probes a midpoint rather than scanning every successive position.
C · incorrect — Interpolation search estimates a probe position from endpoint values.
D · incorrect — DFS follows graph adjacency and unfinished branches rather than a beginning-to-end array scan.
Question 178
Which searching algorithm is more efficient for uniformly distributed data in a sorted array?
A. Linear search
B. Binary search
C. Interpolation search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: C — Interpolation search under the stated uniform-data model.
DSA30 gives interpolation search expected O(log log n) probes on sorted, suitably uniform numeric data. Binary search has logarithmic worst-case probes without that distribution assumption, while linear search scans. The stem supplies the distribution and sortedness conditions that motivate interpolation. The expected advantage does not promise faster finite runs or logarithmic worst-case behavior on arbitrary distributions.
Evidence in the complete study note
Interpolation search estimates the index from numeric values: lo+(hi-lo)×(key-A[lo])/(A[hi]-A[lo]), rounded to a valid index. Guard equal endpoints and out-of-range targets. On sorted, suitably uniform data its expected probes can be O(log log n); pathological distributions can require linear time. Binary search gives a logarithmic worst bound without that distribution assumption.DSA30
Choice by choice
A · incorrect — Linear search still examines successive elements and does not exploit uniform numeric distribution for sublinear expected probing.
B · incorrect — Binary search gives logarithmic worst-case probing, but does not exploit uniform values for the stated expected advantage.
C · correct — Interpolation estimates positions from uniformly distributed sorted numeric values, supporting the note’s expected O(log log n) probes.
D · incorrect — DFS explores graph or tree branches and is not the distribution-based ordered-array search described here.
Question 179
Which named algorithms explore a graph or tree by following adjacency links to unvisited vertices, using branch-first or distance-layer-first traversal? Select all that apply.
A. Linear search
B. Binary search
C. Depth-first search
D. Breadth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): C, D — C. Depth-first search; D. Breadth-first search
DFS explores an unvisited branch before returning to later neighbors, using recursion or a stack. BFS instead processes a FIFO frontier so successive distance layers are explored in order. Both follow adjacency relationships and apply to trees as well as general graphs. Linear sequence scanning and binary interval search are different algorithms and do not implement these two adjacency-frontier traversal disciplines.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · incorrect — Linear sequence search does not implement the specified adjacency-frontier traversal.
B · incorrect — Binary search eliminates ordered interval halves rather than following arbitrary adjacency.
C · correct — DFS is branch-first adjacency traversal.
D · correct — BFS is distance-layer-first adjacency traversal.
Question 180
Under a uniform random permutation of distinct keys, which ordinary sorting algorithms have tight average time Theta(n log n)? Use fixed-position-pivot quicksort, buffered mergesort without merge-skipping, and standard bubble/insertion implementations. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): B, C — B. Quick sort; C. Merge sort
The random-order model supplies the average-case assumption needed for ordinary quicksort’s expected n log n work. Buffered mergesort performs n log n work across input orders, so its average has the same order. Bubble and insertion have quadratic ordinary average behavior under this random permutation model. Tight bounds and the stated distribution make quicksort and mergesort the complete selection, rather than leaving average cost unspecified. The DSA31 comparison table supplies the average-case entries used in this comparison.
Evidence in the complete study note
n log n / n log n / n²DSA31
n / n² / n²DSA31
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Choice by choice
A · incorrect — Ordinary bubble sorting has quadratic random-order average work.
B · correct — The stated random-input model gives quicksort expected n log n work.
C · correct — Buffered mergesort has n log n work in every input order.
D · incorrect — Ordinary insertion has quadratic random-order average work.
Question 181
Which sorting algorithm works by repeatedly selecting the smallest element from the
unsorted portion and placing it at the beginning?
A. Bubble sort
B. Quick sort
C. Selection sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The source selection sort scans for the smallest remaining element and swaps it with the current first unsorted position. Evidence: assigned PDF pages 3, 4, 11.
Evidence in the complete study note
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls.DSA33
Choice by choice
A · incorrect — Bubble pushes elements through adjacent swaps. See assigned PDF 3, 4, 11, 3.
B · incorrect — Quicksort partitions by a pivot, not necessarily the minimum. See assigned PDF 3, 4, 11, 3.
C · correct — Exactly the minimum-selection and placement procedure given. See assigned PDF 3, 4, 11, 3.
D · incorrect — Insertion places the next encountered element into a sorted prefix. See assigned PDF 3, 4, 11, 3.
Question 182
Which ordinary array sorting algorithms are comparison sorts that use constant extra element storage inside the original array? Count recursive call stacks separately from element storage; use buffered mergesort for C. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, B, D — A. Bubble sort; B. Quick sort; D. Insertion sort
Bubble sort swaps adjacent keys and insertion sort shifts a prefix while retaining one saved key. Quicksort partitions within the same array using constant extra element storage. Its recursive frames are counted separately under the explicitly stated convention. Buffered mergesort instead allocates a linear merge buffer. Therefore bubble, quick and insertion meet the element-storage definition, while a total-auxiliary-space question would need to account for quicksort’s stack as well.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
Quicksort normally rearranges in the same array but recursive storage can be linear in the worst case.DSA36
Ordinary array merging needs a linear auxiliary buffer.DSA37
Choice by choice
A · correct — Bubble compares and swaps within the original array.
B · correct — Quicksort partitions in the array; its recursive stack is separately counted.
C · incorrect — Buffered mergesort needs linear extra element storage.
D · correct — Insertion compares and shifts within the original array with one saved key.
Question 183
Which searching algorithm requires the input array to be sorted?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA29 defines binary search over an ascending random-access sequence and reverses comparisons for descending data. Sortedness makes the half-elimination step sound. Linear scanning works without order; hashing needs a built table rather than sorted positions; DFS follows adjacency. Only Binary search among this option set requires a sorted input sequence for its ordinary operation.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.DSA25
Choice by choice
A · incorrect — Linear search explicitly permits unsorted data and compares items one after another.
B · correct — Binary search relies on ordered values to determine which half can still contain the target.
C · incorrect — Hash lookup needs a hash-table organization, not values arranged in sorted-array order.
D · incorrect — Depth-first search follows graph or tree adjacency and does not require a sorted input array.
Question 184
Which searching algorithm has a worst-case time complexity of O(log n)?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: B — Binary search has logarithmic worst-case time.
DSA29 bounds binary-search probes by floor(log₂n)+1 on nonempty random-access input. This supplies logarithmic worst-case time under constant-cost comparisons. Linear search may scan all items; adverse hash collisions may require linear work; DFS can inspect all vertices and edges. Their ordinary worst cases do not share binary search’s logarithmic bound.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
Choice by choice
A · incorrect — Linear search can inspect every item when the target is absent or last, giving linear worst-case time.
B · correct — Each comparison discards about half the ordered interval, giving logarithmic worst-case probes.
C · incorrect — Ordinary hash lookup can degrade to linear time under adverse collisions, despite expected constant-time performance.
D · incorrect — DFS may visit all graph vertices and edges, rather than guarantee logarithmic worst-case work.
Question 185
Which search compares a target with consecutive sequence elements at a fixed stride of one, stopping at the first match or after exhausting the sequence? No hashing or other preprocessing is used.
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
The stated unit stride means the algorithm inspects successive elements in order. It stops early when a comparison matches or reports failure after the sequence is exhausted, which is linear search. Binary search uses a shrinking midpoint interval rather than consecutive positions. Hash search starts from computed addresses, and DFS follows graph adjacency. Specifying stride one distinguishes ordinary scanning from larger-step jump-search interpretations.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.DSA25
Choice by choice
A · correct — Linear search compares successive elements until a match or exhaustion.
B · incorrect — Binary search chooses midpoints rather than every consecutive element.
C · incorrect — Hash search uses computed addresses rather than the stated scan.
D · incorrect — DFS follows graph adjacency rather than consecutive sequence positions.
Question 186
Which searching algorithm is suitable for unsorted arrays or lists?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: A — Linear search directly searches an unsorted sequence.
DSA28 explicitly allows unsorted data for linear search: compare successive elements until the target is found or the sequence ends. Binary search requires sortedness. Hash lookup can be useful after building a table, but it does not directly search the supplied ordinary list without that preprocessing. DFS presumes graph or tree adjacency rather than a simple sequence query.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.DSA25
Choice by choice
A · correct — Linear search can inspect an unsorted array or list directly without sorting or building another structure.
B · incorrect — Binary search needs ordering to safely eliminate half the remaining candidate positions.
C · incorrect — Hash search needs a constructed hash table; the stem supplies an ordinary unsorted array or list.
D · incorrect — DFS explores graph or tree adjacency and is not the direct unsorted-sequence scan described here.
Question 187
Which searching algorithm is commonly used for traversing graphs or trees?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA42 describes marking a vertex and recursively visiting each unmarked neighbor before resuming later neighbors. That procedure is standard depth-first traversal and applies to graphs and trees. Linear search scans a sequence, binary search uses an ordered interval, and hash search queries table addresses. None of those alternatives names the adjacency-following traversal in this option set.
Evidence in the complete study note
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Choice by choice
A · incorrect — Linear search scans sequence elements and is not the named adjacency-following graph/tree traversal.
B · incorrect — Binary search reduces an ordered interval rather than visiting arbitrary graph or tree connections.
C · incorrect — Hash search probes key-derived table addresses rather than traversing graph or tree edges.
D · correct — DFS follows unvisited neighbors recursively or through an explicit stack, providing a standard traversal.
Question 188
Which specified sorting implementations are stable? Use strict adjacent swaps for bubble, ordinary in-place quicksort, left-first merge ties, and insertion shifts of strictly larger keys only. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, C, D — A. Bubble sort; C. Merge sort; D. Insertion sort
Bubble sort’s strict adjacent swaps do not exchange equal keys. Mergesort preserves ties by taking an equal key from the left run first. Insertion sort shifts only strictly larger keys, leaving equal earlier keys ahead of the inserted one. Those three mechanisms preserve relative equal-key order. Ordinary in-place quicksort does not guarantee it because partition exchanges can move equal records past one another.
Evidence in the complete study note
Strict swaps preserve equal-key order.DSA32
Shift only strictly larger keys for stability.DSA34
With left-first tie handling, equal keys retain order.DSA37
stack usually log n average, n worst; unstableDSA31
Choice by choice
A · correct — Strict adjacent swaps preserve ties.
B · incorrect — Ordinary quicksort does not guarantee equal-key order.
C · correct — Left-first equal-key merging preserves ties.
D · correct — Shifting only larger keys leaves equal earlier keys in place.
Question 189
Which sorting algorithm is commonly used for small input sizes or partially sorted arrays?
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA34 explicitly favors insertion for small arrays or few inversions. Each inversion corresponds to shifting work, so nearly sorted data requires few shifts; sorted input is linear. This low-setup incremental algorithm is the conventional match among the choices. The other algorithms can sort these inputs, but their mere applicability does not identify the specific use case emphasized in the note.
Evidence in the complete study note
Few inversions mean few shifts, favouring insertion for nearly sorted or small arrays. Shift only strictly larger keys for stability. A linked implementation saves array shifts but still must locate each insertion position.DSA34
Choice by choice
A · incorrect — Bubble can exploit early stopping but is not the note’s specific small-array/few-inversions recommendation.
B · incorrect — Quicksort incurs partition and recursive setup and is not the cited small-subarray method.
C · incorrect — Ordinary merge sorting uses its merge levels and buffer even on nearly sorted input.
D · correct — Insertion has low setup and few shifts on nearly sorted or small arrays.
Question 190
Which searching algorithm divides the search space into three parts at each step?
A. Linear search
B. Binary search
C. Ternary search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA30 explicitly describes sorted-array ternary search as comparing two split points and retaining the relevant third. The three candidate regions give the technique its name. Binary search uses one midpoint and two regions, linear search scans successively, and DFS explores graph branches. Thus Ternary search uniquely matches the described three-part split.
Evidence in the complete study note
Sorted-array ternary search compares two split points and keeps the relevant third, still logarithmic. Jump search probes block boundaries then scans within a block. Regular intervals could mean unit-step scanning or larger jumps. Interpolation also needs sortedness, so prerequisite questions can overlap binary search.DSA30
Choice by choice
A · incorrect — Linear search advances through successive items and does not divide the remaining interval into thirds.
B · incorrect — Binary search uses one midpoint and retains one of two halves, not one of three regions.
C · correct — Ternary search uses two split points to divide the ordered search interval into three candidate parts.
D · incorrect — DFS explores graph or tree branches rather than repeatedly trisecting an ordered search interval.
Question 191
Which ordinary array sorting implementations use O(1) total auxiliary space in both best and average cases? Count live recursive frames; use recursive quicksort without tail-call elimination and buffered mergesort. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, D — A. Bubble sort; D. Insertion sort
The DSA31 table gives bubble and insertion constant extra storage across input cases. Their iterative forms retain only a fixed number of indices and temporaries, so total auxiliary space stays constant. The same table gives ordinary recursive quicksort a logarithmic average stack, and buffered mergesort needs a linear auxiliary array. Counting all live frames and buffers therefore leaves exactly bubble and insertion as the qualifying choices.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right.DSA32
For each remaining item, save its value, shift larger preceding values right, and insert it into the gap.DSA34
stack usually log n average, n worst; unstableDSA31
Ordinary array merging needs a linear auxiliary buffer.DSA37
Choice by choice
A · correct — Bubble uses fixed temporary storage across cases.
B · incorrect — The recursive quicksort stack is not constant in its ordinary average case.
C · incorrect — Buffered mergesort uses linear auxiliary storage.
D · correct — Insertion needs a saved key and fixed-size indices.
Question 192
Which searching algorithm is based on the principle of divide-and-conquer?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
DSA29 compares the middle value with the target and continues only in the half that can contain it. This solves a smaller instance of the same ordered-search problem and is the divide-and-conquer reduction intended here. Linear scanning removes one candidate at a time, hashing computes addresses, and DFS follows adjacency without this ordered half-elimination rule.
Evidence in the complete study note
Divide and conquer reduces a problem to smaller instances of the same kind, solves the required smaller instances and obtains the original result from them. Mergesort recursively sorts two halves and merges; quicksort partitions and recursively sorts the resulting ranges. This course also classifies binary search as divide and conquer: an ordered comparison selects the only half that can contain the target. This is different from simply repeating adjacent swaps, choosing successive minima, or making stable LSD digit passes.DSA-S04
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Choice by choice
A · incorrect — Linear search scans successive candidates rather than repeatedly solving a half-size ordered-search instance.
B · correct — Binary search divides the ordered interval and continues in the only half that can contain the target.
C · incorrect — Hash search derives an address and resolves collisions rather than recursively dividing an ordered problem.
D · incorrect — DFS follows adjacency branches and does not inherently apply the ordered half-elimination strategy described here.
Question 193
Which sorting algorithm has the worst-case time complexity of O(n log n)?
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Ordinary merge combines n items over log n levels, giving n log n even in the worst case. The other offered algorithms have quadratic adverse-input work. Evidence: assigned PDF pages 4, 11, 3.
Evidence in the complete study note
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work.DSA36
Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Choice by choice
A · incorrect — Bubble can perform quadratic passes/exchanges. See assigned PDF 4, 11, 11, 3.
B · incorrect — Quicksort is explicitly quadratic in the worst case. See assigned PDF 4, 11, 11, 3.
C · correct — Merge is explicitly n log n. See assigned PDF 4, 11, 11, 3.
D · incorrect — Reverse-order insertion requires quadratic movement. See assigned PDF 4, 11, 11, 3.
Question 194
Which sorting algorithm is efficient for sorting data in external memory (hard disks)?
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: C — Merge sort using buffered external runs.
DSA37 describes external sorting by building sorted runs and merging buffered disk streams to reduce I/O. Merge sort naturally supports that strategy even when the whole dataset does not fit RAM. Bubble and insertion sorting repeatedly move local data, while ordinary quicksort assumes partition access rather than the external sequential-run pattern specified here.
Evidence in the complete study note
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively. In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant. Internal sorting fits the working dataset in memory. External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.DSA37
Choice by choice
A · incorrect — Bubble sort’s repeated adjacent passes do not provide the buffered sorted-run strategy used for efficient external sorting.
B · incorrect — Ordinary quicksort partitioning is not the sequential buffered-run merging strategy identified for external data here.
C · correct — Merge sorting combines buffered sorted runs sequentially and is directly suited to disk-backed external sorting.
D · incorrect — Insertion sort’s repeated local insertion work does not provide the note’s efficient external-run merging mechanism.
Question 195
A large dataset has an equality-key index implemented by a hash table with suitable key distribution and bounded load. No ordered or range queries are needed. Which listed search uses this index for expected constant-time lookup?
A. Linear search
B. Binary search
C. Hash search
D. Depth-first search
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Hash lookup computes a bucket or probe start from the key and uses the existing index to locate an equality match. With suitable distribution and bounded load, the note gives expected constant lookup. The important assumptions are the index and workload, rather than dataset size alone. Linear scanning ignores the index, binary search needs an ordered interval, and DFS follows graph relationships instead of this equality-key access structure.
Evidence in the complete study note
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.DSA27
Choice by choice
A · incorrect — A scan can inspect linearly many records and does not use the hash index.
B · incorrect — Binary search uses an ordered interval rather than this index.
C · correct — Hash search uses the stated index with expected constant lookup.
D · incorrect — DFS follows graph connections rather than the equality-key index.
Question 196
For a uniform random permutation of distinct keys, which listed ordinary algorithms have the smallest tight average-case growth order? Use fixed-position-pivot quicksort, buffered mergesort without merge-skipping, and standard bubble/insertion. Select all algorithms tied for the smallest order.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Insertion sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): B, C — B. Quick sort; C. Merge sort
Under the stated random-input model, ordinary quicksort has expected n log n work. Buffered mergesort performs n log n work in every order, so its average shares that order. Bubble and insertion have quadratic average work on random permutations. Quicksort and mergesort therefore tie for the smallest asymptotic average order among these options; the question does not ask for a measured running-time ranking between the tied methods. The DSA31 comparison table supplies the average-case entries used in this comparison.
Evidence in the complete study note
n log n / n log n / n²DSA31
n / n² / n²DSA31
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.DSA37
Choice by choice
A · incorrect — Quadratic average growth is larger than n log n.
B · correct — Expected n log n ties for the smallest listed average growth.
C · correct — n log n across orders ties for the smallest listed average growth.
D · incorrect — Quadratic average growth is larger than n log n.
Question 197
Which data structure is best suited for implementing a dictionary with fast lookup and
insertion?
A. Array
B. Linked list
C. Hash table
D. Stack
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answer: C — Hash table for expected fast dictionary lookup and insertion.
DSA27 explicitly names hashing as a dictionary implementation with expected constant lookup. DSA26 qualifies this by a suitable distribution and controlled load; insertion is likewise expected fast under those conditions. Arrays and linked lists lack the same ordinary key-lookup performance, while a stack specifies LIFO access. This is an expected-performance recommendation, not a universal worst-case guarantee.
Evidence in the complete study note
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.DSA27
Choice by choice
A · incorrect — An ordinary array lacks key-derived lookup and may require scanning or maintaining a sorted order with costly insertions.
B · incorrect — An ordinary linked list needs traversal to locate an arbitrary dictionary key, giving linear worst-case lookup.
C · correct — A well-sized hash table offers expected fast key lookup and insertion under suitable hashing and load assumptions.
D · incorrect — A stack exposes LIFO top operations and does not directly provide efficient arbitrary-key dictionary lookup.
Question 198
Which listed algorithm guarantees shortest paths from one source to all reachable vertices for arbitrary graphs with nonnegative edge weights that may differ? Compare the standard forms of the listed algorithms.
A. Depth-first search
B. Breadth-first search
C. Dijkstra's algorithm
D. Prim's algorithm
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Standard Dijkstra repeatedly finalizes the unsettled vertex with the smallest tentative distance and relaxes its outgoing edges. Nonnegative edge weights justify this shortest-path procedure even when different edges have different costs. BFS minimizes edge count and is sufficient when edge costs are equal, which is weaker than the stated guarantee. DFS supplies reachability paths, while Prim minimizes total spanning-tree cost rather than source-to-vertex route lengths.
Evidence in the complete study note
For nonnegative weights, standard Dijkstra initializes source distance zero and others infinity, repeatedly finalizes the unsettled vertex with smallest distance, and relaxes each outgoing edge: dist[v]=min(dist[v],dist[u]+w(u,v)). A min-priority queue supports the next choice. BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford.DSA43
BFS finds minimum-edge paths in unweighted graphs, not arbitrary minimum-weight paths.DSA41
Choice by choice
A · incorrect — A DFS path need not have minimum total weight.
B · incorrect — BFS minimizes edge count and does not guarantee minimum weight for arbitrary differing costs.
C · correct — Dijkstra guarantees source shortest paths under nonnegative weights.
D · incorrect — Prim solves the spanning-tree objective rather than source shortest paths.
Question 199
Which listed standard representations directly implement stack push/pop at an array top or linked-chain head, without simulating LIFO through another ADT? Select all that apply.
A. Array
B. Linked list
C. Queue
D. Tree
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, B — A. Array; B. Linked list
The array representation maintains a top index and changes it when pushing or popping. The linked representation inserts and removes at the chain head, so the latest node is also the next one removed. Both directly implement LIFO with ordinary constant endpoint operations. A queue has FIFO service, while a generic tree has no stack-top contract; emulations through those ADTs are outside this representation question.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Arrays or linked nodes can implement the same LIFO stack.DSA01
Choice by choice
A · correct — An array with a top index directly implements stack operations.
B · correct — A linked chain with head insertion/removal directly implements stack operations.
C · incorrect — An ordinary FIFO queue is not a direct stack representation.
D · incorrect — A generic tree does not supply the specified stack-top representation.
Question 200
Given a consistent comparator on a priority field, which listed comparison sorting algorithms can sort records by that field? No particular extraction mechanism or equal-priority stability is required. Select all that apply.
A. Bubble sort
B. Quick sort
C. Merge sort
D. Heap sort
Hint / Module Reference (Where to Read)
Compare the algorithmic steps and access policy with the exact resource or ordering requirement in the question.
Correct answers (select all): A, B, C, D — A. Bubble sort; B. Quick sort; C. Merge sort; D. Heap sort
Priority is a key field that any comparison sort can use through a consistent comparator. Bubble compares neighboring priorities, quicksort partitions by priority, mergesort combines priority-ordered runs, and heapsort repeatedly places a priority extreme. Since no heap-extraction mechanism or tie-stability condition is required, every listed algorithm can produce the requested priority ordering. Priorities alone do not identify one unique sorting method.
Evidence in the complete study note
It is not uniquely the method for sorting by priorities: any comparison sort can compare a priority field. Heap extraction is its distinctive mechanism.DSA38
Choice by choice
A · correct — Bubble can compare adjacent priority fields.
B · correct — Quicksort can partition with the priority comparator.
C · correct — Mergesort can merge runs by the priority field.
D · correct — Heapsort can extract priority extremes.
Question 201
An LRU cache already has hash lookup that returns a reference to the matching entry. Which listed representation should maintain recency order so a known entry can be removed and moved to the recent end in constant time, with eviction at the least-recent end?
A. Array
B. Doubly linked list with head and tail
C. Hash table
D. Queue
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Correct answer: B — B. Doubly linked list with head and tail
The hash index handles locating an entry, while the recency component must unlink a known entry and reconnect it at the recent end. A doubly linked list supplies both neighboring links for that constant-time removal and maintains endpoints for movement and eviction. An array would generally shift entries, a bare hash table does not supply recency order, and an ordinary FIFO queue cannot remove an arbitrary known interior entry.
Evidence in the complete study note
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.DSA27
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
Choice by choice
A · incorrect — Maintaining array recency order generally requires shifts.
B · correct — A doubly linked recency list supports unlinking a known node and endpoint updates.
C · incorrect — The existing hash index handles lookup but does not itself maintain LRU order.
D · incorrect — An ordinary queue lacks arbitrary known-interior-node removal.
Question 202
Which algorithm is used to find the maximum subarray sum in an array?
A. Binary search
B. Quick sort
C. Merge sort
D. Kadane's algorithm
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA44 directly identifies Kadane as the contiguous maximum-sum-subarray algorithm. It updates the best sum ending at the current item and the best sum seen overall, using linear time and constant working storage. Binary search does not optimize contiguous sums, and quicksort or merge sort reorder values rather than preserve the original adjacency needed by this problem.
Evidence in the complete study note
Kadane’s algorithm finds a contiguous maximum-sum subarray. For a required nonempty answer, initialize ending=best=A[0]; update ending=max(x,ending+x), then best=max(best,ending). It is linear time with constant working storage. Initializing best=0 instead silently allows an empty answer and fails the nonempty all-negative case.DSA44
Choice by choice
A · incorrect — Binary search locates targets or ordered boundaries; it does not compute a contiguous maximum-sum subarray.
B · incorrect — Quicksort reorders values and does not preserve the original adjacency required for maximum subarray sum.
C · incorrect — Merge sort orders values; the named sorting algorithm is not the maximum-subarray recurrence.
D · correct — Kadane maintains the best sum ending here and the best anywhere, directly solving the stated problem.
Question 203
Which data structure is commonly used to implement a graph?
A. Array
B. Linked list
C. Hash table
D. Adjacency list
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA40 describes adjacency lists as storing each vertex’s neighbors in Θ(V+E) space. This names a complete graph representation among the choices. Arrays, linked lists, or maps may store parts of a representation, but those container names alone do not specify how vertices and their edges are encoded. The answer identifies the graph-specific organization.
Evidence in the complete study note
A matrix uses Theta(V²) space and constant edge lookup. Adjacency lists use Theta(V+E) space and enumerate neighbours. Dense simple graphs approach quadratic edge counts. Examining every edge costs more on denser graphs; vertex-only operations need not inspect every edge.DSA40
Choice by choice
A · incorrect — An array can store a matrix or adjacency containers, but its name alone does not specify a graph representation.
B · incorrect — A linked list can hold neighbor records, but alone does not describe the vertex-to-neighbor organization.
C · incorrect — Hash tables may index vertices or neighbors, but do not by themselves name the graph representation supplied here.
D · correct — An adjacency list explicitly associates vertices with their neighbors and is a standard graph representation.
Question 204
Which algorithm is used to find the minimum spanning tree in a graph?
A. Depth-first search
B. Breadth-first search
C. Dijkstra's algorithm
D. Prim's algorithm
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA43 defines an MST as a minimum-total-cost connection of all vertices in a connected undirected weighted graph. Prim repeatedly adds the cheapest edge crossing from its current tree to an outside vertex. Dijkstra minimizes source-path distances instead, while BFS and DFS are traversals without a general minimum-weight spanning-tree guarantee. Thus Prim is the listed MST algorithm.
Evidence in the complete study note
An MST minimizes the total cost of connecting all vertices of a connected undirected weighted graph. Prim adds the cheapest edge crossing from its current tree to an outside vertex. Kruskal processes edges by increasing weight and rejects those joining vertices already connected. An MST need not give shortest source-to-vertex routes, and equal weights can permit several MSTs.DSA43
For nonnegative weights, standard Dijkstra initializes source distance zero and others infinity, repeatedly finalizes the unsettled vertex with smallest distance, and relaxes each outgoing edge: dist[v]=min(dist[v],dist[u]+w(u,v)). A min-priority queue supports the next choice. BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford.DSA43
Choice by choice
A · incorrect — DFS can produce a spanning tree but does not generally minimize total edge weight.
B · incorrect — BFS produces minimum-edge source layers in unweighted graphs, not a general minimum-weight spanning tree.
C · incorrect — Dijkstra minimizes source-to-vertex distances, a different objective from total spanning-tree connection cost.
D · correct — Prim grows a spanning tree by repeatedly choosing a cheapest edge crossing to an outside vertex.
Question 205
A priority queue needs O(1) peek and O(log n) worst-case insertion and extraction for an interleaved workload. Compare ordinary sorted/unsorted array and linked-list implementations, a binary heap, and an unmodified FIFO queue; exclude representations with extra search indexes. Which meets all requirements?
A. Array
B. Linked list
C. Binary heap
D. Queue
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
A binary heap exposes the extreme key at its root, so peek is constant, and insertion or extraction restores order along a logarithmic-height path. Ordinary unordered arrays or lists need a linear search for an extreme, while ordered versions pay linear insertion in the general case. An unmodified FIFO queue follows arrival order rather than priority. The stated operation bounds make the heap the unique matching standard representation.
Evidence in the complete study note
A priority queue returns the smallest or largest priority key under its convention. Urgent patients may precede earlier arrivals. Insertions and extractions can interleave. Binary heaps support constant peek and logarithmic insert/extract.DSA17
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff. Equal priorities have no inherent FIFO guarantee. If stable service is required, compare (priority, arrival_counter). Choose the priority direction and tie rule before tracing.DSA17
Choice by choice
A · incorrect — Ordinary ordered/unsorted arrays trade linear insertion against linear extremum selection.
B · incorrect — Ordinary lists likewise have a linear cost in one required operation.
C · correct — A binary heap provides constant peek and logarithmic insertion/extraction.
D · incorrect — An unmodified queue serves FIFO rather than priority order.
Question 206
Which algorithm is commonly used for pattern matching in strings?
A. Depth-first search
B. Breadth-first search
C. Dijkstra's algorithm
D. Knuth-Morris-Pratt algorithm
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA44 explicitly defines KMP as finding a pattern inside text. It preprocesses longest proper prefix/suffix lengths and uses them to avoid restarting comparisons after mismatch, giving linear combined pattern-and-text work. DFS, BFS, and Dijkstra concern graph exploration or paths, rather than this specialized substring-matching mechanism. KMP uniquely matches the question among these choices.
Evidence in the complete study note
Knuth–Morris–Pratt (KMP) finds a pattern inside text. Preprocess the pattern’s longest proper prefix that is also a suffix. After mismatch, fall back using those prefix lengths rather than restarting comparisons from the beginning; the text pointer need not move backward. Pattern preprocessing plus scanning takes O(pattern length+text length).DSA44
Choice by choice
A · incorrect — DFS explores graph or tree branches; it is not the substring-pattern algorithm identified in DSA44.
B · incorrect — BFS explores graph distance layers rather than applying prefix/suffix reuse for text matching.
C · incorrect — Dijkstra computes nonnegative weighted shortest paths, not substring pattern occurrences.
D · correct — KMP is the pattern-matching algorithm using preprocessed prefix/suffix lengths to avoid repeated text comparisons.
Question 207
Assume a very large finite key universe U but only n stored keys, with n much smaller than |U|. A hash table uses capacity proportional to n. Compare allocated storage, rather than unconditional speed. Which statement is false?
A. For n much smaller than |U|, the specified hash table uses less allocated storage than direct addressing.
B. Direct Address table doesn't use hash function to map keys
C. Hash table allocates one separate memory slot for each key in the universe U
D. There is one-to-one correspondence between keys in universe U and memory slots in the Direct Address table
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: C — C. Hash table allocates one separate memory slot for each key in the universe U
Direct addressing reserves a distinct slot for every possible key in the universe, whether present or absent, so its storage is proportional to |U|. The specified hash table stores the actual entries plus capacity proportional to n. For this sparse-universe storage comparison, hashing uses less space. C incorrectly attributes the direct-address allocation rule to hashing, while direct key-to-slot mapping and separate universe slots accurately describe direct addressing.
Evidence in the complete study note
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.DSA25
Choice by choice
A · incorrect — Under the sparse-universe storage assumptions, the hash table uses fewer allocated slots.
B · incorrect — Direct addressing maps directly to a key’s universe slot without compressive hashing.
C · correct — One slot for every possible key describes direct addressing, not the specified hash table.
D · incorrect — Each universe key has a separate direct-address slot.
Question 208
What is the time complexity order of push() operation of Stack data structure implemented
using array?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
The fixed-array push checks fullness, increments top and stores one item. A bounded number of unit-cost operations independent of n gives O(1). Evidence: assigned PDF pages 6.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
A count-based alternative uses size=0 and A[size++]=x. Do not combine its empty/full tests with the top-index convention. Fixed-array push/pop are constant time. Linked stacks achieve constant time by inserting and deleting at the head; using a singly linked tail for pop would require a predecessor traversal.DSA11
Choice by choice
A · incorrect — Linear would require scanning or copying that the given push does not do. See assigned PDF 6.
B · incorrect — Logarithmic would require a search/adjustment absent from push. See assigned PDF 6.
C · incorrect — Quadratic has no nested work in this code. See assigned PDF 6.
D · correct — Only a fullness test, index increment and one assignment are performed. See assigned PDF 6.
Question 209
A zero-based six-slot hash table uses h(key)=key%6. What home index does it compute for key 36, before any collision resolution?
A. At index 35
B. At index 1
C. At index 6
D. At index 0
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
The home address is obtained by applying the stated remainder function. Since 36 is exactly divisible by 6, the remainder is zero and the home index is 0. The question stops before collision resolution, so occupied slots cannot change this computed address. Index 1 could be a displaced location under some probing state, but it is not the function’s output; indices 6 and 35 are outside the table.
Evidence in the complete study note
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.DSA25
Choice by choice
A · incorrect — 35 is outside the valid zero-based range 0–5.
B · incorrect — 1 is not the remainder of 36 divided by 6.
C · incorrect — 6 is outside the valid range and is not a possible remainder modulo 6.
D · correct — 36%6 equals 0.
Question 210
Which method can resolve collision in hashed files by proceeding from the occupied position
specified by the hash address and checking subsequent positions until an empty position is found?
A. Open addressing
B. Multiple hashing
C. Chaining
D. Cluster indexing
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: A — Open addressing, specifically linear probing.
DSA26 defines open addressing as keeping entries within the array and probing until an available slot is found. Checking successive positions is its linear-probing form. Multiple hashing changes probe steps, chaining stores collisions in bucket lists, and cluster indexing is not this insertion procedure. Therefore Open addressing is the matching general method among the options.
Evidence in the complete study note
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
Linear probing tries (h(k)+j)%m. For size 7 and keys 10,17,24, all home addresses are 3 and occupied positions become 3,4,5. Quadratic probing changes the step; double hashing uses h1(k)+j h2(k), modulo m, with a step relatively prime to m to cover all slots. Neither method guarantees no collisions. Deletion needs tombstones or reinsertion so searches do not stop prematurely.DSA26
Choice by choice
A · correct — Open addressing searches alternative table positions; checking successive positions is its linear-probing form.
B · incorrect — Multiple or double hashing derives another probe step rather than the stated simple successive-slot scan.
C · incorrect — Chaining puts colliding entries in a bucket list instead of searching successive array slots.
D · incorrect — Cluster indexing does not name the collision insertion strategy described by the successive-position probing rule.
Question 211
Which one of the following is true about tree data structure?
A. Tree is a static data structure
B. Tree is a linear data structure
C. Tree forms a cycle — in other words tree is a cyclic data structure
D. There is only one unique path when we traverse from one node to another node in a tree
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: D — There is only one unique path when we traverse from one node to another node in a tree
A rooted tree gives every nonroot node exactly one parent and a unique root path. Between any two nodes, ascend to their common ancestor and descend; a second distinct path would create a cycle and violate the parent/path hierarchy. Evidence: assigned PDF pages 9, 2.
Evidence in the complete study note
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children.DSA18
Choice by choice
A · incorrect — The pointer-based tree representation does not require static size. See assigned PDF 9, 2, 9.
B · incorrect — The source explicitly classifies trees as nonlinear. See assigned PDF 9, 2, 9.
C · incorrect — A cycle contradicts the unique-path hierarchy. See assigned PDF 9, 2, 9.
D · correct — The rooted hierarchy gives one unique connecting path for every node pair. See assigned PDF 9, 2, 9.
Question 212
For an unordered heap record file without an ordered index or a maintained sorted copy, which statement is not correct? Ordinary insertion uses available storage rather than maintaining field order.
A. Sorting is required to read records in particular field order
B. Linear search can be used to search a necessary record
C. Record insertion is efficient
D. New records are inserted at the beginning of the file
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: D — D. New records are inserted at the beginning of the file
A heap file does not maintain record order by a chosen field. With no ordered index or sorted copy, ordered output therefore requires sorting; an ordinary scan can locate a record, and insertion can place a record in available storage. Nothing requires new records to be inserted at the beginning of the file. D is the incorrect claim, while the explicit no-index scope makes A’s ordering requirement appropriate.
Evidence in the complete study note
Specify whether a question asks which structure can implement something or which is best under stated costs. ADTs do not force one representation, and serial-access memory is not inherently LIFO. A heap file is an unordered database record file, unrelated to a binary heap: insertion uses available space, scanning can find records, and ordered output requires sorting or an index. It need not insert at the beginning.DSA45
Choice by choice
A · incorrect — Under the specified no-index/no-sorted-copy scope, field-ordered output requires ordering the records.
B · incorrect — A linear scan can search unordered records.
C · incorrect — Using available storage avoids maintaining a sorted record sequence during insertion.
D · correct — Heap-file insertion is not required to place every new record at the beginning.
Question 213
Which listed structures are linear in the course classification? Select all that apply.
A. Tree
B. Array
C. Queue
D. Linked list
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answers (select all): B, C, D — B. Array; C. Queue; D. Linked list
A linear structure arranges items along a sequence rather than through hierarchical branching. The note explicitly includes arrays, queues and linked lists in that category, giving three valid selections. A tree instead models a hierarchy and is classified as nonlinear. The select-all instruction allows every listed member of the linear category to be recognized rather than forcing an arbitrary single choice.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · incorrect — Trees model hierarchy rather than a linear sequence.
B · correct — Arrays are classified as linear.
C · correct — Queues are classified as linear.
D · correct — Linked lists are classified as linear.
Question 214
Which abbreviations name the stack service policy? Select all that apply.
A. LIFO
B. FIFO
C. FILO
D. FCFS
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answers (select all): A, C — A. LIFO; C. FILO
The most recently pushed item is removed first by a stack. This is last in, first out, abbreviated LIFO. Equivalently, the first item inserted remains until later items have been removed, making it first in, last out or FILO. FIFO and FCFS instead preserve arrival order in ordinary queue service. Both A and C therefore name the same stack discipline.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail.DSA14
Choice by choice
A · correct — LIFO means last in, first out.
B · incorrect — FIFO means first in, first out, an ordinary queue policy.
C · correct — FILO is the equivalent first in, last out view of a stack.
D · incorrect — FCFS describes arrival-order service rather than stack service.
Question 215
For ordinary binary search on a sorted random-access array of n elements, what is the tightest listed worst-case time bound? Count each indexed probe as constant work.
A. O(n (log n)²)
B. O(n²)
C. O(n)
D. O(log n)
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Binary search repeatedly removes roughly half of the remaining candidate interval. The note bounds its worst probes by floor(log₂n)+1 for nonempty input, giving logarithmic worst-case time under constant-cost indexing. The linear, quadratic and n-times-squared-log options all grow faster and are looser upper bounds. Explicitly asking for the tightest bound selects the logarithmic alternative rather than treating every valid Big-O upper bound as equally responsive.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · incorrect — n(log n)² is a much looser upper bound.
B · incorrect — Quadratic is a looser upper bound.
C · incorrect — Linear is a looser upper bound.
D · correct — Logarithmic matches the interval-halving probe growth.
Question 216
Which sorting algorithm compares each pair of adjacent elements from the beginning of
an array and, if they are in reversed order, swaps them; if at least one swaps has been
done, repeat step 1.
A. Insertion sort
B. Bubble sort
C. Selection sort
D. Shell sort
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: B — Bubble sort with early stopping
DSA32 describes adjacent comparisons, swapping strict inversions, and repeating passes until a pass performs no swaps. That matches every part of the stem, including its stopping condition. Insertion grows a sorted prefix, selection chooses a suffix minimum, and Shell uses separated gap subsequences, so none has this exact adjacent full-pass mechanism.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Choice by choice
A · incorrect — Insertion places each next value into a sorted prefix rather than repeating full adjacent passes.
B · correct — Adjacent inversion swaps and repetition until no swaps identify optimized bubble sort.
C · incorrect — Selection finds a suffix minimum and exchanges it with the prefix boundary.
D · incorrect — Shell sorts gap-separated subsequences before its final gap-one insertion pass.
Question 217
Among the following one is NOT the application of queue in the real world.
A. It is used in operating systems for handling interrupts.
B. It is used to maintain the play list in media players in order
C. It is used in Depth First search
D. It is widely used as waiting lists for a single shared resource
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: C — Depth-first search uses stack discipline rather than the ordinary queue.
DSA42 finishes a branch using a stack or recursion and explicitly says a queue changes that discipline. DSA14 gives FIFO waiting, play sequences, and asynchronous buffering as queue uses. Interrupt work can also be buffered pending service. Thus the standard DFS claim is the non-queue application among the offered ordinary examples.
Evidence in the complete study note
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
An interrupt service routine may need to record work quickly and defer its completion. Operating systems can queue that deferred work for later processing; Windows deferred procedure calls are one concrete example. This is a queue application, but it does not imply that every interrupt system uses a single FIFO service policy.DSA-S02
Choice by choice
A · incorrect — Pending interrupts can be buffered for later service; queue use need not imply one universal interrupt priority policy.
B · incorrect — A FIFO play queue can preserve the order of media items.
C · correct — Standard DFS uses latest-pending-work-first stack or recursion rather than FIFO queue service.
D · incorrect — Waiting for one shared resource is a direct FIFO queue application.
Question 218
Which data structure uses LIFO?
A. Queue
B. Array
C. Stack
D. Linked List
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA11 explicitly assigns LIFO to a stack. Arrays and linked lists can represent that stack, but neither storage structure inherently fixes its removal order. A queue instead supplies FIFO. The question asks for the service-policy ADT, so Stack is the specific answer rather than one of the possible underlying representations.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · incorrect — A queue follows FIFO, not the latest-in-first-out order requested.
B · incorrect — An array is a representation and does not inherently impose LIFO service.
C · correct — A stack is explicitly defined by LIFO, equivalently FILO.
D · incorrect — A linked list can implement several policies and does not inherently require LIFO.
Question 219
What distinguishes a dynamic data structure from a static one?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Dynamic structures can change size at runtime; static structures have fixed capacity.
DSA02 distinguishes fixed arrays from resizable arrays, and DSA08 allocates linked nodes as needed. Runtime growth or shrinkage is the key distinction; fixed capacity need not mean compile-time allocation.
Evidence in the complete study note
A fixed array has a chosen capacity; the choice need not occur at compile time. A resizable array allocates a larger block and copies when needed. Inserting in the middle shifts later elements, so it costs linear time. Appending into spare capacity is constant; a resizing append can be linear, though repeated geometric growth gives amortized constant append cost.DSA02
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Question 220
Which classification includes both Trees and Graphs?
A. Linear
B. Homogeneous
C. Non-linear
D. Static
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA01 treats arrays, lists, stacks, and queues as linear sequences, trees as hierarchies, and graphs as general connections. Trees and graphs therefore belong to the nonlinear relationship category. Homogeneity describes element types and static describes storage capacity; neither classifies both by their branching relationship structure. C is the appropriate shared category.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Choice by choice
A · incorrect — Linear describes sequence-like structures rather than branching trees and general graphs.
B · incorrect — Homogeneous concerns uniform element types and does not identify their relationship structure.
C · correct — Trees and graphs are nonlinear relationship structures, unlike the listed linear sequences.
D · incorrect — Static concerns storage or capacity decisions, not whether connections branch.
Question 221
In an ADT, what two components are always defined?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: An ADT defines its values/data and permitted operations.
DSA01 explicitly defines an abstract data type through values and operations, leaving representation to the implementation. The same LIFO stack can therefore use arrays or linked nodes without changing its contract.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Question 222
A structure in C that groups int, char, and float is an example of:
A. Homogeneous
B. Non-homogeneous
C. Linear
D. Static
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Correct answer: B — Non-homogeneous, or heterogeneous
DSA01 directly identifies a record grouping integer, character, and floating fields as heterogeneous. The different field types distinguish it from an ordinary same-element-type array. Linear describes relationships, and static describes storage behavior, neither of which follows merely from the field types. Thus Non-homogeneous is the requested classification.
Evidence in the complete study note
Arrays, linked lists, stacks and queues are linear. Trees model hierarchies; graphs model general connections. A record grouping integer, character and floating fields is heterogeneous; an ordinary array has one element type.DSA01
Choice by choice
A · incorrect — Homogeneous would mean a uniform element type, contrary to the mixed int, char, and float fields.
B · correct — The record combines different field types and is therefore heterogeneous or non-homogeneous.
C · incorrect — Linear concerns relationships or order, not the mixed-type classification asked here.
D · incorrect — Static concerns allocation or lifetime and is not established merely by these field types.
Question 223
What does abstraction in algorithms allow programmers to do?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Abstraction preserves relevant behavior and hides irrelevant implementation detail.
DSA01 illustrates abstraction using patient urgency and arrival order while ignoring hair colour. Programmers retain the data and operations needed for the task and separate that contract from representation details. This supports the substantive answer without additional facts.
Evidence in the complete study note
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.DSA01
Question 224
Which operation involves combining elements from two sorted sets into one sorted set?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA03 calls combining sequences merging and works through sorted inputs by repeatedly emitting the smaller current front. Advancing only the selected sequence preserves sorted output until the remaining suffix is appended. For mathematical sets, duplicate handling additionally follows the set contract.
Evidence in the complete study note
Traversal processes every item; searching locates a target; insertion and deletion change membership; updating changes a stored value. Sorting reorders items, while merging combines sequences. To merge sorted [1,4] and [2,3], repeatedly emit the smaller front, producing [1,2,3,4]. Destroying a structure releases owned storage.DSA03
A set forbids duplicate elements.DSA27
Question 225
What is the term for the operation that releases memory when a data structure is no longer needed?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Destruction or deallocation of owned storage.
DSA03 says destroying a structure releases owned storage. In a linked chain, DSA09 visits and releases each owned node; C++ allocation forms must be matched to their deletion forms, and freed nodes must not be dereferenced.
Evidence in the complete study note
A C struct groups named fields, including arrays and pointers. A singly linked node needs payload plus a same-type link. C fields cannot have initializers inside the type declaration; modern C++ permits default member initializers. In C++, match new with delete and new[] with delete[]. Repair links before freeing a node; never dereference it afterwards.DSA03
Deleting the tail of a singly linked list requires its predecessor, even when tail itself is known. Handle empty and single-node lists separately; after removing the only node, set both head and tail to null. To remove a known successor, bypass it before deallocation. Clearing an owned n-node chain visits and releases every node.DSA09
Question 226
Given T(n) = 6n + 4, what is the Big-O complexity?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
For n≥1, 6n+4≤10n, while 6n+4≥6n. These constant upper and lower multiples establish linear growth by DSA06. O(n) is the natural tightest-order response, though larger upper bounds also exist.
Evidence in the complete study note
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Question 227
Show why f(n) = 3n² + 4n + 1 is O(n²). What are the values of c and k?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
For every n≥1, 4n≤4n² and 1≤n², so 3n²+4n+1≤8n². DSA06 supplies the same inequality, proving the required eventual upper bound with c=8 and k=1. Other larger constants may also work.
Evidence in the complete study note
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Question 228
Which property of an algorithm ensures it terminates after a finite number of steps?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA04 defines finiteness as terminating after finitely many steps for every valid input. It is distinct from definiteness, executable instructions, or correctness: a terminating procedure can still return a wrong answer. The required concept is directly covered.
Evidence in the complete study note
Finiteness means termination after finitely many steps for every valid input. Definiteness means each instruction has one interpretation; effectiveness means each step is executable. Correctness means meeting the stated result for every valid input. A finite program can still return the wrong answer.DSA04
Question 229
An algorithm has exactly two independent nested loops. Each executes n iterations, and the innermost body performs constant work. Loop-control operations are constant time, with no early exits or hidden nonconstant operations. What is the tight time complexity as n grows?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
For each of the n outer iterations, the inner loop executes n times, so the constant-cost body runs n×n=n² times. Outer-loop overhead is linear and inner-loop control is also bounded by a constant per body execution. Those contributions do not change the dominant quadratic growth. Under the stated independence, fixed loop count and body-cost assumptions, the tight time complexity is Theta(n²).
Evidence in the complete study note
A loop i=1; i<n; i*=2 takes about log₂n iterations. Two independent n-iteration loops nested around constant work take Theta(n²). An n-level ordinary recursion with constant live storage per level needs Theta(n) stack space.DSA07
Time counts chosen operations; space counts memory, including live recursive frames. Distributed algorithms may also measure communication volume. A single assignment is one unit in the elementary model, not literally one second. Sequential blocks add costs; independent nested loops multiply their iteration counts. Conditional worst-case cost includes the test and the more expensive branch.DSA05
Question 230
Big-Theta (Θ) notation represents:
A. Upper bound only
B. Lower bound only
C. Both upper and lower bound
D. Average case only
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Correct answer: C — Both upper and lower asymptotic bounds.
DSA06 defines Big-O as an eventual upper bound, Omega as the reverse bound, and Theta as requiring both. Thus Theta expresses a tight growth class up to positive constants. It is independent of choosing best, average, or worst input cases; Average case only confuses the bound relation with an input-distribution choice.
Evidence in the complete study note
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Choice by choice
A · incorrect — An upper bound alone is Big-O and does not supply Theta’s lower requirement.
B · incorrect — A lower bound alone is Omega and does not supply Theta’s upper requirement.
C · correct — Theta requires simultaneous eventual upper and lower constant-factor bounds.
D · incorrect — Theta can describe any case or resource function, not only an average case.
Question 231
Which grows faster asymptotically: O(n log n) or O(n)?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Representative n log n grows faster than n; Big-O classes themselves overlap.
DSA06 orders representative rates with n before n log n. Their ratio is log n, which grows without bound, so the representative n log n rate grows faster. However an O(n) function is also O(n log n), so membership alone does not compare actual runtimes.
Evidence in the complete study note
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions.DSA06
Increasing representative rates: 1, log n, n, n log n, n², n³, 2^n, 3^n, n!, n^n. Logarithm bases differ only by a constant factor.DSA06
Question 232
What is the running time contribution of a single assignment statement according to analysis rules?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: One constant time unit in the elementary-operation model.
DSA05 explicitly treats a single assignment as one unit in an elementary model, not one physical second. The convention abstracts hardware and requires that evaluating the assigned expression itself be constant cost; complicated expressions need their own accounting.
Evidence in the complete study note
Time counts chosen operations; space counts memory, including live recursive frames. Distributed algorithms may also measure communication volume. A single assignment is one unit in the elementary model, not literally one second. Sequential blocks add costs; independent nested loops multiply their iteration counts. Conditional worst-case cost includes the test and the more expensive branch.DSA05
Question 233
State the Transitivity theorem of Big-O. Why is it useful?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: If f∈O(g) and g∈O(h), then f∈O(h); this composes upper bounds.
DSA06 composes the eventual inequalities f≤c g and g≤d h to obtain f≤cd h beyond both thresholds. Choose the larger threshold and multiply the positive witness constants. This lets a complicated bound pass through a simpler intermediate function.
Evidence in the complete study note
For n≥1, 3n²+4n+1≤8n²: c=8,k=1 witness O(n²). Constants and lower-order terms disappear from tight polynomial growth. Transitivity multiplies witnesses: f≤c g≤cd h beyond both thresholds.DSA06
Question 234
Rank from slowest to fastest growing: O(n²), O(1), O(2ⁿ), O(log n), O(n)
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Increasing representative growth: 1, log n, n, n², 2^n.
DSA06 gives the standard growth ordering, with constants below logarithms, then linear and quadratic functions, then exponential. The ranking compares representative rates, not disjoint Big-O classes, since loose upper bounds overlap.
Evidence in the complete study note
Increasing representative rates: 1, log n, n, n log n, n², n³, 2^n, 3^n, n!, n^n. Logarithm bases differ only by a constant factor.DSA06
Question 235
What are the three main resources considered in algorithm analysis?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Time, memory space, and—in distributed settings—communication volume.
DSA05 measures operation counts and live memory, and adds communication volume for distributed algorithms. Thus the third resource is context-dependent rather than a universal resource needed by every local algorithm. These are the three supported categories in the note.
Evidence in the complete study note
Time counts chosen operations; space counts memory, including live recursive frames. Distributed algorithms may also measure communication volume. A single assignment is one unit in the elementary model, not literally one second. Sequential blocks add costs; independent nested loops multiply their iteration counts. Conditional worst-case cost includes the test and the more expensive branch.DSA05
Question 236
What is the worst-case time complexity of Linear Search and when does it occur?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Θ(n) worst time, when absent or at the last position.
DSA28 scans until equality or exhaustion. An absent target or one in the final position requires all n comparisons, giving linear worst time; a first-position match instead takes constant time. The operation and cases are directly supported.
Evidence in the complete study note
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear.DSA28
Question 237
Binary Search requires the list to be:
A. Unsorted
B. Sorted
C. Circular
D. Linked
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA29 eliminates half an ordered interval according to the midpoint comparison. That elimination is valid only when comparable values follow a consistent order; descending input works with reversed comparisons. Circularity and links are representation properties, not substitutes for sortedness. An unsorted sequence gives no safe smaller-half decision. Therefore Sorted is the required prerequisite.
Evidence in the complete study note
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement.DSA29
Choice by choice
A · incorrect — Without order, a midpoint comparison cannot safely eliminate either half.
B · correct — Consistent sorted order supports the midpoint half-elimination invariant.
C · incorrect — Circular storage does not establish the value ordering needed by binary search.
D · incorrect — Linked storage does not imply sortedness and also changes midpoint-access costs.
Question 238
How many steps does Binary Search take for a list of 1,000,000 elements (approximately)?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA29 gives floor(log₂n)+1 probes for n>0. Since 2^19=524288 and 2^20=1048576, one million lies between them, so the worst probe count is twenty under the ordinary interval algorithm. A root/midpoint hit can finish earlier.
Evidence in the complete study note
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality.DSA29
Question 239
What is the time complexity of Bubble Sort and why?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Worst and usual average Θ(n²); early-stop best Θ(n).
DSA32 sums repeated adjacent passes to at most n(n−1)/2 comparisons, yielding quadratic worst and ordinary average work. A no-swap early-stop pass makes sorted input linear, while a fixed pass schedule remains quadratic. The answer needs these implementation and case distinctions.
Evidence in the complete study note
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons.DSA32
Question 240
In Selection Sort, what does each pass through the unsorted subarray accomplish?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Select the remaining minimum and put it at the next prefix position.
DSA33 scans the unsorted suffix for its minimum and exchanges it with A[i]. After each meaningful pass, the sorted prefix grows by one and contains the smallest keys placed so far. This differs from inserting the next encountered item into a prefix.
Evidence in the complete study note
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls.DSA33
Question 241
How does Insertion Sort differ from Selection Sort conceptually?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Selection finds a suffix minimum; insertion places the next item into a sorted prefix.
DSA33 chooses the globally smallest remaining key for each next output position. DSA34 instead takes the next input item, shifts larger prefix values, and inserts it into their gap. Both grow sorted prefixes, but choose their next item differently.
Evidence in the complete study note
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls.DSA33
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap. That gives n-1 insertion passes. On sorted input each pass needs one ordering check and no shifts: linear time. Reverse order causes 1+2+…+(n-1) shifts: quadratic time.DSA34
Question 242
What is the best-case scenario for Bubble Sort and what is its complexity in that case?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Already sorted input; Θ(n) with no-swap early stopping.
DSA32 performs one pass over an already sorted array, makes no swaps, and stops when early-exit detection is enabled. That is linear best work. A fixed-pass implementation still executes its quadratic comparison schedule even on the same input.
Evidence in the complete study note
Early stopping makes a sorted input linear: one no-swap pass finishes. A fixed pass schedule stays quadratic. Strict swaps preserve equal-key order. Cocktail sort runs bubble passes in both directions and is stable with strict swaps.DSA32
Question 243
What are the two components of each node in a singly linked list?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA08 defines a singly linked node as data plus next. The head reference points to the first node, and a null next terminates an ordinary noncircular chain. Head is a list-level reference rather than a second payload field inside every node.
Evidence in the complete study note
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Question 244
How does a circular linked list differ from a singly linked list?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: A circular tail links back to head instead of ending at null.
DSA10 defines circularity by the tail-to-head link and stops traversal after returning to the start. This is independent of singly versus doubly linked: a singly linked list can itself be circular. Compared with the ordinary noncircular singly linked chain, termination changes from null to return-to-start.
Evidence in the complete study note
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Question 245
To delete a node from the front of a singly linked list, what single update is needed?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Advance head to the old head’s next link, then reclaim the old node.
DSA09 saves old=head, sets head=head.next, and releases old in an owned C++ chain. The essential link update is advancing head; check empty before dereferencing, and clear tail too if the only node was removed. This answers the operation without hiding ownership work.
Evidence in the complete study note
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++.DSA09
Deleting the tail of a singly linked list requires its predecessor, even when tail itself is known. Handle empty and single-node lists separately; after removing the only node, set both head and tail to null. To remove a known successor, bypass it before deallocation. Clearing an owned n-node chain visits and releases every node.DSA09
Question 246
What extra pointer does each node in a doubly linked list have compared to a singly linked list?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA10 says doubly linked nodes add prev alongside next. That extra link permits backward traversal and supports endpoint updates when head and tail are maintained. It does not automatically give constant arbitrary positional access, which may still need traversal.
Evidence in the complete study note
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately.DSA10
Question 247
Why do linked lists have slower access times than arrays?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
DSA02 computes an element address from base, index, and element size in constant time. DSA08’s chain lacks direct index arithmetic, so reaching an arbitrary position may traverse linearly many links. This comparison concerns positional access rather than every operation: a known-head update can be constant.
Evidence in the complete study note
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing. This arithmetic gives constant-time positional access in the usual RAM cost model. A row-major rectangular matrix uses base + (row × columns + column) × element_size.DSA02
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic.DSA08
Question 248
Convert the infix expression A + B * C - D / E to postfix.
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
DSA13 works the exact expression. Multiplication groups B*C and division groups D/E before addition and subtraction. Emit A, then B C *, then +, then D E /, then −, producing ABC*+DE/-.
Evidence in the complete study note
Infix places an operator between operands and uses precedence and parentheses. Prefix places it first; postfix places it last. Their fixed operator arity determines grouping. To convert infix to postfix, output operands immediately and hold operators on a stack. Pop higher-precedence operators before pushing a new operator; also pop equal precedence for left-associative operators. Parentheses temporarily override this order.DSA13
A+B*C-D/E becomes ABC*+DE/-.DSA13
Question 249
What condition causes stack overflow in an array-implemented stack?
Hint / Module Reference (Where to Read)
Use the cited definitions and invariants to distinguish the requested concept from related operations.
Answer: Attempting push when the fixed array is full.
DSA11 distinguishes full storage from the overflow attempt. Under zero-based top-as-last-occupied convention, full means top=C−1; a count convention uses size=C. A push must check this before writing beyond capacity.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
Overflow is an attempted insertion into full storage; underflow is an attempted removal from empty storage.DSA11
Question 250
What are the three main operations of a Stack and their time complexities?
Hint / Module Reference (Where to Read)
State the representation and cost model, then count the operations or storage demanded by the question.
Answer: Push, pop, and peek are O(1) for fixed-array or head-linked stacks.
DSA11 defines push insertion, pop removal/return, and peek observation at top. Fixed-array indexing and linked-head updates take constant work. A resizing append or singly linked tail-pop implementation can change the cost, so the guarantee needs the stated representations.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
A count-based alternative uses size=0 and A[size++]=x. Do not combine its empty/full tests with the top-index convention. Fixed-array push/pop are constant time. Linked stacks achieve constant time by inserting and deleting at the head; using a singly linked tail for pop would require a predecessor traversal.DSA11
Question 251
In postfix notation, why are parentheses unnecessary?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Operator position and known arity determine grouping.
DSA13 places postfix operators after their operands. During stack evaluation, each binary operator consumes the two latest operand values in right-then-left order and pushes their result. The sequence therefore encodes grouping without precedence parentheses.
Evidence in the complete study note
Infix places an operator between operands and uses precedence and parentheses. Prefix places it first; postfix places it last. Their fixed operator arity determines grouping. To convert infix to postfix, output operands immediately and hold operators on a stack. Pop higher-precedence operators before pushing a new operator; also pop equal precedence for left-associative operators. Parentheses temporarily override this order.DSA13
To evaluate postfix, push operands. At a binary operator, pop right operand first, then left, and push left op right. Build an expression tree for either prefix (preorder) or postfix (postorder); a stack is useful but is not the only possible conversion representation.DSA13
Question 252
What is the difference between a simple array queue and a circular queue?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Circular wraparound reuses freed front slots; a simple noncircular queue may not.
DSA15 distinguishes a rear index reaching the array end from circular modulo arithmetic. A circular queue can insert into positions freed at the front, while a simple noncircular version may report overflow despite those gaps. Capacity and empty/full conventions still must be consistent.
Evidence in the complete study note
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Question 253
A stable priority queue serves smaller numeric priority keys first and compares equal priorities by an increasing arrival counter, also smallest first. If two tasks have equal priority, in what order are they served?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: FIFO among equal priorities: the task that arrived earlier is served first.
The priority comparison ties, so the specified comparator proceeds to the arrival counter. An increasing counter gives the earlier arrival the smaller secondary key, causing it to be removed first. Equal-priority tasks are therefore served FIFO under this stable policy. That result follows from the explicitly chosen tie rule; an ordinary priority queue without a stability or comparator rule would not inherently guarantee arrival-order service.
Evidence in the complete study note
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff. Equal priorities have no inherent FIFO guarantee. If stable service is required, compare (priority, arrival_counter). Choose the priority direction and tie rule before tracing.DSA17
Question 254
What causes queue underflow and what does it indicate?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Dequeue on an empty queue causes underflow.
DSA11 defines underflow as attempted removal from empty storage; DSA15’s count convention detects empty using size==0. This indicates that no item exists to return, not that the array is full or that an ordinary emptiness test itself failed.
Evidence in the complete study note
Overflow is an attempted insertion into full storage; underflow is an attempted removal from empty storage. Merely checking isEmpty does not underflow.DSA11
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.DSA15
Question 255
Name three real-world applications of stacks.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Runtime call frames, undo/redo history, and string or sequence reversal.
DSA12 gives nested calls latest-first returns, moving latest actions between undo and redo stacks, and reversing input by pushing then popping. Each example uses the same latest-pending-item discipline. A new edit after undo normally clears redo history.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12
Question 256
What property must hold at every node of a Binary Search Tree?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Every left-subtree key is smaller and every right-subtree key larger, for distinct keys.
DSA19 imposes this invariant over entire subtrees at every node, not only immediate children. A descendant can satisfy its parent comparison yet violate an ancestor bound. Duplicate keys require an explicit count or placement policy instead of silently weakening the distinct-key rule.
Evidence in the complete study note
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
Question 257
List the order of nodes visited in Inorder traversal of BST: root=4, left subtree has 1,2,3, right has 5,6,7.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
DSA20 visits left subtree, node, then right subtree for inorder, and says BST inorder returns sorted keys. The supplied seven distinct keys therefore appear in increasing order even though the internal child shapes are not fully specified. Shape would matter to preorder or postorder.
Evidence in the complete study note
Preorder visits node,left,right; inorder left,node,right; postorder left,right,node. Apply recursively; null children do nothing. Inorder returns sorted keys only for a BST. Preorder supports copying, postorder supports deleting children before parents, and level order uses a FIFO queue.DSA20
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy.DSA19
Question 258
When deleting a BST node with two children, what are the two valid replacement choices?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
DSA21 identifies the maximum key in the left subtree and minimum key in the right subtree as valid replacement values. Copy one into the deleted node, then remove that value’s original node, which has at most one child. These preserve the subtree order invariant.
Evidence in the complete study note
A leaf can be detached by clearing its parent link. For one child, make the parent bypass the node and point to the child. For two children, copy the inorder predecessor (left-subtree maximum) or successor (right-subtree minimum), then delete that replacement from its original location. That second deletion has at most one child.DSA21
Question 259
What is the time complexity of BST search in the best case vs worst case?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
DSA19 gives a constant root hit and O(height) search. A chain has linear height, producing linear worst work; logarithmic height disciplines in DSA22 improve that worst bound. Calling every BST logarithmic would incorrectly assume balance.
Evidence in the complete study note
Search compares at each node and follows one child until equality or null. Insertion uses that same path to attach a new leaf. Operations cost O(height): logarithmic for balanced trees, linear for a chain. Best-case successful search is Theta(1), a root hit. An optimal BST minimizes expected search cost using access probabilities; constructing it is a different problem from searching it.DSA19
AVL balance factor is height(left)-height(right); every node must have factor -1,0 or 1. After insertion or deletion, update heights upward and rotate where necessary. LL imbalance needs a right rotation; RR needs left; LR rotates the left child left then the node right; RL is symmetric. Rotations preserve inorder key order.DSA22
Question 260
What is the key difference between BFS and DFS graph traversal?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: BFS explores distance layers with FIFO; DFS finishes branches with a stack or recursion.
DSA41 enqueues discoveries in layer order, while DSA42 resumes the latest unfinished branch before later neighbors. Both can traverse all reachable vertices, but their pending-work discipline and visitation order differ. BFS also has the unweighted minimum-edge guarantee.
Evidence in the complete study note
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers.DSA41
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles.DSA42
Question 261
A directed graph has edges with direction; an undirected graph does not. Give one real-world example of each.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Directed: following accounts; undirected: a mutual friendship relationship.
DSA40 gives following as directed because u following v need not imply v following u. It gives mutual friendship as undirected, representing a symmetric connection. The examples concern relation semantics rather than whether lines happen to be drawn with arrows.
Evidence in the complete study note
A graph has vertices V and edges E. Directed edges distinguish u→v from v→u; undirected edges represent two-way relationships. Following accounts is directed; a mutual friendship relation is undirected. Weighted edges carry costs; unweighted shortest-path questions count edges. DAG expands to directed acyclic graph. Trees are connected acyclic graphs, although graph data structures may also contain cycles.DSA40
Question 262
Why is a dense graph more computationally expensive to process than a sparse graph?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Edge-processing algorithms do more work when E is larger.
DSA40 says dense simple graphs approach quadratic edge counts and adjacency lists use Θ(V+E) space. Traversals or algorithms inspecting every edge therefore require more work as density increases. This is not universal: a vertex-only operation need not inspect edges.
Evidence in the complete study note
A matrix uses Theta(V²) space and constant edge lookup. Adjacency lists use Theta(V+E) space and enumerate neighbours. Dense simple graphs approach quadratic edge counts. Examining every edge costs more on denser graphs; vertex-only operations need not inspect every edge.DSA40
BFS finds minimum-edge paths in unweighted graphs, not arbitrary minimum-weight paths. With adjacency lists it costs O(V+E); scanning a matrix costs O(V²). To traverse a disconnected graph, restart from each unvisited vertex. Neighbour order affects tied traversal order but not minimum distances.DSA41
Question 263
In a full binary tree, every node has either 0 or 2 children. How does this differ from a complete binary tree?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Full restricts each node to zero or two children; complete restricts level filling.
DSA18 defines full by each node’s child count and complete by filled earlier levels plus left-filled final level. Those are distinct conditions: completeness can allow one child at the boundary, while fullness alone need not keep every level filled.
Evidence in the complete study note
Binary means at most two children. Full means each node has zero or two children. Complete means all earlier levels are filled and the last fills from left. Perfect means all leaves share a level and every internal node has two children. Balanced means height stays logarithmic under a stated rule; it does not require a perfect shape.DSA18
Question 264
What distinguishes a weighted graph from an unweighted graph, and when would you prefer weighted?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Weighted edges carry differing costs; use them when edge costs matter.
DSA40 assigns costs to weighted edges and says unweighted shortest-path questions count edges. Distances or travel costs can therefore justify weights when fewer edges is not the true objective. DSA43 then distinguishes weighted shortest paths from unweighted BFS.
Evidence in the complete study note
A graph has vertices V and edges E. Directed edges distinguish u→v from v→u; undirected edges represent two-way relationships. Following accounts is directed; a mutual friendship relation is undirected. Weighted edges carry costs; unweighted shortest-path questions count edges. DAG expands to directed acyclic graph. Trees are connected acyclic graphs, although graph data structures may also contain cycles.DSA40
For nonnegative weights, standard Dijkstra initializes source distance zero and others infinity, repeatedly finalizes the unsettled vertex with smallest distance, and relaxes each outgoing edge: dist[v]=min(dist[v],dist[u]+w(u,v)). A min-priority queue supports the next choice. BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford.DSA43
Question 265
If a BST receives keys in sorted order (1,2,3,4,5), what shape does the tree take and what is the search complexity?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: An ordinary unbalanced insertion forms a right chain; worst search is Θ(n).
DSA19 explicitly traces sorted insertion 1,2,3,4,5 into a right chain. Each new larger key follows right links to the tail, making the height linear. Worst search follows that chain, while a root hit remains constant. Balanced insertion would rotate and is a different assumption.
Evidence in the complete study note
Search compares at each node and follows one child until equality or null. Insertion uses that same path to attach a new leaf. Operations cost O(height): logarithmic for balanced trees, linear for a chain. Best-case successful search is Theta(1), a root hit. An optimal BST minimizes expected search cost using access probabilities; constructing it is a different problem from searching it.DSA19
Sorted insertions 1,2,3,4,5 instead form a right chain.DSA19
Question 266
When would you choose a linked list over an array? Give a specific scenario.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Choose links for frequent known-location updates, such as a doubly linked history cursor.
DSA10 gives browser history with a doubly linked cursor as an application. With references to current insertion or removal positions, link changes avoid shifting an array’s later elements; arbitrary positional lookup can still be linear. This concrete scenario supports the choice without claiming universal superiority.
Evidence in the complete study note
Lists suit changing sequences when references to insertion positions are already available. Finding a position is still linear. Lists can hold polynomial terms (coefficient, exponent), directory or block links, child lists in nonbinary trees, and hash chains. Browser history can use a doubly linked cursor. A playlist may be circular; airline seat lookup requires a specified seat-record model, not an automatic linked-list answer.DSA10
A fixed array has a chosen capacity; the choice need not occur at compile time. A resizable array allocates a larger block and copies when needed. Inserting in the middle shifts later elements, so it costs linear time. Appending into spare capacity is constant; a resizing append can be linear, though repeated geometric growth gives amortized constant append cost.DSA02
Question 267
How does a stack differ from a queue? Give an application for each.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Stack: LIFO for undo; queue: FIFO for equal-priority printer jobs.
DSA11 gives latest-first stack service and DSA12 applies it to undoing the latest edit. DSA14 gives arrival-order queues for equal-priority printing. Both ADTs may use arrays or nodes; their service order, not that representation, is the distinction.
Evidence in the complete study note
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--].DSA11
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation.DSA14
Undo moves the latest action from undo to redo; redo moves it back.DSA12
Question 268
Why is a balanced BST (like AVL) preferred over a regular BST? Explain the worst-case scenario.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Balance prevents linear-height chains and guarantees logarithmic worst search.
DSA22 maintains AVL balance factors through rotations that preserve inorder. DSA19 shows ordinary sorted insertion producing a chain, where a search can traverse all nodes. Maintaining logarithmic height prevents that worst degradation, though root-hit best time remains constant.
Evidence in the complete study note
AVL balance factor is height(left)-height(right); every node must have factor -1,0 or 1. After insertion or deletion, update heights upward and rotate where necessary. LL imbalance needs a right rotation; RR needs left; LR rotates the left child left then the node right; RL is symmetric. Rotations preserve inorder key order.DSA22
Search compares at each node and follows one child until equality or null. Insertion uses that same path to attach a new leaf. Operations cost O(height): logarithmic for balanced trees, linear for a chain. Best-case successful search is Theta(1), a root hit. An optimal BST minimizes expected search cost using access probabilities; constructing it is a different problem from searching it.DSA19
Question 269
What is a hash collision? Name two methods to resolve collisions and compare them.
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: A collision maps different keys to one home address; compare chaining and open addressing.
DSA26 stores colliding entries in bucket lists for chaining, whereas open addressing probes other array slots. Chaining uses link or bucket overhead and expected O(1+α) work; probing keeps entries inside the table and requires careful load and deletion policies. Neither prevents all collisions.
Evidence in the complete study note
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found.DSA26
Linear probing tries (h(k)+j)%m. For size 7 and keys 10,17,24, all home addresses are 3 and occupied positions become 3,4,5. Quadratic probing changes the step; double hashing uses h1(k)+j h2(k), modulo m, with a step relatively prime to m to cover all slots. Neither method guarantees no collisions. Deletion needs tombstones or reinsertion so searches do not stop prematurely.DSA26
Question 270
What is the difference between BFS and DFS? Which finds the shortest path?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
DSA41 guarantees minimum-edge paths for BFS on unweighted graphs. DSA42 says DFS paths are reachability witnesses but need not be shortest. Differing edge weights require an appropriate weighted-path algorithm, such as Dijkstra under nonnegative weights.
Evidence in the complete study note
BFS finds minimum-edge paths in unweighted graphs, not arbitrary minimum-weight paths. With adjacency lists it costs O(V+E); scanning a matrix costs O(V²). To traverse a disconnected graph, restart from each unvisited vertex. Neighbour order affects tied traversal order but not minimum distances.DSA41
Using the same graph and alphabetical neighbours, recursive DFS can discover A,B,D,C. Its path is a valid reachability witness but not necessarily shortest. Adjacency-list cost is O(V+E), with O(V) visited state and possible stack depth. DFS supports cycle and connectivity analysis; a directed cycle test distinguishes active recursion vertices from already completed ones.DSA42
BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford.DSA43
Question 271
A text editor needs to implement multi-level undo. Which data structure is most appropriate and why?
Hint / Module Reference (Where to Read)
Use the cited invariant or operation rule, state its assumptions, and trace a small case to justify the result.
Answer: Use an undo stack, with a second redo stack if needed.
DSA12 moves the latest action from undo to redo and reverses that movement for redo. Pushing each new edit and popping for undo naturally matches the most-recent-edit-first requirement. A new edit after undo normally clears redo history.
Evidence in the complete study note
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.DSA12