Algorithms Test - 2 - PDF Flipbook
Algorithms Test - 2
275 Views
79 Downloads
PDF 5,015,873 Bytes
GATE
CSE
Algorithms
Test-02Solutions
ALGORITHMS
1. The transformation matrix required for conversion of CMY
color model to RGB color model is given as:
R C1
a) �G� = �M�-�1�
B Y1
R C1
b) �G� = �M�-�2�
B Y3
R 1C
c) �G � = �1�-�M�
M 1Y
R C 0.5
d) �G� = �M�-�0.5�
B Y 0.5
Answer: (c)
Solution:
Primaries: Cyan, Magenta and yellow. CMY is used mainly
for hardcopy devices such as color printers. Generally, the
conversion from RGB to CMY follows the equation;
C 1R
�M� = �1� – �G�
Y 1B
Therefore, the conversion from CMY to RGB follows the
equation;
R 1C
�G� = �1� – �M�
B 1Y
1
2. Let G be a connected undirected graph of 100 vertices and
300 edges. The weight of a minimum spanning tree of G is
500. When the weight of each edge of G is increased by five
the weight of a minimum spanning tree becomes
Answer: 995
Number of vertices = 100
Number of edges = 300
Minimum spanning tree cost = 500
If weight of each is increases by ‘5’
Then weight of MST = 500 + (99 × 5) = 995
3. With regard to linked list, which of the following statement is
false?
a) An algorithm to search for an element in a singly linked list
requires O(n)operations in the worst case.
b) An algorithm for deleting the first element in a singly linked
list requires O(n) operations in the worst case.
c) An algorithm for finding the maximum value in a circular
linked list requires O(n)operations.
d) An algorithm for deleting the middle node of a circular
linked list requires O(n)operations.
Answer: (b)
Solution:
An algorithm for deleting the first element in a singly linked
list requires O(1) operation in the worst case. Make the second
2
element as front element of linked list and delete head node
requires only constant time.
4. The in-order traversal of the following tree is:
15
13 20
4 7 17 18
2
36 18
a) 2 3 4 6 7 13 15 17 18 18 20 20
b) 20 18 18 17 15 13 7 6 4 3 2
c) 15 13 20 4 7 17 18 2 3 6 18
d) 2 4 3 13 7 6 15 17 20 18 18
Answer: (d)
Solution:
Given tree is binary tree
15
13
47 17 18
2 36 18
According in order traversal of tree: Left child; node; right child
Therefore, in order of given tree is 2, 4,3, 13, 7, 6, 15, 17, 20,
18, 18
3
5. The correct matching for the following pairs is
List – I
A. All pairs shortest paths
B. Quick Sort
C. Minimum weight spanning tree
D. Connected Components
List – II
1. Greedy
2. Depth-First search
3. D5mamic Programming
4. Divide and Conquer
Codes:
a) A – 2, B – 4, C – 1, D – 3
b) A – 3, B – 4, C – l, D – 2
c) A – 3, B – 4, C – 2, D – 1
d) A – 4, B – 1, C – 2, D – 3
Answer: (b)
6. Consider the graph given below:
The two distinct sets of vertices, which make the graph bipartite
are:
a) (v1, v4, v6); (v2, v3, v5, v7, v8)
4
b) (v1, v7, v8); (v2, v3, v5, v6)
c) (v1, v4, v6, v7); (v2, v3, v5, v8)
d) (v1, v4, v6, v7, v8); (v2, v3, v5)
Answer: (c)
Solution:
A biparthite graph is graph whose vertices can be divided into
two disjoint sets U and V such thet every edge connects a vertex
in U to one V. vertex inU to one in V. vertex sets U and V are
usually called the parts of the graph. Equavaleny, a bipartite
graph is a grph that does not contain any odd length cyles. It
iscycles. It is also 2-colabirate and the degree sum formula for a
bipartiiate graph states that
∑ ∈ deg( )=∑ ∈ deg( )=|E|
Given graph:
a. (3+3+3)≠ (3+3+3+2+2)
b. (3+2+2)≠(3+3+3+3+)
c. (3+3+3+2)=(3+3+3+21)=11=|E|
d. (3+3+3+2)≠(3+3+3)
5
7. Consider the Quick sort 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 z 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: (b)
Solution:
By applying divide and conquer concept one list would have
1/5 elements and the other would have 4/5 of the no. of
elements 'n' comparisons are required for fixing up the pivot.
8. Which one of the following algorithm design techniques is
used in finding all pairs of shortest distances in a graph?
a) Dynamic programming
b) Backtracking
c) Greedy
d) Divide and Conquer
Answer: (a)
6
9. Which of the following is a correct statement?
a) Composition is a strong type of association between two
classes with full ownership.
b) Composition is a strong type of association between two
classes with partial ownership.
c) Composition is a weak type of association between two
classes with partial ownership.
d) Composition is a weak type of association between two
classes with strong ownership
Answer: (a)
Solution:
Composition is a specialized form of aggregation in this
relationship child objects does not have their lifecycle without
parent object. If a parent object is deleted, all its child objects
will also be deleted. This represent ”death” relationship
10. Suppose there are log n sorted list of n log n elements each.
The time complexity of producing a sorted list of all these
elements is (use heap data structure)
a) O (n log log n)
b) Θ (n log n)
c) Ω (n log n)
d) Ω(n3/2)
Answer: (a)
Solution:
7
We can merge x arrays of each size Y in O(xy log y) using
min heap. Given, x=log n and y=n/log n
Therefore, we get O (n/log n*log n. log (logn)) which is O(n
log logn).
11. Let G be a weighted connected undirected graph with distinct
positive edge weights. If every edge weight is increased by the
same value, then which of the following statements is/are
TRUE?
P: Minimum spanning tree of G does not change.
Q: Shortest path between any pair of vertices does not change.
a) P only
b) Q only
c) Neither P nor Q
d) Both P and Q
Answer: (d)
Solution:
Let us consider following graph.
B3 C
2
5
A C
MST is
B3
2
A
8
Shortest path from A to C is A→B→C.
If we increase edge weight by the value 10
Then
B 13 C
12
15
A C
MST is
B 13
12
A
But shortest path from A to C changes as A→C.
12. Which of the following sorting algorithms has the minimum
running time complexity in the best and average case?
a) Insertion sort, Quick sort
b) Quick sort, Quick sort
c) Quick sort, Insertion sort
d) Insertion sort, Insertion sort
Answer: (a)
Solution:
In best case, complexity of intersection sort [O(n)] is lower
than complexity of insertion sort[On2)] is higher than
complexity of quicksort[O(n log n)].
9
13. What is the time required to insert an element in a stack with
linked implementation?
a) O (log2 n)
b) O (n)
c) O (n log2 n)
d) O (1)
Answer: (d)
Solution:
Insertion into stack with linked list implementation also at
first node and deletion also at first node.
So we need only arranging pointers in contact time(i.e.,
O(1)).
14. Match the following:
List-I List- II
1. Prims algorithm 1. O( 2E)
2. Bellman-Ford algorithm 2. O (VE lg V)
3. Floyd-War shall algorithm 3. O (V lg V)
4. Johnson's algorithm 4. O ( 3)
Where V is the set of nodes and E is the set of edges in the
graph.
Codes:
A B CD
a) 1 3 4 2
b) 1 3 2 4
c) 3 1 4 2
10
d) 3 1 2 4
Answer: (c)
Solution:
Prims algorithm to final minimum spanning tree in a
weighted graph has time complexity O(|E| log| V|).
Bellman ford algorithm to find single source shortest path
in a weighted graph has time complexity O(|V| |E|)=O(|V|3)
Flod-warshalls algorithm to find all pair shortest path in a
graph has time complexity O(|V|3).
Johnson’s algorithm to find all pair shortest path in a graph
has time complexity O(|V|2) log |V|+|V| |E|).
15. An example of an adaptive routing algorithm is:
a) distance vector routing
b) flooding
c) selective flooding
d) shortest path routing
Answer: (a)
Solution:
Adaptive routing is a routing algorithm that a router may
select a new route for each packet (even packets belonging to
the same transmission) in response to change in condition and
topology of the networks.
A distance vector routing is a protocol in which a router
informs its Neighbours of topology changes periodically.
11
16. Suppose we want to arrange the n numbers stored in any
array such that all negative values occur before all positive
ones. Minimum number of exchanges required in the worst
case is:
a) n-1
b) n
c) n+1
d) None of above
Answer: (a)
Solution:
Worst case input is when the negative number occur at the end
of positive No's minimum no. of comparisons in such a case is
(n – 1).
17. Assuming there are n keys and each key is in the range [0, m
- 1]. The run time of bucket sort is
a) O (n)
b) O (n lg n)
c) O (n lg m)
d) O (n+ m)
Answer: (d)
Solution:
Bucket sort is an algorithm that employs to sort n keys
assuming that each key is in the range [0(m-1)], then the run
time of bucket sort is O (n+ m).
12
18. The minimum number of comparisons required to sort 5
elements is:
a) Selection sort
b) Merge sort
c) Quick sort
d) Single linked list
Answer: (a)
Solution:
Minimum may be four using bubble sort (or) selection sort
(or) insertion sort
19. Match the following:
List-I
A. Automatic storage class
B. Register storage class
C. static storage class
D. External storage class
List-II
1. Scope of the variable is global.
2. Value of the variable persists between different functions
calls
3. Value stored in memory and local to the block in which the
variable is defined
4. Value stored in CPU registers
Codes:
ABCD
13
a) 3 4 1 2
b) 3 4 2 1
c) 4 3 2 1
d) 4 3 1 2
Answer: (b)
Solution:
Automatic variables are local variables whose lifetime ends
when execution leaves their scopes, and are recreated when the
scope is reentered.
Register variables value is stored in CPU registers.
Global variables are accessible at any point after their
declaration.
The extrema storage class is used to declare a global variable
that will be known to the function in a file and capable of
being known to all functions in a program
20. An array of n numbers is given, where n is an even number.
The maximum as well as the minimum of these n numbers
needs to be determined. Which of the following is TRUE
about the number of comparisons needed?
a) At least 2n - c comparisons, for some constant c, are
needed.
b) At most 1.5 - 2 comparisons are needed.
c) At least n log2 n comparisons are needed.
d) None of the above.
Answer: (b)
14
Solution:
Using Divide and Conquer method not more than (32 − 2)
comparisons are required I all cases of input.
21. Which of the following is not an inherent application of
stack?
a) implementation of recursion
b) Evaluation of a postfix expression
c) Job scheduling
d) Reverse a string
Answer: (b)
Solution:
Applications of stack(s) are:
Implementation of recursion
Evolution of a postfix expression.
Reverse a string.
Job scheduling is commonly done via queue data structure
22. consider the given graph
a)
15
b)
c)
d)
Answer: (b)
Solution:
Given weight graph
Using kruskal’s algorithm minimum cost of spanning tree
16
23. Let T be a depth first search tree in an undirected graph G.
Vertices u and v are leaves of this tree T. The degrees of both
u and v in G are at least 2. Which one of the following
statements is true?
a) There must exist a vertex w adjacent to both u and v in G
b) There must exist a vertex w whose removal disconnects u
and v in G
c) There must exist a cycle in G containing u and v
d) There must exist a cycle in G containing u and all its
Neighbours in G.
Answer: (d)
Solution:
Since the degree of u & v in ‘G' is at least 2, see the answer.
24. A binary search tree is a binary tree:
a) All items in the left subtree are less than root
b) All items in the right subtree are greater than or equal to
the root
c) Each subtree is itself a binary search tree
d) All of the above
Answer: (d)
Solution:
17
A binary search tree (BST) also known as an ordered binary
tree, where the left subtree of a node constitutes only node
with keys less than the nodes key and right subtree of a node
constraints only nodes with keys greater than or equal to the
nodes keys. The left and right subtree each must also be a
binary search tree.
25. Which algorithm has same average, worst case and bet case
time:
a) binary search
b) Maximum of n numbers
c) Quick sort
d) Fibonacci search
Answer: (b)
Solution:
If x is found at loc ‘1’
→1 composition
X is found at loc ‘2’
→2 comparision
X is found at loc ‘3’
→3 comparision
18
X is found at loc ‘n’
→3 comparision
‘n’ is found at loc =n(n+1)/2/n
26. If T1 = O(1), give the correct matching for the following
pairs:
List-I
m)Tn=Tn-1 +n
n) Tn=Tn/2 +n
o) Tn = Tn/2 +nlog n
p) Tn = Tn-1+log n
List-II
u) Tn=O(n)
v) Tn=O (n log n)
w)Tn= O(n2)
x) Tn =O (log2 n)
a) M-W, N-V, O-U, P -X
b) M-W, N-U, O-X, P-V
c) M-V, N-W, O-X, P-U
d) M-W, N-U, O-V, P-X
Answer: (d)
27. The solution of recurrence relation,
T(n) = 2T (floor ()) + logn is
a) O (n log log log n)
b) O (n log log n)
c) O (log log n)
19
d) O (logn log log n)
Answer: (d)
Solution:
Given recurrence relation is: T(n)-2T([√ )] +logn
Substituting
n=2m
⟹m=log n
T(2m)=2T(2m/2)+m
we can rename S(m)=T(2m) to produce the new reference
S(m)=2S(m/2)+m
a=2,b=2, f(m)=m
O(mlog2(2)=f(m)[case (2) master therom]
So, T(n)=Θ(m log2 m)
Replace m=log2(n), therefore,
T(n)=Θ(log n log log n)
28. A binary tree is said to have heap property if the elements
along any path:
a) from leaf to root are non-increasing
b) from leaf to root are non-increasing
c) from root to leaf are non-decreasing
d) from root to leaf are non-increasing
Answer: (d)
Solution:
20
A binary tree is said to have the heap property if the element
along any path from root of leaf are non-increasing A heap is
a complete binary tree that has the heap property.
29. The correction needed in the program to make it work
properly is:
a) Change line 6 to:
If (Y [k] < x) i = k + 1; else j = k – 1;
b) Change line 6 to:
If (Y [k] < x) i = k – 1; else j = k+ 1;
c) Change line 6 to:
If (Y [k] < = x) i = k; else j = k;
d) Change line 7 to:
While (Y [k] = = x) && (i < j));
Answer: (a)
Solution:
It will cause the loop to terminate wherein the condition i
Data Loading...