B C2B001 Pages:2
Page 1 of 2
Reg.
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SECOND SEMESTER MCA DEGREE EXAMINATION, MAY 2017
Course Code: RLMCA104
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

2. How can you overcome the limitations of a linear queue when implemented as an
array?
3. How can you represent a sparse matrix using linked list?
4. Write an algorithm to delete an element from a doubly linked list in a given position.
5. Show that maximum no. of nodes possible in a binary tree of height h is 2h-1.
6. Define a minimum spanning tree for a graph .Give an example.
7. What is the running time of insertion sort if all keys are equal?
8. 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. Devise a formula to calculate memory location for each element in a three
dimensional array
1. Row major order 2. Column Major Order
How can you find out the time complexity of an algorithm which checks whether a
matrix is diagonal or not.
OR
10. Define Asymptotic Notations.
How can asymptotic notations be used to represent time complexity?
MODULE II
11. Write an algorithm to check for balanced parentheses in C language using stack.
OR
B C2B001 Pages:2
Page 2 of 2
12. Write a recursive algorithm using stack to list out all prime factors of a given number
in ascending order.
MODULE III
13. Write an algorithm to delete an element from a linked queue.
Write any two representations of a priority queue.
OR
14. Write an algorithm that reverses all the elements in a queue using stack.
MODULE IV
15. Write an algorithm to add two polynomials using linked list. What is the time
complexity of the algorithm if the polynomials have M and N terms respectively?
OR
16. Given two sorted lists L1 and L2. Write an algorithm to compute L1 L2 using only
the basic list operations.
MODULE V
17. Define a Binary Search Tree.
Show the result of inserting 10, 8 into an initial empty binary search
tree.
Show the result of deleting the root.
OR
18. Write an algorithm to solve the single source shortest path problem with an example.
MODULE VI
19. Show how heapsort processes the input 14,54,12,6,45,88,57,43,11
(ii)What is the running time of heapsort algorithm for
Sorted input in ascending order sorted input in descending order
OR
20. Write a recursive algorithm for merge sorting .What is the worst case complexity of that
algorithm?