Data Structures — Summer 2024

Explain data structure. Enlist and explain the importance of data structure.

Define time and space complexity. Derive time complexity of merge sort.

1) Evaluate the postfix expression in tabular forms: 2 5 3 - * 8 / 4 + 2) Evaluate the prefix expression in tabular forms: / 7 * 1 + 4 – 6 3

Explain Tower of Hanoi with suitable example.

Define hash function. Explain it with suitable example.

Write an algorithm for the following stack operations. 1) PUSH 2) POP 3) DISPLAY

Write an algorithm for the following queue operations. 1) INSERT 2) DELETE 3) DISPLAY

Write an algorithm to add a node into a binary search tree.

Explain Dequeue and Priority queue in detail.

Construct the minimum spanning tree using prim’s algorithm for the following graph.

Write an algorithm to delete an item from the doubly linked list.

Differentiate: BFS and DFS.

Construct the minimum spanning tree using krushkal’s algorithm for the following graph.

Define the terms below: 1) Threaded Tree 2) Acyclic graph 3) Sparse matrix

Explain AVL tree in detail with suitable example.

Construct a binary tree from the traversals given below: Inorder : D, B, E, H, A, I, F, C, G Preorder : A, B, D, E, H, C, F, I, G

Define the terms below: 1) Complete Binary Tree 2) Forest 3) Abstract data type

Explain 2-3 tree in brief.

Write an algorithm to insert an item as below: 1) At the start of the linked list 2) At the end of the linked list

Define file. Explain its types.

Explain bubble sort with suitable example.

Build a chained hash table of 10 memory locations. Insert the keys 121, 3,4, 31, 61, 24, 7, 87, 8, 9 in hash table using chaining. Use h(k) = k mod m (m=10).

Define file organization. Explain different file organizations.

Sort the following array elements using insertion sort algorithm. 8, -2, 5, 3, 9, 4,

Explain Dijakstra’s shortest path using suitable example.