Download AKTU B-Tech 4th Sem 2014-15 Data Structure Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 4th Semester (Fourth Semester) 2014-15 Data Structure Question Paper

Printed Pages : 3
munmuuumummuynml NEW
(Following Paper ID and Roll No. to be ?lled in your Answer Book)
PAPER ID : 131405
Roll No.
B.T_ech
(SEM. IV) THEORY EXAMINATION 2014-15
DATA STRUCTURE
Tune : 3 Hours] [Total Marks : 100
Note: Attempt All Questions. All Questions carry equal marks:-
1 Attempt any FOUR of the following questions.? 5x4=20
(:1) Explain merits and demerits of static and dynamic
memory allocation techniquw.
(b) What is asymptotic notation? Explain the Big '0'
notation
(c) What is Sparse Matrix? Discuss it's representation
in term of lower triangular matrix.
(d) What is Link list? How it is di??erent from an
array?
(e) Write an algorithm to insert and delete an item
from the circular link list. ,
(t) Di??erentiate between over?ow and under?ow
condition in link list.
131405] 1 [ Contd...

' Attempt any TWO of the following questions: 10x2=20
@)
(b)
(C)
Convert E=abcdeM*+ post?x expression to in?x
and pre?x using stack
What is recursion? Write a recursive solution to
solve TOWERS of HANOI problem.
How would you implement a queue of stacks?
Write routines to implement the appropriate
operations for this data structure.
Attempt any TWO of the following questions: 10x2=20
GD
(b)
?3
Prove and explain that a strictly binary tree with
'n' leaves contains ?2n-l' nodes.
? Construct a tree for the following preorder and
postorder and write its inorder traversal.
Preorder: 24,14,13,19,17,15,10,5,8,6,7,20.
Postorder: 13,15,17,10,19,l4,7,6,20,8,5,24 ?
Explain threaded binary tree. How it would be
use?zl and ef?cient in implementing the tree
traversal?
Attempt any TWO of the following questions: l0x2=20
00
(b)
131405]
Explain Depth First Search. Give example to
support your explanation.
Explain Kruskal's algorithm to ?nd minimum
spanning tree in a weighted directed graph. Can
there be two minimum spanning trees of given
weighted directed graph?
2 [ Contd...
(c) How can you ?nd shortest path between two
nodes in a graph by Dijikstra algorithm? Explain
by suitable diagram.
Attempt any TWO of the following questions: 1012=20
(a) With the help of algorithm explain the binary
search and also discuss it's time complexity.
(b) Write and explain the bubble sort algorithms for
a given set of 'n' data's where ?k?h? is the
largest data.
(0) Compare and contrast average case behavior of
Quick Sort and Merge Sort.
131405] 3 [9925]