[This question paper contains 4 printed pages.
]
Your Roll No
J
Sr. No. of Question Paper: 7665
Unique Paper Code : 2342571201
Name of the Paper : Data Structures
Name of the Course : B.A. Prog. With CS As Minor/Non-Major &
[Link]. (Phy. Sc. & MS) With CS
Semester : II
Duration: 3 Hours Maximum Marks: 90
Instructions for Candidate's
1. Write your Roll No. on the top immediately on receipt of this question paper.
2. Section A is compulsory.
3. Attempt any four questions from Section B.
4. Parts of the question must be answered together.
Section A
1. (a) Sort an array A=[10,7,12, 8,5] using insertion sort. Write the elements 5
of the array after each iteration. How many comparisons will be needed to
sort the array.
(b) Solve the recurrence using Master's theorem 5
T(n) = 3T ()+nign
(c) Consider the given series of operations to be performed on an empty stack : 5
push(5), push(3), pop(), push(7), top(), empty(),
push(7), pop(), push(12), size(), pop(), top()
Show the output and stack contents after each stack operation.
P.T.O.
कालिन्दी महाविद्यालय
पुस्तकालय
KALINDI COLLEGE LIBRARY
2
7665
5
C++ to calculate
(d) Write a recursive program in
ar = 0r- 1+a r-2 .fo r r ≥ 2, where a = 0 and a1 =1
draw the recursion trace for as
taking 'r' input from the user. Also
(e) Consider the following binary tree:
6
2
8
1 4
3 7 9
Inorder traversal.
i. Write the Preorder, Postorder and
.
ii. Determine the Height of the tree
5
tree with the following num
bers:
(f) Construct a binary search
2, 6, 25, 50, 15.
8, 51,5, 10, 47, 70,
41,
of the resultant
w the steps for construction
Delete the root node and sho
binary search tree.
Section B
5
the recurrence using Substitu
tion methods
2.(a) Solve
2T( [√n]) +1gn)
T(n) =
5
code for
lement stack using linked list. Write
(b) Write C++ program to imp
a
a
push and pop operations.
5
T)? Differentiate betwee n Stack and Queue.
c) What is an abstract data type (AD
5
the input of size
Write the time complexit
y for the following operations for
3. (a)
'n':
Insert element into binary
search tree
(i)
(ii) Insert element into stack
Insert element into dou
bly link list
(iii)
Insert element into
singly link list
(iv)
(v) Find [Link] in array
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY
7665
3
(b) Define Big-Oh notation. Show
that asympt otic analysis of 5
5n² + 3n logn + 2n is O(n²)
(c) Which ofthe following is/are correct Inorder traversal for a binary search 5
tree. Justify your answer.
(1) 2, 4, 6, 7, 11, 15, 20
(ii) 4, 6, 7, 12, 10, 11, 15
4.
(a) Consider the given series of operations to be performed on an empty Deque 5
(double ended queue):
insertFront(20), insertFront(30), front), eraseFront), insertback(70),
eraseFront(), back(), eraseback(), size(, empty0
Write the output and contents of the Deque after each operation.
(b) Define circular linked list? Explain different operations performed on a 5
circular linked list.
(c) Write a C++ program to create a singly linked list of integers. Write functions 5
to insert and delete an element from the beginning of the list.
5. (a) Define height of a binary tree. Write a C++ function to compute it. 5
(b) Suppose a circular queue of capacity (n- 1) elements is implemented with 5
an array ofelements with initial value 0 for Rear and Front.
n
What are the conditions to detect:
(i) queue is full.
(ii) queue is empty
(c) Write short notes on
5
(i) Complete binary tree
(ii) AVL tree
6. (a) Convert the following infix expression to postfix notation using stack 5
a +b* (c^ d - e)^(f + g * h)-i
where^ represents exponentiation.
(b) Define heap data structure? Construct max heap for the follow
ing array: 5
A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7; 12].
(c) What is priority queue and its types? Explain its real-life applic
ations. 5
7. (a) Write a function in C++ to calculate factorial using:
5
(i) iteration
(ii). recursion
P.T.O.
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE
4
7665
5
rformed on empty queue :
of operations to be pe
an
b) Consider the given series
front(), dequeue(), size(),
queue (A), en
en
queue(B),
size()
dequeue (), front(); empty(),
eue contents after ea
ch queue operation.
the out put an d qu
Show
5
lowing treeis height
ght bal anc ed tre e? Det ermine which ofthe fol
(c) What is hei
balánced. Justify your answer
(4 (5
Tree-B
Tree-A
(1000)
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY