RGPV Exam Question Papers 3rd SEM
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) carry^{1} 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
 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 [20] [50] requires 4 bytes of storage base address of DATA is 2000, determine the location of x [0] [10] when the array is stored as
i) Row^{r}major ii) Columnmajor 7
Unit – II
 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+Vb^{2}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
 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 (k1) 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
UnitIV
2 
 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
UnitV
 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»