# Multiple choice question for engineering

## Set 1

1. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

a) only i)

b) ii) and iii)

c) i) and iii)

d) i) ii) and iii)

### View Answer

2. All undirected Multigraphs contain eulerian cycles.

a) True

b) False

### View Answer

3. Determine the number of vertices for the given Graph or Multigraph?

G is a 4-regular Graph having 12 edges.

a) 3

b) 6

c) 4

d) Information given is insufficient

### View Answer

4. Which of the following statement is true.

a) There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9

b) There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9

c) None of the mentioned

d) There exists a MultiGraph as well as a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9

### View Answer

5. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

a) only i)

b) ii) and iii)

c) i) and iii)

d) i) ii) and iii)

### View Answer

6. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?

a) 3, Infinite, 4

b) 4, 3, Infinite

c) 4, Infinite, infinite

d) 4, Infinite, Infinite

### View Answer

7. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?

a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}

b) V = {v1, v2} E = {e1} = {{v1, v2}}

c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}

d) All of the mentioned.

### View Answer

8. What would be the Incidence Matrix of the given HyperGraph?

V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}

a) {{1,0,1,0},

{1,1,0,1},

{0,0,1,1}}

b) {{1,1,0,0},

{0,1,0,0},

{1,1,1,0}}

c) {{0,1,0,1},

{0,0,1,0},

{1,1,0,0}}

d) None of the Mentioned

### View Answer

9. What is the degree sequence of the given HyperGraph, in non-increasing order.

V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}

a) 3,2,1,1,1,1

b) 3,2,2,2,1,1

c) 3,2,2,2,2,1

d) 3,2,2,1,1,1

### View Answer

10. MultiGraphs having self-loops are called PseudoGraphs?

a) True

b) False

### View Answer

## Set 2

1. Which of the following methods can be used to find the largest and smallest number in a linked list?

a) Recursion

b) Iteration

c) Both Recursion and iteration

d) None of the mentioned

### View Answer

2. Consider the following code snippet to find the largest element in a linked list:

struct Node{ int val; struct Node *next; }*head; int get_max() { struct Node* temp = head->next; int max_num = temp->val; while(______) { if(temp->val > max_num) max_num = temp->val; temp = temp->next; } return max_num; }

Which of the following lines should be inserted to complete the above code?

a) temp->next != 0

b) temp != 0

c) head->next != 0

d) head != 0

### View Answer

3. Consider the following code snippet to find the smallest element in a linked list:

struct Node { int val; struct Node* next; }*head; int get_min() { struct Node* temp = head->next; int min_num = temp->val; while(temp != 0) { if(_________) min_num = temp->val; temp = temp->next; } return min_num; }

Which of the following lines should be inserted to complete the above code?

a) temp > min_num

b) val > min_min

c) temp->val < min_num

d) temp->val > min_num

### 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 get_max() { struct Node* temp = head->next; int max_num = temp->val; while(temp != 0) { if(temp->val > max_num) max_num = temp->val; temp = head->next; } return max_num; } int main() { int n = 9, arr[9] ={5,1,3,4,5,2,3,3,1},i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i<n;i++) { newNode =(struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next =newNode; temp = temp->next; } int max_num = get_max(); printf("%d %d",max_num); return 0; }

a) 5

b) 1

c) runtime error

d) garbage value

### View Answer

5. What is the output of the following code?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int get_max() { struct Node* temp = head->next; int max_num = temp->val; while(temp != 0) { if(temp->val > max_num) max_num = temp->val; temp = temp->next; } return max_num; } int get_min() { struct Node* temp = head->next; int min_num = temp->val; while(temp != 0) { if(temp->val < min_num) min_num = temp->val; temp = temp->next; } return min_num; } int main() { int i, n = 9, arr[9] ={8,3,3,4,5,2,5,6,7}; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i<n;i++) { newNode =(struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next =newNode; temp = temp->next; } int max_num = get_max(); int min_num = get_min(); printf("%d %d",max_num,min_num); return 0; }

a) 2 2

b) 8 8

c) 2 8

d) 8 2

### View Answer

6. What is the time complexity of the above iterative code used to find the smallest and largest element in a linked list?

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 largest element in a linked list:

struct Node { int val; struct Node* next; }*head; int max_of_two(int a, int b) { if(a > b) return a; return b; } int recursive_get_max(struct Node* temp) { if(temp->next == 0) return temp->val; return max_of_two(______, _______); }

Which of the following arguments should be passed to the function max_of two() to complete the above code?

a) temp->val,recursive_get_max(temp->next)

b) temp, temp->next

c) temp->val, temp->next->val

d) none of the mentioned

### View Answer

8. What is the output of the following code?

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int max_of_two(int a, int b) { if(a > b) return a; return b; } int recursive_get_max(struct Node* temp) { if(temp->next == 0) return temp->val; return max_of_two(temp->val,recursive_get_max(temp->next)); } int min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_get_min(struct Node* temp) { if(temp->next == 0) return temp->val; return min_of_two(temp->val,recursive_get_min(temp->next)); } int main() { int n = 9, arr[9] ={1,3,2,4,5,0,5,6,7},i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i<n;i++) { newNode =(struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next =newNode; temp = temp->next; } int max_num = recursive_get_max(head->next); int min_num = recursive_get_min(head->next); printf("%d %d",max_num,min_num); return 0; }

a) 7 1

b) 0 7

c) 7 0

d) 1 1

### View Answer

9. What is the time complexity of the recursive implementation used to find the largest and smallest element in a linked list?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### 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 min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_get_min(struct Node* temp) { if(temp->next == 0) return temp->val; return min_of_two(temp->val,recursive_get_min(temp->next)); } int main() { int n = 5, arr[5] ={1,1,1,1,1},i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i<n;i++) { newNode =(struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next =newNode; temp = temp->next; } int min_num = recursive_get_min(head->next); printf("%d",min_num); return 0; }

a) 1

b) 0

c) compile time error

d) runtime error

### View Answer

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

#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node* next; }*head; int min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_get_min(struct Node* temp) { if(temp->next == 0) return temp->val; return min_of_two(temp->val,recursive_get_min(temp->next)); } int main() { int n = 5, arr[5] ={1,1,1,1,1},i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i<n;i++) { newNode =(struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next =newNode; temp = temp->next; } int min_num = recursive_get_min(head->next); printf("%d",min_num); return 0; }

a) 4

b) 5

c) 6

d) 7

### View Answer

## Set 3

1. Which of the following methods can be used to find the largest and smallest element in an array?

a) Recursion

b) Iteration

c) Both recursion and iteration

d) None of the mentioned

### View Answer

2. Consider the following iterative code snippet to find the largest element:

int get_max_element(int *arr,int n) { int i, max_element = arr[0]; for(i = 1; i < n; i++) if(________) max_element = arr[i]; return max_element; }

Which of the following lines should be inserted to complete the above code?

a) arr[i] > max_element

b) arr[i] < max_element

c) arr[i] == max_element

d) none of the mentioned

### View Answer

3. Consider the following code snippet to find the smallest element in an array:

int get_min_element(int *arr, int n) { int i, min_element = arr[0]; for(i = 1; i < n; i++) if(_______) min_element = arr[i]; return min_element; }

Which of the following lines should be inserted to complete the above code?

a) arr[i] > min_element

b) arr[i] < min_element

c) arr[i] == min_element

d) none of the mentioned

### View Answer

4. What is the output of the following code?

#include<stdio.h> int get_max_element(int *arr,int n) { int i, max_element = arr[0]; for(i = 1; i < n; i++) if(arr[i] > max_element) max_element = arr[i]; return max_element; } int get_min_element(int *arr, int n) { int i, min_element = arr[0]; for(i = 1; i < n; i++) if(arr[i] < min_element) min_element = arr[i]; return min_element; } int main() { int n = 7, arr[7] = {5,2,4,7,8,1,3}; int max_element = get_max_element(arr,n); int min_element = get_min_element(arr,n); printf("%d %d",max_element,min_element); return 0; }

a) 5 3

b) 3 5

c) 8 1

d) 1 8

### View Answer

5. What is the output of the following code?

#include<stdio.h> int get_max_element(int *arr,int n) { int i, max_element = arr[0]; for(i = 1; i < n; i++) if(arr[i] > max_element) max_element = arr[i]; return max_element; } int get_min_element(int *arr, int n) { int i, min_element; for(i = 1; i < n; i++) if(arr[i] < min_element) min_element = arr[i]; return min_element; } int main() { int n = 7, arr[7] = {1,1,1,0,-1,-1,-1}; int max_element = get_max_element(arr,n); int min_element = get_min_element(arr,n); printf("%d %d",max_element,min_element); return 0; }

a) 1 -1

b) -1 1

c) 1 Garbage value

d) Garbage value -1

### View Answer

6. What is the time complexity of the above iterative implementation used to find the largest and smallest element in an array?

a) O(1)

b) O(n)

c) O(n^{2})

d) None of the mentioned

### View Answer

7. Consider the following recursive implementation to find the largest element in an array:

int max_of_two(int a, int b) { if(a > b) return a; return b; } int recursive_max_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return _______; }

Which of the following lines should be inserted to complete the above code?

a) max_of_two(arr[idx], recursive_max_element(arr, len, idx))

b) recursive_max_element(arr, len, idx)

c) max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1))

d) recursive_max_element(arr, len, idx + 1)

### View Answer

8. What is the output of the following code?

#include<stdio.h> int max_of_two(int a, int b) { if(a > b) return a; return b; } int min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_max_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1)); } int recursive_min_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1)); } int main() { int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10}; int max_element = recursive_max_element(arr,n,idx); int min_element = recursive_min_element(arr,n,idx); printf("%d %d",max_element,min_element); return 0; }

a) -1 10

b) 10 -1

c) 1 10

d) 10 1

### View Answer

9. What is the time complexity of the above recursive implementation used to find the largest and the smallest element in an array?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

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

int min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_min_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1)); } int main() { int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10}; int min_element = recursive_min_element(arr,n,idx); printf("%d",min_element); return 0; }

a) 9

b) 10

c) 11

d) 12

### View Answer

11. What is the output of the following code?

#include<stdio.h> int max_of_two(int a, int b) { if(a > b) return a; return b; } int min_of_two(int a, int b) { if(a < b) return a; return b; } int recursive_max_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1)); } int recursive_min_element(int *arr, int len, int idx) { if(idx == len - 1) return arr[idx]; return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1)); } int main() { int n = 5, idx = 0, arr[] = {1,1,1,1,1}; int max_element = recursive_max_element(arr,n,idx); int min_element = recursive_min_element(arr,n,idx); printf("%d %d",max_element,min_element); return 0; }

a) 1 1

b) 0 0

c) compile time error

d) runtime error

### View Answer

## Set 4

1. What is the time complexity for a given pancake sort given it undergoes “n” flip operations?

a) O(n)

b) O(n^{2})

c) O(n^{3})

d) O(2n)

### View Answer

^{2}).

2. Which operation is most essential to the process of pancake sort?

a) Flip the given data

b) Find the largest of given data

c) Finding the least of given data

d) Inserting something into the given data

### View Answer

3. There is one small error in the following flip routine. Find out which line it is on.

1 void flip(int arr[], int i) 2 { 3 int t, init = 0; 4 while (init < i) 5 { 6 t = arr[init]; 7 arr[i] = arr[init] ; 8 arr[i] = t; 9 init++; 10 i--; 11 } 12 }

a) Line 3

b) Line 5

c) Line 7

d) Line 9

### View Answer

4. How many flips does the simplest of pancake sorting techniques require?

a) 3nā3 flips

b) 2n-4 flips

c) 2n-3 flips

d) 3n-2 flips

### View Answer

5. Pancake Sorting appears in which of the following?

a) Frequency Scaling

b) Storage Virtualization

c) Parallel Processing

d) Neural Networking

### View Answer

6. In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______

a) Faced down

b) Faced up

c) It doesn’t matter

d) Both sides are burnt

### View Answer

7. In a computational complexity theory, a problem with decision making is said to be NP-complete when it is both in NP and NP-hard. What does NP mean?

a) Non Polynomial time

b) Non-deterministic Probabilistic

c) Non-deterministic Polynomial time

d) Non Probabilistic time

### View Answer

8. When we realize a specific implementation of a pancake algorithm, every move when we find the greatest of the sized array and flipping can be modeled through __________

a) Combinations

b) Exponential functions

c) Logarithmic functions

d) Permutations

### View Answer

9. The Pancake Problems (1975, 1979, 1973) did NOT involve which of the following people?

a) Bill Gates

b) Jacob Goodman

c) Christos Papadimitriou

d) John Goodman

### View Answer

10. There is a one line error in the following routine. Find that line.

1. int Max(int a[], int n) 2. { 3. int mi, i; 4. for (mi = 0, i = 0; i < n; i++) 5. if (a[i] > a[mi]) 6. mi = i; 7. return mi; 8. }

a) Line 2

b) Line 4

c) Line 6

d) Line 5

### View Answer

## Set 5

1. What are parallel arrays?

a) Arrays of the same size

b) Arrays allocated one after the other

c) Arrays of the same number of elements

d) Arrays allocated dynamically

### View Answer

2. Which of the following can be called a parallel array implementation?

a)

firstName = ['Joe','Bob','Frank','Hans'] lastName = ['Smith','Seger','Sinatra','Schultze'] heightInCM = [169,158,201,199] for i in xrange(len(firstName)): print "Name:",firstName[i], lastName[i] print "Height in CM:,",heightInCM[i]

b)

firstName = ['Joe','Bob','Frank','Hans'] lastName = ['Smith','Seger'] heightInCM = [169,158] for i in xrange(len(firstName)): print "Name:",firstName[i], lastName[i] print "Height in CM:,",heightInCM[i]

c)

firstName = ['Joe','Bob'] lastName = ['Smith','Seger','Sinatra','Schultze'] heightInCM = [169,158] for i in xrange(len(firstName)): print "Name:",firstName[i], lastName[i] print "Height in CM:,",heightInCM[i]

d) None of the mentioned

### View Answer

3. What are the advantages of parallel arrays over the traditional arrays?

a) When a language does not support records, parallel arrays can be used

b) Increased locality of reference

c) Ideal cache behavior

d) All of the mentioned

### View Answer

4. What are some of the disadvantages of parallel arrays?

a) Poor locality of reference for non-sequential access

b) Very little direct language support

c) Expensive to shrink or grow

d) All of the mentioned

### View Answer

5. What is a sorted array?

a) Arrays sorted in numerical order

b) Arrays sorted in alphabetical order

c) Elements of the array are placed at equally spaced addresses in the memory

d) All of the mentioned

### View Answer

6. To search for an element in a sorted array, which searching technique can be used?

a) Linear Search

b) Jump Search

c) Binary Search

d) Fibonacci Search

### View Answer

7. What are some of the applications of sorted arrays?

a) Commercial computing

b) Priority Scheduling

c) Discrete Mathematics

d) All of the mentioned

### View Answer

8. What is the worst case time complexity of inserting an element into the sorted array?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})