[This question paper contains 8 printed pages.
Your Roll No...............
Sr. No. of Question Paper : 4955 H
Unique Paper Code : 2342571201
Name of the Paper : Data Structures
Name of the Course
[Link]. (P)/B.A. (P)
Year of Admission : 2022 & onwards
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. Attempt any four questions from Section B.
4. Parts of the question must be answered together.
कालिन्दी महाविद्यालय पुस्तकालय P.T.O.
KALINDI COLLEGE LIBRARY
4955 2
SECTION A
1. (a) Can you perform binary
a search on the following
list:
(3)
2, 4, 1, 9, 3, 7
If not give reasons and modify this list so that
binary search can be performed.
(b) State true or false for the following statements
and justify your answer: (3)
(i) Nodes of a binary tree may have 0 or 1 or
2 children.
(ii) Stacks use the FIFO access method.
(iii) A doubly linked list uses more memory than
a singly linked list.
(c) Considering root of the Binary tree at level 1,
what is the maximum number of nodes : (3)
(i) In a Binary tree of height 4
(ii) At level 3
(iii) At lowest level
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY
4955
3
(d) What is a recursive function? Under which
situations is it desirable to use a recursive function?
(3)
(e) Why overflow error does not occur in a linked
list? (3)
(f) What is the difference between one-dimensional
and two-dimensional array? Give one example with
code declaration of each. (3)
(g) Write the steps when binary search is applied on
the following list to find 16: (3)
2468 10 12 14
(h) List any three primitive operations considered in
complexity analysis of algorithms. (3)
(i) Apply insertion sort for sorting the following data
in ascending order. Show the outcome after each
pass: (3)
9 7 11 85
कालिन्दी महाविद्यालय पुस्तकालय P.T.O.
KALİNDI COLLEGE LIBRARY
4
4955
SECTION B
2. (a) Write a program in C++ to implement multiplication
of two matrices of order nXn taking input from
the user. Show the output row-wise. (5)
(b) Consider the following sequence of operations
performed on an initially empty doubly-linked
list, where addtohead(), addtotail() and deletef
romhead() are user defined functions to add a
node to the front, add a node to the tail and delete
a node from the front respectively:
(i) addtohead (25)
(ii) addtohead (28)
(iii) addtotail (23)
(iv) addtotail (20)
(v) deletef romhead ( )
Show the pointers head, tail, content of the
list, and hinks between the nodes after each
operation. (5)
म ह ा व ि द ् य ा ल य पुस्तकाला.
कालिन्दी
I C O L L E G E L IBRARY
KALIND
4955 5
(c) Create a binary tree whose following traversals
are given: (5)
Inorder:x y Z a
b
r
p
Preorder: a
y x q p r
3. (a) Write a function in C++ to count the number of
elements in a linked list. (5)
(b) Create a Binary Search Tree using the following
values: (5)
12, 45, 13, 67, 10, 34.
Using the above tree perform the following
operations :
(i) Delete 12
(ii) Insert 8
Show the tree after each operation.
(c) What will be the output after performing the
following operations on an initially 5 empty stack
of size 5. Show the contents of the stack after
each operation:
कालिन्दी महाविद्यालय पुस्तकालय P.T.O.
KALINDI COLLEGE LIB
RARY
4955 6
push(10)
push(20)
pop()
pop()
isempty() (5)
4. (a) Traverse the following binary tree in preorder and
inorder:
(5)
6
12 9
4 8 2
(b) Is the above tree in Q4(a) (5)
(i) A complete binary tree
(ii) Find the siblings of node 8
(iii) What is the height of the above binary tree
(iv) What is the degree of node 4
(v) What is the value of the root node
व ि द ् य ा ल य प ुस्तकालय
कालिन्द ी म ह ा
RARY
LEG E LIB
KALINDI COL
☑
4955
7
(c) Give the Depth First Traversal of the tree in
Q4a. (5)
5.
(a) Write a recursive function in C++ to reverse an
array of integers. Array size and elements must
be taken as input from the user. (5)
(b) What are the properties of stack data structure?
Show how stacks are used to add two numbers a
and b. (5)
(c) Differentiate between a queue and a priority queue.
Give one application of a priority queue. (5)
6. (a) What is a deque? How is it different from a queue?
List all the operations that can be performed on a
deque. (5)
(b) What are the limitations of a queue when
implemented as a linear array? Give an example
to illustrate. How can this error be avoided?
(5)
(c) State true or false giving reasons to justify your
answer :
(i) Elements of an array can be of different
data types.
कालिन्दी महाविद्यालय पुस्तकालय P.T.O.
KALINDI COLLEGE LIBRÁRY
4955 8
(ii) The time complexity of Insertion sort is
O(nlogn).
(iii) An algorithm of complexity O(nlogn) is
faster than one with complexity O(n²).
(iv) Master method can solve all recurrence
relation.
(v) A recursive method is always more efficient
than an iterative method. (5)
7. (a) Write a program in C++ to implement insertion
sort on an array of n elements. Take n and array
elements as input. from the user. (5)
(b) What is a recurrence relation? What is its
significance in complexity analysis? Use
recurrence tree method to solve the following
recurrence relation :
T(n) = T(n - 1) + n (5)
(c) Use master's method to solve following recurrence
relation:
T(n) = 3T(n/4) + nlogn
(5)
ि न ् द ी म ह ा व ि द ् य ा लय पुस्तकालय
काल (2500)
BRARY
KALI NDI COLLEGE LI