# IPU BCA Semester 2 - Data Structure using C (End Term Paper 2015)

END TERM EXAMINATION

SECOND SEMESTER [BCA] MAY- JUNE 2015

Paper Code: BCA-108

## Subject: Data Structure using C

(Batch- 2011 onwards)**Time**: 3 Hours

**Maximum Marks**: 75

**Note**: Attempt any five questions including Q.No 1 which is compulsory.

**Question 1**: 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.

**Question 2**:

(a) What do you mean by a sparse matrix? Write a procedure for addition of two sparse matrices. (6)

(b) Explain the stack data structure. Also write a C function to evaluate a postﬁx expression. (6.5)

**Question 3**:

(a) Write C function that finds the total number of nodes in a linked list.(6)

(b) Write a C function to concatenate two input strings. (6.5)

**Question 4**:

(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)

**Question 5**:

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

**Question 6**:

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

**Question 7**:

(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)

**Question 8**:

(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)