R23
Code No:
I B. TECH II SEMESTER REGULAR EXAMINATIONS, JULY-2024
DATA STRUCTURES
(COMMON TO CSE, IT & ALLIED BRANCHES)
Time: 3 Hours Max. Marks:
70
______________________________________________________________________________
Note: 1. The question paper consists of two parts (Part-A and Part-B)
2. All the questions in Part-A are Compulsory
3. Answer ONE Question from Each Unit in Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART – A (20 Marks)
1. a) Define Time and Space Complexity. [2M]
b) Define ADT. (Abstract Data Type) [2M]
c) List advantages of linked list over arrays. [2M]
d) Discuss operations performed with polynomials. [2M]
e) Write the differences between stack and queue. [2M]
f) What are the disadvantages of representing a stack using [2M]
Arrays
g) Write the applications of queues. [2M]
h) Define Double Ended Queue (deque). [2M]
i) Define Sibling. [2M]
j) Write about hash functions. [2M]
PART – B (50 Marks)
UNIT-I
2. a) Apply the insertion sort for given numbers: 34, 8, 14, 61, 4, [5 M]
53, 81, 47.
b) Illustrate the step-by-step procedure for sorting the following [5 M]
unordered list of elements 52, 37, 63, 14, 17, 8, 6, 25 using
Quick sort technique.
(OR)
3. a) Define Algorithm. Explain time complexity and space [5 M]
complexity of an algorithm.
b) Discuss merge sort algorithm with a suitable example. [5 M]
UNIT-II
4. a) Explain the steps to implement the following operations of [6M]
singly-linked list without head node using illustrative
examples?
(i) removing at front
(ii) removing at end
(iii) removing node before a specified node
b) Provide an example of a real-life scenario where the use of a [4M]
doubly linked list would be appropriate.
(OR)
5. a) Discuss the steps involved in searching for an element in a [5 M]
single linked list.
b) Illustrate how a polynomial can be represented using linked [5 M]
list. Write an algorithm for adding two polynomials
represented by linked lists.
UNIT-III
6. a) Convert following expression X+ (Y * Z) – ((N * M +O) /Q) in to [5 M]
postfix form.
b) Explain the procedure to evaluate postfix expression. Evaluate [5 M]
the following Postfix expression 7 3 4 + - 2 4 5 / + * 6 / 7 +.
(OR)
7. a) Explain the basic operations of stack with pseudo code.(L2) [5 M]
b) Write an algorithm to push and pop an element from linked [5 M]
stack.
UNIT-IV
8. a) Compare the advantages and disadvantages of array-based [5 M]
and
linked list based implementations for queues.
b) Give the structure of Queue. Explain the operations in it. [5 M]
(OR)
9. a) Write an algorithm to insert and delete a key from circular [6M]
queue.
b) Define Deque. Explain the operations in it. [4M]
UNIT-V
10. a) Construct Binary Search Tree by inserting the following key [5 M]
elements: 10, 12, 5, 4, 20, 8, 7, 6, 15.
b) Explain pre-order, in-order and post-order traversals of [5 M]
Binary tree.
(OR)
11. a) What is hashing? Briefly explain various hashing methods. [5 M]
b) Summarize various Collision Resolution Techniques? [5 M]
*****
