END TERM EXAMINATION

SECOND SEMESTER (BCA) MAY-JUNE 2015

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.

Q1. Answer the following questions:- (5x5=25)
(a) Explain the working of insertion sort with suitable example.
(b) What do you mean by binary search tree? How is it different from conventional binary tree?
(c) What is circular queue and how is it different from linear queue?
(d) Explain the differences between linear and non linear data structures.
(e) Write a C function for addition of an element in 1 D array.

Q2. (a) What do you mean by a sparse matrix? write a procedure to add two sparse matrices. (6)
(b) Explain the stack data structure. Also write a C function to evaluate a postfix expression. (6.5)

Q3. (a) Write a C function to find the total number of nodes in a linked list. (6)
(b) Write a C function that concatenates two input strings. (6.5)

Q4. (a) Define a binary tree. Compute total number of nodes in a binary tree of height h. (6)
(b) Explain with suitable example the insertion and deletion operations in a binary search tree. (6.5)

Q5. Explain the preorder, inorder and post order traversals of a binary tree with a suitable example. What are left and right skewed binary search trees? (12.5)

Q6. What is AVL tree? Explain various possible nodes types in this tree. Also explain various rotations to balance an AVL tree. (12.5)

Q7. (a) Describe B-tree indexing with suitable example. (6)
(b) Explain different types of searching techniques. Give a suitable example to illustrate binary search. (6.5)

Q8. (a) Discuss the role of 'Hashing' in data searching. How is it different from other searching techniques? (6)
(b) Write an algorithm for merge sort. (6.5)