1.Recursion is similar to which of the following?
Switch Case
Loop
If-else
if elif else
2.In recursion, the condition for which the function will stop calling itself is ____________
Best case
Worst case
Base case
There is no such condition
3.Consider the following code snippet:
void my_recursive_function()
{
my_recursive_function();
}
int main()
{
my_recursive_function();
return 0;
}
What will happen when the above snippet is executed?
The code will be executed successfully and no output will be generated
The code will be executed successfully and random output will be generated
The code will show a compile-time error
The code will run for some time and stop when the stack overflows
4.What is the output of the following code?
void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);
my_recursive_function(n-1);
}
int main()
{
my_recursive_function(10);
return 0;
}
10
1
10 9 8 ... 1 0
10 9 8 ... 1
5.What is the base case for the following code?
void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);
my_recursive_function(n-1);
}
int main()
{
my_recursive_function(10);
return 0;
}
Return
printf(“%d “, n)
if(n == 0)
My_recursive_function(n-1)
6.How many times is the recursive function called, when the following code is executed?
void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);
my_recursive_function(n-1);
}
int main()
{
my_recursive_function(10);
return 0;
}
9
10
11
12
7.Which of the following statements is true?
Recursion is always better than iteration
Recursion uses more memory compared to iteration
Recursion uses less memory compared to iteration
Iteration is always better and simpler than recursion
8.What will be the output of the following code?
int cnt=0;
void my_recursive_function(int n)
{
if(n == 0)
return;
cnt++;
my_recursive_function(n/10);
}
int main()
{
my_recursive_function(123456789);
printf("%d",cnt);
return 0;
}
123456789
10
0
9
9.
void my_recursive_function(int n)
{
if(n == 0)
{
printf("False");
return;
}
if(n == 1)
{
printf("True");
return;
}
if(n%2==0)
my_recursive_function(n/2);
else
{
printf("False");
return;
}
}
int main()
{
my_recursive_function(100);
return 0;
}
True
False
10.What is the output of the following code?
int cnt = 0;
void my_recursive_function(char *s, int i)
{
if(s[i] == '\0')
return;
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
cnt++;
my_recursive_function(s,i+1);
}
int main()
{
my_recursive_function("thisisrecursion",0);
printf("%d",cnt);
return 0;
}
6
9
5
10
11.What is the output of the following code?
void my_recursive_function(int *arr, int val, int idx, int len)
{
if(idx == len)
{
printf("-1");
return ;
}
if(arr[idx] == val)
{
printf("%d",idx);
return;
}
my_recursive_function(arr,val,idx+1,len);
}
int main()
{
int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8};
int value = 2;
int len = 10;
my_recursive_function(array, value, 0, len);
return 0;
}
3
4
5
6
12.______is the first step in solving the problem
Understanding the Problem
Identify the Problem
Evaluate the Solution
None of these
13.______is the last step in solving the problem
Understanding the Problem
Identify the Problem
Evaluate the Solution
None of these
14.Following is true for understanding of a problem
Knowing the knowledgebase
Understanding the subject on which the problem is based
Communication with the client
All of the above
15.The six-step solution for the problem can be applied to
I. Problems with Algorithmic Solution
II. Problems with Heuristic Solution
Only I
Only II
Both I and II
Neither I nor II
16.______ solution requires reasoning built on knowledge and experience
Algorithmic Solution
Heuristic Solution
Random Solution
None of these
17.The correctness and appropriateness of ___________solution can be checked very easily.
Algorithmic solution
Heuristic solution
Random solution
None of these
18.The branch of computer that deals with heuristic types of problem is called _________________.
System software
Real time software
Artificial intelligence
None of these
19.Artificial Intelligence makes use of following prominently
Database
Data Warehouse
Knowledge base
None of these
20.Naming convention for variable is followed in company because ____________.
It enhances readability
It allows to work without conflicts
It enhances the efficiency
All of the above
Showing posts with label recursion. Show all posts
Showing posts with label recursion. Show all posts
Saturday, October 10, 2020
Analysis and Design of Algorithms Multiple choice questions
Wednesday, June 03, 2020
Algorithm design quiz
There are ______steps to solve the problem
A. Seven
B. Four
C. Six
D. Two
ANSWER: C
______is the first step in solving the problem
A. Understanding the Problem
B. Identify the Problem
C. Evaluate the Solution
D. None of these
ANSWER: B
______is the last step in solving the problem
A. Understanding the Problem
B. Identify the Problem
C. Evaluate the Solution
D. None of these
ANSWER: C
Following is true for understanding of a problem
A. Knowing the knowledgebase
B. Understanding the subject on which the problem is based
C. Communication with the client
D. All of the above
ANSWER: D
The six-step solution for the problem can be applied to I. Problems with Algorithmic Solution II. Problems with Heuristic Solution
A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
ANSWER: C
______ solution requires reasoning built on knowledge and experience
A. Algorithmic Solution
B. Heuristic Solution
C. Random Solution
D. None of these
ANSWER: B
While solving the problem with computer the most difficult step is __________.
A. describing the problem
B. finding out the cost of the software
C. writing the computer instructions
D. testing the solution
ANSWER: C
The correctness and appropriateness of ___________solution can be checked very easily.
A. algorithmic solution
B. heuristic solution
C. random solution
D. none of these
ANSWER: A
The main measure for efficiency algorithm are-
A. Processor and Memory
B. Complexity and Capacity
C. Data and Space
D. Time and space
ANSWER: D
What does the algorithmic analysis count?
A. The number of arithmetic and the operations that are required to run the program
B. The number of lines required by the program
C. The number of seconds required by the program to execute
D. None of these
ANSWER: A
Examples of O(1) algorithms are______________.
A. Multiplying two numbers.
B. assigning some value to a variable
C. displaying some integer on console
D. All of the above
ANSWER: D
Examples of O(n2) algorithms are______________.
A. Adding of two Matrices
B. Initializing all elements of matrix by zero
C. Both A and B
D. Neither A nor B
ANSWER: C
The complexity of three algorithms is given as: O(n), O(n2) and O(n3). Which should execute slowest for large value of n?
A. O(n)
B. O(n2)
C. O(n3)
D. All will execute in same time.
ANSWER: C
There are four algorithms A1, A2, A3, A4 to solve the given problem with the order log(n), nlog(n), log(log(n))n/log(n), Which is the best algorithm.
A. A1
B. A2
C. A3
D. A4
ANSWER: C
Express the formula (n-1)*(n-5) in terms of big Oh notation
A. O(1)
B. O(log n)
C. O(n)
D. O(n2)
ANSWER: D
The time complexity of binary search is________.
A. O(1)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: B
The time complexity of linear search is________.
A. O(1)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: C
In quick sort, the number of partitions into which the file of size n is divided by a selected record is
A. n
B. n - 1
C. 2
D. n/2
ANSWER: C
A sort technique is said to be stable when the original relative order of records with equal keys are retained after sorting.
A. True
B. False
ANSWER: A
The three factors contributing to the sort efficiency considerations are the efficiency in coding, machine run time and the space requirement for running the procedure.
A. True
B. False
ANSWER: A
How many passes are required to sort a file of size n by bubble sort method?
A. N2
B. N
C. N-1
D. N/2
ANSWER: C
How many number of comparisons are required in insertion sort to sort a file if the file is sorted in reverse order?
A. N2
B. N
C. N-1
D. N/2
ANSWER: A
How many number of comparisons are required in insertion sort to sort a file if the file is already sorted?
A. N2
B. N
C. N-1
D. N/2
ANSWER: C
The worst-case time complexity of Quick Sort is________.
A. O(n2)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: A
The worst-case time complexity of Bubble Sort is________.
A. O(n2)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: A
The worst-case time complexity of Selection Exchange Sort is________.
A. O(n2)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: A
The worst-case time complexity of Merge Sort is________.
A. O(n2)
B. O(log n)
C. O(n)
D. O(n logn)
ANSWER: D
The algorithm like Quick sort does not require extra memory for carrying out the sorting procedure. This technique is called __________.
A. in-place
B. stable
C. unstable
D. in-partition
ANSWER: A
Which of the following sorting procedures is the slowest?
A. Quick sort
B. Heap sort
C. Shell sort
D. Bubble sort
ANSWER: D
Two main measures for the efficiency of an algorithm are
A. Processor and memory
B. Complexity and capacity
C. Time and space
D. Data and space
ANSWER: C
The space factor when determining the efficiency of algorithm is measured by
A. Counting the maximum memory needed by the algorithm
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
D. Counting the maximum disk space needed by the algorithm
ANSWER: A
The time factor when determining the efficiency of algorithm is measured by
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
ANSWER: B
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
A. O (n log n)
B. O (n2 log n)
C. O (n2 + log n)
D. O (n2)
ANSWER: A
Which of the following case does not exist in complexity theory?
A. Best case
B. Worst case
C. Average case
D. Null case
ANSWER: D
The concept of order Big O is important because
A. It can be used to decide the best algorithm that solves a given problem
B. It determines the maximum size of a problem that can be solved in a given amount of time
C. It is the lower bound of the growth rate of algorithm
D. Both A and B
ANSWER: A
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
A. T(n) = 2T(n - 2) + 2
B. T(n) = 2T(n - 1) + n
C. T(n) = 2T(n/2) + 1
D. T(n) = 2T(n - 1) + 1
ANSWER: D
Which of the following sorting methods would be most suitable for sorting a list which is almost sorted?
A. Bubble Sort
B. Insertion Sort
C. Selection Sort
D. Quick Sort
ANSWER: B
The running time of insertion sort is
A. O(n^2)
B. O(n)
C. O(log n)
D. O(n log n)
ANSWER: A
A sort which compares adjacent elements in a list and switches where necessary is ____.
A. insertion sort
B. heap sort
C. quick sort
D. bubble sort
ANSWER: A
A sort which iteratively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
A. insertion sort
B. selection sort
C. heap sort
D. quick sort
ANSWER: A
The way a card game player arranges his cards as he picks them one by one can be compared to
A. Quick sort
B. Merge sort
C. Insertion sort
D. Bubble sort
ANSWER: C
Which among the following is the best when the list is already sorted?
A. Insertion sort
B. Bubble sort
C. Merge sort
D. Selection sort
ANSWER: A
As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be
A. Bubble sort
B. Insertion sort
C. Selection sort
D. Merge sort
ANSWER : B
In quick sort, the number of partitions into which the file of size n is divided by a selected record is
A. n
B. n - 1
C. 2
D. None of the above
ANSWER: C
The total number of comparisons made in quick sort for sorting a file of size n, is
A. O(n log n)
B. O(n2)
C. n(log n)
D. None of the above
ANSWER: A
Quick sort efficiency can be improved by adopting
A. non-recursive method
B. insertion method
C. tree search method
D. None of the above
ANSWER: A
For the improvement of efficiency of quick sort the pivot can be
A. the first element
B. the mean element
C. the last element
D. None of the above
ANSWER: B
Quick sort is the fastest available method of sorting because of
A. low over head
B. O(n log n) comparisons
C. low overhead and also O(n log n) comparisons
D. None of the above
ANSWER: C
Straight selection sort is basically a method of repeated
A. interchange
B. searching
C. position adjustment
D. None of the above
ANSWER: C
Number of selections required to sort a file of size N by straight selection requires
A. N - 1
B. log N
C. O(N2)
D. None of the above
ANSWER: A
For sorting a file of size n by straight selection sort, the number of comparisons made in the first pass is
A. n
B. n - 1
C. n(n - 1)/2
D. None of the above
ANSWER: B
Consider the following function f:
int f(int n)
{
int s = 0;
while(n > 1)
{
n = n/2;
s++;
}
return s;
}
What is the asymptotic complexity in terms of n? (Pick the smallest correct ANSWER)
A. O(nlog n)
B. O(n)
C. O( n)
D. O(log n)
E. O(n^2 )
ANSWER: D
What is the asymptotic runtime for traversing all nodes in a binary search tree with n nodes and printing them in order?
A. O(n · log(n))
B. O(n)
C. O( n)
D. O(log(n))
E. O(n^2 )
ANSWER: B
Assuming that the hash function for a table works well, and the size of the hash table is reasonably large compared to the number of items in the table, the expected (average) time needed to find an item in a hash table containing n items is
A. O(1)
B. O(log n)
C. O(nlog n)
D. O(n)
E. O( n)
ANSWER: A
Two main measures for the efficiency of an algorithm are
A. Processor and memory
B. Complexity and capacity
C. Time and space
D. Data and space
ANSWER: B
The time factor when determining the efficiency of algorithm is measured by
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
ANSWER: B
The space factor when determining the efficiency of algorithm is measured by
A. Counting the maximum memory needed by the algorithm
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
D. Counting the maximum disk space needed by the algorithm
ANSWER: A
Which of the following case does not exist in complexity theory
A. Best case
B. Worst case
C. Average case
D. Null case
ANSWER: D
The Worst case occur in linear search algorithm when
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
ANSWER: D
The Average case occur in linear search algorithm
A. When Item is somewhere in the middle of the array
B. When Item is not in the array at all
C. When Item is the last element in the array
D. When Item is the last element in the array or is not there at all
ANSWER: A
The complexity of the average case of an algorithm is
A. Much more complicated to analyze than that of worst case
B. Much more simpler to analyze than that of worst case
C. Sometimes more complicated and some other times simpler than that of worst case
D. None or above
ANSWER: B
The complexity of linear search algorithm is
A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)
ANSWER: A
The complexity of Binary search algorithm is
A. O(n)
B. O(logn)
C. O(n2)
D. O(n log n)
ANSWER: B
The complexity of merge sort algorithm is
A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)
ANSWER: D
Which of the following sorting algorithm is of divide-and-conquer type?
A. Bubble sort
B. Insertion sort
C. Quick sort
D. All of above
ANSWER: C
An algorithm that calls itself directly or indirectly is known as
A. Sub algorithm
B. Recursion
C. Polish notation
D. Traversal algorithm
ANSWER: B
Which one is the correct equation for Fibonacci sequence by Dynamic Programming?
A. F[n]=F[n-1]+F[n-2]
B. Fn=Fn-1+Fn-2
C. F(n)=F(n-1)+F(n-2)
D. All of these
ANSWER: A
Which equation is correct when a character is matched in Longest Common Subsequence problem?
A. c[i,j]=c[i,j-1]
B. c[i,j]=c[i-1,j-1]
C. c[i,j]=c[i-1,j]
D. None of these
ANSWER: B
Which equation is correct to multiply matrix in Matrix Chain Multiplication problem?
A. m[i,j]=min(m[i,k+1]+m[k+1,j]+pi-1pkpj)
B. m[i,j]=min(m[i,k]+m[k+1,j+1]+pi-1pkpj+1)
C. m[i,j]=min(m[i,k]+m[k+1,j]+pi-1pkpj)
D. m[i,j]=min(m[i,k]+m[k+1,j]+pi-1pk-1pj)
ANSWER: C
Dynamic Programming uses_____________
A. Store-and-forward
B. greedy method
C. brute-force
D. none
ANSWER: A
How many spanning tree T can be designed for the graph G with ‘n’ node?
A. 2n
B. n
C. n2-n
D. 2n-n
ANSWER: C
In this algorithm the edges has to be considered to make minimal spanning tree.
A. Prim’s algorithm
B. Kruskal’s algorithm
C. Dijikstra’s algorithm
D. none
ANSWER: B
In this algorithm the vertices has to be considered to make minimal spanning tree.
A. Prim’s algorithm
B. Kruskal’s algorithm
C. Dijikstra’s algorithm
D. none
ANSWER: A
Huffman coding is an example of
A. Greedy algorithm
B. variable length coding
C. both a and b
D. none
ANSWER: A
LCS stands for_________________________
A. Longest common subsequence
B. longest common substring
C. longest common string
D. longest common sequence
ANSWER: A
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
A. Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
B. Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
C. Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
D. Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
ANSWER: B
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
A. O(n^2 Logn)
B. O(n^2)
C. O(n Logn Logn)
D. O(nLogn)
ANSWER: D
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
A. Insertion Sort with time complexity O(kn)
B. Heap Sort with time complexity O(nLogk)
C. Quick Sort with time complexity O(kLogk)
D. Merge Sort with time complexity O(kLogk)
ANSWER: D
Which of the following is not true about comparison based sorting algorithms?
A. The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
B. Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
C. Counting Sort is not a comparison based sorting algortihm
D. Heap Sort is not a comparison based sorting algorithm.
ANSWER: A
The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is
A. T(n) = 2T(n – 2) + 2
B. T(n) = 2T(n – 1) + n
C. T(n) = 2T(n/2) + 1
D. T(n) = 2T(n – 1) + 1
ANSWER: D
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
A. T(n) <= 2T(n/5) + n
B. T(n) <= T(n/5) + T(4n/5) + n
C. T(n) <= 2T(4n/5) + n
D. T(n) <= 2T(n/2) + n
ANSWER: D
Which of the following sorting algorithms has the lowest worst-case complexity?
A. Merge Sort
B. Bubble Sort
C. Quick Sort
D. Selection Sort
ANSWER: A
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(= 2) numbers? In the recurrence equations given in the options below, c is a constant.
A. T(n) = 2T (n/2) + cn
B. T(n) = T(n – 1) + T(0) + cn
C. T(n) = 2T (n – 2) + cn
D. T(n) = T(n/2) + cn
ANSWER: D
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
A. T(nlogn)
B. T(n)
C. T(logn)
D. T(1)
ANSWER: B
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + vn for n = 2 and T(1) = 1 Which of the following statements is TRUE?
A. T(n) = ?(log n)
B. T(n) = ?(vn)
C. T(n) = ?(n)
D. T(n) = ?(n log n)
ANSWER: B
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
A. T(n log n), T(n log n) and T(n2)
B. T(n2), T(n2) and T(n Log n)
C. T(n2), T(n log n) and T(n log n)
D. T(n2), T(n log n) and T(n2)
ANSWER: D
Friday, May 12, 2017
Data structure in C with answers
Q.1 which of the fallowing reflects the correct
definition of recursion?
a)
Calling of a function by some other function b) Calling of a
function by main() function.
c)
Calling of a function by itself
d) None of the above.
Q.2 which of the fallowing reflects the correct meaning
of Dynamic memory allocation (DMA)?
a)
Memory allocation at Run time
b) Memory allocation at Compile time
c)
Memory allocation at Load time
d) None of the above
Q.3 which of the fallowing function is not used for
dynamic memory allocation or de-allocation in C?
a)
malloc() b)
calloc()
c)
free()
d)getch()
Q.4 let us assume that List is a pointer pointing to the
first node of singly linked list, and next is a pointer pointing to the next
node of linked list then after the execution of the while loop given below List
contains
While(List->next!=NULL)
List=List->next;
a)
List contains the
address of first node of linked list
b) List contains the address of second last node linked list.
b)
List contains the
address of second node linked list
d) List contains the address of last node of linked list.
Q.5 which of the following condition reflects that the Is
full condition in Circular Queue where rear ,front and size are variable with
their usual meaning in Circular queue
a)
if(front==(rear+1)mod size);
b) if(rear==(front+1)mod size);
c)
if(rear==front); d)
if(rear==-1 && front==-1);
Q.6 Stack fallows which of the fallowing principle?
a) FIFO
b) LIFO
c) Both
a) and b)
d) none of the above
Q.7 which of the fallowing condition reflects that the Is
Empty condition in linear Queue where rear ,front and size are variable with
their usual meaning in linear queue
a)
if(front==rear);
b) if(front!=rear);
c)
if(front+1==rear-1)
d) none of the above
Q.8 Queue fallows which of the following principle?
a) FIFO
b) LIFO
c) Both
a) and b)
d) none of the above
Common data for question 9 & 10. A binary tree is
given below:
Q.9 height of the binary tree is?
a) 2
b) 3
c) 4
d) 5
Q.10 number of leaf and non-leaf node in the binary tree
respectively is?
a) 4, 6
b)
6, 4
c) 5, 5
d)none of the above is correct
Subscribe to:
Posts (Atom)