# Computer Science(June 2014)

Note: i) Answer five questions. In each question part A, B, C is compulsory and D part has internal choice.

ii)           All parts of each question are to be attempted at one place.

iii)         All questions carry equal marks, out of which part A and B (Max. 50 words) carry1 2 marks, part C (Max. 100 words) carry 3 marks, part D (Max. 400 words) carry 7 marks.

iv)         Except numericals, Derivation, Design and Drawing

etc.

Unit -1

1. a)                                 What are the goal of data structure.          2

b)         What do you mean by garbage collection.                         2

c)          Difference between abstract data type specification and

implementation.                                                                3

d)         Give the simulation of recursive version of tower of Hanoi

problem and simplify the simulation to produce a non recursive version.       7

OR

How is physical memory allocated for a two dimension array? If each element of an array x   requires 4 bytes of storage base address of DATA is 2000, determine the location of x   when the array is stored as

i)                                                                                                       Rowrmajor        ii) Columnmajor        7

Unit – II

1. a) What is dangling pointer and how to avoid it?                                                                       2

b)            What are the disadvantage of representing a stack or queue by link list?       2

c)  Convert following infix notation into prefix and postfix.

-b+Vb2-4ac/2a                                                                   ^

d)         Design a C function for keeping two stack of integer within

a single array main stack Lspace size] so that neither stack overflow until all of the memory in used and an entire stock is never shifted to a different location within the array.                                                                                7

OR

Suppose we wish to use an extra bit in a queue records to indicate whether a queue is empty modify the declaration and operation of circular queue to accomodate this feature.

7

Unit – III

1. a)   Why complete binary tree structure considered as

efficient space and time comp] ixity? •                             2

b)            In an AVL tree at what condition the balancing is to be done.    2

c)             Prove that a tree with K nodes has exactly (k-1) edge or branches.      3

d)            The following data arc to be inserted in an AVL tree in the following order.

20, 25.30,40,45, 60, 55,57

Show the tree every time balancing is required. 7

OR

Suppose A, B. C, D, E, F, G, & H are 8 data items and suppose they are assigned weights as Data item                    ABCDEFG     H

Weight          22      5 11 19 2              11    25      5

P]

Construct the tree T with minimum weighted path length using above data and using Huffman’s algorithm.                                                       7

Unit-IV

 2
1. a)   Define the term

i)        Internal sorting

ii)      External sorting

 2 3 7

b)          What are the disadvantages of sequential search?

c)           Describe the complexity of heap sort.

d)          Sort the following integers using quick sort 25, 57,48,37, 12, 92, 86,33.

OR

 7

Construct a heap tree for following nodes 5,16, 22, 45,2,10,18, 30, 50, 12,1

Unit-V

1. a)   What do you mean by graph and multi graph?                 2

b)         Is it possible to connect a graph into tree if yes how.        2

c)          For following graph find                                                   3

i)        In degree and out degree of each vertex

ii)      Strongly connected component i i i) Adj accncy matrix

d)

 Find minimum cost spanning tree of given graph using kruskaPs algorithms.    7

 Consider graph (G)

 OR

i)  Find adjacency matrix (A) of graph G

ii)                                                                                                                                                                                                                             Find path matrix (P) of G     7

W v!> \I/

M »T»