Contents

# MCS-021 Ignou Important Question 2018 [ Data and File Structures ]

1.       What is Data Structure? Write Application of Data Structure.
2.       Write an algorithm for implementing insertion and deletion operations in a singly linked list.
3.       Write prim’s algorithm for constructing a minimum cost spanning tree and trace the algorithm on the following network.

4.       Explain in detail the algorithmic implementation of multiple stacks (2-way stack).
5.       Explain the DFS and BFS algorithm with example.
6.       Write Floyd’s algorithm for all-pairs shortest path algorithm.
7.       Discuss about the linear search and Binary Search in detail.
8.       Construct BST for the following unordered elements
2, 3, 81, 64, 4, 25, 36, 16, 9, 49
9.       What is a sparse matrix? What is its 3-tuple representation? Also, write an algorithm that accepts 5×4 sparse matrixes and outputs its 3 tuple representation.
10.   Sort the following numbers using Quick sort algorithm. Show all intermediate steps.
10, 70, 2, 32, 11, 48, 6, 19
11.   Construct a binary tree using the following pre-order and in-order sequences :
Pre-order: 35, 31, 15, 7, 33, 32, 43, 38, 40, 49
In-order: 7, 15, 31, 32, 33, 35, 38, 40, 43, 49
.
12.   Solve the following instance of single source shortest paths problem with vertex ‘a’ as the Source.

13.   Sort the following data using heap sort. Show various steps of sorting.
40, 86, 32, 99, 41, 56, 74
14.   What is a circular queue? Write an algorithm to insert and delete a node in a
15.   What are the differences between sequential and direct file organisation? Under what conditions, if any, is it advantageous to have the file organised as a direct file rather than sequential file?
16.   Write short notes on the following with an example : 5×4=20
a.       Red Black Tree
b.       Applications of Tree
c.       AA Tree
17.   Elaborate various asymptotic notations used to evaluate the efficiency of the algorithm. Or Explain Complexity and Asymptotic Equation.
18.   Write a program that accepts two polynomials as input and displays the resultant polynomial due to the addition of input polynomials.
19.   Explain the recursive algorithm for each of the binary tree traversals.
20.   What are the pre conditions for applying binary search on any list containing Integer values? Write the algorithm and manually run it on the following list of number :
10, 27, 2.3, -56, 38, 66, 45
What is worst case complexity of the above algorithm?
21.   Write an algorithm that sort a given linked list of integers. Also, write a function that splits this linked list into a linked list of even integers and a linked list of odd integers.
22.   What is the need for external sorting? Explain any one method to perform external sorting.
23.   Write an algorithm for sorting whose average and best time complexities are same.
24.   Explain the process of converting any Tree into a Binary Tree.
25.   Draw AVL tree by inserting the following elements one by one :
10, 7, 13, 27, 9, 11, 14, 8, 37, 24
26.   Write an algorithm for array implementation of a circular queue. Write an algorithm to insert and delete a node from a doubly-linked list.
27.   What is a splay tree? Write the steps involved in a top-down splaying procedure.

28.   Write a program to merge two sorted arrays into one array.