GATE CS 2015 Set 2 — Question 49
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumSelection (Order Statistics)SearchingAlgorithmsFunctions & RecursionC ProgrammingProgramming & Data StructuresArrays & Strings in C
Algorithms → C Programming → Arrays & Strings in C
Last updated
Question
Suppose you are provided with the following function declaration in the C programming language.The function treats the first element of The missing argument lists are respectively
int partition(int a[], int n);
a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part.The following partially given function in the C programming language is used to find the smallest element in an array a[] of size n using the partition function. We assume .int kth_smallest(int a[], int n, int k)
{
int left_end = partition(a, n);
if ( left_end+1 == k ) {
return a[left_end];
}
if ( left_end+1 > k ) {
return kth_smallest( ___________ );
} else {
return kth_smallest( ___________ );
}
}
Correct answer
(A) (a, left end, k) and (a+left end+1, n-left end-1, k-left end-1)
Solution
The code returns
a[left_end] when left_end+1 == k, so left_end is used as the 0-based index of the pivot after partitioning: the pivot is the -th smallest element, every element in a[0..left_end-1] is the pivot, and every element in a[left_end+1..n-1] is greater.Case left_end+1 > k: the -th smallest lies strictly to the left of the pivot, in a[0..left_end-1]. That subarray starts at a and has left_end elements, and the rank is unchanged. Call: kth_smallest(a, left_end, k).Case left_end+1 < k: the -th smallest lies to the right of the pivot, in a[left_end+1..n-1]. That subarray starts at a+left_end+1 and has n-left_end-1 elements. The left_end+1 elements up to and including the pivot are all smaller, so we need the -th smallest of the subarray. Call: kth_smallest(a+left_end+1, n-left_end-1, k-left_end-1).Checking the options:- (A) gives exactly these two argument lists. Correct.
- (B) recurses on the right part but starts from
ainstead ofa+left_end+1, so it searches the wrong elements. - (C) and (D) swap the two branches (and (D) also uses the wrong start pointer).
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on C Programming
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 1 Q24Consider a hash table that is initially empty. The hash table is maintained…