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 RCS 406 Data Structure And Algorithm Question Paper
| 16-May-2019 08:59:26 | 45.115.62.2
FirstRanker.com | 16-May-2019 08:59:26 | 45.115.62.2
Printed Pages: 02 Sub Code: RCS-406
Paper Id:
131286
Roll No.
B.TECH
(SEM IV) THEORY EXAMINATION 2018-19
DATA STRUCTURE AND ALGORITHM
Time: 3 Hours Total Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper specific instruction.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. Calculate total number of moves for Tower of Hanoi for n=15 disks.
b. Explain AVL. List general cases to maintain the height factor.
c. Explain priority queue. What is the condition if queue is full?
d. What do you mean by breadth first search (BFS)?
e. State the rules to be followed during infix to postfix conversions.
f. Define data type and what are the types of data type?
g. What is the difference between complete binary tree and full binary tree?
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Write an algorithm for insertion sort. Trace your algorithm on the following data
to sort the list: 77, 33, 44, 11, 88, 22, 66, 55
b. Define an algorithm. Write down the parameters to judge the efficiency of any
algorithm.
c. Write an algorithm to insert an element in a Queue. Define deque. Discuss input
and output restricted deque with suitable diagram.
d. How to find Minimum Spanning Tree? Explain the Krushkal?s Algorithm with
example.
e. Convert given infix expression to postfix expression.
A^B-C^D*E$F+G/H-I+J
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
a. What is heap? Differentiate between max-heap and min-heap. To build a heap H
of the following using Min-heap : 60,33,50,22,55,40,11,22,65,30
b. What is binary search tree? Suppose the following 10 members are inserted in
order into an empty binary search tree T: 50,48,35,44,80,70,10,55,11,85. Draw the
tree.
4. Attempt any one part of the following: 7 x 1 = 7
a. What is Tower of Hanoi problem. Explain solutions of Tower of Hanoi problem
using proper problem using proper tree representation where number of disks n= 3
and towers are A B C.
b. Consider the any AVL tree and insert 12, 22, 17 and 20 as new node. Show proper
rotation to maintain the tree as AVL.
FirstRanker.com - FirstRanker's Choice
FirstRanker.com
| 16-May-2019 08:59:26 | 45.115.62.2
FirstRanker.com | 16-May-2019 08:59:26 | 45.115.62.2
Printed Pages: 02 Sub Code: RCS-406
Paper Id:
131286
Roll No.
B.TECH
(SEM IV) THEORY EXAMINATION 2018-19
DATA STRUCTURE AND ALGORITHM
Time: 3 Hours Total Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper specific instruction.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. Calculate total number of moves for Tower of Hanoi for n=15 disks.
b. Explain AVL. List general cases to maintain the height factor.
c. Explain priority queue. What is the condition if queue is full?
d. What do you mean by breadth first search (BFS)?
e. State the rules to be followed during infix to postfix conversions.
f. Define data type and what are the types of data type?
g. What is the difference between complete binary tree and full binary tree?
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Write an algorithm for insertion sort. Trace your algorithm on the following data
to sort the list: 77, 33, 44, 11, 88, 22, 66, 55
b. Define an algorithm. Write down the parameters to judge the efficiency of any
algorithm.
c. Write an algorithm to insert an element in a Queue. Define deque. Discuss input
and output restricted deque with suitable diagram.
d. How to find Minimum Spanning Tree? Explain the Krushkal?s Algorithm with
example.
e. Convert given infix expression to postfix expression.
A^B-C^D*E$F+G/H-I+J
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
a. What is heap? Differentiate between max-heap and min-heap. To build a heap H
of the following using Min-heap : 60,33,50,22,55,40,11,22,65,30
b. What is binary search tree? Suppose the following 10 members are inserted in
order into an empty binary search tree T: 50,48,35,44,80,70,10,55,11,85. Draw the
tree.
4. Attempt any one part of the following: 7 x 1 = 7
a. What is Tower of Hanoi problem. Explain solutions of Tower of Hanoi problem
using proper problem using proper tree representation where number of disks n= 3
and towers are A B C.
b. Consider the any AVL tree and insert 12, 22, 17 and 20 as new node. Show proper
rotation to maintain the tree as AVL.
FirstRanker.com
| 16-May-2019 08:59:26 | 45.115.62.2
FirstRanker.com | 16-May-2019 08:59:26 | 45.115.62.2
Printed Pages: 02 Sub Code: RCS-406
5. Attempt any one part of the following: 7 x 1 = 7
a. What is a Circular Queue? Write an Algorithm to insert an item and delete an item
from the circular queue.
b. How can we represent a Double Linked list? explain with example.
6. Attempt any one part of the following: 7 x 1 = 7
a. Describe Dijkstra?s algorithm for finding shortest path. Describe its working for
the graph given below.
b. Write down the algorithm for DFS and BFS explain it with example.
7. Attempt any one part of the following: 7 x 1 = 7
a. Each element of an array A[20][50] requires 4 bytes of storage. Base is 2000.
Determine the location of A[10][10] when the array is stored as :
(i) Row Major
(ii) Column Major
b. Consider the following keys are to be placed in the hash table.
11, 31, 32, 49, 55, 27, 60, 50, 77, 25, here size of tables is 15. Solve with the help
of open addressing and chaining method.
FirstRanker.com - FirstRanker's Choice
This post was last modified on 29 January 2020