IGNOU MCS-21 - Data and File Structures

Q1: Elaborate various asymptotic notations used 10 to evaluate the efficiency of the algorithm. Q2: Write a program that accepts two polynomials as input and displays the resultant polynomial after multiplication of input polynomials. Q3: Write a C programme to implement a doubly linked list. Also write functions to perform insertion and deletion operations in it. Q4: What is a Circular Queue? Write an algorithm to perform insertion and deletion operation in a Circular Queue Q5: Write a program in C for insertion sort. Write the step-by-step working of the insertion sort for the following set of data: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4. Also count the number of swaps and comparison operations performed for it. Q6: Write a detailed note on file organization techniques. Q7: Create the binary tree for which the in-order and post order traversal are given as below: In-order: QUVTMPSYZXR Post-order: VUTQZYXSRPM Q8: Create a B tree of order-5 for the following keys, inserted in the sequence. 25, 5, 10, 2, 3 35, 45, 30, 50, 55, 60, 12, 18, 20, 1 Further, delete the keys 1, 2, 10, and 12. Show all the intermediate steps. Q9: Create AVL tree for the following keys inserted in the order: 5, 15, 3, 25, 10, 2, 35, 7, 45, 30, 12, 20, 14 Further, delete the keys 2, 5, 7, and 8. Show all the intermediate steps. Q10: Solve the following instance of single source shortest paths problem with vertex 'a' as the source using suitable method.

Q1. Write an algorithm that converts a Tree into a Binary Tree. Q2. Is it possible to implement multiple stacks in a Queue. Justify your answer. Q3. List the names of all SEARCH Algorithms along with their Complexities (Best case, Average case and Worst case). List as many names as possible along with their year of Invention and Inventor. Make necessary assumptions. Q4. Write an algorithm for creation of an AVL tree.