CS04 : DATA STRUCTURE THROUGH “C” & “PASCAL”
Dec. 2003
1(a) Write an array implementation of a SelfAdjusting 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 nonrecursive.
4(a) Consider the graph of the following figure:
Perform a BreadthFirst 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.
