# RGPV Exam Question Papers 3rd SEM

# Computer Science(Dec 2010)

Note : Attempt any five questions All questions carry equal marks. „

Unit—I

- (a) What are- Asymptotic notations ? Explain each

notation with example and diagram. 12

(b) Solve the following recurrence relation _{X}(_{n}) = t (n – 1) + 1, with T(0) = 0 as initial condition. Also find big oh notation. 8

Or /

- (a) What is recursion ? How does it differ from iteration ?

Write an algorithm to generate first ten Fibonacci numbers recursively. . < ^

(b) Consider a 2D array declared in “C” A [20] [30]. Element type is integer. If the base address is 1076, what will be the address of A [17] [29] ? Memory’ is

O

byte oriented.

P. T. O.

[ 2 3 CS/IT-305(N)

Unit-II

. ✓ »

- (a) Explain the inserting and deleting node from linked

list implementing stack and queue. 16

(b) What are D-queue and priority queue ? 4

‘ Or

- (a) Write an algorithm to convert infix to postfix

expression. Explain with example. 10

(b) Write function for : 10

(i) Finding size

(ii) Checking empty

(iii) Checking full . –

for the implementation of a queue in circular array with index values to indicate emptiness.

Unit-III

- (a) Following nodes are insert into empty tree in order

” . ^{12} 5, 16,22,45,2, 10, 18,30,50, 12, 1

Construct : ^{r} < ■ .

(i) Binary Search Tree

(ii) AVL Tree

(b) Draw the order-5 B-tree resulting from inserting the following keys (in th’l order) into an initially empty tree : — 8

4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, ’77, 39, 12 ;

_{c} Or . .

- (a) Explain the operation of AVL Tree. 8

(b) Write, an algorithm to delete operation in any binary search tree (Taking all cases). 12

Unit -IV

. (a) Compare the worst case performance of heap sort with

the worst case performance and average case of quick

^{10}

sort.

(b) Explain insertion sort and selection sort brietly. 10

Or

- (a) What is the difference between an index function ana

a hash function ? Explain three techniques to built the

. 10 hash function.

(b) Explain how balance is restored when an insertion into – – height-balanced tree puts a code out of balance ? 10 . Unit-V

- -(a) Apply Prim’s algorithm to find the minimum spanning

tree of the given graph.

Display the tree at each stage. „

(b) Compare graph traversal techniques.

Or

f

- (a) Explain Dijkstra algorithm with suitable example. 10 (b) Write short notes on the following : 5 each

(i) Strongly connected graph

17,660 |

(ii) Sparse matrix