Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU)) B-Tech 4th Semester (Fourth Semester) 2018-19 RCS405 Data Structures Question Paper
| 22-May-2019 09:12:32 | 45.115.62.2
FirstRanker.com | 22-May-2019 09:12:32 | 45.115.62.2
RCS405
Page 1 of 2
Printed Pages:2 Sub Code: RCS 405
Paper Id: 110258 Roll No.
B TECH
(SEM IV) THEORY EXAMINATION 2018-19
DATA STRUCTURES
Time: 3 Hours Total Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. What is asymptotic notation? Explain Big Oh notation?
b. Given a 2D array A [-100:100,-5:50]. Find the address of element A [99, 49]
considering base address 10 and each element requires 4 bytes for storage. Follow
row major order?
c. If the in order traversal of a binary tree is D, J, G, B, A, E, H, C, F, I and its pre order
traversal is A, B, D, G, J, C, E, H, F, I Determine the binary tree?
d. Evaluate postfix expression 8 2 ? 4 + 5 6 7 - + ?
e. Explain collision resolution strategies used in hashing?
f. Write a recursive solution to solve Tower of Hanoi problem.
g. Define complete binary tree and full binary tree.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Consider the following infix expression and convert it into postfix using stack
A + (B * C ? (D/E-F) * G) * H
b. What is doubly linked list? Write an algorithm to insert a node at begin in single
linked list.
c. Construct a Huffman tree for given characters A, B, C, D, E, F, G, H having frequencies
22, 5, 11, 19, 2, 11, 25, 5 respectively. What will be the code of HEAD in binary?
d. Find the shortest path from S to all remaining vertices of graph using Dijikstra
Algorithm
e. Use Heap sort algorithm to sort the following sequence {8, 5, 45, 24, 36, 11, 43, and
21}.
FirstRanker.com - FirstRanker's Choice
FirstRanker.com
| 22-May-2019 09:12:32 | 45.115.62.2
FirstRanker.com | 22-May-2019 09:12:32 | 45.115.62.2
RCS405
Page 1 of 2
Printed Pages:2 Sub Code: RCS 405
Paper Id: 110258 Roll No.
B TECH
(SEM IV) THEORY EXAMINATION 2018-19
DATA STRUCTURES
Time: 3 Hours Total Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. What is asymptotic notation? Explain Big Oh notation?
b. Given a 2D array A [-100:100,-5:50]. Find the address of element A [99, 49]
considering base address 10 and each element requires 4 bytes for storage. Follow
row major order?
c. If the in order traversal of a binary tree is D, J, G, B, A, E, H, C, F, I and its pre order
traversal is A, B, D, G, J, C, E, H, F, I Determine the binary tree?
d. Evaluate postfix expression 8 2 ? 4 + 5 6 7 - + ?
e. Explain collision resolution strategies used in hashing?
f. Write a recursive solution to solve Tower of Hanoi problem.
g. Define complete binary tree and full binary tree.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Consider the following infix expression and convert it into postfix using stack
A + (B * C ? (D/E-F) * G) * H
b. What is doubly linked list? Write an algorithm to insert a node at begin in single
linked list.
c. Construct a Huffman tree for given characters A, B, C, D, E, F, G, H having frequencies
22, 5, 11, 19, 2, 11, 25, 5 respectively. What will be the code of HEAD in binary?
d. Find the shortest path from S to all remaining vertices of graph using Dijikstra
Algorithm
e. Use Heap sort algorithm to sort the following sequence {8, 5, 45, 24, 36, 11, 43, and
21}.
FirstRanker.com
| 22-May-2019 09:12:32 | 45.115.62.2
FirstRanker.com | 22-May-2019 09:12:32 | 45.115.62.2
RCS405
Page 2 of 2
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
a. What do you understand by time space trade off? How to analysis the time complexity
of the algorithm in three different cases.
b. What is circular linked list? Write an algorithm to delete a node from begin in single
linked list.
4. Attempt any one part of the following: 7 x 1 = 7
a. What do you mean by priority queue? Explain the types to maintain the priority queue
in memory?
b. Write an algorithm for conversion of an infix expression into prefix expression using
stack?
5. Attempt any one part of the following: 7 x 1 = 7
a. Draw a binary tree with following traversals:
Preorder: A B C D E F G H I J K L
Postorder: C F E G D B K J L I H A
b. What is threaded binary tree? Explain two-way in order threading with suitable
example?
6. Attempt any one part of the following: 7 x 1 = 7
a. Implement Floyd Warshall algorithm on the following graph.
b. What is transitive closure? What are the steps to obtain the transitive closure of a
Graph?
7. Attempt any one part of the following: 7 x 1 = 7
a. Describe an AVL tree. Construct an AVL tree by inserting the following elements
in the order of their occurrence {60, 2, 15, 20, 12, 115, 90 and 88}.
b. Show the results of inserting the keys F, S, Q, K ,C, L, H, T, V, W, M, R, N, P, A, B
in order into a empty B-Tree of order 5.
FirstRanker.com - FirstRanker's Choice
This post was last modified on 29 January 2020