END TERM EXAMINATION

SECOND SEMESTER (BCA) MAY-JUNE 2014

Solve The Paper

• Q1. (a) What do you mean by data structure? Explain the difference between linear and non-linear data structures.
• (b) What is an AVL tree? Why is it useful in searching?
• (c) Explain the sparse matrix & its representation.
• (d) Prove that in a complete binary tree of height h, total no. of nodes are 2^h-1.
• (e) Explain binary search with suitable example. (5x5=25)

UNIT-I

• Q2. (a) Write a c program that takes an input expression in infix notation and convert it into postfix notation. (8)
• (b) Give an algorithm for insertion of an element in circular queue. (4.5)

OR

• Q3. (a) Write a c function that reverse a string and finds its length. (6)
• (b) Implement an stack using linked list. (6.5)

UNIT-II

• Q4. (a) Write a c function that takes a linear linked list as its input and display it in the reverse order. (6)
• (b) Write a c function that concatenates two linear linked list. (6.5)

OR

• Q5. Define binary search tree. Write algorithms for pre-order, post-order & in-order traversal of a binary tree. (12.5)

UNIT-III

• Q6. (a) Define the time complexity & ratio for left or right skew & binary search tree. Justify. (6)
• (b) Explain the insertion of a node in B-tree. (6.5)

OR

• Q7. What do you mean by a binary search tree based indexing? How is it different from multilevel indexing? (12.5)

UNIT-IV

• Q8. Explain selection sort and merge sort with suitable example. Show various stages. (12.5)

OR

• Q9. (a) How linear search is used to find an element? (6)
• (b) Explain the concept of collision in hashing and its remedies. (6.5)