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

Sunday, 20 January 2013 03:00Web

2009

B.S

**c.**

**(3 Y.D.C.) Examination,**

**Part I**ICOMPUTER SCIENCE

Paper I : Data Structure CPN-21

**Time :**three hours

Ma

**x.**Marks. : 50

Note : ans all 5 ques.. All ques. carry equal marks. The blind candidates will be

provided 60 minutes extra time.

1.

**(**Why recursion is avoided ? elaborate the steps of removal of recursion ?

**a)****(**A 2 dimensional array LIST[5][3] is described in C language for storing real numbers, if the

**b)**base address of array is 2008 then determine the physical address of array element

LIST[1][2].

Or

**(**Determine the best case, worst case and avg. case complexity of linear search algorithm.

**a)****(**What is amortized complexity ? What is it's significance ? Under what circumstances it is

**b)**used ? discuss with example.

2.

**(**Which data structure is used in function calling ? Write C function to insert and remove

**a)**elements from it.

**(**Write C functions for deletion from input restricted queue and insertion in output

**b)**restricted queue.

Or

**(**How subsequent expression will be processed by computer ? discuss the procedure by drawing

**a)**diagram of stack.

(A-

**B)*** (D/

**E)**where A=12,B=10,D=32,E=2.

**(**For implementing a priority queue write C function for subsequent :

**B)****(**Function for initialization

**i)****(**Function for checking empty and full condition

**i****i)****(**Function for insertion

**i****i****i)****(**Function for deletion

**i****v)****(**Function for display.

**v)**3.

**(**Write C function for sorting of Linked List.

**a)****(**Write C function to merge 2 doubly circular Linked List.

**b)**Or

**(**How iteration is better then Tll recursion ? discuss with example.

**a)****(**How Sparse matrix is implemented by using Linked List ? How it's transpose will be

**b)**determined ? Write C function for this.

4.

**(**Write an algorithm of C function to display Binary search tree nonrecursively.

**a)****(**How you will access parent, brother and child of a node in array representation of binary

**b)**search tree ?

Or

How rotation will beperformed in un-balanced binary search tree, to make it balanced tree ?

5.

**(**Write a C function to implement interpolation search.

**a)****(**How merge sort is better then quick sort ? Justify your ans.

**b)**Or

Write short note on the subsequent : (any two)

**(**Graph Traversal Algorithm

**i)****(**Shortest Path Algorithm

**i****i)****(**Time complexities of different Sorting Algorithm

**i****i****i)****(**Memory Representation of Graph.

**i****v)**Earning: Approval pending. |