# WBUT Question Papers EC

## Data Structure And Algorithm B Tech Third Sem

Time : 3 Hours ]

[ Full Marks : 70

Graph sheet is provided on Page No. 31

Group – A

(Multiple Choice Questions)

1. Choose the correct alternatives of the following :                  10 x 1 = 10

i)                A graph G with n nodes bipartite if it contains

a)               n edges

b)               a cycle of odd length

c)               no cycle of odd length

d)  n2 edges.

ii)              The postfix equivalent of the prefix * + ab-cd is

a)               ab + cd- *

b)               abed + – *

c)               ab + cd*-

d)  ab + – cd * .

iii)            A sort which compares adjacent elements in a list and switches where necessary is

a)              insertion sort

b)               heap sort

c)               quick sort

d)              bubble sort.

iv)             The following sequence of operations is performed on a stack: push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop. The sequence of popped out values are

a)               2, 2, 1, 1, 2

b)               2, 2, 1, 2, 2

c)               2, 1, 2, 2, 1

d)              2, 1, % 2, 2. 1

4

v)               The initial configuration of queue Is a, b, c, d (‘a’ is at the front). To get the configuration dTc,b, a one needs a minimum of

a)              2 deletions and 3 additions

b)               3 deletions and 2 additions

c)               3 deletions and 3 additions

d)               3 deletions and 4 additions.                    [

vi)             Which of the following sorting techniques requires extra space, than the data to be stored ?

a)              Selection sort

b)               Bubble sort

c)               Heap sort

d)              None of these.                                  ____

vii)           Which of the following methods has the best average case complexity for searching ? ~

£0 Hashing          ,

b)              Sequential

c)               Random

d)              Binaiy.

viii)   A binaiy search tree is generated by inserting in order the following integers :

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is

a)    (4,7)

b)    (7,4)

c)    ( 8, 3 )

d)    (3, 8).                                                         I

Ix) The tecnlque of linear probing for Collision Resolution can lead to

a)               clustering

b)               efficient storage utilization

c)               overflow

d)               underflow.

x) Inserting a new node after a given node in a doubly Linked list requires

a)               four pointer exchanges

b)               two pointer exchanges

c)               one pointer exchanges

d)              no pointer exchanges.           ,

Group • B ( 8hort Answer Questions )

1. Prove that for any non-empty binary true T, if is the number of leaves and n2 be the

number of nodes having degree 2, then n0 = n2 + 1.

1. Write an algorithm for inorder traversal of a threaded binary tree.                                             5
2. a) How can a polynomial such as 6x 6 + 4x 3 – 2x + 10 be represented by a linked

list ?

b)               Suggest an algorithm to reverse the direction of all the links of a singly linked

list.

1. a) Explain /( n) = O ( g ( n)).

b)               What is the advantage of binary search over linear search ?

Group – C ( Long Answer Questions )

Define a directed graph. Provide an example.

I)                 Indegree

II)               Sink

III)             Cycle

iv)             Network.

Define adjacency matrix corresponding to a digraph.

Draw the graph corresponding to the following bit matrix :

0 0 0 1 10 11 10 0 1 0 0 10

What is path matrix ?                                                                                                          2

Count the total number of nodes of a binary tree having depth n.                                     1

Let a & b denotes positive integers. Suppose a function Q is defined as follows : 0            if a < b

Q ( a.b) = { Q ( a – b, b ) + 1 if b < = a }

Find the value of Q ( 2, 3 ) and Q ( 14. 3 ).

Transform the following expression to the expression In Postfix notation :

A*(B + D)/E-P»(G + H/K)

Why is the Queue Data Structure called FIFO ?

Construct the following Queue of characters where Queue is a circular array which Is allocated six memory cells.

FRONT = 2 REAR = 4                           QUEUE : _ . A, C, D________

Describe the Queue as the following operations take place :

I)                 F is added to the Queue

II)              Two letters are from the Queue.

Hi)    K.L.M are added to the Queue.

Iv)     Two letters are deleted from the Queue.

v)                R Is added to the Queue.

vi)              One letter Is deleted from the Queue.

The inorder & preorder traversal sequence of nodes in a binary tree are given below :

Inorder:              D G B A H E I C F

Preorder: ABDGCEHI F.

Draw the binary tree. State briefly the logic used to construct the tree.

Insert the following keys in the order given below to build them into an AVL tree. g, h, s, I e, m. t, u.

Clearly mention different rotations used and balance factor of each node.

What is 2-way threading ?                                                      6 + 6 + 3

What is BST ?

For the following Graph Find

i) BFS Traversal

DFS Traversa

c)  Explain with a suitable example the principles of operation of Heap sort.

d)   Find the Time Complexity of the above algorithm.                                        2 + 5 + 5 + 3

1. Write short notes on any three of the following :

a)               AVL Tree

b)               Tail Recursion

c)                Collision Resolution using chaining

d)               Dequeue — operation & application

e)               Wars hall’s Algorithm.