· Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest. Marks are indicated against each question.
· Parts of a question should be answered at the same place.
a. State two important differences between a pointer and an array.
b. Assume A = 1, B = 2, C = 3. Evaluate the following postfix expression:
ABC + * C B A - + *
c. Write a function, length, in C that will return the number of nodes in a given singly linked list.
d. Represent the polynomial 3x14 + 2x8 - 1 using linked list.
e. Do the preorder and inorder sequences of a binary tree uniquely define the binary tree? Justify your answer.
f. Let the adjacency matrix of a graph G be given as
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
find the graph G?
Q.2 a. Write a C program to add a new given node at the end of a singly linked list.
b. Let G be an undirected connected graph given by Using Kruskal’s algorithm generate a minimum cost spanning tree. (9+9)
Q.3 a. Write an algorithm to determine the number of nodes in a given binary tree?
b. For the following input list of numbers
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Find the binary search tree? (9+9)
Q.4 a. Write a function in C program that traverses a threaded binary tree in preorder.
b. Show that the maximum number of nodes in a binary tree of depth K is
2k – 1, k ≥ 0 (9+9)
Q.5 a. With an example, explain the working of heap sort algorithm.
b. Find the shortest path using Dijkstra’s algorithm in the given weighted directed graph from A to E. Explain the steps. (9+9)
Q.6 a. Discuss boundary tag method and write a C program for freeing memory blocks.
b. If a binary search tree with n nodes is well balanced, what is the approximate number of
comparisons of keys needed to find a target? What is the number if the tree degenerates
to a chain? (9+9)
Q.7 Write short note on any THREE of the following:-
(i) Circular queue and priority queue
(ii) Huffman trees
(iii) Shell sort
(iv) Game trees