Guru Gobind Singh Indraprastha Vishwavidyalaya 2008-2nd Year B.C.A Computer Application Data Structures, Second Semester, End Term , Year , , - Question Paper

Jpf'Define Complete Binary Tree, Fufl Binary Tree, Degree of a Tree. Height of a Tree and Ancestors of a node Take an example to expie*v    (5)

JftyGcve the Binary Tree representation of the following expression    (3)

E (a-b) / ((c d>*e)

Define a B-Tree.    (2)

UNIT-1

/

(a)    What are sparce Matrices? Discuss various types of spares matrices    (S) (b> Give an algorithm to evaluate a given postfix expression. (5)

(c) Wnte a *C function to Insert an element into a Inear Queue. (5)

Q3 (a) What is a Stack? Give the algorithm for converting a given Infix expression to its postfix notation Using the above algorithm find the postfix expression of the foAowmg infix expression    (11)

(A*By (C*D+E)

(b)    Consider a circular queue inilially having 3 elements A. B. C inserted in same sequence and having a maximum capacity of 5 elements Show the current value of FRONT & REAR Delete 2 elements from the queue and insert 4 more elements (0- E. F. G) in the queue and show final position of REAR & FRONT    (4)

UNIT-tl

04    (a} Write a *C functions for deleting a node from the beginning of a Linear.

Linked bst    (5)

(bl>Vrita a short note on doubly linked list and explain with an example deletion of a node from the middle of the bst.    (5)

jcWrrte a C recursive function for Inorder traversal of a binary tree    (5)

05    <a) Write an algorithm to search for an ITEM' in an already existing unordered

linked bst    (6)

P.T.O.

(b) Give the Inordet. Preorder and Poetorder traversals o< the following binary tree.    (9)

UNfT-ll

06 lf Consider the hst of foCowing number;    (10)

14.10.17.12.11.20,18. 25. 8.22.23

Create a tanary search tree Then show the vanous tree* obtained after deletion of (I) node 11 (U) node 22 () node 20 (btftMh a binary tree * the foaovwng Preorder and inorder Traversal* of the / tree are given    (5)

07. Create a B-tree of order 5 with the following keys neerted in the sequence

from left to right.    <18)

agfbkdhmjeslrxclntup

Also show the tree after deletion of the key p' from the tree.

UNIT-IV

tel Sort the foiowing iet using ineerton sort ' 44 33 11 55 77 90 40 60 (p) What * Hashing? Discuss any . two Hash functions. What is collision resolution?     (8)

09 (a) Give algorithm for bubble sorting    (S)

(b) Wrtfe a 'C function for searching an item from a given list using Binary search Also explain the working of the algorithm by taking a sUtabie example        (10)