** B.C.A. (Third Semester) 2019**

**Time: **Three Hours** Maximum Marks: **75

**Note**: Attempt any five questions. All question carry equal marks**. **The answer to short questions should not exceed 200 words and the answer to long answer type questions should not exceed 500 words.

**1.(A) **What is data structure? Explain various types of data structure in detail.

**(B) **Differentiate between row major and column major array index notation. How is index calculated in both.

**2.(A) **What is sparse matrix? Write a C program to add two sparse matrices and explain the assumed data structure.

**(B) **Convert the following infix expression to postfix using stack (A+B*C)/(D-E)+F

**3.(A) **What is meant by circular queue and priority queue. write a function to insert and delete an element from a circular queue.

**(B) **What do you mean by linked list? Write a function to insert and delete a node in linked list.

**4.(A) **Write a C/C++ program to reverse a linked list by traversing it only once.

**(B) **What is binary tree? Explain the representation of binary tree? Explain the different operation an a binary tree.

**5.(A) **List the types of binary search trees. Explain insertion and deletion operation on a binary search tree.

**(B) **Show the result of inserting 3,1,4,6,9,2,5,7 into an initially empty binary search tree. Also show three result of deleting the root.

**6.(A) **What is B-Tree? Generatea B-Tree of order 5 with the alphabets arrive in the sequence as follows :

a g b k d h m j e s I r x c l n t u p.

**(B) **Differentiate between B and – Tree

**7.(A) **Explain the concept of hashing division method of hashing. Store the following values in a hash table of size 11,25,45,96,101,102,162,197,201.

**(B) **Write C/C++ program for selection sort.

**8.(A) **Explain the working of merge sort on the following data:

10,15,0,17,20,25,30,16,70,6.

**(B) **What is the difference between a heap and a binary tree? Obtain heap and binary search tree for following data set.

45,56,78,23,11,54,88,43,55,21,67,55.

** B.C.A. (Third Semester) 2018**

**Time: **Three Hours** Maximum Marks: **75

**Note**: Attempt any five questions. All question carry equal marks**. **The answer to short questions should not exceed 200 words and the answer to long answer type questions should not exceed 500 words.

**(A)**What do you mean by complexity of an algorithm? Explain the meaning of worst case analysis and best case analysis with an example.

**(B) ** Why do we use a sympatotic notation in the study of algorithm? Describe commonly used asymptotic notation and give their significance.

**2. (A) ** Define list .what are the type of linked list. What are the advantages and disadvantages of linked list and application of linked list.

**(B) **Write a complete program in C to create a singly linked llist.

Write function to do the following operations.

- Insert a new node at the end
- Delete the first node.

**3.(A**) Given the following inorder and preorder traversal reconstruct a binary tree

** Inorder – D,G,B,E,A,F,I,C**

** Preorder – A,B,D,E,H,C,F,I**

** (B) **What is a binary tree? What is the maximum numbers of nodes possible in a binary tree of depth. Explain the following term with respect to binary trees

** (i) Strictly Binary tree**

** (ii)Complete binary tree**

**Almost complete binary tree**

** 4.(A) **Sort the following list using heap sort.

66,33,40,20,50,88,60,11,77,30,45,65

**(B) **Describe insertion sort with a proper algorithm. What is the complexity of insertion sort in the worst case?

**5.(A) **Define Hashing. How do collision happen during hashing? Explain the different techniques resolving of collision.

**(B) ** The following values are to be stored in a hash table:

25,,42,96,101,102,162,197

Describe how the values are hashed by using division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

**6.(A) **What is post fix notation? Explain with examples.

**(B) **Write the algorithm for converting from infix to post fix.

**7.(A) ** how do you push and pop elements in a stack. Explain the application of stack?

**(B) ** What are queues? Write down algorithm for inserting and deleting elements from a queue implemented using arrays.

**8.(A) **Distinguish between stack and queue.

**(B) **State the difference between array and linked list.

**(C) **Explain the application of a stack for implementing function call and return mechanism.

**9. **Explain short notes on :

(a) Sparse arrays

(b) Tridiagonal matrix

(c) B-Tree

**9.(A) **Write a C/C++ program for binary search.

**(B) **Explain the various collision resolving technique used in hashing functions.

** B.C.A. (Third Semester)** 2017

**Time: **Three Hours** Maximum Marks: **75

**Note**: Attempt any five questions. All question carry equal marks**. **The answer to short questions should not exceed 200 words and the answer to long answer type questions should not exceed 500 words.

- Write a program in C to obtain the sum of two upper triangular matrices of order 3×3.
**(A)**Explain the procedure of converting from infix to postfix with the help of an expression tree.

**(B) **What is priority queue? What are its application.

**3.(A) **Write a C program to count the number of nodes (elements) in a singly linked list.

**(B) **Write a program in C to insert an elements (new node) in a singly linked list at the third position from the start node.

**4. (A) ** What is Binary search tree? Write the application areas that use a binary search tree.

**(B) **What do you understand by the spanning tree(T) of a given graph G? What is the difference between a tree and a graph?

**5. (A) **Explain : B – Tree, B – Tree Creation.

**(B) **Explain the application of B =Trees in databag environment

** (C) **How can binary searches trees be used for the creation of index sequential Files.

**6. (A) **Write a C program for the selection sort of a list of N numbers.

**(B) **What is Insertion sort? Explain its technique with an example.

**7.(A) **Write the algorithm for binary search and explain it.

**(B) ** Write a C Program for quick sort on a list of N integers.

**8.** Explain the technique of ‘Hashing’ as an effective searching technique. What are ‘Collisions’? How can they be handled ?

**9. **Write short notes on :

**(a) **Tridiagonal Matrices

** (b) **Application of stacks

** (c) ** Recursion.