Linear Search Interview Questions Part 2

23.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
Ans. c
If the search key matches the very first item, with one comparison we can terminate.If it is second,two comparisons ,etc.So,average is (1+2+3+…+n)/n , i.e.,(n+1)/2

24. 6 files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 number of records respectively.In what order should they be stored so as to optimize access time .Assume each file is accessed with the same frequency.
a. F3,F4,F1,F5,F6,F2
b. F2,F6,F5,F1,F4,F3
c. F1,F2,F3,F4,F5,F6
d. Ordering is immaterial as all files are accessed with the same frequency
Ans. a
Since the access is sequential,greater the distance,greater will be the access time.Since all the files are referenced with equal frequency,overall access time can be reduced by arranging them as in option (a).

25. For small arrays, _____________ is a good solution because it's straightforward.
a. binary search
b. linear search
c. fibonacci search
d. none of the above
Ans. b

26. If the loop in a linear search finishes without finding a match,the search is failed and _____ is returned.
Ans. -1
If the loop finishes without finding a match, the search failed and -1 is returned.



27. What is the output of the following program using linear search
#include
using namespace std;

int LinearSearch(const int *Array, const int Size, const int ValToSearch)
{
bool NotFound = true;
int i = 0;

while(i < Size && NotFound)
{
if(ValToSearch != Array[i])
i++;
else
NotFound = false;
}

if( NotFound == false )
return i;
else
return -1;
}

int main()
{
int Number[] = { 67, 278, 463, 2, 4683, 812, 236, 38 };
int Quantity = sizeof(Number) / sizeof(int);
int NumberToSearch = 0;

cout << "Enter the number to search: "; cin >> NumberToSearch;
int i = LinearSearch(Number, Quantity, NumberToSearch);

if(i == -1)
cout << NumberToSearch << " was not found in the collection\n\n";
else
{
cout << NumberToSearch << " is at the " << i+1;
if( i == 0 )
cout<< "st position of the collection\n\n";
else if( i == 1 )
cout<< "nd position of the collection\n\n";
else if( i == 2 )
cout<< "rd position of the collection\n\n";
else
cout<< "th position of the collection\n\n";
}

return 0;
}


Enter the number to search: 278
a. 278 is at the 1st position of the collection
b. 278 is at the 2nd position of the collection
c. 278 is at the 3rd position of the collection
d. 278 was not found in the collection
Ans:b


28.For the above program what is the output for
Enter the number to search: 288
a. 288 is at the 1st position of the collection
b. 288 is at the 2nd position of the collection
c. 288 is at the 3rd position of the collection
d. 288 was not found in the collection
Ans:d