END TERM EXAMINATION (DS) | |
| Second Semester[BCA] | June 2024 |
| Paper Code: BCA-104 | Subject : Data Structure and Algorithm Using C |
| Time:3 Hour | Maximum Marks:60 |
| Note: Attempt all questions as directed. Internal Choice is indicated. | |
| Q1 Answer the following (Attempt any four): (4*5=20) | |
| (a) Give properties of good Algorithms. Explain how the performance analysis of an algorithm can be measured. | |
| (b) Explain all Dynamic Memory allocation function with example. | |
| (c) An array X[-15……10, 15……..40] require 4 bytes of storage. If beginning location is 1300 determine the location of X[5][25] by using row major order and column major order. | |
| (d) Explain Adjacency Matrix and Adjacency List by taking a suitable example. | |
| (e) Difference Linear and Non-Linear data structure . Give four applications of Data Structure. | |
| (f) Explain Binary Search Tree and construct a Binary Search Tree from the following set of letters : J, R, D, G, T, E, M, H, P, A, F, Q. | |
| (g) Explain the advantages and disadvantages of different types of Queues. | |
| (h) Define hashing and explain at least four techniques to perform hashing and also give two methods of collision resolutions. | |
| UNIT I | |
| Q2 (a) Consider the list of numbers in sorted order: 10, 20, 30, 40, 50, 60, 70, 80, 90. Write a program to search an element 80 in the given list using binary search. Show all the steps. (5) | |
| b) Write a program to perform the selection sort on the following list. Show all the pass : 45, 67, 23, 30, , 42, 15, 78, 39, 48 (5) | |
| Or | |
| Q3 Explain sparse matrix and its various types with examples. Give a function to convert it into its 3-tuple memory representations. (10) | |
| UNIT-II | |
| Q4 Write a program in C to implement the following functions on Doubly linked list. (10) a) Insert a node at end. b) Delete a node from the beginning. c) Insert a node based on information. | |
| Or | |
| Q5 Write a program to do following operations on single linked list. (2*5=10) a) Reversal of linked list. b) Linear search on linked list. | |
| UNIT-III | |
| Q6 (a) Write an algorithm to convert infix expression to postfix expression. Convert the following infix expression into postfix expression using stack: A+(B*C-(D/E^F)*G)*H (6) | |
| (b) Evaluate the following postfix expression : ABC+DE*/- for A=2, B=5, C=3, D=2, E=4. Show stack at each step. (4) | |
| or | |
| Q7 (a) What is circular queue and state the advantage of Circular Queue over linear queue? Illustrate with any example. (5) | |
| (b) Write a program to implement insertion operation in a Circular Queue using array. (5) | |
| UNIT IV | |
| Q8. a) Draw a Tree T with the following traversals : (5) Inorder: 10,25,35,40,45,61,,68,71 PreOrder: 45,25,10,35,40,61,71,68 | |
| b) Draw an AVL tree with the following sequence: (5) Insert : 20, 15, 25, 30, 16, 18, 19 Delete 30 | |
| or | |
| Q9. Create a B-Tree of order 5 for the following sequences of keys C S D T A M P I B W N G R K E H O L J Y Q Z F X V U | |
