Consider the following C++ switch statement: switch (i) { case 234: j = 1; break
ID: 655914 • Letter: C
Question
Consider the following C++ switch statement:
switch (i) {
case 234: j = 1; break;
case 78: j = 2; break;
case 191: j = 3; break;
case 45: j = 4; break;
case 26: j = 5; break;
case 833: j = 6; break;
case 17: j = 7; break;
case 93: j = 8; break;
case 511: j = 9; break;
case 405: j = 10; break;
case 865: j = 11; break;
case 273: j = 12; break;
case 430: j = 13; break;
case 89: j = 14; break;
case 31: j = 15; break;
case 66: j = 16; break;
case 213: j = 17; break;
case 765: j = 18; break;
}
(a) How many comparisons would be performed, on average, if linear search were used to implement this switch statement? (Assume that i always matches one of the case values listed and that each value is equally likely.) A
Explanation / Answer
#include <stdio.h>
#include <conio.h>
int binary_search(int key, int list[], int n)
{
int c=0;
int low = 1, high = n,mid;
while ( high >= low ) {
c++;
mid = ( low + high ) / 2;
if ( key < list[mid] ){c++;
high = mid - 1;}
else if ( key > list[mid] ){c++;
low = mid + 1;}
else {
printf("%d is present at location %d. ", key, mid);
break;
}
}
return c;
}
int linear_search(int item, int array1[],int n)
{
int c;
int count=0;
int flag=0;
for (c = 1; c <=n; c++)
{
count++;
if (array1[c] == item) /* if required element found */
{
count++;
printf("%d is present at location %d. ", item, c);
flag=1;
break;
}
}
if (flag==0)
{
printf("%d is not present in array. ", item);
}
return count;
}
int main()
{
int array[100], search, c, n,comp2,comp1;
printf("Enter the number of elements in array ");
scanf("%d",&n);
printf("Enter %d integer(s) ", n);
for (c = 1; c <=n; c++)
scanf("%d", &array[c]);
printf("Enter the element to search ");
scanf("%d", &search);
comp1=linear_search(search, array,n);
comp2=binary_search(search, array,n);
printf("No.of comparisions made in Linear Search:%d ",comp1);
printf("No.of comparisions made in binary Search:%d ",comp2);
getch();
return 0;
}
Answer for a) and b):
Enter the number of elements in array:18
Enter 18 integer(s)
233 78 191 45 26 833 17 93 511 405 865 273 430 89 31 66 213 765
Enter the element to search
405
405 is present at location 10
405 is present at location 8
No.of comparisions made in Linear Search: 10
No.of comparisions made in binary Search:8
Answer for c) :
If we implement jump table, advantages are
1. Provides compact code structure
2. It will reduce no.of source code statements
3. It will reduce the requirement to test return codes individually
But we will face following disadvantages
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.