RGPV Exam Question Papers 3rd SEM
Computer Science(Dec 2010)
Note : Attempt any five questions All questions carry equal marks. „
- (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
- (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  . Element type is integer. If the base address is 1076, what will be the address of A   ? Memory’ is
P. T. O.
[ 2 3 CS/IT-305(N)
. ✓ »
- (a) Explain the inserting and deleting node from linked
list implementing stack and queue. 16
(b) What are D-queue and priority queue ? 4
- (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.
- (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
. (a) Compare the worst case performance of heap sort with
the worst case performance and average case of quick
(b) Explain insertion sort and selection sort brietly. 10
- (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.
- (a) Explain Dijkstra algorithm with suitable example. 10 (b) Write short notes on the following : 5 each
(i) Strongly connected graph
(ii) Sparse matrix