Back to Subject

Unit 5: Transform-and-Conquer and Advanced Algorithmic Techniques - Practice Quiz

CSE408 — Design And Analysis Of Algorithms 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main purpose of keeping a binary search tree balanced?

Balanced Search Trees Easy
A. To remove all leaf nodes
B. To sort keys in descending order
C. To keep its height small
D. To store duplicate keys

2 What is the typical worst-case search time in a balanced binary search tree containing keys?

Balanced Search Trees Easy
A.
B.
C.
D.

3 Which operation is commonly used to restore balance in an AVL tree?

Balanced Search Trees Easy
A. Linear probing
B. Digit counting
C. Bucket merging
D. Tree rotation

4 Counting Sort is most suitable when the input consists of which kind of values?

Counting Sort Easy
A. Integers from a limited range
B. Graphs with weighted edges
C. Floating-point values without bounds
D. Strings of arbitrary length

5 What does the count array store during the basic counting phase of Counting Sort?

Counting Sort Easy
A. The digits of each key
B. The frequency of each key
C. The depth of each element
D. The position of each swap

6 What is the time complexity of Counting Sort for elements with a key range of size ?

Counting Sort Easy
A.
B.
C.
D.

7 How does Radix Sort primarily process numbers?

Radix Sort Easy
A. One digit position at a time
B. One adjacent pair at a time
C. One tree level at a time
D. One random pivot at a time

8 In least-significant-digit Radix Sort, which digit is processed first?

Radix Sort Easy
A. The rightmost digit
B. The middle digit
C. The largest digit
D. The leftmost digit

9 What property should the digit-sorting method used by Radix Sort have?

Radix Sort Easy
A. It should be in-place
B. It should be stable
C. It should be recursive
D. It should use comparisons

10 What is the first main step of Bucket Sort?

Bucket Sort Easy
A. Distribute elements into buckets
B. Compare every pair of elements
C. Build a balanced search tree
D. Reverse the entire input array

11 After the individual buckets have been sorted, how is the final result formed?

Bucket Sort Easy
A. Merge the buckets randomly
B. Select the largest bucket only
C. Reverse the buckets independently
D. Concatenate the buckets in order

12 Bucket Sort generally performs well when input values are distributed in what way?

Bucket Sort Easy
A. Only in strictly decreasing order
B. Randomly across linked lists
C. Roughly uniformly across a range
D. Only as identical repeated values

13 What special property does a monotonic stack maintain?

Monotonic Stack Easy
A. Elements alternate between signs
B. Elements remain in sorted order
C. Elements remain at fixed indices
D. Elements always have equal values

14 Which problem is commonly solved using a monotonic stack?

Monotonic Stack Easy
A. Building a minimum spanning tree
B. Finding the next greater element
C. Multiplying two square matrices
D. Finding a graph's minimum cut

15 Why can many monotonic-stack algorithms process an array in time?

Monotonic Stack Easy
A. Each element is pushed and popped at most once
B. Each element is compared with every other element
C. The stack stores only a single element
D. The array is always sorted before processing

16 Which problem is a common application of a monotonic queue?

Monotonic Queue Easy
A. Computing matrix determinants
B. Finding the maximum in each sliding window
C. Finding all graph cycles recursively
D. Sorting strings alphabetically

17 Which data structure is commonly used to implement a monotonic queue?

Monotonic Queue Easy
A. Undirected graph
B. Binary search tree
C. Double-ended queue
D. Singly linked stack

18 In a sorted array, where are two pointers commonly placed when searching for a pair with a target sum?

Two-Pointers Technique Easy
A. At the same middle position
B. At the two ends
C. Outside the array bounds
D. At two random positions

19 What is the usual time complexity of the two-pointers method for finding a target-sum pair in a sorted array?

Two-Pointers Technique Easy
A.
B.
C.
D.

20 If the sum of the two pointed values in an ascending sorted array is less than the target, which pointer is usually moved?

Two-Pointers Technique Easy
A. The right pointer moves left
B. Neither pointer is moved
C. The left pointer moves right
D. Both pointers move left

21 An empty AVL tree receives the keys , , and in that order. Which operation restores balance after the third insertion?

Balanced Search Trees Medium
A. A right-left rotation at node
B. A single left rotation at node
C. A single right rotation at node
D. A left-right rotation at node

22 A balanced binary search tree contains keys. What is the worst-case time complexity of searching for a key?

Balanced Search Trees Medium
A.
B.
C.
D. because each visited node may require rebalancing during the search

23 In a B-tree with minimum degree , what is the maximum number of keys that a node can contain?

Balanced Search Trees Medium
A.
B.
C.
D.

24 For the input array , what is the cumulative count for key in counting sort?

Counting Sort Medium
A.
B.
C.
D.

25 When cumulative counts are used, which implementation choice makes counting sort stable?

Counting Sort Medium
A. Scan the count array from right to left before accumulating counts
B. Scan the input from right to left while placing elements
C. Scan the input from left to right and reset each cumulative count after placement
D. Place each key directly at the index equal to its numeric value

26 A counting sort implementation must process integer keys ranging from through , inclusive. What is the minimum required size of the count array?

Counting Sort Medium
A.
B.
C.
D.

27 Using base- LSD radix sort, how many digit-processing passes are required to sort ?

Radix Sort Medium
A. passes
B. passes
C. passes
D. passes

28 After the first, ones-digit pass of stable base- LSD radix sort, what is the order of ?

Radix Sort Medium
A.
B.
C.
D.

29 Why must the per-digit sorting method used by LSD radix sort be stable?

Radix Sort Medium
A. It ensures that every digit value occurs exactly once per pass
B. It preserves the ordering established by earlier digit passes
C. It allows the algorithm to compare complete keys whenever two current digits are equal
D. It reduces the number of required passes from to

30 Bucket sort divides the interval into equal buckets using index . Into which zero-based bucket is placed?

Bucket Sort Medium
A. Bucket
B. Bucket
C. Bucket
D. Bucket

31 If all input values are placed into one bucket and that bucket is sorted using insertion sort, what is the worst-case running time?

Bucket Sort Medium
A.
B.
C.
D.

32 For temperatures , how many days must the temperature at index wait for a warmer day?

Monotonic Stack Medium
A. days
B. days
C. day
D. days

33 In the array , what is the next strictly smaller element to the right of the value ?

Monotonic Stack Medium
A.
B.
C. No smaller element
D.

34 What is the largest rectangle area in the histogram with bar heights ?

Monotonic Stack Medium
A.
B.
C.
D.

35 For the array with window size , what are the first three sliding-window maximums?

Monotonic Queue Medium
A.
B.
C.
D.

36 A deque is used to compute sliding-window maximums. Which invariant should be maintained?

Monotonic Queue Medium
A. Only the newest index is retained because older indices cannot become maximums later
B. All window indices are sorted by value using a full sort after each insertion
C. Indices are stored so their values increase from front to back
D. Indices are stored so their values decrease from front to back

37 What are the sliding-window minimums for using window size ?

Monotonic Queue Medium
A.
B.
C.
D.

38 Using two pointers on the sorted array , which pair sums to the target ?

Two-Pointers Technique Medium
A. and
B. and
C. and
D. and

39 A two-pointer algorithm removes duplicates in place from the sorted array . What unique-element count should it return?

Two-Pointers Technique Medium
A.
B.
C.
D.

40 In the container-with-most-water problem, the initial pointers reference heights and at the two ends of . Which pointer should move next?

Two-Pointers Technique Medium
A. Move both pointers inward
B. Move the left pointer inward
C. Keep both pointers fixed and examine every interior height before deciding which endpoint to replace
D. Move the right pointer inward

41 Which statement correctly compares AVL-tree rebalancing after a single insertion and after a single deletion? Count a double rotation as two primitive rotations.

Balanced Search Trees Hard
A. Both operations may require rebuilding every ancestor subtree because restoring balance at one node can invalidate all descendants below it.
B. Insertion may require primitive rotations, while deletion requires at most two.
C. Insertion requires at most two primitive rotations, while deletion may require primitive rotations.
D. Both insertion and deletion require at most one primitive rotation regardless of tree height.

42 A red-black tree contains internal nodes, and its height is measured as the number of edges on the longest root-to-internal-node path. Which worst-case upper bound follows from the red-black invariants?

Balanced Search Trees Hard
A.
B.
C.
D.

43 An order-statistic tree stores . During a left rotation at node , let before the rotation. Which size updates are sufficient after the structural pointers are changed?

Balanced Search Trees Hard
A. Set to the old , then increment by one.
B. Swap and without inspecting any child sizes.
C. Set to the old , then recompute from its new children.
D. Recompute the sizes of all nodes from to the root because a rotation changes the number of descendants at every ancestor.

44 Consider records , where subscripts distinguish records with equal keys. Counting sort obtains cumulative counts for keys . Scanning the input from right to left and decrementing after each placement produces which output?

Counting Sort Hard
A.
B.
C.
D.

45 Records have integer fields and must be sorted lexicographically with as the primary key and as the secondary key. Both fields have small ranges. Which sequence of stable counting-sort passes is correct?

Counting Sort Hard
A. Sort stably by , then sort stably by .
B. Sort stably by , then sort stably by .
C. Sort unstably by , then sort stably by .
D. Sort both fields independently and concatenate their resulting index orders.

46 An array contains integer keys with . A direct shifted counting sort allocates one counter for every integer in this range. What are its worst-case time and auxiliary-space complexities?

Counting Sort Hard
A. time and space
B. time and space
C. time and space
D. time and space

47 An LSD radix sort processes digits from least significant to most significant. What happens if the per-digit sorting procedure correctly orders each digit but is not stable?

Radix Sort Hard
A. The algorithm becomes equivalent to MSD radix sort because an unstable pass automatically gives priority to the most recently processed digit.
B. The algorithm remains correct whenever all keys have the same number of digits.
C. The algorithm remains correct but its running time increases by one digit pass.
D. The algorithm may destroy ordering established by earlier passes and need not sort correctly.

48 A radix-sort implementation orders fixed-width -bit words as unsigned integers, but the input must be sorted in ascending two's-complement signed order. Which preprocessing transformation permits the unsigned radix sort to produce the required order?

Radix Sort Hard
A. Reverse the bytes within every key.
B. XOR every key with .
C. Complement all bits of every key.
D. Take the absolute value of every key.

49 An LSD radix sort handles -bit nonnegative integers using bits per digit and counting sort for each pass. Its cost is . Which choice yields time and auxiliary space?

Radix Sort Hard
A.
B.
C.
D.

50 Independent keys follow a known continuous distribution with cumulative distribution function , and can be evaluated in time. Which bucket assignment makes buckets approximately equiprobable and supports expected sorting time with insertion-sorted buckets?

Bucket Sort Hard
A. Assign to bucket determined only by the binary length of .
B. Assign to bucket , clamping the endpoint if needed.
C. Assign to a bucket selected by repeatedly comparing it with every previously inserted key and then balancing all bucket sizes.
D. Assign to bucket regardless of the support of the distribution.

51 Suppose bucket receives each independently drawn key with probability , and each bucket is sorted by insertion sort. With buckets and keys, which condition on the probabilities characterizes an expected linear bound through the bucket-squared-cost analysis?

Bucket Sort Hard
A.
B. only
C. only
D.

52 To compute the sum of all subarray minimums by assigning each subarray to exactly one occurrence of its minimum, let and be boundary indices for . Which asymmetric tie rule and contribution formula are valid?

Monotonic Stack Hard
A. and are both previous and next smaller-or-equal; contribute .
B. is previous greater-or-equal and is next strictly greater; contribute .
C. and are both previous and next strictly smaller; contribute .
D. is previous strictly smaller and is next smaller-or-equal; contribute .

53 In the standard largest-rectangle-in-a-histogram algorithm, index is popped when processing index because . After the pop, the new stack top is index . What maximal width is associated with height ?

Monotonic Stack Hard
A.
B.
C.
D.

54 For the circular next-strictly-greater-element problem, an algorithm scans indices modulo for iterations. It pushes each original index only during the first iterations and pops while the current value is strictly greater than the value at the stored index. Which claim is correct?

Monotonic Stack Hard
A. Its time is because every original index is pushed once and popped at most once.
B. Its time is whenever the array is nonincreasing.
C. Its time is because the second traversal repeats all stack comparisons.
D. It incorrectly handles equal values because equal elements must always be treated as strictly greater in a circular traversal.

55 For the shortest nonempty subarray with sum at least , let be prefix sums and maintain candidate indices in a deque. Which processing rule is correct for each ?

Monotonic Queue Hard
A. Remove every negative prefix sum before testing feasibility because negative prefixes cannot begin a minimum-length qualifying subarray.
B. Pop back while , then pop front while , and finally append .
C. Append first, sort the deque by index, and remove only candidates whose prefix sums equal .
D. Pop front while , then pop back while , and finally append .

56 A deque is used to compute sliding-window maxima of width . To keep the newest index among equal maximum values, which update rule should be applied at index ?

Monotonic Queue Hard
A. Expire indices above , pop the front while , then append .
B. Expire indices below , pop the back while , then append .
C. Retain every equal value and linearly search the entire deque after each window shift to identify the newest maximum.
D. Expire indices below , pop the back while , then append .

57 Consider with given. Which monotonic-deque order computes all states in time?

Monotonic Queue Hard
A. Append before computing , then use the deque front even if it refers to the same state.
B. Read the back for the minimum, expire indices greater than , pop front while , then append .
C. Sort all indices in the current window by both index and cost after computing every new dynamic-programming state.
D. Expire indices less than , read the front for the minimum, pop back while , then append .

58 For an array of strictly positive integers, a sliding window counts subarrays whose product is strictly less than . Which rule correctly handles all values of ?

Two-Pointers Technique Hard
A. For , retain zero-length windows as valid and count one additional subarray for every right endpoint.
B. For every , shrink while the product is at most and add the current window length.
C. If , return ; otherwise shrink while the product is greater than and add .
D. If , return ; otherwise shrink while the product is at least and add .

59 In the container-with-most-water problem, pointers start at both ends. Why is moving the pointer at the shorter line a safe elimination step?

Two-Pointers Technique Hard
A. Moving the shorter line guarantees that the next area is strictly larger.
B. Keeping the shorter line while reducing width cannot produce a larger area, regardless of the new opposite height.
C. The taller line can never participate in any globally optimal container.
D. The shorter line must be smaller than every line located between the two current pointers, so it cannot be part of an optimal pair.

60 A sorted array may contain duplicates. To count index pairs with and in time, what should be done when the two pointer values form a valid sum?

Two-Pointers Technique Hard
A. If the values differ, multiply their run lengths; if equal, add and terminate.
B. Always add one pair and move both pointers by exactly one position.
C. Multiply the distances of both pointers from the array endpoints.
D. If the values differ, add both run lengths; if equal, add and continue scanning every interior pair.
Previous MCQ
Unit 4
Next MCQ
Unit 6