Searching And Sorting

1:	The time complexity of linear search algorithm over an array of n elements is
	A. O (log2 n) B. O(n) C. O(n log2 n) D. 0 (n2)
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :
2:	The time required to search an element in a linked list of length n is
	A. O(log2 n) B.  O(n) C. O(1) D. 0 (n2)
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

3:	The worst case time required to search a given element in a sorted linked list of length n is
	A. O(1) B. O(log2 n) C. O(n) D. O(n log2 n)
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

4:	Which of the following sorting algorithms does not have a worst case running time of O(n2)?
	A. Insertion sort B. Merge sort C. Quick sort D. Bubble sort
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

5:	For a linear search in an array of n elements the time complexity for best, worst and average case are ......., ....... and ........ respectively
	A. O(n), O(1), and O(n/2) B. O(1), O(n) and O(n/2) C. O(1),O(n) and O(n) D. O(1), O(n) and (n-1/2)

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/1.html#ixzz2fUPEvw53

6:	The average time required to perform a successful sequential search for an element in an array A(1 : n) is given by
	A. (n + 1)/2 B. log2n C. n(n + 1)/2 D. n2
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

7:	Using the standard algorithm, what is the time required to determine that a number n is prime ?
	A. Linear time B. Logarithmic time C. Constant time D. Quadratic time
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

8:	The average time required to perform a successful sequential search for an element in an array A (1 : n) is given by
	A. (n+1)/2 B. n (n + 1)/2 C. log(n/2) D. n2
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

9:	Which of the following is false ?
	A. A serial search begins with the first array element B. A serial search continues searching, element by element, either until a match is found or until the end of the array is encountered C. A serial search is useful when the amount of data that must be search is small D. For a serial search to work, the data in the array must be arranged in either alphabetical or numerical order
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation :

10:	A search begins the search with the element that is located in the middle of the array
	A. serial B. random C. parallel D. binary
	View Answer Report Error Comment Answer & Explanation Answer: Option D

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/2.html#ixzz2fUPNWaik

11:	To sort many large object or structures, it would be most efficient to
	A. Place reference to them in and array an sort the array B. Place them in a linked list and sort the linked list C. Place pointers to them in an array and sort the array D. Place them in an array and sort the array
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

12:	To sort many large objects or structures, it would be most eficient to place
	A. Them in an array and sort the array B. Pointers to them in an array and sort the array C. Them in a linked list and sort the linked list D. References to them in an array and sort the array
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

13:	A matrix "a" is called lower triangular if and only if for all j > ai j = 0. If such a matrix is to be sorted in a one dimensional array, A then ai j could be mapped to which of the following index of A ?
	A. 1/2 * i (i + 1) j  B. i + j C. i (i + 1) + j D. none of these
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

14:	Average successful search time for sequential search on 'n' items is
	A. n/2 B. (n-1)/2 C. (n+1)/2 D. None of these
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation : If search key matches the very first item, with one comparison we can terminate. If it is second, two comparisons, etc. Average =[ n (n + 1) ] / 2

15:	The average search time of hashing, with linear probing will be less if the load factor
	A. Is far less than one B. equals one C. is far greater than one D. none of these
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation : Load factor is the ratio of number of records that are currently present and the total number of records that can be present. If the load factor is less, free space will be more. This means probability of collision is less. So, search time will be less.

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/3.html#ixzz2fUPVl655

16:	Suppose DATA array contains 1000000 elements. Using the binary search algorithm, one requires only about n comparisons to find the location of an item in the DATA array, then n is
	A. 60 B. 45 C. 20 D. None of these
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

17:	Which of the following sorting procedure is the slowest ?
	A. Quick sort B. Heap sort C. Shell sort D. Bubble sort
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation :

18:	Which of the following sorting method is stable ?
	A. Straight insertion sort B. Binary insertion sort C. Shell sort D. Heap sort
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

19:	Which of the following best describes sorting ?
	A. Accessing and processing each record exactly once B. Finding the location of the record with a given key C. Arranging the data (record) in some given order D. Adding a new record to the data structure
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

20:	A sort which compares adjacent elements in a list and switches where necessary is
	A. insertion sort B. heap sort C. quick sort D. bubble sort
	View Answer Report Error Comment Answer & Explanation Answer: Option D

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/4.html#ixzz2fUPd59UT

21:	A sort which iteratively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
	A. insertion sort B. selection sort C. heap sort D. quick sort
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

22:	Which of the following statements is used in the binary search algorithm to halve the array ?
	A. middle Sub = (start Sub + stop Sub)/2; B. middle Sub = start Sub + stop Sub/2; C. middle Sub = middle Sub/2; D. middle Sub = (stop Sub - start Sub)/2;
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

23:	The data for which you are searching is called
	A. search argument B. sorting argument C. detection argument D. binary argument
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

24:	If the binary search algorithm determines that the search argument is in the lower half of the array, which of the following statements will, set the appropriate variable to the appropriate value?
	A. start Sub = middle Sub - 1; B. start Sub = middle Sub + 1; C. stop Sub = middle Sub - 1; D. stop Sub = middle Sub + 1.
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

25:	Which of the following is false ?
	A. A binary search begins with the middle element in the array B. A binary search continues having the array either until a match is found or until there are no more elements to search C. If the search argument is greater than the value located in the middle of the binary, the binary search continues in the upper  half of the array D. For a binary search to work, the data in the array must be arranged in either alphabetical or numerical order
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/5.html#ixzz2fUPl4rOc

26:	The number of possible comutative binary operations that can be defined on a set of n elements (for a given n) is
	A. 2 B. n C. 2n D. n2
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

27:	The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order, using bubble sort is
	A. 11 B. 12 C. 13 D. 14
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation :

28:	The average successful search time taken by binary search on a sorted array of 10 items is
	A. 2.6 B. 2.7 C. 2.8 D. 2.9
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation : The 10 items i1, i2, ..., i10 may be arranged in a binary search trees as in Fig   To get i5, the number of comparision needed is 1; for i2, it is 2; for i8 it is 2; for i1 it is 3, and so on. The average is (1+(2+2) +(3+3+3+3)+(4+4+4))/10, i.e., 2.9.

29:	The average successful search time for sequential search on 'n' items is
	A. n/2 B. (n-1)/2 C. (n+1)/2 D. log (n)+1
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation : If the search key matches the very first item, with one ocmparision we can terminate. If it is second, two comparisons , etc. So, average is (1+2+...+n)/n .i.e. (n+1)/2

30:	The running time of an algorithm T(n), where 'n' is the input size, is given by T(n) = 8T(n/2) + qn, if n>1 Where p,q are constants. The order of this algorithm is
	A. n2 B. nn C. n3 D. n
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/6.html#ixzz2fUPtX7qk

31:	L:et m, n be positive integers. Define Q (m, n) as Q (m, n) = 0, if m>n Then Q (m, 3) is (a div b, gives the quotient when a is divided by b)
	A. a constant B. p x (m mod 3) C. p x (m div 3) D. 3 x p
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation : Let m>n. Let m/n yield a quotient x and remainder y. So, m= n*x+y and y<m div 3 is the quotient when m is divided by 3. So, that many times p is added, before we terminate recursion by satisfying the end condition Q (m,n) = 0 if m<n. Hence the result.

32:	Sorting is useful for
	A. report generation B. responding toe queries easily C. making searching easier and efficient D. All of these
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation :

33:	Choose the correct statements
	A. Internal sorting is used if the number of items to be sorted is very large. B. External sorting is used if the number of items to be sorted is very large C. External sorting needs auxilary storage D. Both (b) & (c)
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation :

34:	A sorting technique that guarantees that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
	A. stable B. consistent C. external D. linear
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

35:	The way a card game player arranges his cards as he picks them up one by one, is an example of
	A. bubble sort B. Selection sort C. insertion sort D. merge sort
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/7.html#ixzz2fUQJUWL0

You want to check whether a given set of items is sorted. Which of the following sorting methods will be most efficient if it is already in sorted order?
A. Bubble sort B. Selection sort C. Insertion sort D. Merge Sort
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

37:	Which of the following sorting methods will be the best if number of swappings done, is the only measure of efficienty?
	A. Bubble sort B. Selection sort C. Insertion sort D. Quick sort
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

38:	You are asked to sort 15 randomly generated numbers. You should prefer
	A. bubble sort B. Selection sort C. Insertion sort D. Quick sort
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

39:	As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be
	A. bubble sort B. insertion sort C. selection sort D. heap sort
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

40:	The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is 4 digit decimal number)
	A. 280 B. 40 C. 47 D. 38
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation : The maximum number of comparison is number of items ´ radix ´ number of digits i.e., 7´10´4 = 280.

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/8.html#ixzz2fUQcUfhq

41:	Which of the following algorithms exhibits the unnatural behavior that, minimum number of comparisons are needed if the list to be sorted is in the reverse sorted order and maximum number of comparisons are needed if they are already in sorted order?
	A. heap sort B. Radix sort C. Binary insertion sort D. There can't be any such sorting method
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation :

42:	Which of the following sorting algorithm has the worst time complexity of nlog(n)?
	A. Heap sort B. Quick sort C. Insertio nsort D. Selection sort
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

43:	Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?
	A. Heap sort B. Quick sort C. Insertion sort D. Selection sort
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation :

44:	The order of the binary search algorithm is
	A. n B. n2 C. nlog(n) D. log(n)
	View Answer Report Error Comment Answer & Explanation Answer: Option D Explanation : Let there be ‘n’ items to be searched, After the first search the list is divided into two, each of length n/2. After the next search, 2 liss, each of length n/4 and so on. This successive division has to stop when the length of lists becomes 1. Let it happen after k steps. After the k steps, n/2k=1. Solving, k = log2n. Hence the order is log(n).

45:	Merge sort uses
	A. divide and conquer strategy B. backtracking approach C. heuristic search D. greedy approach
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/9.html#ixzz2fUQjPmt6

46:	To store details of an employee, a storage space of 100 characters is needed. A magentic tape with a density of 1000 characters per inch and an inter-record gap of 1 inch is used to store information about all employees in the company. What should be the blocking factor so that the wastage does not exceed one-third of the tape?
	A. 0.05 B. 20 C. 10 D. 0.1
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation : Blocking factor is the number of logical records that is packed to one physical record. Here in every 3 inch, there should be 2 inch of information. Hence 2´ 10 = 20 logical records.

47:	A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
	A. 50.2 sec B. 6.7 sec C. 72.7 sec D. 11.2 sec
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation : In the best case, quick sort algorithm makes nlog(n) comparisons. So 1000´log (1000) = 9000 comparisons, which takes 100s. To sort 100 names a minimum of 100 (log 100) = 600 comparisons are needed. The takes 100´600/9000= 6.7s.

48:	A machine took 200 see to sort 200 names, using bubble sort. In 800 sec, it can approximately sort
	A. 400 names B. 800 names C. 750 names D. 800 names
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation : For sorting 200 names bubble sort makes 200x(199/2)= 19900 c9omaprisons. The time needed for 1 comparison is 200 sec (approximately). In 800 sec it can make 80,000 comparisons. We  have to find n, such that n(n-1)/2= 80,000. Solving, n is approximately 400.

49:	Which of the following is useful in implementing quick sort?
	A. Stack B. Set C. List D. Queue
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

50:	The recurrence relation that arises in relation with the complexity of binary search is
	A. T(n)= T(n/2)+k, where k is a constant B. T(n)= 2 T(n/2)+k, where k is a constant C. T(n) = T(n/2)+log(n) D. T(n) = T (n/2) + n
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/10.html#ixzz2fUQrjDq6

51:	Assume 5 buffer pages are available to sort a file of 105 pages. The cost of sorting using m-way merge sort is
	A. 206 B. 618 C. 840 D. 926
	View Answer Report Error Comment Answer & Explanation Answer: Option C Explanation : In the first pass we can create [105/5] = 21 sorted sub-files, each 5 pages long. In the second pass by 4-way merging (4 because one of the 5 available buffers has to be reserved for holding the output), one can create [21/4] = 6 sorted sub-files, each 20 pages long (except the last). Again applying 4-way merge sort, we get create [6/4] = 2 sorted sub-files. These two can be merged to get the final sorted file. We need a total of 4 passes. Total cost will be 2 x 105 x 4 = 840 units.

52:	What is the number of swaps required to sort n elements using selection sort, in the worst case?
	A. Θ(n) B. Θ(n log n) C. Θ(n2) D. Θ(n2 log n)
	View Answer Report Error Comment Answer & Explanation Answer: Option A Explanation : Note that we are concerned about the swaps, not the comparisons. In the best case, there is no need for any swap. The best case scenario is when the given list of elements is already in sorted order. In the worst case, we need (n-1) swaps. For example, consider the list 10, 5, 6, 7, 8, 9. We need 5 swaps. To conclude, 0 ≤ (the number of required swaps) < n

53:	In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an Θ(n) time algorithm. What is the worst case time complexity of the quick sort?
	A. Θ(n) B. Θ(n log n) C. Θ(n2) D. Θ(n2 log n)
	View Answer Report Error Comment Answer & Explanation Answer: Option B Explanation : If the list is evenly split at each and every step, the recursion depth will be log n, and the (worst) time complexity will be n log n. In the given scenario, the recursion depth cannot be greater than 2 log n. So the (worst) time complexity will still be bound by n log n.

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/15/11.html#ixzz2fUQzlZdS