[This question paper contains 8 printed pages.

Your Roll No.

Sr. No. of Question Paper : 4935 H

Unique Paper Code : 2342571201

Name of the Paper : Data Structures

Name of the Course

: B.A. (Prog) / [Link].
(Programme) NEP
Year of Admission : 2022

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.

SectionA

1. (a) Sort an array of elements A = {13,12,14,6,7} using

insertion sort. Write the elements of the array
after each step. How many comparisons will be
needed to sort the array.
(4)
कालिन्दी महाविद्यालय पुस्तकालय
P.T.O.

KALINDI COLLEGE LIBRARY

 2
4935

(b) Solve the recurrence given T(n) = 3T(n/2)+n2 using

.
the masters method (4)

(c) List two differences between each of the

following:-

(i) Array and Linked List

(ii) Stack and Queue (4)

(d) Identify and write the name of the Data Structures

suitable for the following applications (4)

Application 1: Storing high score entries for a

game

Application 2: Undo/Redo Functionality in text

editors

Application 3: To manage traffic flow in the

transportation systems

Application 4: To find a specific element in a

sorted collection of elements

(e) In the array implementation of a circular queue

how are front and rear indices modified upon
insertion and deletion of an element. Write the
conditions for the following :

(i) Full Queue

(4)
(ii) Empty Queue
ा ल य प ु स ्तकालय
कालिन्दी महाविद्य
り

L I B R A RY
I C O L LEGE
KALIND
4935
3

(f) What is an abstract data type (ADT)? Give two

advantages of using ADT in data structure?
(4)

(g) What is a height balanced tree? Are the following

binary trees height balanced trees? Justify your
answer. (4)

2 2

4 6
4

(i) (ii)
(h) Give two advantages of a doubly linked list over

a singly linked list. (2)

Section B

2. (a) Write a C++ program to create a singly linked list

of integers. Write functions to insert and delete
an element from the front of the list. (6)

(b) Consider an initially empty doubly linked list.

Show the updated doubly linked list after each
operation.
(5)
कालिन्दी महाविद्यालय पुस्तकालय
KALINDI COLLEGE LIBRARY P.T.O.
 4
4935

Insert AtStart(30)

InsertAtStart(18)
Delete(33)

InsertAtEnd(8)

DeleteAtStart()

(c) What is a complete binary tree? Consider the

following binary trees. Are the following binary
trees complete binary trees? Justify your answer.

(4)

A 1

B C
2 3

D E F G

L
1
H K 4 5 7

(i) (ii)

3. (a) Sort the given array A={7,1,2,0,2,3,4,5,1,6,3} using

counting sort. Show the array contents after each

step. (6)

(b) Write a recursive program in C++ to calculate x".

(5)
taking x and n input from the user.

कालिन्दा महाविद्यालय पुस्तकालय

KALINDI COLLEGE LIBRARY
4935
5

(c) Give two differences between static arrays and

dynamic arrays. Write the syntax of declaring a

dynamic array in C++. (4)

4. (a) Consider a queue with a maximum size of 6

elements. Currently the queue has three elements
A,D and F with Front=2 Rear=4 as shown in
figure.

A D F

figure: Queue

Write the output and status of queue after each of

the following operation :

(i) enqueue(L)

(ii) enqueue(K)

(iii) dequeue()

(iv) front()

(v) enqueue(X)

(vi) size() (6)

(b) Write a C++ program to implement a stack

using linked list. Give necessary declarations for

the stack. Write functions for push and pop

operations. (5)
तकालय
कालिन्दी महाविद्यालय पुस्
IBRARY Р.Т.O.
KALINDI COLLEGE L
 6
4935

(c) List two real life applications of priority queue.

a

What are the two types of priority qucues?

(4)

5.(a) Construct a binary search tree with the following

numbers.

51, 14, 61, 5, 20, 57, 90, 3, 7, 35, 60, 25

Write the steps required to delete the root node

from the binary search tree. Show the resultant
tree. (6)

(b) Write twoproperties of a heap data structure.

Differentiate between min heap and max heap.
Give two applications of the heap data structure.
(5)
(c) Prove that running time T(n) = n3 + 20n + 1 is

O(n³). What would be the value of c and n?

(4)

6. (a) Write the preorder, inorder and post order tree

traversal of the following binary tree. (6)

A

B C

D E F G

Binary Tree
कालिन्दी महाविद्या
लय पुस्तकालय
KALINDI COLL
EGE LIB RARY
 4935 7

(b) Let us consider the following series of operations

on an initially empty double

ended Queue(Deque).
insertFront(13)

insertFront(15)

front()

eraseFront()

eraseFront()

size()

Write the output and contents of the deque after

each operation. (5)

(c) What will be the time complexity of delete

operation (dequeue()) of a linear queue, when the
queue is implemented using

(i) stack

(ii) array

Give justifications for your answer. (4)

7. (a) Consider the given series of operations to be

performed on an initially empty stack of size 5:

कालिन्दी महाविद्यालय पुस्तकालय

KALINDI COLLECE LIBRARY P.T.O.

4935 8

push(9)

Pop()

Pop()

push(7)

push(12)

empty()

Show the output and stack contents after each

stack operation. (6)

(b) What is the advantage of using a circular linked

list over a singly linked list? Enumerate four

different operations that can be performed on a

circular linked list. (5)

(c) Write and explain the time complexity of

performing the following operations on one

dimensional array.

(i) Deleting an element at a given index

(ii) Searching an element in an array of n

elements (4)

ालय
कालिन्दी काविद्यालय पुस्तक
KALINDI COLLEGE LI
BRARY(1000)