IGNOU MCS-21 - Data and File Structures

Q1. Write a program in C to accepts two polynomials as input and prints the resultant polynomial due to the multiplication of input polynomials. Q2. Write a program in ‘C’ to create a single linked list and perform the following operations on it: (i) Insert a new node at the beginning, in the middle or at the end of the linked list. (ii) Delete a node from the linked list (iii) Display the linked list in reverse order (iv) Sort and display data of the linked list in ascending order. (v) Count the number of items stored in a single linked list Q3. Write a program in ‘C’ to create a doubly linked list to store integer values and perform the following operations on it: (i) Insert a new node at the beginning, in the middle or at the end of the linked list. (ii) Delete a node from the linked list (iii) Sort and display data of the doubly linked list in ascending order. (iv) Count the number of items stored in a single linked list (v) Calculate the sum of all even integer numbers, stored in the doubly linked list. Q4. What is a Dequeue? Write algorithm to perform insert and delete operations in a Dequeue. Q5. Draw the binary tree for which the traversal sequences are given as follows: (i) Pre order: A B D E F C G H I J K In order: B E D F A C I H K J G (ii) Post order: I J H D K E C L M G F B A In order: I H J D C K E A F L G M B Q6. Write a program in ‘C’ to implement a binary search tree (BST). Traverse and display the binary search tree in the Inorder, Preorder and Post order form. Q7. Define AVL tree. Create an AVL tree for the following list of data if the data are inserted in the order in an empty AVL tree. 12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4 Further delete 2, 4, 5 and 12 from the above AVL tree. Q8. Define a B-tree and its properties. Create a B-tree of order-5, if the data items are inserted into an empty B-tree in the following sequence: 12, 5, 15, 20, 60, 45, 35, 40, 25, 8, 7, 55, 50, 66, 65, 80 Further, delete the items 5, 12, 8, and 20 from the B-tree. Q9. Apply Dijkstra’s algorithm to find the shortest path from the vertex ‘S’ to all other vertices for the following graph: Q10. Apply Prim’s Algorithm to find the minimum spanning tree for the following graph. Q11. Apply Insertion and Selection sorting algorithms to sort the following list of items. So, all the intermediate steps. Also, analyze their best, worst and average case time complexity. 12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7 Q12. What is a heap tree? Create a max heap tree for the following list of items inserted in the order. Also, explain the heap sort with the help of thus created heap tree. 10, 20, 5, 25, 30, 18, 3, 70, 55, 45, 12, 24 Q13. Write a program in ‘C’ language for 2-way merge sort. Q14. What is Splay tree? Explain the Zig zag and Zag zig rotations in Splay tree with the help of a suitable example. Q15. What is Red-Black tree? Explain insertion and deletion operations in a Red-Black tree with the help of a suitable example. Q16. Explain Direct File and Indexed Sequential File Organization.

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.