Shivaji University 2005 B.E Computer Science Data Structure - exam paper

H-419
SECOND YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2005
SHIVAJI UNIVERSITY, KOLHAPUR
DATA STRUCTURE

Day and Date: Friday, 13-05-2005 Total Marks: 100
Time: 3.00pm to 6.00pm

Instructions: 1) Attempt any 3 ques. from every part.

2) Figures to right indicate full marks.



SECTION-1

Q.1. a) suppose ‘Stack’ is allocated N=6 memory cells and initially STACK is empty (TOP=0).Find the output of the subsequent sequence of operations:[Marks 8]

1) Set A=2 and B=5 where A and B are variables.

2) Call PUSH (STACK, A)

3) Call PUSH (STACK, B)

4) Call PUSH (STACK, B+4)

5) Call PUSH (STACK, 9)

6) Call PUSH (STACK, A+B)

7) Repeat while (TOP! =0)

{Call POP (STACK, ITEM), write item}


b) What is priority queue? discuss operations on the priority queue.[Marks 8]



Q.2. a) Show the status of array after every step in sorting the subsequent elements using heap sort:
95, 19, 44,8,32,75,25,65

b) discuss the subsequent with suitable examples: [Marks 8]

1) Linear search

2) Binary search


Q.3. a) Suppose CLIST is a circular linked list in memory consisting of numerical values. Write algorithms for every of the subsequent operations:[Marks 8]

1) Finding the numbers ‘NUM’ holding total number of even numbers in the CLIST.

2) Finding product ‘PRODS’ of numbers in the CLIST.

3) Multiplications of every number in CLIST with a provided number ‘K’.

b) discuss the operations on doubly linked list in detail.[Marks 8]



Q.4. Write a short notes on:[Marks 18=6*3]

1.Selection sort

2.Radix sort

3.Stack



SECTION-2



Q.5. a) Write a ‘C’ program to create and swap the tree. [To swap the provided tree means to interchange the left child and right child of every node in a tree] [Marks 8]

b) Compare Graph and Binary Tree.[Marks 8]



Q.6.a) the graphs are provided beneath. Represent the graphs using adjacency matrix and Adjacency list.[Marks 8]












b) describe subsequent (any five).[Marks 5]

a) Tree

b) Binary Tree

c) Complete binary tree

d) Almost complete binary tree

e) Skewed Binary Tree

f) Binary search Tree


c) State a few applications of a graph.[Marks 3]



Q.7.a) discuss closed hashing and open hashing.[Marks 8]


b) Write an algorithm for insertion and deletion into binary search tree.[Marks 8]



Q.8.a) discuss Reheap-up and Reheap-down functions in heap.[Marks 8]


b) Compare B-Tree AND B+ Tree.[Marks 8]

Earning:   Approval pending.