B (28001 Pages:2

Reg. No. Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SECOND SEMESTER MCA DEGREE EXAMINATION, MAY 2017

Course Code: RLMCA 104
Course Name: DATA STRUCTURES
Max. Marks: 60 Duration: 3 Hours

PART A
Answer All Questions, Each Carries 3 Marks

1. Convert the given infix expression to prefix and postfix

(A-B)4C4D*E+F-G/H
2. How can you overcome the limitations of a linear queue when implemented as an
array?
How can you represent a sparse matrix using linked list?
Write an algorithm to delete an element from a doubly linked list in a given position.
Show that maximum no. of nodes possible in ೩ binary tree of height h is 2"-1.
Define a minimum spanning tree for a graph .Give an example.

What is the running time of insertion sort if all keys are equal?

9० > nn ടാ

Is Bubble Sort a stable sort algorithm? Justify your answer.

PART B
Answer Any One Question from Each Module, Each Carries 6 Marks
MODULE I
9. (i) Devise a formula to calculate memory location for each element in a three
dimensional array
1. Row major order 2. Column Major Order (2)

(ii) How can you find out the time complexity of an algorithm which checks
whether a

matrix is diagonal or not. (4)
OR
10. (i) Define Asymptotic Notations. (3)
(ii) How can asymptotic notations be used to represent time complexity?
(3)
MODULE II
11. Write an algorithm to check for balanced parentheses in C language using stack.

OR

Page 1 of 2