# WBUT Question Papers CS Data Structure And Algorithms

# B Tech Third Sem 2011- 12

Time Allotted : 3 Hours

FuH Marfcs : 70

The figures in the margin indicate full marks.

Candidates are required to give their answers in their own words

as far as practicable. ’

GROUP – A (Multiple Choice Type Questions )

Choose the correct alternatives for the following : 10 x 1 = 10

i) Which of the following traversal techniques lists the elements of a binary search tree in ascending order ?

a) Pre-order b) Post-order

c) Inorder d) None of these.

U) The list data structure can be defined recursively.

a) True

*

b) False.

ill) Best case time complexity of insertion sort is

^{93} ° ^{{ 1} ) b) O ( n)

c) O { n log n). d) Ofn^{2}).

[ Turn over

**iv) **In C language, arrays are stored in which representation ?

a) Column major b) Row major

c) Layer major d) None of these.

**v) **The number of stacks required to implement mutual recursion is

a) 3 b) 2

c) 1 d) none of these.

**vi) **Priority queue can be implemented using

a) array b) linked list

c) heap d) all of these.

**vii) **Binary search cannot be used in linked lists.

**a) **True

**b) **False.

**viii) **A complete directed graph of 5 nodes has ………………..

number of edges

—- ‘

a) 5 b) 10

**c) **20 ; d) 25.

**ix) **Breadth-first-search algorithm uses ……………….. data

structure

**a) **stack b) queue

c) binary tree d) none of these.

**x) **Which of the following is not related to hashing ?

**a) **Synonyms b) Collision

c) Balance factor d) Load factor.

GROUP -B ( Short Answer Type Questions )

Answer any three of the following. 3×5= 15

**2.**What is an Abstract Data Type ? What do you mean by a Dynamic Data Structure ? 3 + 2**3.**Write a C language function to delete the nth node of a singly-linked list. The error conditions are to be handled properly.**4.**Write a C language function to find the in-order successor of- the root of a binary tree. .

• ■ . ,

**5.**Write an algorithm to test whether a given binary tree is a

binary search tree.

**6.**Convert the following infix expression to postfix notation by showing the operator stack and output string after reading each input token :

A*B + C*(D-E) — F * G

GROUP -C ( Long Answer Type Questions )

Answer any three of the following. 3 x 15 = 45

**7.**Explain the mergesort algorithm. Why does it run faster than bubble sort in most of the cases ? Show how the mergesort algorithm will sort the following array in increasing order :

100, 90, 80, 70, 60, 50, 40, 30, 20.

Analyse the time complexity of the mergesort algorithm.

3 + 2 + 5 + 5

**8.**What are the problems of binary tree ? Explain the

improvement of performance by the use of height-balanced tree.

Explain how a height-balanced tree can be formed by inserting the following elements in the given order :

1. 2, 3, 4, 5, 6, 8. 9, 10, 7. 11

Show the root element the can be deleted from the above

^{tree}– 2 + 3 + 8 ♦ 2

**9.**Define the ADT for stack. Show the implementation of the

stack data structure using linked list. , 5+10

**10.**a) Write an algorithm for deletion of a node from a doubly-

linked list. _{5}

**b) **What is a threaded binary tree ? Write an algorithm for

non-recursive in-order traversal of a threaded binary

tree. _{n} _

2 + 5

**c) **Write an algorithm to left rotate a binary tree. 3

**11.**a) What do you mean by hashing ? What are the

applications where you will prefer hash tables to other data structures ? What do you mean by collision ? How is it handled ? 2 + 2 + 2

**b) **What is a B-tree ? Show how the letters A to P of English alphabet can be entered into a B-tree of order 4. _{3 + 6}

**12.**A rat has entered a checkerboard maze through one comer, whose the white boxes are open and black boxes represent obstacles. Develop an algorithm by which the rat can exit the maze through the opposite comer. Clearly explain the representation of the maze and any specific data structure you have used for the algorithm.