Devi Ahilya University 2009 B.Sc Computer Science Part II (3 Y.D.C.) , - Question Paper

2009
B.Sc. Part II (3 Y.D.C.) Examination,
COMPUTER SCIENCE
Paper I : Data Structure CPN-21
Time : three hours
Max. Marks. : 50

Note : ans all 5 ques.. All ques. carry equal marks. The blind candidates will be
provided 60 minutes extra time.

1.(a) Why recursion is avoided ? elaborate the steps of removal of recursion ?
(b) A 2 dimensional array LIST[5][3] is described in C language for storing real numbers, if the
base address of array is 2008 then determine the physical address of array element
LIST[1][2].
Or
(a) Determine the best case, worst case and avg. case complexity of linear search algorithm.
(b) What is amortized complexity ? What is it's significance ? Under what circumstances it is
used ? discuss with example.

2.(a) Which data structure is used in function calling ? Write C function to insert and remove
elements from it.
(b) Write C functions for deletion from input restricted queue and insertion in output
restricted queue.
Or
(a) How subsequent expression will be processed by computer ? discuss the procedure by drawing
diagram of stack.
(A-B) * (D/E) where A=12,B=10,D=32,E=2.
(B) For implementing a priority queue write C function for subsequent :
(i) Function for initialization
(ii) Function for checking empty and full condition
(iii) Function for insertion
(iv) Function for deletion
(v) Function for display.

3.(a) Write C function for sorting of Linked List.
(b) Write C function to merge 2 doubly circular Linked List.
Or
(a) How iteration is better then Tll recursion ? discuss with example.
(b) How Sparse matrix is implemented by using Linked List ? How it's transpose will be
determined ? Write C function for this.

4.(a) Write an algorithm of C function to display Binary search tree nonrecursively.
(b) How you will access parent, brother and child of a node in array representation of binary
search tree ?
Or
How rotation will beperformed in un-balanced binary search tree, to make it balanced tree ?

5.(a) Write a C function to implement interpolation search.
(b) How merge sort is better then quick sort ? Justify your ans.
Or
Write short note on the subsequent : (any two)
(i) Graph Traversal Algorithm
(ii) Shortest Path Algorithm
(iii) Time complexities of different Sorting Algorithm
(iv) Memory Representation of Graph.

Earning:   Approval pending.