1.
d) Differentiate the following terms:
(a). Liner and Non-Linear Data Structures
(b). Primitive and Non-Primitive Data Structures
2. e) Convert the given infix expression to postfix expression using a stack.
I. A + ( (B – C) * (D – E) + F) / G ) $ (H – J)
II. (A + B) * (C – D) $ E * F
III. (A + B) * (C ^ (D – E) + F) – G
IV. A + [(B +C) + (D + E) * F] / G
V. (A + B) * C / D + E ^ F /G
3. c) Apply insertion sort (show step by step) algorithm to sort the following data. Justify the steps.
42, 29, 74, 11, 65, 58, and 3
4. h) There is a doubly linked list with data: 42, 29, 74, 11, 65, 58, 3. Update the node with data 47 with
the new data 87. Show (draw) the necessary figure(s) and write an algorithm (pseudo-code) to perform
the operation
5. a) Construct a binary tree for the given inorder and postorder traversals sequences.
Inorder: D, G, B, A, H, E, I, C, F
Postorder: G, D, B, H, I, E, F, C, A
b) Construct a binary tree for the given inorder and postorder traversals sequences.
Inorder: 4, 2, 1, 7, 5, 8, 3, 6
Postorder: 4, 2, 7, 8, 5, 6, 3, 1
g) Construct a max heap (show step by step) for the following data
I. 10,3,15,22,6,45,65,23,78,34,5.
II. 50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5
III. Delete maximum (show step by step) from the max heaps of (a) and (b)
IV. Perform heap sort (show step by step) on the heaps of (a) and (b)
6. c) Find the minimum cost spanning tree (show step by step) of the following graph using Kruskal’s
algorithm.