[This question paper contains 8 printed pages.

]
Your Roll No.....

Sr. No. of Question Paper : 5960

J

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

II
Semester

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. The paper has two sections. Section A is compulsory.

3. Attempt any four questions from Section B.

4. All parts of a question must be answered together.

Šection A

1. (a) Draw all possible binary search trees for the three elements A, B, and C. 3

(b) Explain the operation performed by the following code on a singly linked list. 3

void func(int x)

head = new node (x, head);

if (tail == 0)

tail = head;

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

KALINDI COLLEGE LIBRARY P.T.O.
5960 2

3
(c) 'Stack data structure plays an important role in the implementation of recursion'.
Justify the statement with suitable example.

(d) Where in a max-heap might the smallest element reside, assuming that all elements 3
are distinct? Justify your answer.

3
(e) Consider the following list of numbers:

3, 28, 45, 23, 12, 26, 90, 56, 76

To search given number in the above list, which of the searching techniques
a

(linear/binary) is best suited in terms of time complexity? What is the time

complexity of the suggested techhique?

(f What will happen if we attempt to remove a node from an empty queue? Give one 3
way to solve this problem.

(g) In the balanced binary tree given below, how many nodes will become unbalanced 3
when a node is inserted as a child of the node "G"? Justify your answer.

B C

D E F

(h) Explain the meaning of the following expressi

ons: 4

i. f (n) is O(1).

ii. f (n) is© (1).

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

KALINDI COLLEGE LIBRARY
5960 3

5
(i) Consider the following sequence of operations on an empty stack:

push (54); push(52); pop(); push(55); push(62); s=pop() ;

Consider the following sequence of operations on an empty queue:

enqueue (21); enqueue (24); dequeue(); enqueue (28);

enqueue(32); q=dequeue () ;

After performing these operations, what would be the value of the expression
(s+q)? Also show the contents of stack and queue.

Section В

2. (a) Differentiate between Binary Search Tree and Balanced Search Tree. 4

(b) Consider the following tree: 5

B C

D E F G H

1 J K L M N P
Ο

Q R S

i. Name the internal nodes.

ii. How many descendants and ancestors does node B have?

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

KALINDI COLLEGE LIBRARY
5960 4

iii. What are the siblings of node E?

iv. What is the depth of node О?

v. What is the height of the tree?

(c) Write member functions to perform the following operations on Queue using array: 6

i. isEmpty()

ii. isFull()

iii. enqueue (x)

iv. dequeue ()

3. (a) Differentiate between min-heap and max-heap. 4

(b) Sort the following set of elements using insertion sort: 5

29, 10, 14, 37, 13, 25, 7, 18, 5, 33

Show the content of array after every iteration.

(c) Consider the following recursive function:

6

int myFunc(int n) {
if (n >= 0 && n <= 9)

return n;

return (n % 10) + myFunc(n/10);

i. What will be the output of

my Func (234)?
ii. How many recursive calls will be perf
ormed to compute myFunc (234) ?
iii. Write the iterative version of the
above function.

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

KALINDI COLLEGE LIBRART
5960 5

4. (a) Convert the following infix notations to postfix notations: 4

A* ((B+C)/D)

Show the contents of stack at each step.

(b) i. Calculate the asymptotic time complexity of the following code: 5

for(i=0;i<n;i++)

{ for(j=0;j<n;j++)

{ Statement;

ii. Prove that 5n²+3nlogn+2n+5 is O (n²). Find the values

of the constants
no and c.

(c) Explain how Master's theorem can be used for solving recurrences giving suitable 6
example.

5 (a) Consider the following recursive function:

4

void fun(int x)

if(x > 0)

fun (x-1);

cout << x <<" ";

fun(x-1);
}

Draw the recursion tree when fun(4) is called.

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

KALINDI COLLEGE LIBRARY
5960 6

5
(b) Create a Binary search tree with the keys inserted in following order:

50, 30, 70, 20, 40, 60, 80, 10, 25, 35

Draw the tree after each insertion.

6
(c) Determine the preorder, inorder and postorder traversals of the following tree:

B C

D E F

give one real life application 4

6 (a) Compare and contrast priority queue and deque. Also,
of priority queue.

(b) Consider the following array-based queue of characters, where queue is allocated 5
n=6 memory cells:

Queue: b, d, a, g

(where"" means empty memory cell)

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

KALINDI COLLEGE LIBRARY
5960 7

Perform the following sequence of operations on the given queue:

i. enqueue('p')

ii. dequeue ()

iii. enqueue ('c)

iv. enqueue('z')

v. front()

After every operation, show the contents of the queue with front and rear
pointers.

(c) Write member functions to perform the following operations on Doubly Linked List: 6

i. Insertion at head

ii. Deletion from head

iii. Search an element 'x' in linked list

7 (a) Consider a circular linked queue: (9,8,7,6,5,4,3, 2) such that the cursor 4
points to performing following operations
5. After on this queue, what would be the
front and rear elements of the queue?

Enqueue (1), Dequeue(), Dequeue (), Enqueue (12),

Dequeue(), Dequeue ()

Also draw the resultant queue.

5
(b) Write a program to implement the following operations for stack using linked list:
i. isEmpty)(
ii. size()
iii. push ()
iv. pop ()

य पुस्तक ालय
कालिन्दी महाविद्यालGE LIBRARY
LLE
KALINDI CO P.T.O.
5960 8

6
(c) Build a max heap from the following array of numbers:
4, 10, 3, 5, 1, 12, 7, 9

Draw the heap after each insertion.

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

KALINDI COLLEG
E LIBRARY (1200)