Download AKTU B-Tech 3rd Sem 2017-2018 RCS305 Data Structures Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2017-2018 RCS305 Data Structures Question Paper

Printed Pages: 02 Sub Code: RCS305
PaperID= In?ll] RollNo-i \ i i i i i i i i \
B TECH
(SEM III) THEORY EXAMINATION 2017-18
DATA STRUCTURES
T ime: 3H0urs Max. Marks: 70
Note: Attempt all Sections. Assume missing data, if any.
w
1. Attempt all questions in brief: 2 x 7 = 14
a. De?ne the term Data Structure. List some linear and non-linear data
structures stating the application area where they will be used.
b. Discuss the concept of "successor" and ?predecessor? in Binary Search
Tree.
0. Convert the following arithmetic infix expression into its equivalent postfix
expression.
Expression: A-B/C+D*E+F
(1. Explain circular queue. What is the condition if circular queue is full?
e. Calculate total number of moves for Tower of Hanoi for n=10 disks.
f. List the different types of representation of graphs.
g. Explain height balanced tree. List general cases to maintain the height.
w
2. Attempt any three of the following: 7 x 3 = 21
a. What do you understand by time space trade off? Explain best, worst and average case
analysis in this respect with an example
b. Use quick sort algorithm to sort 15,22,30,10,15,64,1,3,9,2. Is it a stable sorting
algorithm? ? J ustify.
c. Define spanning tree. Also construct minimum spanning tree using prim?s algorithm for
the given graph.
d. Define tree, binary tree, complete binary tree and full binary tree. Write algorithms or
function to obtain traversals of a binary tree in preorder, postorder and inorder.
e. Construct a B-tree on following sequence of inputs.
10, 20, 30, 40, 50, 60, 70, 80, 90
Assume that the order of the B?tree is 3.
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
(a) What are the various asymptotic notations? Explain Big O notation.
(b) Write an algorithm to insert a node at the end in a Circular linked list.
1|Page

4. Attempt any one part of the following: 7 x 1 = 7
(a)What is a Stack .Write a C program to reverse a string using stack.
(b)Define the recursion. Write a recursive and non recursive program to calculate
the factorial of the given number.
5. Attempt any one part of the following: 7 x 1 = 7
(a) Draw a binary tree with following traversals:
Inorder: BCAEGDHFIJ
Preorder:ABCDEGFHIJ
(b) Consider the following AVL Tree and insert 2, 12, 7and 10 as new node. Show
proper rotation to maintain the tree as AVL.
6. Attempt any one part of the following: 7 x 1 = 7
(a)What is a Threaded Binary Tree? Explain the advantages of using a threaded
binary tree.
(b)Describe Dijkstra?s algorithm for finding shortest path. Describe its working for
the graph given below.
7. Attempt any one part of the following: 7 x 1 = 7
(a)Write short notes on:
i. Hashing Technique
ii. Garbage collection
(b)EXplain the following:
i. Heap Sort
ii. Radix Sort.
ZIPage