Shivaji University 2006 B.E Computer Science DATA STRUCTURE - exam paper

Q-182
SECOND YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2006
SHIVAJI UNIVERSITY, KOLHAPUR
DATA STRUCTURE

Day and Date: Thursday, 11-11-2006 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.



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) Write a program to implement Insertion and Deletion in doubly linked list.[Marks 8]

b) discuss an algorithm for merge sort.[Marks 8]

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 any two: [Marks 18=9*2]

1.Comparison of sorting methods.

2.Traversals techniques in binary trees.

3.AVL tree.

SECTION-2



Q.5. a) what is hashing? discuss open Hashing and Closed Hashing. [Marks 8]

b) Write a C program to implement searching of numbers in a table using Hashing technique.[Marks 8]

Q.6. a) Write a ‘C’ program to Implement Insertion in a Binary Search Tree.[Marks 8]

b) What causes deletion of a node in a binary search tree more difficult than insertion? discuss with example.[Marks 8]



Q.7. a) discuss the graph data structure and its storage representation.[Marks 10]

b) Write an algorithm for breadth 1st traversal of a graph.[Marks 6]

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

a) B tree and B+ tree

b) Heaps, operations and its application

Earning:   Approval pending.