DATA AND FILE STRUCTURES

1 What are the preconditions for applying binary search on any list containing integer values ? Write the algorithm and manually run it on the following list of number 

11 22 33 44 55 66 77 88

2 What is worst case complexity of the above algorithm ?

3 How can a polynomial be represented with the help of a linked list ? Write an algorithm to multiply two polynomials of degree 'm' and degree 'n' ?

4 Write a program to implement a static stack. Also, mention few applications of stack ?

5 Differentiate between the following 
(i) Space and Time complexity
(ii) Indexed file organisation and Indexed sequential file organisation

6 Write an algorithm to balance a Red-Black tree after deleting a node ?

7 How are the deletions performed in Binary Search Tree ? Explain each case of deletion with an example

8 Write algorithm to insert elements in a B-Tree. Make B-Tree using your algorithm for the following list of elements ?

2. 4, 9, 8, 7, 6,3, 1, 5, 10

9 Two Binary trees are similar if they are both empty or if they are both non-empty and left and right subtrees are similar. Write an algorithm to determine if two Binary trees are similar?

10 Explain the factors involved in the selection of a particular file organization for user. What is sequential file ? Why are sequential files stored in disk cylinder by cylinder ?

11 What are the limitations of a Binary Search Tree (BST) ? How does AVL tree help in this regard ?

12 Give an AVL tree for which the deletion of a node requires two double rotations. Draw the tree and explain why two rotations are needed ?


13 Write a function in 'C' to insert a node in a linked list at the following position 
(a) at the beginning
(b) at the end


14 What are the different types of hash functions How can clustering involved in linear probing be avoided ? Explain any two methods.

15 Write an algorithm to sort an array
25, 15, 30, 9, 99, 20, 26
using insertion sort . Also write the steps involved in it ?

16 Write an algorithm to discuss the implementation of breadth first traversal method of a graph?



17 Write algorithms for the following 
(i) To insert a node at a given position in a circular linked list.
(ii) To delete the first node from circular linked list.


18 Write an algorithm to create a Binary Tree. The algorithm should accept elements and display Binary Tree with those elements ?

19 What is a linear queue ? Write an algorithm for adding an element to a linear queue .

20 Write a 'C' program to implement priority queue using arrays, check for overflow and underflow conditions ?

21 Write an algorithm for the implementation of multiple stacks in an array?


22 Write a program in 'C' for the implementation of a Doubly Linked List ?

23 Explain sequential file organisation. What are various operations that can be
performed on it ? Also, list any two disadvantages of it.

24 Write algorithm for Heap sort. Also run your algorithm manually and show how sorting is done by your algorithm for the following sets of data ?

1 6 , 1 4 , 1 0 , 8 , 7 , 9 , 3 , 2 , 4 , 7

25 Compare Arrays with linked list by mentioning the advantages and limitations of both?
26 Why is Red-Black tree considered a better data structure than Binary Search tree and AVL tree ? Write algorithm to insert a node in Red-black tree. Take proper example also.

27 Sort the following numbers using Quick sort algorithm. Show all intermediate steps. 
10, 70, 2, 32, 11, 48, 6, 19

28 Differentiate between singly linked list and Doubly linked list. Write algorithm to insert and delete elements in a singly linked list ?

29 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 ?

30 Write short notes on the following with an example 
(a) Red Black Tree
(b) Multiple stacks
(c) Applications of Tree
(d) Kruskal's Algorithm.
(e) Binary search

31 Define the term "Complexity". For what types of applications is Time Complexity Critical and for what types of applications is Space Complexity Critical?

32 Write an algorithm to implement the following functions of a dequeue. Also, give an example to show the working of these functions ?
(i) Insert Element
(ii) Create DEQUEUE
(iii) Delete Element

33 Write an algorithm for multiplication of two sparse matrices?

34 What is cylinder - surface indexing ? Explain it with an example. Also, write its merits and demerits.

35 Define Abstract Data Type, and give two examples of it ?

36 Explain the following using an example
(i) Breadth First Search
(ii) AVL Tree

37 Write a program to store the roll numbers and names of students in a binary search
tree. Write a function to accept a number and display the name of the student, whose
roll number matches with this number. Give suitable messages if the roll number does not
exist in the binary search tree ?
38 Write a program to simulate a circular queue using pointers with functions for insertion, deletion. (Use singly linked list)?

39 Write an algorithm for pushing an element into a stack?

40 Write a program to find the frequency of words in a given text. The list of words and
their corresponding frequency should be in the alphabetical order of words ?

41 Explain the properties and operations of AA trees ?

42 What are the essential features of a binary tree ? Explain, how a general tree can be converted into a binary tree ?

43 Write an algorithm to balance a Red-Black tree after deleting a node ?