JNTU Kakinada B-Tech 1-2 R161213 DATA STRUCTURES R16 May 2018 Question Paper

JNTU Kakinada (JNTUK) B-Tech First Year Second Semester (1-2) DATA STRUCTURES Common to to ECE, EIE, E Com E R16 Regulation May 2018 Question Paper

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the properties of Abstract Data Type? (2M)
b) What is the difference between a queue and a stack? (2M)
c) What are the disadvantages of representing a stack or queue by linked list? (2M)
d) What is the use of threaded binary tree? (2M)
e) What is Sollin?s algorithm? (2M)
f) What is the complexity of insertion sort? (2M)
g) P: 12/7+3-4*2*1+5. Transform P into infix expression. (2M)
PART -B
2. a) What is sparse matrix? Discuss its implementation using arrays. (7M)
b) Explain matrix multiplication using arrays with an example. (7M)
3. a) Define stack ADT. Explain basic operations of a stack ADT. (7M)
b) Explain an algorithm for evaluating postfix expression with suitable example. (7M)
4. Describe how a polynomial is represented using singly linked lists. Write an
algorithm to add two polynomials using linked list. (14M)
5. a) Explain the properties of a binary search tree in detail. (7M)
b) Develop a binary search tree resulting after inserting the following integer keys
49, 27, 12, 11, 33, 77, 26, 56, 23, 6. (i) Check whether the tree is almost complete
or not? (ii) Determine the height of the tree (iii) Write post order and preorder
traversals. (7M)
6. a) Explain how Prim?s algorithm is used for finding the minimum spanning tree of a
graph. Find a minimum cost spanning tree of the following graph using Prims
algorithm

(14M)
7. Define heap. Explain heap sort algorithm. Apply heap sort algorithm to sort
following list of elements in ascending order: 9, 3, 5, 27, 4, 67, 18, 31, 13, 20, 39,
21. Clearly show the sorting process at each step. (14M)

1 of 1
SET – 1
R16
A
E
B
D
C
3
2
3
5
4
4

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the properties of Abstract Data Type? (2M)
b) What is the difference between a queue and a stack? (2M)
c) What are the disadvantages of representing a stack or queue by linked list? (2M)
d) What is the use of threaded binary tree? (2M)
e) What is Sollin?s algorithm? (2M)
f) What is the complexity of insertion sort? (2M)
g) P: 12/7+3-4*2*1+5. Transform P into infix expression. (2M)
PART -B
2. a) What is sparse matrix? Discuss its implementation using arrays. (7M)
b) Explain matrix multiplication using arrays with an example. (7M)
3. a) Define stack ADT. Explain basic operations of a stack ADT. (7M)
b) Explain an algorithm for evaluating postfix expression with suitable example. (7M)
4. Describe how a polynomial is represented using singly linked lists. Write an
algorithm to add two polynomials using linked list. (14M)
5. a) Explain the properties of a binary search tree in detail. (7M)
b) Develop a binary search tree resulting after inserting the following integer keys
49, 27, 12, 11, 33, 77, 26, 56, 23, 6. (i) Check whether the tree is almost complete
or not? (ii) Determine the height of the tree (iii) Write post order and preorder
traversals. (7M)
6. a) Explain how Prim?s algorithm is used for finding the minimum spanning tree of a
graph. Find a minimum cost spanning tree of the following graph using Prims
algorithm

(14M)
7. Define heap. Explain heap sort algorithm. Apply heap sort algorithm to sort
following list of elements in ascending order: 9, 3, 5, 27, 4, 67, 18, 31, 13, 20, 39,
21. Clearly show the sorting process at each step. (14M)

1 of 1
SET – 1
R16
A
E
B
D
C
3
2
3
5
4
4

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the limitations of arrays? How can it be overcome? (2M)
b) Transform the infix expression into its equivalent post fix expression: (A-B)*(D/E). (2M)
c) What are the advantages of using a linked list rather than array? (2M)
d) What are the applications of priority queues? (2M)
e) Define DFS and BFS. What is the difference between them? (2M)
f) What is merge sort? (2M)
g) What is the difference between queue and priority queue? (2M)
PART -B
2. a) Write ADT for array implementation of polynomial addition. (7M)
b) Explain transposing of a matrix using with an example. Also write a function for
its implementation. (7M)
3. a) Convert given Infix expression: (a + b * c ^ d) * (e + f / g) to Postfix expression
using Stack and show the details of Stack at each step of conversion. (Note: ^ indicates exponent operator) (7M)
b) Explain the operations of queue with suitable algorithms and examples. (7M)
4. a) Explain the procedure to insert and delete element from sparse matrix. (7M)
b) Write an algorithm for representing the polynomial 6x
6
+ 4x
3
? 2x + 10 using
linked lists. (7M)
5. a) What are the different tree traversals? Explain with example. (7M)
b) Write an iterative function to search for a key value in Binary search tree. (7M)
6. a) Explain the Kruskal?s algorithm to find the minimum cost spanning tree with an
example. (7M)
b) What is Transitive Closure? Explain in detail. (7M)
7. Describe insertion sort algorithm and trace the steps of insertion sort for sorting
the list- 12, 19, 33, 26, 29, 35, 22, 37. Find the total number of comparisons made. (14M)

1 of 1
SET – 2
R16

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the properties of Abstract Data Type? (2M)
b) What is the difference between a queue and a stack? (2M)
c) What are the disadvantages of representing a stack or queue by linked list? (2M)
d) What is the use of threaded binary tree? (2M)
e) What is Sollin?s algorithm? (2M)
f) What is the complexity of insertion sort? (2M)
g) P: 12/7+3-4*2*1+5. Transform P into infix expression. (2M)
PART -B
2. a) What is sparse matrix? Discuss its implementation using arrays. (7M)
b) Explain matrix multiplication using arrays with an example. (7M)
3. a) Define stack ADT. Explain basic operations of a stack ADT. (7M)
b) Explain an algorithm for evaluating postfix expression with suitable example. (7M)
4. Describe how a polynomial is represented using singly linked lists. Write an
algorithm to add two polynomials using linked list. (14M)
5. a) Explain the properties of a binary search tree in detail. (7M)
b) Develop a binary search tree resulting after inserting the following integer keys
49, 27, 12, 11, 33, 77, 26, 56, 23, 6. (i) Check whether the tree is almost complete
or not? (ii) Determine the height of the tree (iii) Write post order and preorder
traversals. (7M)
6. a) Explain how Prim?s algorithm is used for finding the minimum spanning tree of a
graph. Find a minimum cost spanning tree of the following graph using Prims
algorithm

(14M)
7. Define heap. Explain heap sort algorithm. Apply heap sort algorithm to sort
following list of elements in ascending order: 9, 3, 5, 27, 4, 67, 18, 31, 13, 20, 39,
21. Clearly show the sorting process at each step. (14M)

1 of 1
SET – 1
R16
A
E
B
D
C
3
2
3
5
4
4

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the limitations of arrays? How can it be overcome? (2M)
b) Transform the infix expression into its equivalent post fix expression: (A-B)*(D/E). (2M)
c) What are the advantages of using a linked list rather than array? (2M)
d) What are the applications of priority queues? (2M)
e) Define DFS and BFS. What is the difference between them? (2M)
f) What is merge sort? (2M)
g) What is the difference between queue and priority queue? (2M)
PART -B
2. a) Write ADT for array implementation of polynomial addition. (7M)
b) Explain transposing of a matrix using with an example. Also write a function for
its implementation. (7M)
3. a) Convert given Infix expression: (a + b * c ^ d) * (e + f / g) to Postfix expression
using Stack and show the details of Stack at each step of conversion. (Note: ^ indicates exponent operator) (7M)
b) Explain the operations of queue with suitable algorithms and examples. (7M)
4. a) Explain the procedure to insert and delete element from sparse matrix. (7M)
b) Write an algorithm for representing the polynomial 6x
6
+ 4x
3
? 2x + 10 using
linked lists. (7M)
5. a) What are the different tree traversals? Explain with example. (7M)
b) Write an iterative function to search for a key value in Binary search tree. (7M)
6. a) Explain the Kruskal?s algorithm to find the minimum cost spanning tree with an
example. (7M)
b) What is Transitive Closure? Explain in detail. (7M)
7. Describe insertion sort algorithm and trace the steps of insertion sort for sorting
the list- 12, 19, 33, 26, 29, 35, 22, 37. Find the total number of comparisons made. (14M)

1 of 1
SET – 2
R16

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) Give Polynomial Abstract Data Type? (2M)
b) Transform the infix expression into its equivalent Pre-fix expression: (A+B^D)/(E*F)+G. (2M)
c) What is a doubly linked list? (2M)
d) Define binary search tree. (2M)
e) What is Kruskal?s algorithm? (2M)
f) Write the steps in heap sort. (2M)
g) What are the error conditions that could occur in stack implementation? How
could they be rectified? (2M)
PART -B
2. a) Explain how to implement polynomial ADT using array. (7M)
b) Discuss about the representation of array as an ADT along with their advantages
and disadvantages. (7M)
3. a) Write an algorithm for converting infix expression to postfix expression with an
example. (7M)
b) Discuss the algorithms for push and pop operations on a stack. (7M)
4. a) Write an algorithm to insert new node at the beginning, at middle position and at
the end of a singly linked list. (7M)
b) Explain following applications of a linked list for (i) representation of a
polynomial expression (ii) sparse matrix manipulation. (7M)
5. a) Explain in detail about creation of a binary search tree and insertion of a node into
a binary search tree with suitable example. (7M)
b) Define priority queue. Discuss briefly about the heap representation of priority
queue. (7M)
6. a) What is minimum cost spanning Tree? How many Minimum spanning trees can be
formed from a given graph? Explain the process of finding the minimum spanning
tree with suitable example. (7M)
b) Write Sollin?s algorithm to find the shortest path and explain. (7M)
7. a) Explain merge sort algorithm with a suitable example. (7M)
b) ?Selecting the pivot element plays vital role in Quick sort? support this statement
with proper explanation. Explain various choices available for selecting the pivot. (7M)
1 of 1
SET – 3
R16

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the properties of Abstract Data Type? (2M)
b) What is the difference between a queue and a stack? (2M)
c) What are the disadvantages of representing a stack or queue by linked list? (2M)
d) What is the use of threaded binary tree? (2M)
e) What is Sollin?s algorithm? (2M)
f) What is the complexity of insertion sort? (2M)
g) P: 12/7+3-4*2*1+5. Transform P into infix expression. (2M)
PART -B
2. a) What is sparse matrix? Discuss its implementation using arrays. (7M)
b) Explain matrix multiplication using arrays with an example. (7M)
3. a) Define stack ADT. Explain basic operations of a stack ADT. (7M)
b) Explain an algorithm for evaluating postfix expression with suitable example. (7M)
4. Describe how a polynomial is represented using singly linked lists. Write an
algorithm to add two polynomials using linked list. (14M)
5. a) Explain the properties of a binary search tree in detail. (7M)
b) Develop a binary search tree resulting after inserting the following integer keys
49, 27, 12, 11, 33, 77, 26, 56, 23, 6. (i) Check whether the tree is almost complete
or not? (ii) Determine the height of the tree (iii) Write post order and preorder
traversals. (7M)
6. a) Explain how Prim?s algorithm is used for finding the minimum spanning tree of a
graph. Find a minimum cost spanning tree of the following graph using Prims
algorithm

(14M)
7. Define heap. Explain heap sort algorithm. Apply heap sort algorithm to sort
following list of elements in ascending order: 9, 3, 5, 27, 4, 67, 18, 31, 13, 20, 39,
21. Clearly show the sorting process at each step. (14M)

1 of 1
SET – 1
R16
A
E
B
D
C
3
2
3
5
4
4

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the limitations of arrays? How can it be overcome? (2M)
b) Transform the infix expression into its equivalent post fix expression: (A-B)*(D/E). (2M)
c) What are the advantages of using a linked list rather than array? (2M)
d) What are the applications of priority queues? (2M)
e) Define DFS and BFS. What is the difference between them? (2M)
f) What is merge sort? (2M)
g) What is the difference between queue and priority queue? (2M)
PART -B
2. a) Write ADT for array implementation of polynomial addition. (7M)
b) Explain transposing of a matrix using with an example. Also write a function for
its implementation. (7M)
3. a) Convert given Infix expression: (a + b * c ^ d) * (e + f / g) to Postfix expression
using Stack and show the details of Stack at each step of conversion. (Note: ^ indicates exponent operator) (7M)
b) Explain the operations of queue with suitable algorithms and examples. (7M)
4. a) Explain the procedure to insert and delete element from sparse matrix. (7M)
b) Write an algorithm for representing the polynomial 6x
6
+ 4x
3
? 2x + 10 using
linked lists. (7M)
5. a) What are the different tree traversals? Explain with example. (7M)
b) Write an iterative function to search for a key value in Binary search tree. (7M)
6. a) Explain the Kruskal?s algorithm to find the minimum cost spanning tree with an
example. (7M)
b) What is Transitive Closure? Explain in detail. (7M)
7. Describe insertion sort algorithm and trace the steps of insertion sort for sorting
the list- 12, 19, 33, 26, 29, 35, 22, 37. Find the total number of comparisons made. (14M)

1 of 1
SET – 2
R16

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) Give Polynomial Abstract Data Type? (2M)
b) Transform the infix expression into its equivalent Pre-fix expression: (A+B^D)/(E*F)+G. (2M)
c) What is a doubly linked list? (2M)
d) Define binary search tree. (2M)
e) What is Kruskal?s algorithm? (2M)
f) Write the steps in heap sort. (2M)
g) What are the error conditions that could occur in stack implementation? How
could they be rectified? (2M)
PART -B
2. a) Explain how to implement polynomial ADT using array. (7M)
b) Discuss about the representation of array as an ADT along with their advantages
and disadvantages. (7M)
3. a) Write an algorithm for converting infix expression to postfix expression with an
example. (7M)
b) Discuss the algorithms for push and pop operations on a stack. (7M)
4. a) Write an algorithm to insert new node at the beginning, at middle position and at
the end of a singly linked list. (7M)
b) Explain following applications of a linked list for (i) representation of a
polynomial expression (ii) sparse matrix manipulation. (7M)
5. a) Explain in detail about creation of a binary search tree and insertion of a node into
a binary search tree with suitable example. (7M)
b) Define priority queue. Discuss briefly about the heap representation of priority
queue. (7M)
6. a) What is minimum cost spanning Tree? How many Minimum spanning trees can be
formed from a given graph? Explain the process of finding the minimum spanning
tree with suitable example. (7M)
b) Write Sollin?s algorithm to find the shortest path and explain. (7M)
7. a) Explain merge sort algorithm with a suitable example. (7M)
b) ?Selecting the pivot element plays vital role in Quick sort? support this statement
with proper explanation. Explain various choices available for selecting the pivot. (7M)
1 of 1
SET – 3
R16

Code No: R161213
I B. Tech II Semester Regular/Supplementary Examinations, April/May- 2018
DATA STRUCTURES (Com. to ECE, EIE, E Com E)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is Compulsory
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a) What are the properties of sparse matrix? (2M)
b) Transform the expression into its equivalent post fix expression:
A*(B+D)/E-F*(G+H/K). (2M)
c) What are the advantages of linked list? (2M)
d) Write steps for inorder, preorder and postorder traversals. (2M)
e) Define all-pair?s shortest path problem. (2M)
f) What is the complexity of quick sort algorithm? (2M)
g) Why queue is called FIFO list and stack is called LIFO list? (2M)
PART -B
2. a) Explain polynomial addition using arrays with an example. (7M)
b) Explain representation of arrays along with their advantages and disadvantages.
(7M)
3. a) Write an algorithm for converting infix expression to prefix expression. (7M)
b) Give the structure of Queue ADT. Explain the operations in it.
(7M)
4. a) Write an algorithm to delete an element anywhere from doubly linked list. (7M)
b) Discuss sparse matrix representation using linked list.
(7M)
5. a) Explain, in detail, deletion of a node from a binary tree with one suitable example. (7M)
b) What is a threaded binary tree? Explain with an example.
(7M)
6. Explain Depth First Search and Breadth First Search algorithms in detail.
(14M)
7. a) Explain about iterative merge sort and recursive merge sort. (7M)
b) Give an algorithm for quick sort and explain its time complexity. Trace the
algorithm for the following data: 65 70 75 80 85 60 55 50 45 (7M)

1 of 1
SET – 4
R16