# WBUT Exam Papers EC

## Data Structure And Algorithm B Tech Third Sem Dec 2008

Time : 3 Hours ] [Full Marks : 70

( Multiple Choice Type Questions )

- Choose the correct alternatives for any ten of the following : 10×1 = 10

1) Each element of an array arrl20][50) requires 4 bytes of storage. Base address of arr is 2000. The location of arrll0][10] when the array is stored as column major is ^

a) 2820 b) 2840

c) 4048 d) 4840.

li) Maximum possible height of an AVL Tree with 7 nodes is .

a) 3 b) 4

c) 5 d) 6. L J

ill) In a circularly linked list organization, insertion of a record involves the modification 2 pointers d)_ 3 pointers. [ ]

iv) The in-order and post-order traversal of a binary tree are DBEAFC and DEBFCA respectively. What will be the total number of nodes in the left subtree of the given tree_{c) } d) None of these. I _■ j

v) Which data structure Is used for breadth first traversal of a graph ?

a) Stack b) Queue

c) Both stack and queue d) None of these.

vi) The prefix expression for the infix expression a*(b + c) / e- fis

a) /*a + be – ef b) -/* + abcef

c) -/*a + beef d) none of these.

vii) Which of the following is not a requirement of good hashing function ?

a) Avoid collision b) Reduce the storage space c) Make faster retrieval d) None of these,

viii) The adjacency matrix of an undirected graph is

a) Unit matrix b) asymmetric matrix

c) symmetric matrix d) none of these.

ix) BFS

a) scans all incident edges before moving to the other vertex

b scans adjacent unvisited vertex as soon as possible

c) is same as backtracking ‘

d) none of these.

x) A non-planar graph with minimum number of vertices has

a) 9 edges, 6 vertices b) 6 edges, 4 vertices

c) 10 edges, 5 vertices d) 9 edges, 5 vertices.

xi) A binary tree is a special type of tree

a) that is ordered

b) such that no node has degree more than 2

c) for which both (a) and (b) above are correct

d) in which non-leaf nodes will have degree 2.

xii) A B-tree is a) always balanced b) an ordered tree ,

c) a directed tree d) all of these.

GROUP-B ( Short Answer Type Questions )

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

- Prove that, the best case time complexity for quick sort is O ( n log n ) for input size of n.
- a) Compare sequential versus direct access file structures,

b) Explain multi-index file structure.

- ‘The designer of an algorithm need to balance between space complexity and time complexity.” — Comment on the validity of the statement in the context of recursive algorithms.
- What are the advantages of linked list over an array ? Write an algorithm to insert a data X after a specific data item Y in a linked list.
- Give an algorithm to search for an element in an array using binary search.

GROUP -C ( Long Answer Type Questions)

Answer any three questions. 3 x 15 = 45

- a) Why is hassing referred as a heuristic search method ?
- b) What is the primary advantage of hashing over deterministic search algorithms ?

c) Define collision. Discuss two collision resolution techniques and compare their performances.

d) Why the hash functions need to be simple ? 3 + 4 + 7+1

- a) What is linear data structure ?

b) Do you consider the following data-structures as linear ?

i) Circular doubly linked list

ii) Binary tree.

Explain for both cases.

c) Represent the following polynomial by linked list ( show the diagram only ) :

d) Write an algorithm to delete all nodes having value greater than X from a given singly linked list. 1 + 6 + 2 + 6

- a] Define circular queue.

b) Write an algorithm to insert an item in circular queue.

c) What is input restricted dequeue ?

d) Write an algorithm to convert an infix expression to postfix using stack.

2 + 5 + 2 + 6

- a) What do you mean by external sorting ? How does it differ from internal

sorting

b) Write an algorithm for sorting a list numbers in ascending order using selection sort technique.

c) Describe Kruskal’s minimal spanning tree algorithm. 3 + 7 + 5

- a) In a 2-tree, if E be the external path length, P be the internal path length and Q

be the number of vertices that are not leaves, then prove that

E = P + 20.

b) What is threaded binary tree ?

c) Write an algorithm to delete a node from a binary search tree.

d) Create a AVL tree by inserting the following numbers in the order in which they are given : 17 25 19 23 75. Draw figure for each step.END