| |

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 |