DATA STRUCTURES, MCA Question Paper

punjabtechnicaluniversity.blogspot.in

Roll No. .......................

Total No. of Questions : 13]                                                                          [Total No. of Pages : 02

Paper ID [A0512]

(Please fill this Paper ID in OMR Sheet)

MCA (302) (Old/S05) (Sem. - 3rd)

B.Sc. IT 202 (Old)

DATA STRUCTURES

Time : 03 Hours                                                                                         Maximum Marks : 75

Instruction to Candidates:

1) Section-A is Compulsory.

2) Attempt any Nine questions from Section-B.

Section - A

Q1)                                                                                                    (15 × 2 = 30)

a) Define ADT? What are its advantages?

b) What is the difference between linklist and array?

c) What is the difference between graph and tree?

d) What is the complexity of an algorithm?

e) What is deque? List its different types?

f) What are the applications of stack?

g) Define: (i) almost complete binary tree (ii) strictly binary tree?

h) A complete binary tree contains 15 nodes. Calculate the depth of the tree?

i) What are AVL trees? What are its advantages?

j) Write the complexities of (i) Heap sort (ii) Quick sort (iii) Merge sort

k) Differentiate between depth first search and breadth first search?

l) Define: (i) Minimum spanning tree (ii) Forest

m) What is Bubble sort technique?

n) What are the applications of graph?

o) What are the limitations of binary tree?

Section – B

 (9 × 5 = 45)

Q2) Write an algorithm to insert an element at the end in a circular link list?

Q3) Write the procedure to insert an element in the middle of an array?

Q4) How would you implement a queue of stacks, a stack of queues, a queue of queues? Write routines to implement the appropriate operations for each of these data structures.

Q5) Write a procedure to convert infix expression to postfix expression? Apply the procedure on the following data

Q: ((A+B)*D)↑(E–F)

Q6) Write heap sort algorithm? Discuss its complexity?

Q7) Discuss the different tree representation methods?

Q8) Let E denote the following algebric expression: [a+(b-c)]*[(d-e)/(f+g-h)]

(a) Draw the corresponding binary tree.

(b) Apply the preorder traversal.

(c) Apply the postorder traversal.

Q9) Write an algorithm to insert an element in a binary search tree?

Q10) Explain the various graph representation methods. List merits and demerits

of each?

Q11) Explain Dijkastra’s algorithm?

Q12) Write a short note on Redix sort?

Q13) Write an algorithm for selection sort?