**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.
- Name
- Age
- Class

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.

**Sorting Efficiency**

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**

AMCAT Searching & Sorting Sample Question

**Exercises on Searching and Sorting Questions**

**Question 1
**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)**

**Option**

Answer:

Answer:

**(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

Explanation:

**T(n) = T(n-1) + T(0) + O(n)**

**The above expression can be rewritten as**

**T(n) = T(n-1) + O(n)**

**Question 2
**Which of the following Sorting Algorithm will perform the worst if the numbers are ordered in the opposite form?

**(A)Quick Sort**

**(B)Radix**

**(C)Bubble**

**(D)Selection**

**Option**

Answer:

Answer:

**A**

Explanation:Quick sort, most of all, performs the worst if arranged in either alphabetic or ascending order

Explanation:

**Question 3
**Which of the following is not a stable sorting algorithm in its typical implementation.

**(A) Insertion Sort**

**(B)Merge Sort**

**(C)Quick Sort**

**(D)Bubble Sort**

**Option**

Answer:

Answer:

**C**

**Question 4
**Binary Search can have _____ number of maxm comparsions?

**(A)log(n) + 1**

**(B)2*log n**

**(C) n**

**(D)(n+1)/2**

**Option**

Answer:

Answer:

**A**

Explanation:Most number of comparison possible for BST is log(n) + 1

Explanation:

**Question 5
**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).

**(A)Quick Sort**

**(B) Heap Sort**

**(C)Merge Sort**

**(D)Insertion Sort**

**Option**

Answer:

Answer:

**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.

Explanation

Download AMCAT Questions on Arrays, Linked Lists, Trees, Graphs

AMCAT Questions on Stacks and Queues

Questions from Hash Tables in AMCAT pdf

Any confusion on **AMCAT Searching and Sorting Questions 2018**, please comment.