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) 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
- 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
d) Give the simulation of recursive version of tower of Hanoi
problem and simplify the simulation to produce a non recursive version. 7
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
- 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.
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
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.
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 (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
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
Construct the tree T with minimum weighted path length using above data and using Huffman’s algorithm. 7
- a) Define the term
i) Internal sorting
ii) External sorting
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.
Construct a heap tree for following nodes 5,16, 22, 45,2,10,18, 30, 50, 12,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
|Find minimum cost spanning tree of given graph using kruskaPs algorithms. 7
Consider graph (G)
i) Find adjacency matrix (A) of graph G
ii) Find path matrix (P) of G 7
W v!> \I/