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 2023-24
DATA STRUCTURES & ANALYSIS OF ALGORITHMS
TIME: 3 HRS M.MARKS: 100

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A
1. Attempt all questions in brief. 2 x 10 = 20
Q no. Question Marks CO
a. Define algorithm. Give its characteristics. 02 1
b. What is header linked list? 02 1
c. Define recursion. 02 2
d. What is priority queue? 02 2
e. Traverse a given tree in Pre-order traversal. 02 3

0
13
11

7.
_3

.6
P2

45
f. Define Threaded binary tree. 02 3
4E

g. Define fully connected graph. 02 4

.2
h. What is weighted graph?
15 02 4
P2

i. Apply Quick sort algorithm on the string : D, E, L, H, I 02 5

|1
Q

j. What is minimum spanning tree (MST)? 02 5

AM

SECTION B
2. Attempt any three of the following: 3 x 10 = 30
54

Q no. Question Marks CO

:
02

a. How polynomials can be represented using linked list? Write a 10 1

function/algorithm to add two polynomials.
9:

b. What is hashing? How can we define hash function? 10 2

24

c. Define binary search tree. Create a binary search tree by inserting 10 3

20

following keys: 9, 2, 3, 4, 5, 6, 8, 1, 7, 0
d. What is the divide and conquer problem solving strategy? How binary 10 4
g-

search algorithm follows this approach?

Au

e. Given two strings, find the Longest Common Subsequence (LCS), 10 5

9-

present in both of the strings.

String-1=ASDFGHJK
|0

String-2=SHJLU

SECTION C
3. Attempt any one part of the following: 1 x 10 = 10
Q no. Question Marks CO
a. Define linked list. Write a function in C to create a singly linked list. 10 1
b. What is sparse matrix? How it can be represented using header linked 10 1
list.

QP24EP2_311 | 09-Aug-2024 9:02:54 AM | 115.245.67.130

 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 2023-24
DATA STRUCTURES & ANALYSIS OF ALGORITHMS
TIME: 3 HRS M.MARKS: 100

4. Attempt any one part of the following: 1 x 10 = 10

Q no. Question Marks CO
a. Give applications of stack. Write an algorithm to evaluate postfix 10 2
expression.
b. Define linear queue. Write a program or algorithm to implement linear 10 2
queue.

5. Attempt any one part of the following: 1 x 10 = 10

Q no. Question Marks CO
a. Define AVL tree. Demonstrate LL, RR, LR, RL rotations of AVL tree 10 3
with suitable examples.
b. Write the properties of B-Tree. Insert the following keys in a B-Tree of 10 3
order 3: 98, 76, 54, 32, 12, 34, 56, 78, 95, 48

6. Attempt any one part of the following: 1 x 10 = 10

0
Q no. Question Marks CO

13
11
a. What is breadth first search (BFS) algorithm for traversing a graph? 10 4

7.
_3

Apply BFS in the given graph, assuming vertex A as starting vertex.

.6
P2

45
4E

.2
15
P2

|1
b. Differentiate between Graph and Tree. Give adjacency matrix 10 4
Q

representation of the following graph.

AM
54
:
02
9:

7. Attempt any one part of the following: 1 x 10 = 10

24

Q no. Question Marks CO

20

a. Write a program in C to implement merge sort. Give its time and space 10 5
complexity.
g-

b. Find the shortest paths from the source to all the other vertices in the 10 5
Au

given graph using Dijkstra’s algorithm. Assume source vertex as S.

9-
|0

QP24EP2_311 | 09-Aug-2024 9:02:54 AM | 115.245.67.130