Guru Gobind Singh Indraprastha Vishwavidyalaya 2006 B.C.A Computer Application Data Structure Using C - Question Paper

Q1 (a) Design an algorithm to reverse print the contents of a singly linked list.
(b) describe a B-tree? provide an example.
(c) Draw a binary tree representation for the subsequent infix expression.
A * b + c * d – e +f/g
(d) Write a recursive procedure for the pre-order traversal of a Binary tree
(e) define how a stack is useful in recursion? Illustrate with an example.
(5x5=25)
Q2 A sparse matrix is normally represented as a 2 dimensional array A[t+1, 3]
(where t is no. of non-zero elements in the sparse matrix). The 1st row contains
Number of rows, number of columns of the original marrix and t. Design a suitable
algorithm for the addition of 2 sparse matrices represented in the above form.
OR
provide 2 arrays of integers organizes in ascending order. Design an algorithm to merge
These arrays to form a 3rd stored in ascending order. (12.5)
Q3 (a) Design an algorithm to deleted every alternate node starting with the 1st node
In a singly linked list.
(b) Write a procedure for deleting an element form a circular Queue.
(c) What is a priority queue?
OR
discuss Kruskal’s algorithm for generating minimum cost spanning tree. Illustrate the
Working of the algorithm with an example. (12.5)
Q4 What is multilevel indexing? How B-tree are useful in indexing? How do you generate
a B-Tree? discuss the insertion operation of B-Tree with an example.
OR
Design an algorithm for obtaining a mirror image of a Binary tree (Left child should be
Right child for every non-leaf node) (12.5)
Q5 Write quick sort algorithm and explain its time and space complexities. discuss different
passes of the quick sort algorithm to sort the subsequent array.
{15,4,23,32,87,43,8,72,93,25,7,89}
OR
Write a C program for sorting an array of integers using Bubble sort technique. Disucss
Its complexity and compare it with merge sort. Sort the subsequent numbers in ascending
Oder using Bubble sort technique.
{15,4,23,32,87,43,8,72,93,25,7,89)

Earning:   Approval pending.