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
- a. What do you mean by Abstract Data Type of a data structure?
- b. Differentiate internal sorting and external sorting also enlists the name of two sorting techniques of each.
- c. Write a C program to multiply two integer number using recursion.
- d. What do you mean by priority queue?
- e. Define Threaded binary tree with advantage over binary tree.
- f. Explain Transitive Closure.
- g. Write the function to insert an element in circular queue.
--- Content provided by FirstRanker.com ---
SECTION B
Attempt any three of the following: 7 x 3 = 21
--- Content provided by FirstRanker.com ---
- 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.
- 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? - 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.
- d. Translate the infix string (a+b^c^d)*(e+f/d) to reverse polish notation using stack.
- 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.
--- Content provided by FirstRanker.com ---
SECTION C
Attempt any one part of the following: 7x1=7
- 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
- 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.
- 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
- Find the Minimum Spanning tree for following graph
[Graph Description or Image Placeholder]
--- Content provided by FirstRanker.com ---
- 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 ---
- 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 + v(b² - 4ac)) / 2a. Give pre-order, in-order and post-order traversals of the expression tree so formed
--- Content provided by FirstRanker.com ---
This download link is referred from the post: AKTU B-Tech Last 10 Years 2010-2020 Previous Question Papers || Dr. A.P.J. Abdul Kalam Technical University