POPULAR PUBLICATIONS

INTRODUCTION
Multiple Choice Type guestions
[WBUT 2009]
AnC language, malloc( ) returns b) structure pointer
a) integer pointer
c) null pointer d) void pointer
Answer: (c)
[WBUT 2010]
2.Which of the following is the best time for an algorithm? d)O(nlog, n)
a) O(n) b)O(log, n) )o(2)
Answer: (b)
same task. Which algo. should execute the slowest for large
3/Four algo.s do the (WBUT 2010]
values of n?
b) O(n) c) O(log, n) d) o(2")
a) o(n)
Answer: (d)
values of
the following algorithm should execute the slowest for large
(WBUT 2012]
4. Which of
/N? c) O(log,N) d) None of these
a) O (N) b) O(N')
Answer: (b)
algorithm)? [WBUT 2013]
Which is better computing time (in analysis of d) None of these
b) O(2n). c) O(log 2n)
a) o(n)
Answer: (c)

data structure where we can search for desired records in O(logn)

We. A dynamic WBUT 2013]
time is
b) binary search tree
a) heap d) array
c) circularly linked list
Answer: (b)
Short Answer Type guestions
[WBUT 2006]
1.Explain f (n) =O(g(n)).
Answer:
Let f(n), g(n) be functions of natural(real) numbers.
t{n) = 0(gn)) if there exist constants A, N such that | f(n)) <-|A.g(n)| for all n>=N.
For example, 1+ n= O(n)

DSA-2
 ARRAYS
Muitiple Choice Type Questions
addressof
1. Each element of an array bytes of storage. Base major is
arr is 2000. The location of arr20;50] when
requires 4
the array is stored
as column
WBUT2008]
a) 2320 arr10110] c) 4048
b) 2840 d) 4840
Answer: (b
WBUT 2011]
sclanguage, arrays are stored in which representation?
a) Column major b) Row major
c) Layer major d) none of these
Answer: (b)
3. For Column Major, what is the 2ddress of 13, th element of a 3x4 auu
(cOmains integer number)? it is aiven that the Base Address is 2000.d)[WBUT Z013|
c) 2016 2018
a) 2010 b) 2012
Answer: should be 2020.

Short Answer Type Questions

Y Let the size of the elements stored in an 8 3 matrix be 4bytes each. f the base
address of the matrix is 3500, then find the adress ofA[4, for both[WBUT
row major &
2007]
column major cases. What is sparse matrix?
Answer:
1 Part: 3
In row major order the address will be
Loc (A(iJ) = Lo+ (-l)* n+6) *c
Therefore i 4
Loc (A(4,2)) =350 +(4-1) *3 + (2-1))*4
= 3500 + (10) * 4
-3500+ 40 J= 2
= 3540

In column-majcr order the address will be

Loc (A(j) =Lo- (p-i) *m -(i- 1))*c
Therefore
Loc (A(4,2)) =3500 +(2-1)* 8+ (4-1) *4
=3500 +(11)*4
=3500+ 44
= 3544

DSA-9
POPIILAR PIRIAvin
POPULAR PUBLICATIONS

LINKED LIST
Type guestions
Multiple Choice of an
following function for insertion
[WBUT 2005]
inserted in the
statement to be
1. Choose the linked list:
into a doubly
elementstruct list next, * prev; }i
dlist struct prev )
int ral; struct list
dlist * x, element
( .struct of the new
void insert Contains the addresg
{ /* x next;
next = prev
prev;
prev = inserted here
statements to be next =x
/* next =x -’ next ’
b) prev -’ prey =x
next =X next =x -’ next ’
prev=x- next - d) prev ’
a) preV --’ prev FX
prev =x ’ next
c) preV
Answer: (d) Linked list requires
after a givennode in adoubly
pointer exchanges WBUT 2006]
node
2Anserting anew exchanges b) two exchanges
a) four pointer d) nopointer
exchanges
c) one pointer involves the
Answer: (a) insertion of a record [WBUT 2008]
organization,
circularly linked list d) 3 pointers
13Tn a c) 2 pointers
modificationof
b) 1 pointer
a) no pointer
Answer: (c) [WBUT 20121
d) Binary search
not suitable for c) AVL Tree
V4. Linked list are b) Deque
a) Stack
Answer: (d) [WBUT 2012]
d) al! of these
memory allocation use c). Free
15. Dynamic
a)Calloc
b)Malloc
Answer: (d) previous nde
pointer to the next as wellas [WBUT 2013]
Which type of linked Listcontains a
6. List
in the sequence? b) Circular Linked
ist d) Allof these
a) Singly Linked !List
c)Doubly Linked
Answer: (c) following
structure for which one of the
[WBUT 2014]
list is not suitable data
A. Linked
problems? b) radix sort
a) insertionsort d) polynomial addition
c) binary search
Answer: (c)
DSA-30
POPULAR PUBLICATIONS

RECURSION
guestions
Multiple Choice Type
[WBUT 2005]
.Which of the following statements is not true? be nearer in some sense to a
must
function calls itself, it
a) Each time a
memory
always fast and use less
solution
known as
b) Recursive functions are
function is a recursive callthen it is
statement of
c) When the last
taifrecursion. used.
implementing recursion, stacks are generally
d) In
Answer: (b)
of [WBUT 2009)
fib (n) = fib (n-1) is an example
+ fib (n-2)b)Binary Recursion
function
1 2Fibonacci
a)Linear Recursion d) Mutual Recursion
Recursion
c) Non- linear
Answer: (b)
non-negative values of m and nis recursively
for all
3. The Ackerman function,
defined as if m=0
n+1
A(m, n) =A(m-1,l) if m!=0 but n = 0
|A(m-1, A(m, n-1)) if m! =0 and n!=0
[WBUT 2007, 2010]
Therefore the value of A (1, 2) is
b) 3 c) 5 d) 2
a) 4
Answer: (a)
recursively. [WBUT 2011]
A. The list datastructure can be defined
a) True b) False
Answer: (a)

Short Answer TypeQuestions

a recursive algorithm? State
1. How do we find the time and space requirements of [WBUT 2005]
advantages of both recursion and iteration.
Answer:
1 Part:
between
Recursive functions are internally evaluated by using stack. Now, the connection
called recursion
the stacks and function calls can be shown by using a tree. That tree is callsthat the
tree. Now, the first function call is shown in the root of the tree and all the Now, each
first function makes directly are shown as the vertices directly belowthe root. as further
of these function calls may call other functions or themselves, which are shown
vertices on lower levels.

DSA-40
 TREES
Multiple Choice Type guestions

Afull binary tree with n leaves contains [WBUT 2005]

a) n nodes b) log, n nodes c) 2n-1 nodes d) 2" nodes
Answer: (c)

2Abinary search tree is generated by inserting in order the following integers:

50, 15,62, 5, 20, 58, 91, 3, 8, 37,60, 24 respectival.
subtree of the root
The number of nodes in the left subtree and right
is [WBUT
d) (3, 8)
2006]
o(7, 4) c) (8, 3)
a) (4, 7)
Answer: (b)
a binary tree is threaded for in-order traversal a right NULL link of any node i
3. If [WBUT 2007)
replaced by the address of its c) root d) own
a) suCcessor b) predecessor
Answer: (a)
two sub-trees of every node never
4. In a height balanced tree the heights of [WBUT 2007, 2009)
differ by more than
c) 1 d) -1
a) 2 b)0
Answer: (c)
5.Maximum possible height of an AVL Tree with 7
nodes is WBUT 2008, 2013
b) 4 c) 5 d) 6
a) 3
Answer: (a)
binary tree are DBEAFC and DEBFCA
6. The in-order and post-order traversal of a in the left subtree of the given
respectively. What will be the total number of nodes [WBUT 2008
tree?
c) 5 d) None of these
a) 1 b) 4
Answer: (d)
[WBUT 2008)
.Abinary 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
Answer: (b)
WBUT208
8. A B-tree is
a) Always balanced b) An ordered tree
c) A direct tree d) Allof these
Answer: (d)
DSA-50
 DATA STRUCTURE & ALGORITHM
9. Whichi tree
structure is used for efficient access of records residing in disc
memory?a) AVL Tree
b) B Tree c) 2-3 Tree
[WBUT 2009]
d) Binary Tree
Answer: (b)
10. Which of the following is essential for converting an infix expression to postfix
notation?
a)
[WBUT 2009]
Aparse tree b) An operand stack
c) An
operator stack d) None of these
Answer: (c)
which of the
vaides in a BST can be sorted in ascending order by using[WBUT
fol 2009]
following traversals? d) Level - order
a) Pre - order b) In - order c) Post - order
Answer: (b)
.J2 The prefix expression for the infix expression a, (b+c)!e-fis [WBUT 2009]
a) /* a+ bc ef b) -/* + abcef
o-*a+ bcef d) None of these
Answer: (c)
In array representation of Binary tree, if the index number of a child node is 6
A. [WBUT 2010, 2014]
then the index number of its present node is
a) 2 b) 3 c) 4 d) 5
Answer: (d)
[WBUT 2012]
14. The depth of a complete binary tree with nc)nodes d) log(n)+1
log(n+1-1 b) log(n) log(n-1)+1
a)
Answer: (a)
of nodes of a tree is 9, then the
15. Ina binary search tree , if the number [WBUT 2012|
minimum height of the tree is c) 4 d) None of these
a) 9 b) 5
Answer{d)
stack to hold nodes that are waitina
A6 Which method of traversal does not WBUT 2012]
to be processed:
b) Depth- first
a)Breadth - first d) None of these
c)D- search
Answer: (a)
infix expression to the
sWhich of the following is essential for converting an WBUT 2013]
postfix expression efficiently?
operatorstack b) An operand stack
a) An stack and operator stack d) Aparse tree
c) An operand
Answer: (a)
DSA-51
POPULAR PUBLICATION
GRAPHS
Questions
Type
Multiple Cholce
[WBUT 2006]
bipartite if it contains odd length
Gwith n nodes b) a cycle of
1. Agraph
a)n edges
d) edges
longth
of odd
c) no cyclo [WBUT 20071
Answer: () disconnected is called
d)colored vertex
graph
makes a c) articulation point
of which
2. The vertox, removal
a) Pendant vortex b) bridge
Answer: (c) WBUT 2007]
directed graph is called d) root vertex
in-degree zero in a c) ísolated vertex
3. Aa)vertex of b) sink
articulation point
Answer: (c) [WBUT 2007, 2012]
of adigraph is c) asymmetric d) none of these
4. Adjacency matrix b)symmetric
a) identity
Answer: (b) 2008]
breadth first traversalof a graph? [WBUT
is used for d) None of these
5. Which data structure c) Both stack and queue
a) Stack b) Queue
Answer: (b)
[WBUT 2008, 2010]
of an undirected graph is
6. The adjacency matrix b) Asymmetric matrix
a)Unit matrix
c)Symmetric matrix d) None of these
Answer: (c)
WBUT 2008]
7. BFS
moving to the other vertex
a) scans all incident edges before possible
b) scans adjacent unvisited vertex as soon as
c) is same as backtracking
d) none of these
Answer: (b)
[WBUT2008]
8.Anon-planar graph with minimum number of vertices has
a) 9edges, 6 vertices b) 6 edges, 4 vertices
c) 10 edges, 5 vertices d) 9 edges, 5 vertices
Answer: (c)
[WBUT2009]
9. Any connected graph with x vertices must have at least
a) x+ 1 edges b) x-1 edges c) x edges d) x/2 edges
Answer: (b)
DSA-90
 ALGORITHM
DATA SIRUCTURE &
10. Mazirmum number of edges in a n-node
undirected araph without ser o
a) n b) n(n-1) (n+1)(n) WBUT 2010]
2 c) n-2 d)
2
Answer: (b)
11. BFS constructs
WBUT 2010, 2014]
a) a
b) aminimal
depth
cost spanning tree of a graph
first
c) a breath first spanning tree of a graph
d) none of thesespanning tree of a graph
Answer: (a)
12. Acomplete directed graph of 5
a) 5 b)10
nodes has...... WBUT 2011]
Answer: (b) cj 20 d) 25

13.A vertex with degree one in a

a) leaf b) pendant vertex
graph is called [WBUT 2012]
c) end vertex d)none of these
Answer: (b)
14. To implement DFS which data structure is
a) Stack b) Queue
generally used? [WBUT 2013]
c) Both (a) and (b) d) None of these
Answer: (a)
15. Adjacency matrix for a digraph is - [WBUT 2014]
a) unit matrix b) symmetric matrix
c) asymmetric matrix d) none of these
Answer: (b)
Short Answer Type Questions
for the following Graph [WBUT 2006]
Find
V) BFS Traversal
i) DFS Traversal. ,2,4,8,6,3
(213,4, S,6,3,7,
Answer:
a)(i) Thec BES traversal of the graph is:
Event Queue (Front to Rear) BES
Visit 1
2 12
Visit 2
Visit 3 23 123
DSA-91
 &ALCORITHM
DATA STRUCIURE

HASHING & COLLISIONS

Multiple Choice Type Questions
1. The ratio of the number of items in ahash table. to
the table size 15007
a) load factor
c) balanced factor b) item factor[WBUT 2005, 2007, 202009]
d) all of these
Answer:(a)

2. Which of the following methods had the hest average case complexe
searching? [WBUT 2006]
a) Hashing b) Sequential c) Random d) binary
Answer: (a)

3. The technique of linear probing for Colision Resolution can lead

a) Clustering
to [WBUT 2006]
utilization
c) Overflow b)efficient storage
d) underflow
Answer: (a)

4. Which of the followingis nota requirement of good hashing function?

a) Avoid collision b)Reduce the storage space
c) Make faster retrieval d) None of these [WBUT 2008]
Answer: (b)

5. The Linear Probing Technique for collision resolution can lead to WBUT 2009]
a) Primary clustering b) Secondary clustering
c) Overflow d) Efficiency storage utilization
Answer: (a)

6. Which of the following is not related to hashing? WBUT 2011]

a) Synonyms b) Collision c) Balance d) Load factor
Answer: (c)

7. Which of the following is a hash function? [WBUT 2014]

a)Quadratic probing b) chaining
c) open addressing d) folding
Answer: (a)
Short Answer Type Questions

1. What is hashing? [WBUT 2007, 2012, 2014]

Explain Linear Probing & Quadratic Probing with example. [WBUT 2007]
OR,
schema
Define 'Hashina'. Explain with a suitable exarmple the collision resolution
using linear probing with open addressing. WBUT 2010}
DSA-107
 SEARCHING &SORTING
1. Which of the Multiple Choice Type Questions
common computing following
times shows
for the correct relationship among Some of the more
a) algorithm?
b) 0(0(7)<0(l
logn)<o0(gn)n)<o(n*
logn)
<0(n* logn) <<0(2")<o()
WBUT 2005]

c) O(n)< 0(2")<0(n)
d) o(logn)0(logn)<0(n
*logn)
<0(")<o(2")
<0(n)<0(n* logn) <0(r
Answer: (d) )<o(2")
2. Asot, which
iteratively
any element less than it and passes through a list to exchange the first element with
then repeats with a new first
a) bubble sort element, I5 WBUT
ai
c) heap sort b) quick sort 2005]
Answer: (d) d) selection sort

3. A Sort which compares adjacent elements in a list

necessary is and switches where
[WBUT 2006]
a) insertion sort b) heap sort c)quick sort d) bubble sort
Answer: (a)

4. Which of the following sortingtechniques requires extra space, than the data to
be stored? [WBUT 2006]
a) Selection sort b) Bubble sort c) Heap sort d) None of these
Answer: (c)

5. Stability of Sorting Algorithm is important for [WBUT 2007]

a) Sorting records on the basis of multiple keys
b) Worst case performance of sorting algorithm
c) Sortingalpha numeric keys as they are likely to be the same
d) None of these
Answer: (a)
an algorithm?
6. Which of the following is the best time for c) O(2n) [WBUT 2007)
I)O(n log2 n)
a) O(n) b) O(log2 n)
Answer: (b)
sorting algorithm for an almost already sorted array is WBUT 20091
7. The fastest b)merge sort c)selection sort d) insertion sort
a) quick sort
Answer: (d)
DSA-115
POPULAR PUBLICATIONS
8. The time complexity of binary search is c)O(log n)
WBUT 2009)
d) O(n log n)
a) O(n') b)O(n)
Answer: (c)
9. Thebest case time complexity of
Bubble sort technique is WBUT 2010)
a) O(u) b) O(r) c)O(nlog n) d) O(logn)
Answer: (a)

10. Which of the following sorting

procedures is the slowest? WBUT 2010]
b) Heap sort c) Merge sort d) Bubble sort
a) Quick sort
Answer: (d)
lists the elements of a binary
11. Which of the following traversal techniques [WBUT 2011]
search tree in ascending order? d) None of these
a) pre-order b) Post-order c) Inorder
Answer: (c)
linked lists. [WBUT 2011]
12. Binary search cannot be used in
a) True b) False
Answer: (b)
.data structure [WBUT 2011]
13. Breadth-first-search algorithm uses...... c) binary tree d) none of these
a) stack b) queue
Answer: (b)
insertion sort is - WBUT 2011]
14. The best case complexity of
a) O(n') b) O(nlog, n) d) O(n)
Answer: (d)
sort 1000 names by quick sort. The
15. A machine needs aminimum of 100sec to
minimum time needed to sort 100 names will be approximately [WBUT 2012]
b)11.2 sec c) 50.2 sec d) 6.7 sec
a) 72.7 sec
Answer: (d)
array ot n
16. What will be the time complexity for selection sort to sort an[WBUT 2012]
elements?
a) O(logn) b)O(n log n) c) O(n) d) O(n)
Answer: (d)
[WBUT 2013]
17. The best sorting technigue when the data is almost sorted is
a)) Selection sort b) Bubble sort
c) Quick sort d) Insertion sort
AINWer: (d)

DSA-116