Solve any one question from Q1 and Q2

1 (a)
Write the frequency count of the following code and derive the time complexity.

For (i=n-1; i>0; i--)

For (j=0; j<1; j++)

If (a[i] {

Temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

}

For (i=n-1; i>0; i--)

For (j=0; j<1; j++)

If (a[i] {

Temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

}

4 M

1 (b)
Prove the following:

i) If f(n)=2n

ii) if f(n)=5n

i) If f(n)=2n

^{2}+2 then f(n)ϵ O(n^{2})ii) if f(n)=5n

^{3}+2n^{2}+3 then f(n) ϵ O(n^{3}).
4 M

1 (c)
Prove that if height of a full or couple binary tree is 'h' then number of nodes in the tree equal to 2

^{h+1}-1.
4 M

2 (a)
Prove that a full binary tree having n nodes, the height is O(log

_{2}n).
3 M

2 (b)
Evaluate the following postfix expression using stack. Show all steps.

3,2,4,*,+,5,9,3,/,+,*.

3,2,4,*,+,5,9,3,/,+,*.

3 M

2 (c)
Define Big O, Ω and θ.

3 M

2 (d)
Show analysis of quick sort in worst and best case.

3 M

Solve any one question from Q3 and Q4

3 (a)
Find the minimum spanning tree for the following graph using Kruskal's Algorithms.

4 M

3 (b)
Find the topological ordering of the following graph:

4 M

3 (c)
Construct the AVL tree for the following data:

5, 4, 7, 1, 3, 2, 15, 20, 10, 12.

5, 4, 7, 1, 3, 2, 15, 20, 10, 12.

4 M

4 (a)
Insert the following data in the has table of size 10, using linear probing with chaining with replacement.

Here h(x)=x%10

21, 35, 31, 37, 32, 33, 48.

Here h(x)=x%10

21, 35, 31, 37, 32, 33, 48.

4 M

4 (b)
Write 'C' code for the following functions w.r.t. AVL Tree:

i) LR Rotation

ii) RL Rotation.

i) LR Rotation

ii) RL Rotation.

4 M

4 (c)
Find the minimum spanning tree for the following graph using Prim's Algorithms.

4 M

Solve any one question from Q5 and Q6

5 (a)
Construct B tree of order 5 for the following data:

4, 8, 10, 5, 3, 9, 2, 15, 20, 80.

4, 8, 10, 5, 3, 9, 2, 15, 20, 80.

5 M

5 (b)
Sort the following data in ascending order using heap sort:

10, 5, 3, 8, 9, 4, 2.

10, 5, 3, 8, 9, 4, 2.

4 M

5 (c)
Explain various operations on sequential files.

4 M

6 (a)
Construct B

5, 4, 6, 2, 1, 7, 1, 8, 9, 3, 10.

^{+}Tree of the order 5 for the following data:5, 4, 6, 2, 1, 7, 1, 8, 9, 3, 10.

5 M

6 (b)
Explain with example different methods of heap creation, also explain which method is better and why?

4 M

6 (c)
Write short notes on:

i) Sequential files

ii) Random access files.

i) Sequential files

ii) Random access files.

4 M

Solve any one question from Q7 and Q8

7 (a)
Computer the prefix sum for the following list using list ranking:

5, 3, -2, 7, 6.

5, 3, -2, 7, 6.

4 M

7 (b)
Explain pointer jumping techniques.

3 M

7 (c)
Write a note on odd even merge sort.

3 M

7 (d)
Find the largest number in the following list using parallel algorithmic technique:

5, 3, 7, 8, 2.

5, 3, 7, 8, 2.

3 M

8 (a)
Explain different parallel algorithmic techniques with examples.

6 M

8 (b)
Explain list ranking problem using pointer jumping techniques. Compute prefix sum of (8, 2, -1, 5) using binary tree techniques.

4 M

8 (c)
Compute the sum of the following numbers using complete binary tree technique:

5, 4, 3, 2.

5, 4, 3, 2.

3 M

More question papers from Data Structures Algorithm