END TERM EXAMINATION

SECOND SEMESTER (BCA) MAY-JUNE 2017

Paper Code: BCA-108

Subject: Data Structure using C

Time: 3 Hours

Maximum Marks: 75

Note: Attempt any five questions including Q no.1 which is compulsory.Select one question from each unit.

Q1. (a) Add and subtract the following two sparse matrices. (5)
(b) Perform insertion sort on the following values. (5)
6, 55, 11, 10, 18
(c) Convert the following infix expression into postfix expression. (5)
(A+B-C*D)/H
(d) Write the preorder traversal of the following tree. (5)
(e) Write a Recursive function to count number of nodes in Tree. (5)

UNIT-I

Q2. (a) Classify primitive and non-primitive data structures. Discuss the operations performed on data structures. (6)
(b) Evaluate the following postfix expression using stacks
320, 10,*, 10, 60,100, *, / (6.5)

Q3. (a) Explain why circular queue is better than linear queue? (6)
(b) Discuss D-queues and priority queues. What are the applications of stacks and queues? (6.5)

UNIT-II

Q4. (a) Write a function to insert a node at the end of single linked list. (6)
(b) Write a function to delete a node from beginning of double linked list. (6.5)

Q5. (a) A binary tree T has 9 nodes. The inorder and preorder traversals of T yield the following sequences of nodes.
Inorder: D G B A H E I C F
Preorder: A B D G C E H I F
Draw the tree T (6)
(b) Consider the following binary tree T with N=10 nodes. What is the inorder traversal of the tree? (6.5)

UNIT-III

Q6. (a) Construct B-tree of order 3 by inserting the following keys in the order shown:
18, 19, 6, 10, 40 (6.5)
(b) Construct Binary Search Tree of the following keys in the order shown
1, 2, 3, 1, 2, 3, 15, 8, 25, 7, 9, 10, 13 (6)

Q7. (a) Construct an AVL search tree of the following values
1, 2, 11, 20, 23, 5, 3 (6)
(b) Insert the following values in the order of their occurrence 30, 31 in the given B tree of order 5. (6.5)

UNIT-IV

Q8. (a) Define hashing. Why do we use hashing? Discuss any two hashing methods with example. (6.5)
(b) Which searching technique is best and under what conditions? Justify your answer with the help of an example. (6)

Q9. (a) Compare Selection sort and Merge sort. (6)
(b) Which sorting technique is better and why? Explain with an example. (6.5)