Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2018-2019 Data Structures Rcs 305 Question Paper
Paperld: IIIIEID RonNo.L J Li 1 l J I l l i
B. TECH.
(SEM III) THEORY EXAMINATION 2018-19
DATA STRUCTURES
T ime: 3 Hours T otal Marks: 70
Note: 1. Attempt a1] Sections. If require any missing data; then choose suitably.
SECTION A
l. Attempt all questions in brief. 2 x 7 = 14
a. How the graph can be represented in memory? Explain with suitable
example.
b. Write the syntax to check whether a given circular queue is full or empty?
c. Draw a binary Tree for the expression: A * B - (C + D) * (P /Q)
d. Differentiate between over?OVv and under?ow condition in a linked list.
e. What do you understand by stable and in place sorting?
f. Number of nodes in a complete tree is lOOOOQKFind its depth.
g. What is Recursion? Give disadvantages of recursion.
SECTION ?13; i
2. Attempt any three of the following: .~ a 7 x 3 =21"
a. What do you understand by time and space trade off? De?ne the various
asymptotic notations Derive the O-notation for linear search.
b. Consider the following intlx expression and convert into. reverse polish
notation using stack?: A + (B * C? (D / E A F) * H)
c. Explain Hu?man algorithm Construct Huffman tree 101 MAHARASHTRA
with its optimal code.
C]. What IS a height balanced Tree? Why height balancirig ofTree is required?
Create an AVL Tree for the following elements: a, z, b, y, c, x, d, w, e, V, f
e. Write the Floyd Warshall algorithm to cempute the all pair shortest path. Apply
the algorithm on following graph: *
MANISH KUMAR JHA I 29-Dec?2018 09:10:47 | 117.55.242.131
SECTION C
Attempt any one part of the following: 7 x 1 = 7
(21) Write a program in c to delete a speci?c element in single linked list. Double
linked list takes more space than single linked list for storing one extra address.
Under what condition, could a double linked list more bene?cial than single
linked list.
(b) Suppose multidimensional arrays P and Q are declared as P (-2: 2, 2: 22) and
Q (1: 8, -5: 5, -10: 5) stored in column major order
(i) Find the length of each dimension of P and Q
(ii) The number of elements in P and Q
(iii) Assuming Base address (Q) = 400, W=4, Find the effective indices E1,
E2, E3 and address of the element Q [3, 3, 3].
Attempt any one part of the following: 7 x 1 = 7
(a) Explain Tower of Hanoi problem and write a recursive algorithm to solve it.
(b) Explain how a circular queue can be implemented using arrays. Write all
functions for circular queue operations.
Attempt any one part of the following: 333 7 x 1 = 7
(a) Write the algorithm for deletion of an elew??n binary search tree. 2%.
(b) Construct the binary tree for the follo . ?3m,?
In-order. Q, B, K,,C F, A G P Tagn, 3X?
Preorder: G,,BQ,,A,CK,,,FP? ,:RH 3:3
Find the Post Order of the Tree?v ,?3 1% ?
Attempt any one part of the follo?mg: ME 7
(a) By considering vertex: ?(3?35 source vertex, Find the shortest p 5 t1? all other
vertices in the followi?? graph using Dijkstra? s algorithms Shivv?all the steps.
(b) Explain 1n detail about the graf?ti traversal techniques with suitable examples.
Attempt any one part of the foqjigg: 7 11 1= 7
(a) Write algorithm fonwk sort. Trace your algorithm on the following data to
sort the list: 2 133, 4v21, 7 56, 51, 85, 59, 1, 9, 10. How the choice of pivot
element effects th?ief?ciency of algorithm
(b) Construct a B- tree of order 5 created by inserting the following elements
3,14, 7,1. 8, 5,11,17,13, 6, 23, 12, 20, 26, 4,16,18, 24,25,19
Also delete elements 6, 23 and 3 from the constructed tree.
MANISH KUMAR JHA I 29?Dec-2018 09:10:47] 117.55.242.131
This post was last modified on 29 January 2020