Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

1. Which of the following methods can be used to search an element in a linked list?
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) All of the mentioned

Answer: a [Reason:] Iterative linear search can be used to search an element in a linked list. Binary search can be used only when the list is sorted.

2. Consider the following code snippet to search an element in a linked list:

```struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
_________;
}
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) temp = next
b) temp->next = temp
c) temp = temp->next
d) return 0

Answer: c [Reason:] The line “temp = temp->next” should be inserted to complete the above code.

3. What does the following code do?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[5] = {1,2,3,4,5};
int n = 5,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(60);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Finds the index of the first occurrence of a number in a linked list
b) Finds the index of the last occurrence of a number in a linked list
c) Checks if a number is present in a linked list
d) None of the mentioned

Answer: c [Reason:] The above code checks if a number is present in a linked list.

4. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[5] = {1,2,3,4,5};
int n = 5,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(-1);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

5. What is the time complexity of the above implementation of linear search on a linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above implementation of linear search on a linked list is O(n).

6. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp -> next != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(60);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

Answer: b [Reason:] The condition in the while loop “temp->next == 0”, checks if the current element is the last element. If the current element is the last element,the value of the current element is not compared with the value to be searched. So, even though the number 6 is present in the linked list, it will print not found.

7. Can binary search be applied on a sorted linked list in O(Logn) time?
a) No
b) Yes

Answer: a [Reason:] Since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.

8. What will be time complexity when binary search is applied on a linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity will be O(n) when binary search is applied on a linked list.

9. Consider the following recursive implementation of linear search on a linked list:

```struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return _________;
}```

Which of the following lines should be inserted to complete the above code?
a) 1
b) 0
c) linear_search(temp, value)
d) linear_search(temp->next, value)

Answer: d [Reason:] The line “linear_search(temp->next, value)”, should be inserted to complete the above code.

10. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return linear_search(temp->next, value);
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

Answer: a [Reason:] Since the element 6 is present in the linked list, the program prints “Found”.

11. How many times is the function linear_search() called when the following code is executed?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return linear_search(temp->next, value);
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
if(ans == 1)
printf("Found");
else
return 0;
}```

a) 5
b) 6
c) 7
d) 8

Answer: b [Reason:] The function linear_search() is called 6 times when the above code is executed.

12. What is the time complexity of the above recursive implementation of linear search?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above recursive implementation of linear search is O(n).

## Set 2

1. Which of the following methods can be used to find the factorial of a number?
a) Recursion
b) Iteration
c) Dynamic programming
d) All of the mentioned

Answer: d [Reason:] All of the above mentioned methods can be used to find the factorial of a number.

2. Which of the following recursive formula can be used to find the factorial of a number?
a) fact(n) = n * fact(n)
b) fact(n) = n * fact(n+1)
c) fact(n) = n * fact(n-1)
d) fact(n) = n * fact(1)

Answer: c [Reason:] fact(n) = n * fact(n – 1) can be used to find the factorial of a number.

3. Consider the following iterative implementation to find the factorial of a number:

```int main()
{
int n = 6, i;
int fact = 1;
for(i=1;i<=n;i++)
_________;
printf("%d",fact);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) fact = fact + i
b) fact = fact * i
c) i = i * fact
d) i = i + fact

Answer: b [Reason:] The line “fact = fact * i” should be inserted to complete the above code.

4. Consider the following recursive implementation to find the factorial of a number:

```int fact(int n)
{
if(_________)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) n = 0
b) n != 0
c) n == 0
d) n == 1

Answer: c [Reason:] The line “n == 0” should be inserted to complete the above code. Note: “n == 1” cannot be used because it does not take care of the case when n = 0, i.e when we want to find the factorial of 0.

5. What is the time complexity of the above recursive implementation to find the factorial of a number?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above recursive implementation to find the factorial of a number is O(n).

6. What is the space complexity of the above recursive implementation to find the factorial of a number?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: a [Reason:] The space complexity of the above recursive implementation to find the factorial of a number is O(1).

7. Consider the following recursive implementation to find the factorial of a number:

```int fact(int n)
{
if(n == 0)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

Which of the following lines is the base case?
a) return 1
b) return n * fact(n-1)
c) if(n == 0)
d) none of the mentioned

Answer: c [Reason:] The line “if(n == 0)” is the base case.

8. What is the output of the following code?

```int fact(int n)
{
if(n == 0)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 0;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

a) 0
b) 1
c) 2
d) 3

Answer: b [Reason:] The program prints 0!, which is 1.

9. What is the output of the following code?

```int fact(int n)
{
if(n == 0)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 1;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

a) 0
b) 1
c) 2
d) 3

Answer: b [Reason:] The program prints 1!, which is 1.

10. How many times will the function fact() be called when the following code is executed?

```int fact(int n)
{
if(n == 0)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

a) 4
b) 5
c) 6
d) 7

Answer: c [Reason:] The fact() function will be called 6 times with the following arguments: fact(5), fact(4), fact(3), fact(2), fact(1), fact(0).

11. What is the output of the following code?

```int fact(int n)
{
if(n == 0)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}```

a) 24
b) 120
c) 720
d) 1

Answer: b [Reason:] The function prints 5!, which is 120.

## Set 3

1. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
a) 5
b) 6
c) 7
d) 8

Answer: a [Reason:] The sixth fibonnaci number is 5.

2. Which of the following is not a fibonnaci number?
a) 8
b) 21
c) 55
d) 14

Answer: d [Reason:] 14 is not a fibonnaci number.

3. Which of the following methods can be used to find the nth fibonnaci number?
a) Dynamic programming
b) Recursion
c) Iteration
d) All of the mentioned

Answer: d [Reason:] All of the above mentioned methods can be used to find the nth fibonacci number.

4. Consider the following iterative implementation to find the nth fibonacci number:

```int main()
{
int  n = 10,i;
if(n == 1)
printf("0");
else if(n == 2)
printf("1");
else
{
int a = 0, b = 1, c;
for(i = 3; i <= n; i++)
{
c = a + b;
________;
________;
}
printf("%d",c);
}
return 0;
}```

Which of the following lines should be added to complete the above code?
a) c = b
b = a
b) a = b
b = c
c) b = c
a = b
d) a = b
b = a

Answer: b [Reason:] The lines “a = b” and “b = c” should be added to complete the above code.

5. Which of the following recurrence relations can be used to find the nth fibonacci number?
a) F(n) = F(n) + F(n – 1)
b) F(n) = F(n) + F(n + 1)
c) F(n) = F(n – 1)
d) F(n) = F(n – 1) + F(n – 2)

Answer: d [Reason:] The relation F(n) = F(n – 1) + F(n – 2) can be used to find the nth fibonacci number.

6. Consider the following recursive implementation to find the nth fibonacci number:

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return ________;
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) fibo(n – 1)
b) fibo(n – 1) + fibo(n – 2)
c) fibo(n) + fibo(n – 1)
d) fibo(n – 2) + fibo(n – 1)

Answer: b [Reason:] The line fibo(n – 1) + fibo(n – 2) should be inserted to complete the above code.

7. Consider the following recursive implementation to find the nth fibonnaci number:

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

Which of the following is the base case?
a) if(n == 1)
b) else if(n == 2)
c) return fibo(n – 1) + fibo(n – 2)
d) both a and b

Answer: d [Reason:] Both a and b are the base cases.

8. What is the time complexity of the above recursive implementation to find the nth fibonacci number?
a) O(1)
b) O(2*n)
c) O(n2
d) O(2n)

Answer: d [Reason:] The time complexity of the above recursive implementation to find the nth fibonacci number is O(2n).

9. What is the space complexity of the above recursive implementation to find the nth fibonacci number?
a) O(1)
b) O(2*n)
c) O(n2)
d) O(2n)

Answer: a [Reason:] The space complexity of the above recursive implementation to find the nth fibonacci number is O(1).

10. What is the output of the following code?

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = -1;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

a) 0
b) 1
c) Compile time error
d) Runtime error

Answer: d [Reason:] Since negative numbers are not handled by the program, the function fibo() will be called infinite times and the program will produce a runtime error when the stack overflows.

11. What is the output of the following code?

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

a) 1
b) 2
c) 3
d) 5

Answer: c [Reason:] The program prints the 5th fibonacci number, which is 3.

12. How many times will the function fibo() be called when the following code is executed?

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

a) 5
b) 6
c) 8
d) 9

Answer: d [Reason:] The function fibo() will be called 9 times, when the above code is executed.

13. What is the output of the following code?

```int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 10;
int ans = fibo(n);
printf("%d",ans);
return 0;
}```

a) 21
b) 34
c) 55
d) 13

Answer: b [Reason:] The program prints the 10th fibonacci number, which is 34.

## Set 4

1. Which algorithmic technique does Fibonacci search use?
a) Brute force
b) Divide and Conquer
c) Greedy Technique
d) Backtracking

Answer: b [Reason:] With every iteration, we divide the given array into two sub arrays(not necessarily equal).

2. Choose the recursive formula for the Fibonacci series.(n>=1)
a) F(n) = F(n+1) + F(n+2)
b) F(n) = F(n) + F(n+1)
c) F(n) = F(n-1) + F(n-2)
d) F(n) = F(n-1) – F(n-2)

3. Write a function for the Fibonacci search method.
a)

```public static int fibSearch(final int key, final int[] a)
{
int low = 0;
int high = a.length - 1;
int fibCurrent = 1;
int fibPrev = 1;
int N = a.length;
while (low <= high)
{
while(fibCurrent < N)
{
int tmp = fibCurrent + fibPrev;
fibPrev = fibCurrent;
fibCurrent = tmp;
N = N - (fibCurrent - fibPrev);
}
final int mid = low + (high - low) - (fibCurrent + fibPrev);
if      (key < a[mid]) high = mid - 1;
else if (key > a[mid]) low = mid + 1;
else return mid;
}
return -1;
}```

b)

```public static int fibSearch(final int key, final int[] a)
{
int low = 0;
int high = a.length - 1;
int fibCurrent = 1;
int fibPrev = 1;
int N = a.length;
while (low <= high)
{
int tmp = fibCurrent + fibPrev;
fibPrev = fibCurrent;
fibCurrent = tmp;
N = N - (fibCurrent - fibPrev);
final int mid = low + (high - low) - (fibCurrent + fibPrev);
if      (key < a[mid]) high = mid - 1;
else if (key > a[mid]) low = mid + 1;
else return mid;
}
return -1;
}```

c)

```public static int fibSearch(final int key, final int[] a)
{
int low = 0;
int high = a.length - 1;
int fibCurrent = 1;
int fibPrev = 1;
int N = a.length;
while (low <= high)
{
while(fibCurrent < N)
{
int tmp = fibCurrent + fibPrev;
fibPrev = fibCurrent;
fibCurrent = tmp;
N = N - (fibCurrent - fibPrev);
}
final int mid = low + (high - low) - (fibCurrent + fibPrev);
if      (key < a[mid]) low = mid + 1;
else if (key > a[mid]) high = mid - 1;
else return mid;
}
}```

d) None of the mentioned

Answer: a [Reason:] Here instead of choosing middle of the array as a point of array division, we use Fibonacci numbers, the division index are strictly between two Fibonacci numbers.

4. What is the time complexity of Fibonacci Search?
a) O(logn)
b) O(n)
c) O(n2)
d) O(nlogn)

Answer: a [Reason:] Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.

5. What are the advantages of Fibonacci Search?
a) When the element being searched for has a non uniform access storage
b) Can be used in magnetic tapes
c) Can be used for large arrays which do not fit in the CPUcache or in the RAM
d) All of the mentioned

Answer: d [Reason:] When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion.

6. What is the length of the step in jump search?
a) n
b) n/2
c) sqrt(n)
d) 1

Answer: c [Reason:] If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).

7. Select the code snippet for Jump Search.
a)

```public int jumpSearch(int arr[], int key)
{
int size = arr.length;
int step = floor(sqrt(size));
int prev = 0;
while (arr[(step > size ? step : size)] < key)
{
prev = step;
step += floor(sqrt(size));
if (step >= size)
{
return -1;
}
}
while (arr[prev] < key)
{
prev++;
if (prev == (step < size ? step : size))
{
return -1;
}
}
if (arr[prev] == key)
{
return prev;
}
return -1;
}```

b)

```public int jumpSearch(int arr[], int key)
{
int size = arr.length;
int step = floor(sqrt(size));
int prev = 0;
while (arr[(step < size ? step : size)] < key)
{
prev = step;
step += floor(sqrt(size));
if (step >= size)
{
return -1;
}
}
while (arr[prev] < key)
{
prev++;
if (prev == (step < size ? step : size))
{
return -1;
}
}
if (arr[prev] == key)
{
return prev;
}
return -1;
}```

c)

```public int jumpSearch(int arr[], int key)
{
int size = arr.length;
int step = floor(sqrt(size));
int prev = 0;
while (arr[(step > size ? step : size)] < key)
{
prev = step;
step += floor(sqrt(size));
if (step >= size)
{
return -1;
}
}
while (arr[prev] > key)
{
prev++;
if (prev == (step < size ? step : size))
{
return -1;
}
}
if (arr[prev] == key)
{
return prev;
}
return -1;
}```

d) None of the mentioned

Answer: b [Reason:] After finding the correct block of k elements, a sequential search is performed in this block.

8. What is the time complexity of Jump Search?
a) O(logn)
b) O(n)
c) O(sqrt(n))
d) O(nlogn)

Answer: c [Reason:] Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).

## Set 5

1. Free lists are used in
a) static memory allocation
b) dynamic memory allocation
c) contagious allocations
d) are used for speeding up linked list operations

Answer: b [Reason:] Their property is meant for dynamic allocations.

2. What are implicit and explicit implementations of freelists?
a) garbage collection and new or malloc operators respectively
b) new or malloc and garbage collection respectively
c) implicit implementation is not favored
d) explicit implementation is not favored

Answer: a [Reason:] Gc and new most widely known.

3. What datastructures can be used in implementing a free list?
b) linked list or sort trees
c) arrays
d) trees

Answer: b [Reason:] Sort trees can also be used in impelementing free lists which remaincomplex.

4. What are different ways of implementing free lists ? and which is simple among them ?
a) best fit, first fit, worst fit , simple-first fit
b) best fit, first fit, worst fit , simple-best fit
c) best fit, first fit, worst fit , simple-worst fit
d) best fit simple-best fit

Answer: a [Reason:] The‭ ‬simplest form of memory management system can be called as first-fit.‭ ‬a device or system maintains a single‭ ‬list of free memory locations.‭ ‬When request to memory is sent,‭ ‬the list is searched and the first block that is large enough is returned.

5. What is buddy memory management of free lists ?
a) modified version of first fit
b) buddy allocation keeps several‭ ‬free lists,‭ ‬each one holds blocks which are of one particular size
c) modified version of best fit
d) a tree representation of free lists

Answer: b [Reason:] When an allocation request is received,‭ ‬the list that holds blocks that are just large enough to satisfy the request are considered, and an open location is returned.‭ ‬If no‭ ‬free‭ ‬blocks that are smaller than two times the size that are requested are available,‭ ‬a larger block is split in two to satisfy the requirements.

6. How does implicit free lists(garbage collection) works in adding memory to free list ?
a) whichever comes last will be added to free list
b) whichever comes first will be added to free list
c) certain blocks cannot be used if there are no pointers to them and hence they can be freed
d) makes a probabilistic guess

Answer: c [Reason:] When no pointers pointing a block that means it is useless to be in memory.

a) internal fragmentation
b) it takes so much space
c) we no more have the hole lists in order of memory address, so it is difficult to detect if 2 holes remain adjacent in memory and shall be merged into one hole
d) both a and c are correct

Answer: d Explantion: Internal fragmentation is an issue to be dealt and it takes so much space.

8. Assume there is a free list which contains nodes and is filled with a value if it is already assigned and the value will be the size of requested block else will be 0.

``` z = startpoint;
while ((z < end) &&     didn't reach end
(*z <= len))           too small to satisfy request
{
assign this block
}```

The above code represents what ?
a) code for first fit
b) code for best fit
c) code for worst fit
d) none of the mentioned

Answer: a [Reason:] As z is start point and now from beginning we are moving and checking if we reached end and then checking size naively assigning the first block which is bigger than required size hence it is first fit.

9. How are free blocks linked together mostly and in what addressing order?
d) none of the mentioned

Answer: a [Reason:] A common way is circular linked list and address are arranged in increasing order because merging would be easier which is actually a problem in buddy memory allocation.

10. Accessing free list very frequently for wide range of addresses can lead to
a) paging
b) segmentation fault
c) memory errors
d) cache problems