Categories

Algorithms

CSE - Algorithms - Questions and solutions
Question:-
Option (A)

ohm (n2)

Option (B)

ohm (n log n) and O(n2)

Option (C)

q(n)

Option (D)

o(n)

Correct Option:
C
Question Solution:

The given code is
1. Counter = 0;
2. for (i=1; i<= n; i++)
3. { if (A[i] == 1) Counter++;
4. else { f(counter); counter = 0;}
5. }
The time complexity of the program fragment depends on the frequency (Number of steps) of line 3 and 4. In line 4 the frequency depends on the variable which is initialize to 0, so f(0) then counter = 0 it means there is no cell in an array which having a bit 0, so all cells in the array contains 1. Consider the line 3 if (A[i] ==1) counter +=; the value of I will be increases upto n so the value of counter will be n. since n is the frequency of the line 3 and the frequency of line 4 is 0. So the time complexity of 4. So the time complexity of the program fragment is maximum of line 3 and 4 which is O(n) on average

Question:-
Option (A)
3
Option (B)
4
Option (C)
5
Option (D)
6
Correct Option:
C
Question Solution:
I[n-1] + 1 = L
n = {(L-1) /I} + 1
Total No. of nodes = L + T + 1
nn = 41 + 10 = 51 + 1
n = 5
Question:-
Option (A)
10, 8, 7, 5, 3, 2, 1
Option (B)
10, 8, 7, 2, 3, 1, 5
Option (C)
10, 8, 7, 1, 2, 3, 5
Option (D)
10, 8, 7, 3, 2, 1, 5
Correct Option:
D
Question Solution:
Initially the sequence of max Hoop is

So, the sequence of level order traversal is
10 , 8, 7, 3, 2, 15
Question:-
Option (A)
Θ(n)
Option (B)
O( n log n)
Option (C)
O(n)2
Option (D)
O(2n)
Correct Option:
A
Question Solution:
g(x) is min {number of leaf nodes in subtree of x, number of leaf nodes in right subtree of x} If balanced binary search tree is used and contains n node then in worst case time complexity of g(x) is O(n).
Question:-
Option (A)
log2 n
Option (B)
n
Option (C)
2n + 1
Option (D)
2n
Correct Option:
B
Question Solution:
The root of the tree is stored at X[1]
Left X[i] stored at X[2i]
Right X[i] stored at [2i +1]
If tree is complete Binary tree minimum it require n consecutive memory location of x,x[1] .... x[n-1]x[n].
Question:-
Option (A)
(X È Y)
Option (B)
(X Ç Y)
Option (C)
(X – Y)Ç(Y – X)
Option (D)
(X – Y)È(Y – X)
Correct Option:
D
Question Solution:
In given algorithm the loop contains a logical expression z[i] = (x[i] Ù ~ y[i]) v (~x[i] Ù y[i])
The equivalent set representation of given logical expression if we assume z[i] = z, x[i] = x and y[i] = y then
z = (x Ç y’) È (x’ – y)
z = (x – y) È (y – x) [A Ç B’ = A – B]