# 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

### View Answer

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

struct Node { int val; struct Node* next; }*head; int linear_search(int value) { struct Node *temp = head->next; 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

### View Answer

3. What does the following code do?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int linear_search(int value) { struct Node *temp = head->next; 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; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; struct Node *temp; temp = head; 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 printf("Not found"); 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

### View Answer

4. What is the output of the following code?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int linear_search(int value) { struct Node *temp = head->next; 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; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; struct Node *temp; temp = head; 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 printf("Not found"); return 0; }

a) Found

b) Not found

c) Compile time error

d) Runtime error

### View Answer

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(n^{2})

d) O(n^{3})

### View Answer

6. What is the output of the following code?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int linear_search(int value) { struct Node *temp = head->next; 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; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; struct Node *temp; temp = head; 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 printf("Not found"); return 0; }

a) Found

b) Not found

c) Compile time error

d) Runtime error

### View Answer

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

a) No

b) Yes

### View Answer

8. What will be time complexity when binary search is applied on a linked list?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

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

struct Node { int val; struct Node* next; }*head; 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)

### View Answer

10. What is the output of the following code?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; 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; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; struct Node *temp; temp = head; 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(head->next,6); if(ans == 1) printf("Found"); else printf("Not found"); return 0; }

a) Found

b) Not found

c) Compile time error

d) Runtime error

### View Answer

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; }*head; 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; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; struct Node *temp; temp = head; 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(head->next,6); if(ans == 1) printf("Found"); else printf("Not found"); return 0; }

a) 5

b) 6

c) 7

d) 8

### View Answer

12. What is the time complexity of the above recursive implementation of linear search?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

## 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

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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(n^{2})

d) O(n^{3})

### View Answer

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(n^{2})

d) O(n^{3})

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

2. Which of the following is not a fibonnaci number?

a) 8

b) 21

c) 55

d) 14

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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)

### View Answer

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

### View Answer

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(n^{2}

d) O(2^{n})

### View Answer

^{n}).

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(n^{2})

d) O(2^{n})

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## Set 4

1. Which algorithmic technique does Fibonacci search use?

a) Brute force

b) Divide and Conquer

c) Greedy Technique

d) Backtracking

### View Answer

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)

### View Answer

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

### View Answer

4. What is the time complexity of Fibonacci Search?

a) O(logn)

b) O(n)

c) O(n^{2})

d) O(nlogn)

### View Answer

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

### View Answer

6. What is the length of the step in jump search?

a) n

b) n/2

c) sqrt(n)

d) 1

### View Answer

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

### View Answer

8. What is the time complexity of Jump Search?

a) O(logn)

b) O(n)

c) O(sqrt(n))

d) O(nlogn)

### View Answer

## 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

### View Answer

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

### View Answer

3. What datastructures can be used in implementing a free list?

a) only linked list

b) linked list or sort trees

c) arrays

d) trees

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

7. What are the disadvantages in implementing buddy system algorithm for free lists ?

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

### View Answer

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

### View Answer

9. How are free blocks linked together mostly and in what addressing order?

a) circular linked list and increasing addressing order

b) linked list and decreasing addressing order

c) linked list and in no addressing order

d) none of the mentioned

### View Answer

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