Data Structure previous year paper

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.

1. (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.

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

1. Write a program in C to obtain the sum of two upper triangular matrices of order 3×3.
2. (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.