A. 1

B. n - 1

C. n log n

D. n^2

2 .Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

* A. O(n log n) sorts

* B. Divide-and-conquer sorts

* C. Interchange sorts

* D. Average time is quadratic.

3 . Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

* A. 21

* B. 41

* C. 42

* D. 43

4 .Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

1 2 3 4 5 0 6 7 8 9

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.

* B. The algorithm might be selectionsort, but could not be insertionsort.

* C. The algorithm might be insertionsort, but could not be selectionsort.

* D. The algorithm is neither selectionsort nor insertionsort.

5 .Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

2 4 5 7 8 1 3 6

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.

* B. The algorithm might be selectionsort, but it is not insertionsort.

* C. The algorithm is not selectionsort, but it might be insertionsort.

* D. The algorithm is neither selectionsort nor insertionsort.

6 .When is insertionsort a good choice for sorting an array?

* A. Each component of the array requires a large amount of memory.

* B. Each component of the array requires a small amount of memory.

* C. The array has only a few items out of place.

* D. The processor speed is fast.

7 What is the worst-case time for mergesort to sort an array of n elements?

* A. O(log n)

* B. O(n)

* C. O(n log n)

* D. O(n^2)

8 What is the worst-case time for quicksort to sort an array of n elements?

* A. O(log n)

* B. O(n)

* C. O(n log n)

* D. O(n^2)

9 .Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

* A. The array elements form a heap.

* B. Elements in each half of the array are sorted amongst themselves.

* C. Elements in the first half of the array are less than or equal to elements in the second half of the array.

* D. None of the above.

10 .Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

* A. The pivot could be either the 7 or the 9.

* B. The pivot could be the 7, but it is not the 9.

* C. The pivot is not the 7, but it could be the 9.

* D. Neither the 7 nor the 9 is the pivot.

11 .What is the worst-case time for heapsort to sort an array of n elements?

* A. O(log n)

* B. O(n)

* C. O(n log n)

* D. O(n^2)

12.Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements.How would you sort the entire list if

* A. f(N)=O(1)

* B. f(N)=O(logN)

* C. f(N)=O(N^1/2)

* D. How large can f(N) be for the entire list still to be sortable in O(N) time?

13.Prove that any algorithm that find an element X in a sorted list of N elements requires Omega(log N) comparisons.

14.Prove that sorting N elements with integer keys in the range 1 < Key < M

takes O(M + N) time using bucket sort.

15.Suppose you have an array of N elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm to sort the array.

16.Prove that any comparison based algorithm to sort 4 elements requires atleast 5 comparisons

17. In how many ways can 2 sorted arrays of combined size N be merged?

18.Show that binary insertion may reasonably be expected to be an O(n log n) sort.

19.You are given two sets of numbers Xi and Yj , where i and j run from 1 to N.

Devise an algorithm to find the M largest values of Xi −Yj . This algorithm should

not be quadratic in N, though it is permitted to be quadratic in M.

You should regard N as being of the order of 20,000 and M as being of the order

of 1,000.

20.If 1024 numbers are drawn randomly in the range 0–127 and sorted by binary

insertion, about how many compares would you expect?

__Click Here for Solutions__

hi

ReplyDeleteit would be nice if the solutions would be given to all sorting and searching questions for freshers

thanq vry much

ReplyDeleteplease can you give me the comparison of these sorting algorithms;

ReplyDeletebubble sort

insertion sort

selection sort

shell sort

merge sort

heap sort

quick sort

answers:

ReplyDelete1)B

2)D

3)C

4)C

5)

6)

7)C

8)D

9)B

10)

11)D

1)B

ReplyDelete2)D

3)C

4)b

5)b

6)c

7)C

8)D

9)B

10)a

11)c

The answer for question 2 can't be D, it's C as the quicksort algorithm average time is

ReplyDeleteO(nlogn) and not O(n^2).

In this question worst case scenario has been asked, in which partition occurs such that on one side of pivot only one element is left and on the other side we have n-2 elements.We have to make pivots O(n) time and each takes O(n) comparison so ans O(n^2).

Delete

ReplyDeleteHere, are some sample questions based on “Data Structures”. Read it carefully as these questions will improve your basic concept on Data Structures using C programming language, and will help you in cracking any interview.Click on any question to find out it's answers:

Question - 1) What Is Data Structure ?

Question - 2) What Is The Need For Data Structures In Programming ?

Question - 3) What Are The Different Data Types Which A Data Structure May Comprise Of ?

Question - 4) How Can Data Structures Be Classified ?

Question - 5) What Are Linear Data Structures ?

Question - 6) What Are Non Linear Data Structures ?

Question - 7) Differentiate Between Data Types & Data Structures ?

Question - 8) List Four Major Operations On Linear Data Structures ?

Question - 9) What Do You Mean By A Static Data Structure ?

Question - 10) What Is Dynamic Memory Allocation ?

Question - 11) What Is A Stack ?

Question - 12) What Is A Queue ?

Question - 13) What Are Linked Lists ?

Question - 14) What Are Trees ?

Question - 15) What Are Arrays ?

Great and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai