Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU)) B-Tech 4th Semester (Fourth Semester) 2017-18 RCS 406 Data Structure And Algorithm Question Paper
Paper Id: 1 1 0 4 3 6 Roll No.
B.TECH
(SEMESTER IV)?THEORY EXAMINATION 2017-18
DATA STRUCTURE & ALGORITHMS
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. 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 is circular queue.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
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.
FirstRanker.com - FirstRanker's Choice
Printed Pages:03 Sub Code: RCS 406
Paper Id: 1 1 0 4 3 6 Roll No.
B.TECH
(SEMESTER IV)?THEORY EXAMINATION 2017-18
DATA STRUCTURE & ALGORITHMS
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. 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 is circular queue.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
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.
SECTION C
3. Attempt any one part of the following: 7 x 1 = 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.
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
4. Attempt any one part of the following: 7 x 1 = 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 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.
5. Attempt any one part of the following: 7 x 1 = 7
a. Write C function for following in Binary Tree
(i) Count the number of total nodes.
(ii) Height of Binary Tree.
??????????????b.?Write Prim?s algorithms and Find the Minimum Spanning tree for following graph
?
?
?
FirstRanker.com - FirstRanker's Choice
Printed Pages:03 Sub Code: RCS 406
Paper Id: 1 1 0 4 3 6 Roll No.
B.TECH
(SEMESTER IV)?THEORY EXAMINATION 2017-18
DATA STRUCTURE & ALGORITHMS
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. 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 is circular queue.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
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.
SECTION C
3. Attempt any one part of the following: 7 x 1 = 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.
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
4. Attempt any one part of the following: 7 x 1 = 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 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.
5. Attempt any one part of the following: 7 x 1 = 7
a. Write C function for following in Binary Tree
(i) Count the number of total nodes.
(ii) Height of Binary Tree.
??????????????b.?Write Prim?s algorithms and Find the Minimum Spanning tree for following graph
?
?
?
6. 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.
7. Attempt any one part of the following: 7 x 1 = 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
2
? 4ac) ) / 2a. Give pre-order,
in-order and post-order traversals of the expression tree so formed
FirstRanker.com - FirstRanker's Choice
This post was last modified on 29 January 2020