Download AKTU B-Tech 4th Sem 2018-19 RCS 406 Data Structure And Algorithm Question Paper

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14

1. Calculate total number of moves for Tower of Hanoi for n=15 disks.
2. Explain AVL. List general cases to maintain the height factor.
3. Explain priority queue. What is the condition if queue is full?
4. What do you mean by breadth first search (BFS)?

--- Content provided by​ FirstRanker.com ---

5. State the rules to be followed during infix to postfix conversions.
6. Define data type and what are the types of data type?
7. What is the difference between complete binary tree and full binary tree?

SECTION B

2. Attempt any three of the following: 7x3 = 21

1. 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.

--- Content provided by FirstRanker.com ---

2. Define an algorithm. Write down the parameters to judge the efficiency of any algorithm.
3. Write an algorithm to insert an element in a Queue. Define deque. Discuss input and output restricted deque with suitable diagram.
4. How to find Minimum Spanning Tree? Explain the Krushkal's Algorithm with example.
5. Convert given infix expression to postfix expression: A^B-C^D*E^F/G/H-J+I

SECTION C

3. Attempt any one part of the following: 7x1=7

--- Content provided by FirstRanker.com ---

1. 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
2. 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: 7x1=7

1. 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.
2. Consider the any AVL tree and insert 12, 22, 17 and 20 as new node. Show proper rotation to maintain the tree as AVL.

--- Content provided by‍ FirstRanker.com ---

5. Attempt any one part of the following: 7x1=7

1. What is a Circular Queue? Write an Algorithm to insert an item and delete an item from the circular queue.
2. How can we represent a Double Linked list? explain with example.

6. Attempt any one part of the following: 7x1=7

1. Describe Dijkstra's algorithm for finding shortest path. Describe its working for the graph given below.
   

   --- Content provided by​ FirstRanker.com ---

   A 100 10 B E 30 10 60 50 C 20 D
2. Write down the algorithm for DFS and BFS explain it with example.

7. Attempt any one part of the following: 7x1=7

1. 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
2. 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.

--- Content provided by‍ FirstRanker.com ---