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

Contents

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

### Most Employability Test 2019

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

**More Articles AMCAT CSE Questions Paper:**

- Data Types
- Iteration, Recursion, Decision
- Procedure, functions and scope
- Arrays, Linked Lists, Trees, Graphs (Data Structure)
- Stacks, Queues
- Hash Tables
- Heaps Questions
- Searching and Sorting
- Polymorphism
- Abstraction
- Encapsulation
- Complexity Theory

**Looking for AMCAT Discount? – check here** AMCAT Discount Code

**Question 6**

What is the third number from the left while doing bubble sort in the 3rd iteration for 5 1 4 2 8?

(A) 4

(B) 5

(C) 2

(D) 8

Answer: Option A

Explanation: First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and

swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 >

2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not

swap them. Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5

8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not

know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –>

( 1 2 4 5 8 )

**Question 7**

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

(A)Heap Sort

(B)Selection Sort

(C)Insertion Sort

(D)Merge Sort

Answer: Option B

Explanation: Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.

**Question 8**

Find the 3rd number from the left in the 3rd iteration while doing selection sort for – arr[] = 64 25 12 22

11

(A) 22

(B) 12

(C) 25

(D)64

Answer: Option A

Explanation: arr[] = 64 25 12 22 11 // Find the minimum element in arr[0…4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1…4] // and place it at beginning of arr[1…4] 11 12 25 22 64 // Find the minimum element in arr[2…4] // and place it at beginning of arr[2…4] 11 12 22 25 64

**Question 9**

Which of the following is not true about comparison based sorting algorithms?

(A)The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array

(B)Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared

(C)Counting Sort is not a comparison based sorting algorithm

(D)Heap Sort is not a comparison based sorting algorithm

Answer: Option D

**Question 10**

Which of the following algorithm will be the slowest amongst the following

(A) Shell

(B) Heap

(C)Quick

(D)Bubble

Answer: Option D

Can u explain heap,merge,quick,insertions sorts in detail