[This question paper contains 8 printed pages.
Your Roll No....
Sr. No. of Question Paper : 4008 H
Unique Paper Code : 2342571201
Paper
:
Name of the Data Structure
Name of the Course :
[Link]. (Programme) and
B.A. (Programme)
Semester II
Duration: 3 Hours Maximum Marks: 90
Instructions for Candidates
1. Write your Roll No. on the top immediately on receipt
of this question paper.
2. Section A is compulsory.
3. Answer any four questions from Section B.
4. All parts of Question must be attempted together.
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY P.T.O.
2
4008
SECTION A
1. (a) Explain any two Abstract Data Types in C++.
(3)
(b) What will be the output of the following operations
on an empty Stack. (3)
Push(3), Push(4),Pop(),Push(5), Push(6),Pоp()
(c) Write C++ code to add an element into a Queue.
(3)
(d) Define Deque and explain any two operations that
can be performed on it. (3)
(e) Write C++ code to read and write an array of n-
dimension. (3)
(f) Differentiate between the following with a suitable
example:
(i) BPS and DFS tree traversal
कालिन्दा महाविद्यालय पुस्तकल
KALINDI COLLEGE LIBRARY
4008
3
(ii) Complete and Perfect Binary (6)
tree
(g) Define Height Balanced trees with a suitable
example. (3)
(h) How to convert a singly link list into a circular
link list? Explain. (3)
(i) What do you mean by asymptotic Big-O analysis
of an algorithm? (3)
SECTION B
2. Consider the following BST (15)
3 10
1 6 (14
4 7 13
कालिन्दी महावयालय पुस्तकालय
KALINDI COLLEGE LIBRARY P.T.O.
4008 4
Show the status of BST after each of the following
operations :-
(i) Draw the updated tree after 2 will be
inserted in the BST.
(ii) Draw the updated tree after deleting 3 from
the BST.
(iii) Write post-order traversal of the resultant
BST.
(iv) Check if the resultant tree is height
balanced or not? Justify your answer.
(v) Write pre-order traversal of the Final
resultant tree.
3. (a) Explain Master's theorem with the help of suitable
example. (6)
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY
4008
5
(b) Write a program in C++ to find nth Fibonacci
Series using recurs (5)
ive function.
(c) Write a program in C++ to find factorial of a
number 'n'.
(4)
4. (a) Write a program in C++ to implement stack using
Linked List.
(6)
(b) Draw a tree whose in-order and post-post
traversals given below:
are
(5)
In-order: BFEADGC
Post-order: FEBGDCA
(c) Evaluate the Cost of the given function:
- (4)
T(n)=7T(n/6) + n²
महाविद्यालय पुस्तकाल
य
कालिन्दी
A L I N D I C O L L E G E LIBRARY P.T.O.
K
4008 6
5. (a) Differentiate between Singly and Doubly Linked
list. Also, write program in C++
a to insert an
element in the beginning of a singly linked list.
(6)
(b) Write C++ code to delete a node from the end of
a singly linked list.
(5)
(c) Mention any two advantages and disadvantages
of Linked list.
(4)
6. (a) Create a BST with the following values
{7,5,1,8,3,6,0,9,4
,2} if the number
s are inserted in
the order as given into an initially empt
y BST.
Also, write it
s in- order t
raversal.
(6)
(b) Draw a Recursion tree for the recurrence
T(n) = 3T
4 + cn²
(5)
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY
4008
7
(c) Write any two real-life applications each of
stack
and queue. (4)
7. (a) Consider the following seq
uence of operations
performed on an initially empty doubly linked
list: (6)
InsertBeginning(12),
InsertBeginning(4),
InsertEnd(3),
InsertEnd(1),
DeleteBeginning(),
•
Deletenode(1)
Show the contents of the list, links between the
nodes, and head and tail after each operation.
(b) Perform and explain count sort on the array
{5,5,7.6,7,4,3} (5)
् द ी ह ा व ि द ् य ा ल य पुस्तकालय
कालिन म
I C O L L E G E L IBRARY P.T.O.
KALIN D
4008 8
(c) Mention any two properties of a Binary Heap.
(4)
म ा य ा ल य पस्तकालय
कालिन्दी क (1500)
O L L E G E L I BRARY
KALINDI C