Printed Page: 1 of 2
Subject Code: KCA205
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0
MCA
(SEM II) THEORY EXAMINATION 2021-22
DATA STRUCTURES & ANALYSIS OF ALGORITHMS
Time: 3 Hours Total Marks: 100
Note: Attempt all Sections. If you require any missing data, then choose suitably.
SECTION A
1. Attempt all questions in brief. 2*10 = 20
Qno Questions CO
(a) Discuss the limitation of arrays. 1
(b) Give applications of linked list. 1
(c) Convert following infix expression into postfix expression: 2
A + (B*C + D)/E.
(d) What are the 3 different ways in which priority queue can be 2
implemented?
(e) Can we apply binary search on unsorted array? 3
(f) Give an example to demonstrate insertion sort. 3
(g) Draw the expression tree/2-Tree of following arithmetic expression: 4
(2 * (4 + (5 + 3))).
90
2
(h) What are threaded binary tree? 4
13
_2
(i) How the graph can be traversed using Breadth First Search (BFS)? 5
2.
P2
(j) Discuss Strassen’s algorithm for matrix multiplication. 5
24
2E
5.
SECTION B
.5
P2
17
2. Attempt any three of the following: 10*3 = 30
Q
|1
Qno Questions CO
(a) What is doubly linked list? Write a function to traverse a doubly linked 1
5 3
list in reverse order.
9:
(b) Write a function or algorithm to implement enqueue and deque 2
:0
operations on circular queue.
09
(c) Use heap sort algorithm to sort the following sequence: {8, 5, 45, 24, 3
36, 11, 43, 21}. What is the time complexity of the algorithm?
2
(d) Draw B-Tree of order 3 by inserting following keys in empty tree: 4
02
{78, 52, 81, 40, 33, 90, 85, 20, 38}.
-2
(e) Discuss Longest Common Subsequence (LCS) problem solution by 5
08
using dynamic programming. Give example.
6-
|0
SECTION C
3. Attempt any one part of the following: 10*1 = 10
Qno Questions CO
(a) Write a function or algorithm to add two Polynomials using linked list. 1
(b) Define header linked list. Write a function to perform insertion at end 1
in a singly linked list.
QP22EP2_290 | 06-08-2022 09:09:53 | 117.55.242.132
Printed Page: 2 of 2
Subject Code: KCA205
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0
MCA
(SEM II) THEORY EXAMINATION 2021-22
DATA STRUCTURES & ANALYSIS OF ALGORITHMS
4. Attempt any one part of the following: 10 *1 = 10
Qno Questions CO
(a) What is Tower of Hanoi problem? Explain the solutions of Tower of 2
Hanoi problem using recursion where number of disks n= 3 and
towers are A, B and C.
(b) What do you understand by hashing? Consider Inserting the keys 2
{76, 26, 37, 59, 21, 65, 88} into a Hash table of size m =11. Using
linear Probing, consider the primary hash function is h’(k) = k mod m.
5. Attempt any one part of the following: 10*1 = 10
Qno Questions CO
(a) Perform Quick sort on the following data items stored in single 3
dimensional array: {6, 9, 5, 8, 7, 4,3, 1, 2, 0}. Also discuss its time
complexity.
(b) Discuss the function to implement merge sort. What is the time and 3
space complexity of the algorithm?
90
2
13
_2
6. Attempt any one part of the following: 10*1 = 10
2.
P2
Qno Questions CO
24
(a) How BST is different from sorted array? Discuss the process to find an 4
2E
5.
element in BST?
.5
P2
(b) Insert the following element in empty AVL tree: 4
17
{45, 55, 65, 75, 80, 90, 100, 110, 120, 130, 40, 35, 25, 20, 15, 10, 5}.
Q
|1
7. Attempt any one part of the following: 10*1 = 10
5 3
Qno Questions CO
9:
(a) What is minimum spanning tree (MST)? Draw MST of the following 5
:0
graph by applying Kruskal’s algorithm.
09
2
02
-2
08
6-
(b) For the given graph (weighted, directed) apply Floyd-Warshall 5
|0
algorithm for constructing shortest path.
QP22EP2_290 | 06-08-2022 09:09:53 | 117.55.242.132
