DATA STRUCTURES
(Common to CSE and IT)
Time: 3 hours Max. Marks: 70
PART ? A
--- Content provided by FirstRanker.com ---
(Compulsory Question)*****
1 Answer the following: (10 X 02 = 20 Marks)
--- Content provided by FirstRanker.com ---
(a) Consider the function f(n)=?
=
n
i
--- Content provided by FirstRanker.com ---
i1
. Express f(n) in terms of Big-O notation.
(b) Differentiate singly linked list and doubly linked list.
(c) State the applications of stack.
--- Content provided by FirstRanker.com ---
(d) Define priority queue with diagram and give the operations.(e) Define Threaded Binary tree.
(f) Define Topological sort. What is the running time for topological sort?
(g) Write worst case and best case time complexity of the bubble sort algorithm.
(h) State the algorithmic technique used in merge sort. Define it.
--- Content provided by FirstRanker.com ---
(i) What are the two broad classes of collision resolution techniques?(j) Write the time complexity of linear search and binary search techniques.
PART ? B
(Answer all five units, 5 X 10 = 50 Marks)
--- Content provided by FirstRanker.com ---
UNIT ? I
2 (a) Briefly discuss about various asymptotic notations with an example.
(b) Write an algorithm for determining transpose of a matrix using multi dimensional array.
--- Content provided by FirstRanker.com ---
OR3 Explain the following operations in a doubly linked list:
(a) Create an empty list.
(b) Insert the elements 10 and 20 at the front of the list.
(c) Insert the elements 30 at the middle of the list.
--- Content provided by FirstRanker.com ---
(d) Insert the elements 15, 45 at the end of the list.(e) Delete the middle element from the list.
UNIT ? II
--- Content provided by FirstRanker.com ---
4 (a) Construct an empty stack and perform PUSH operation for any five elements. Also perform POPoperation for two elements and show the value on the top of stack.
(b) What do you mean by stack overflow and stack underflow?
OR
5 Write an algorithm to implement insert and delete operations in Queue with array implementation for the
--- Content provided by FirstRanker.com ---
following elements 88, 25, 67, 15, 56 with diagrammatic representations.Contd. in page 2
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Page 1 of 2
--- Content provided by FirstRanker.com ---
R15
FirstRanker.com - FirstRanker's Choice
--- Content provided by FirstRanker.com ---
Code: 15A05201
B.Tech I Year II Semester (R15) Supplementary Examinations November 2017
--- Content provided by FirstRanker.com ---
DATA STRUCTURES(Common to CSE and IT)
Time: 3 hours Max. Marks: 70
PART ? A
(Compulsory Question)
--- Content provided by FirstRanker.com ---
*****
1 Answer the following: (10 X 02 = 20 Marks)
(a) Consider the function f(n)=
--- Content provided by FirstRanker.com ---
?=
n
i
i
--- Content provided by FirstRanker.com ---
1. Express f(n) in terms of Big-O notation.
(b) Differentiate singly linked list and doubly linked list.
(c) State the applications of stack.
(d) Define priority queue with diagram and give the operations.
--- Content provided by FirstRanker.com ---
(e) Define Threaded Binary tree.(f) Define Topological sort. What is the running time for topological sort?
(g) Write worst case and best case time complexity of the bubble sort algorithm.
(h) State the algorithmic technique used in merge sort. Define it.
(i) What are the two broad classes of collision resolution techniques?
--- Content provided by FirstRanker.com ---
(j) Write the time complexity of linear search and binary search techniques.PART ? B
(Answer all five units, 5 X 10 = 50 Marks)
--- Content provided by FirstRanker.com ---
UNIT ? I2 (a) Briefly discuss about various asymptotic notations with an example.
(b) Write an algorithm for determining transpose of a matrix using multi dimensional array.
OR
--- Content provided by FirstRanker.com ---
3 Explain the following operations in a doubly linked list:(a) Create an empty list.
(b) Insert the elements 10 and 20 at the front of the list.
(c) Insert the elements 30 at the middle of the list.
(d) Insert the elements 15, 45 at the end of the list.
--- Content provided by FirstRanker.com ---
(e) Delete the middle element from the list.UNIT ? II
4 (a) Construct an empty stack and perform PUSH operation for any five elements. Also perform POP
--- Content provided by FirstRanker.com ---
operation for two elements and show the value on the top of stack.(b) What do you mean by stack overflow and stack underflow?
OR
5 Write an algorithm to implement insert and delete operations in Queue with array implementation for the
following elements 88, 25, 67, 15, 56 with diagrammatic representations.
--- Content provided by FirstRanker.com ---
Contd. in page 2--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Page 1 of 2
--- Content provided by FirstRanker.com ---
R15
Code: 15A05201
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
UNIT ? III6 (a) Construct Binary Search Tree by inserting the following key elements:
10, 12, 5, 4, 20, 8, 7, 6, 15.
(b) Construct height balanced tree for the following after rotation.
--- Content provided by FirstRanker.com ---
OR
7 Draw the adjacency list representation for the following graph. Also perform topological sorting for the
following graph.
--- Content provided by FirstRanker.com ---
UNIT ? IV
8 Sort the following numbers using selection sort and insertion sort: 45, 25, 10, 2, 9, 85, 102, 1
OR
--- Content provided by FirstRanker.com ---
9 Write an algorithm to sort a set of ?N? numbers using Quick Sort. Trace the algorithm for the following setof numbers: 54, 26, 93, 17, 77, 31, 44, 55 and 20.
UNIT ? V
--- Content provided by FirstRanker.com ---
10 (a) Compare binary search and linear search techniques.(b) Find the number 77 from the following set of numbers using binary search:
6, 12, 17, 23, 38, 45, 77, 84, 90.
OR
11 Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x(mod 10), show
--- Content provided by FirstRanker.com ---
the resulting: (i) Open hash table using linear probing. (ii) Open hash table using quadratic probing.(iii) Open hash table using double hashing with second hash function h2(x) =7-(x mod 7).
*****
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Page 2 of 2R15
2 3
4 5
1
--- Content provided by FirstRanker.com ---
FirstRanker.com - FirstRanker's Choice