Data Structure — Summer 2018

Do as directed.. 1. Define Minimum spanning tree. 2. Full form of KWIC. 3. Write application of queue. 4. Write algorithm for PUSH operation. 5. Draw the node structure to represent polynomial having two variable. 6. Draw the trie tree for the sequence : a,ba,bab 7. Write best, average and worst case complexity for bubble sort.

Define data structure. Explain various types of data structure in detail.

Explain the creation of min heap and max heap for the following set of data [20,5,34,6,8,10,14]

Explain Big ‘Oh’ notation. What is best case, average case and worst case of algorithm? Compare bubble sort, selection sort, merge sort, quick sort methods using their average case and worst case.

Write and explain the steps to convert the given infix expression into postfix expression. A*B(C+D)^E-F

How can we represent a node in a doubly linked list? Write the insert after data operation on a doubly linked list.

Generate Binary tree using following traversal. Inorder : H,D,B,I,E,A,F,J,C,K,G,L Postorder : H,D,I,E,B,J,F,K,L,G,C,A Also write the pre-order for the tree.

What is the disadvantages of simple queue? Explain circular queue in detail. Write an algorithm for the insertion in circular queue.

Generate a binary search tree for the following set of data. 55, 10, 39, 42, 76, 93, 14, 69, 24, 84. Generate in-order threaded binary tree of the above tree after deleting the node with value 93.

Explain topological sorting using following graph :

Define adjacency matrix and path matrix of a digraph. Explain how a path matrix can be calculated from the adjacency matrix of a simple digraph.

Write and Explain BFS algorithm with suitable example.

Find minimum cost of following graph using Prim’s algorithm.

Write the algorithm for quick sort and sort the following numbers using quick sort [25,2,65,1,60,5,80,15,90,45].

Write a recursive algorithm of Binary search.

What is hashing? Write down any four collision resolution techniques.

Explain AVL tree with suitable example.