Code No.
: 20CSC08
CHAITANYA BHARATHI INSTITUTE OF TECHNOLOGY (Autonomous)
B.E. III Sem (Main) Examination February/March 2022
Data Structures
(Common to CSE, CSE - AI&ML, CSE - IoT&CS Including BCT)
Time: 3 Hours Max Marks: 60
Note: Answer ALL questions from Part-A & Part –B (Internal Choice) at one place in the
same order
Part - A
(5Q X 3M = 15 Marks)
M CO BT
1 Write about Asymptotic notations. (3) 2 1
2 Differentiate Arrays and Linked Lists. (3) 3 4
3 Explain Priority Queues. (3) 4 1
4 What are the properties of Binary Trees? (3) 5 1
5 Explain Quadratic Probing. (3) 5 1
Part – B
(5Q X 9M = 45 Marks)
M CO BT
6 (a) Demonstrate different operations that can be performed on Data (5) 1 2
Structures.
(b) Show that 400n3 + 20n2 = O(n3). (4) 2 3
(OR)
7 (a) Sort the numbers given below using Radix Sort (5) 1 3
345, 654, 924, 123, 567, 472, 555, 808, 911.
(b) Write an algorithm to implement Quick Sort. (4) 1 1
8 (a) Describe Single Linked List and explain the operations that can be (5) 4 1
performed on Single Linked Lists.
(b) Justify why Doubly Linked List is more useful than a Singly Linked (4) 4 4
List.
(OR)
9 Write a program to create a Circular Linked List and perform insertion (9) 4 3
and deletion operations.
10 (a) What is a Queue? Write an algorithm to insert and delete an element in (5) 4 1
a Queue.
(b) List out the applications of Stack. (4) 6 4
(OR)
11 Write a program to implement Stack using Linked List with (9) 4 3
appropriate Abstract Data type.
Page 1 of 2
Code No.: 20CSC08
12 (a) Define the following terms. (5) 5 1
i. Leaf node
ii. Path
iii. Degree
iv. Height of a tree
v. Sibling
(b) Construct the Binary Tree for the given traversals (4) 5 3
In-order traversal: D B H E I A F J C G
Post-order traversal: D H I E B J F G C A
(OR)
13 (a) Write an algorithm to Search for a value and Insert a value in a Binary (5) 5 1
Search Tree.
(b) Construct an AVL tree by inserting the following elements in given (4) 5 3
order
63, 9, 19, 27, 18, 108, 99, 81
14 Illustrate Depth First Search algorithm with an example. (9) 5 2
(OR)
15 (a) Describe various Hash functions. (5) 5 1
(b) Explain Rabin- Karp String Matching algorithm. (4) 5 1
******
Page 2 of 2
