AMCAT Data Structure Questions: Computer Programming module is especially covered for Engineering candidates. It includes Arrays, Linked Lists, Trees, Graphs,Stacks and Queues, Hash Tables, Heaps, Searching and Sorting. Below we will be covering in detail sample of AMCAT Searching and Sorting Questions.
AMCAT Searching and Sorting Questions with Answers – Computer Programming
AMCAT Computer Programming is more important for job profiles like Technical Support Executive, Computer Engineer, Software Developer Web, System s/w, Product, Trainee, Testing Engineer, Research Engineer, Content Developer-IT, IT Recruiter, etc.
Also 2- 3 questions come from Searching and Sorting topic each time. The difficulty level of the questions is, rather moderate. It takes probably, 1.5- 2 minutes to solve the problems.
Overview of Searching and Sorting concept
Sorting is nothing but storage of data in sorted order, it can be in either ascending or descending order. Hence, the term Sorting comes into picture with the term Searching. There are probably so many things in our real life that we need to search, like a particular record in database, roll numbers in merit list, a particular telephone number, any particular page in a book etc.
Sorting arranges data in a sequence which makes searching much easier. Each record which is going to be sorted will contain one key. Therefore, based on the key the record will be sorted. For example, suppose we have a record of students, every such record will have the following data:
- Roll No.
Here Student roll no. can be taken as key for sorting the records in either ascending or descending order. Furthermore, suppose we have to search a Student with roll no. 15, we don’t need to search the complete record, rather we will simply search between the Students with roll no. 10 to 20.
Since there are many techniques for sorting, hence implementation of particular sorting technique depends upon situation. Sorting techniques especially depends on two parameters. First parameter is the execution time of program, which means time taken for execution of program. Another is the space, which means space taken by the program.
Types of Sorting Techniques
There are many types of Sorting techniques, differentiated mostly by their efficiency and space requirements. Following are some sorting techniques which are most noteworthy, especially for searching.
- Bubble Sort
- Insertion Sort
- Selection Sort
- Quick Sort
- Merge Sort
- Heap Sort
Download AMCAT Searching and Sorting Questions
Exercises on Searching and Sorting Questions
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
(A) Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
(B) Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
(C) Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
(D) Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
Answer: Option (B)
Explanation: The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n-1). So recurrence is
T(n) = T(n-1) + T(0) + O(n)
The above expression can be rewritten as
T(n) = T(n-1) + O(n)
Which of the following Sorting Algorithm will perform the worst if the numbers are ordered in the opposite form?
Answer: Option A
Explanation: Quick sort, most of all, performs the worst if arranged in either alphabetic or ascending order
Which of the following is not a stable sorting algorithm in its typical implementation.
(A) Insertion Sort
Answer: Option C
Binary Search can have _____ number of maxm comparsions?
(A)log(n) + 1
Answer: Option A
Explanation: Most number of comparison possible for BST is log(n) + 1
Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).
(B) Heap Sort
Answer: Option D
Explanation: Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than linear time in their typical implementation.
Any confusion on AMCAT Searching and Sorting Questions 2018, please comment.