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

Firstranker's choice

Printed Pages: 03

Paper Id: 110436

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

Sub Code: RCS 406

Roll No.

B.TECH

(SEMESTER IV) THEORY EXAMINATION 2017-18

DATA STRUCTURE & ALGORITHMS

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

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

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

Attempt all questions in brief. 2 x 7 = 14

1. a. What do you mean by Abstract Data Type of a data structure?
2. b. Differentiate internal sorting and external sorting also enlists the name of two sorting techniques of each.
3. c. Write a C program to multiply two integer number using recursion.
4. d. What do you mean by priority queue?

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

5. e. Define Threaded binary tree with advantage over binary tree.
6. f. Explain Transitive Closure.
7. g. Write the function to insert an element in circular queue.

SECTION B

Attempt any three of the following: 7 x 3 = 21

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

1. a. Consider the two dimensional lower triangular matrix(LTM) of order N. Obtain the formula for address calculation in the address of row major and column major order for location LTM[j][k], if base address is BA and space occupied by each element is w byte.
2. b. In the Towers of Hanoi puzzle, we are given a platform with three tower, a,b, and c, sticking out of it. On tower a is a stack of n disks, each larger than the next, so that the smallest is on the top and the largest is on the bottom. The puzzle is to move all the disks from tower a to tower c, moving one disk at a time, so that we never place a larger disk on top of a smaller one.
   (i) Describe a recursive algorithm for solving the Towers of Hanoi puzzle for arbitrary n disk.
   (ii) How many function calls are there for n disks?
3. c. Define stack with suitable example. Write a program to reverse a string using Stack. Choose a C data structure for such a stack and design push and pop functions for it.

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

4. d. Translate the infix string (a+b^c^d)*(e+f/d) to reverse polish notation using stack.
5. e. Explain any three commonly used hash function with the suitable example? A hash function H defined as H(key) =key%7, with linear probing is used to insert the key 37,38,72,48,98,11,56 into a table indexed from 0 to 6. what will be the location of key 11. Justify your answer, also count the total number of collision in this probing.

SECTION C

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

1. a. What are the advantages of linked list over arrays? Implement Doubly Circular linked list and insert an element at given position in this linked list.
   

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

   b. Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x, +, -. Then find the postfix expression corresponding to the infix Expression a + b×c-d^e^f

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

1. a. Draw the Huffman tree for the following symbols (each of 7 bits) whose frequency Of occurrence of a message is stated along with the symbols below:
   M1: 0.45
   M2:0.02 M3: 0.24
   

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

   M4: 0.18 M5: 0.11
   decode the following message 10110011011111001100101111101101100. and what is the average number of bits required per message.
   b. Write algorithm for Floyd warshall algorithm also explains with a suitable example.

1. a. Write C function for following in Binary Tree
   (i) Count the number of total nodes.
   

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

   (ii) Height of Binary Tree.
   b. Write Prim's algorithms and

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

1. Find the Minimum Spanning tree for following graph
   [Graph Description or Image Placeholder]

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

1. Attempt any one part of the following: 7 x 1 = 7
   a. Construct a binary tree for the following preorder and inorder traversals. Explain with a neat diagram:
   Preorder: ABDIEHJCFKLGM
   Inorder: DIBHJEAFLKCGM
   b. Explain Binary Search algorithm and it time complexity? Implement the binary search in C language.

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

1. Attempt any one part of the following: 7 x1=7
   a. Discuss what type of data structure used in DFS. Write an algorithm for DFS, Traverse the given graph starting from node A using DFS
   b. Construct an expression tree for the expression (-b + √(b² - 4ac)) / 2a. Give pre-order, in-order and post-order traversals of the expression tree so formed

FirstRanker.com

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