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 store duplicate keys
B. To keep its height small
C. To remove all leaf nodes
D. To sort keys in descending order

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. Digit counting
B. Tree rotation
C. Bucket merging
D. Linear probing

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

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

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

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

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 tree level at a time
B. One adjacent pair at a time
C. One random pivot at a time
D. One digit position at a time

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

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

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

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

10 What is the first main step of Bucket Sort?

Bucket Sort Easy
A. Compare every pair of elements
B. Distribute elements into buckets
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. Reverse the buckets independently
B. Concatenate the buckets in order
C. Select the largest bucket only
D. Merge the buckets randomly

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

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

13 What special property does a monotonic stack maintain?

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

14 Which problem is commonly solved using a monotonic stack?

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

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

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

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

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

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

Monotonic Queue Easy
A. Binary search tree
B. Undirected graph
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. Outside the array bounds
B. At the same middle position
C. At the two ends
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. Neither pointer is moved
B. The left pointer moves right
C. The right pointer moves left
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 single left rotation at node
B. A single right rotation at node
C. A left-right rotation at node
D. A right-left 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. because each visited node may require rebalancing during the search
C.
D.

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 input from left to right and reset each cumulative count after placement
B. Place each key directly at the index equal to its numeric value
C. Scan the count array from right to left before accumulating counts
D. Scan the input from right to left while placing elements

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 reduces the number of required passes from to
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 ensures that every digit value occurs exactly once per pass

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. days
D. day

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

Monotonic Stack Medium
A. No smaller element
B.
C.
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. Indices are stored so their values increase from front to back
B. Indices are stored so their values decrease from front to back
C. All window indices are sorted by value using a full sort after each insertion
D. Only the newest index is retained because older indices cannot become maximums later

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. Keep both pointers fixed and examine every interior height before deciding which endpoint to replace
C. Move the left pointer inward
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. Both insertion and deletion require at most one primitive rotation regardless of tree height.
D. Insertion requires at most two primitive rotations, while deletion may require primitive rotations.

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. Swap and without inspecting any child sizes.
B. Set to the old , then increment by one.
C. Recompute the sizes of all nodes from to the root because a rotation changes the number of descendants at every ancestor.
D. Set to the old , then recompute from its new children.

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 unstably by , then sort stably by .
B. Sort stably by , then sort stably by .
C. Sort stably 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 remains correct whenever all keys have the same number of digits.
B. The algorithm becomes equivalent to MSD radix sort because an unstable pass automatically gives priority to the most recently processed digit.
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. Complement all bits of every key.
C. XOR every key with .
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 regardless of the support of the distribution.
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 determined only by the binary length of .

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. only
B.
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. is previous strictly smaller and is next smaller-or-equal; contribute .
D. and are both previous and next strictly smaller; 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 the second traversal repeats all stack comparisons.
B. Its time is whenever the array is nonincreasing.
C. Its time is because every original index is pushed once and popped at most once.
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. Pop front while , then pop back while , and finally append .
B. Append first, sort the deque by index, and remove only candidates whose prefix sums equal .
C. Pop back while , then pop front while , and finally append .
D. Remove every negative prefix sum before testing feasibility because negative prefixes cannot begin a minimum-length qualifying subarray.

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

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. If , return ; otherwise shrink while the product is greater than and add .
B. For every , shrink while the product is at most and add the current window length.
C. For , retain zero-length windows as valid and count one additional subarray for every right endpoint.
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. The taller line can never participate in any globally optimal container.
B. Moving the shorter line guarantees that the next area is strictly larger.
C. The shorter line must be smaller than every line located between the two current pointers, so it cannot be part of an optimal pair.
D. Keeping the shorter line while reducing width cannot produce a larger area, regardless of the new opposite height.

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, add both run lengths; if equal, add and continue scanning every interior pair.
B. If the values differ, multiply their run lengths; if equal, add and terminate.
C. Multiply the distances of both pointers from the array endpoints.
D. Always add one pair and move both pointers by exactly one position.
Previous MCQ
Unit 4
Next MCQ
Unit 6