CS-04 : DATA STRUCTURE THROUGH “C” & “PASCAL”
Dec. 2003

1(a) Write an array implementation of a Self-Adjusting List (SAL). A SAL is a list in which all insertions are performed at the front and when an element is accessed by a procedure like FIND, it is moved to the front of the list without changing the relative order of the other items.

(b) Show that in a binary tree of N nodes, there are N + 1 NULL pointers representing children.

(c) Two binary trees are similar if they are both empty or both nonempty and have similar left and right subtrees. Write a function to decide whether two binary trees are similar. What is the running time of your program?

2(a) Write a program to check for balancing symbols in the ‘C’ language. The symbols include (/* */, ( ), { }).

(b) Give the prefix and infix expressions corresponding to the tree in the following figure:

3(a) Show how to implement three stacks in one array.

(b) Write an algorithm to evaluate a postfix expression. The algorithm should be non-recursive.

4(a) Consider the graph of the following figure:

Perform a Breadth-First Search beginning at vertex V1. List the vertices in the order in which they are visited.

(b) Write an algorithm to find the minimum number of edges that need to be removed from an undirected graph so that the resulting graph is acyclic.

5(a) In an Insertion Sort, suppose we exchange elements A[i] and A[i + k], which were originally out of order. Prove that atleast 1 and atmost 2k - 1 inversions are removed.

(b) Here are ten integers : 25, 40, 2, 4, 3, 89, 76, 99, 101, 24
Sort them using Insertion Sort and show all the stages.

6 Develop a program in C to sort the numbers 25, 40, 35, 15, 6, 8 using Merge Sort without recursion.

Previous Paper

UNIVERSAL TEACHER PUBLICATIONS
Web: www.universalteacherpublications.com, www.universalteacher.com