Algorithms And Data Structures

Q.1) In linked lists there are no NULL links in
A. Single linked list
B. Linear doubly linked list
C. Circular linked list
D. None of these

Q.2) In a stack the command to access nth element from the top of the stack S will be
A. S [Top-n]
B. S [Top+n]
C. S [Top-n-1]
D. None of the above

Q.3) If yyy, xxx and zzz are the elements of a lexically ordered binary tree, then in preorder traversal which node will be traverse first
A. xxx
B. yyy
C. zzz
D. Can not be determined


Q.4) In a balance binary tree the height of two sub trees of every node can not differ by more than
A. 2
B. 1
C. 0
D. 3

Q.5) The result of evaluating prefix expression */b+0dacd, where a=3, b=6, c=1, d=5 is
A. 0
B. 5
C. 10
D. 15

Q.6) In array representation of binary tree teh right child of root will be at location of
A. 2
B. 5
C. 3
D. 0


Q.7) The total number of comparisons in a bubble sort is
A. O(n logn)
B. O(2n)
C. O(n2)
D. None of above


Q.8) The dummy header in linked list contain
A. First record of the actual data
B. Last record of the actual data
C. Pointer to the last record of the actual data
D. None of above

Q.9) Write the output of following program: int a[ ] = {1,2,3,} *p;
A. 3
B. Junk value
C. Run time error
D. Address of the third element



Q.10) If the out degree of every node is exactly equal to M or 0 and the num ber of nodes at level K is Mk-
1 [con sider root at level 1], then tree is called as 
(i) Full m-ary try
(ii) Com plete m-ary tree
(iii)Positional m-ary tree

A. Only (i)
B. Only (ii)
C. Both (i) and (ii)
D. Both (ii) and (III)

Q.11) In the following tree:

If post order traversal generates sequence xy-zw*+, then label of nodes 1,2,3,4,5,6,7 will be

A. +, -, *, x, y, z, w
B. x, -, y, +, z, *, w
C. x, y, z, w, -, *, +
D. -, x, y, +, *, z, w



Q.12) If the following tree is used for sorting, then a new number 10 should be placed at

A. Right child of node labeled 7
B. Left child of node labeled 7
C. Left child of node labeled 14
D. Right child of node labeled 8


Q.13) A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of 
A. 2 deletion and 3 additions
B. 3 deletions and 2 additions
C. 3 deletions and 3 additions
D. 3 deletions and 4 additions



Q.14) Number of possible ordered trees with 3 nodes A,B,C is
A. 16
B. 12
C. 6
D. 10




Q.15) Number of swapping, operations need to sort numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort
A. 11
B. 12
C. 13
D. 14



Q.16) Consider two sorted lists of size L1, L2. Number of comparisions needed in worst case my merge sort algorithm will be
A. L1,L2
B. Max(L1,L2)
C. Min(L1,L2)
D. L1+L2-1




Q.17) A hash tabale with 10 buckets with one slot per bucket is depicted in following diagram. Symbols S1 to S7 are initially entered using a hashing function with linear probing. Maximum number of comparisions needed in searching an item that is not present is

A. 4
B. 5
C. 6
D. 3



Q.18) Following sequence of operation is performed on a stack. Push(1), Push(2), Pop, Push(1), Push(2), Pop, Pop, Pop, Push(2), Pop. The sequences of popped out values are
A. 2,2,1,2,2
B. 2,2,1,1,2
C. 2,1,2,2,1
D. 2,1,2,2,2



Q.19) A binary tree in which every non-leaf node has non-empty left and right sub trees is called a strictly binary tree. Such a tree with 10 leaves
A. Has 19 nodes
B. Has 16 nodes
C. Has 15 nodes
D. None of the above


Q.20) Depth of a binary tree with n node is
A. log (n +1) - 1
B. log (n)
C. log (n -1)n -1
D. log (n) + 1




Q.21) To arrange a binary tree in ascending order we need 
A. post order traversal
B. inorder traversal
C. preorder traversal
D. none of above


Q.22) Average successful search time taken by binary search on sorted array of 10 items is
A. 2.6
B. 2.7
C. 2.8
D. 2.9



Q.23) Hash function f is defined as f(key) = key mod 7. If linear probing is used to insert the key 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6,  11 will be stored at the location
A. 3
B. 4
C. 5
D. 6


Q.24) Average successful search time for sequential search on 'n' item is 
A. n/2
B. (n-1)/2
C. (n+1)/2
D. log (n) + 1


Q.25) Running time of an algorithm T(n), where n is input size is given by T(n) = 8 T(n/2) + qn, if n>1 T(n) = p, if, n=1 where p and q are constants. The order of algorithm is
A. n2
B. nn
C. n3
D. n


Q.26) 6 files X1, X2, X3, X4, X5, X6 have 150, 250, 55, 85, 125, 175 number of records respectively. The order of storage ot optimize access time is
A. X1, X2, X3, X4, X5, X6
B. X3, X4, X1, X5, X6, X2
C. X1, X3, X2, X4, X5, X6
D. None of the above


Q.27) In above question average access time will be
A. 150
B. 140
C. 55
D. None of the above



Q.28) An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of algorithm is
A. Max(f(n),g(n))
B. Min(f(n),g(n))
C. f(n)+g(n)
D. f(n)*g(n)


Q.29) Bib O notation w.r.t algorithm signifies
A. It decides the best algorithm to solve a problem
B. It determines maximum size of a problem, that can be solved in given system in given time
C. It is the lower bound of growth rate of algorithm
D. None of the above


Q.30) Running time T(n), where 'n' is input size of recursive algorithm is given as follows:
T(n) = c + T(n-1), if n>1, T(n) = d if n<1. The order of algorithm is
A. n2
B. n
C. n3
D. nn


Q.31) Four altorithm A1, A2, A3, A4 solves a problem with order log(n), log log(n), nlog(n), n. Which is best algorithm
A. A1
B. A2
C. A3
D. A4


Q.32) Time complexity of an algorithm T(n), where n is the input size is given by T(n) = T (n-1) + 1/n, if n>1 otherwise T(n) = 1. The order of algorithm is
A. Log n
B. n
C. n2
D. nn


Q.33) Which of the following is correct
A. Internal sorting is used, if number of items to be sorted is very large
B. External sorting is used, if number of items to be sorted is very large
C. External sorting needs auxiliary storage
D. Internal sorting needs auxuliary storage


Q.34) A sorting technique which guarrantees that records with same primary key occurs in the sorted list as in the original unsorted list is said to be
A. Stable
B. Consistent
C. External
D. Linear


Q.35) A text is made up of five characters, T1, T2, T3, T4, T5. The probability of occurance of each character is .12, .4, .15, .88 and .25, respectively. The optimal coding technique will have average length of 
A. 2.15
B. 3.01
C. 2.3
D. 1.78



Q.36) If running time of an algorithm is given by T(n) = T(n-1) + T(n-2) + T(n-3), if n>3 otherwise T(n)=n, what should be relation between T(1), T(2), T(3) where algorithm order become constant
A. T(1)=T(2)=T(3)
B. T(1) + T(2) = 2T2
C. T(1) - T(3) = T(2)
D. T(1) + T(2) = T(3)


Q.37) Arranging a pack of cards by picking one by one is an example of
A. bubble sort
B. selection sort
C. insertion sort
D. merge sort



Q.38) In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible
A.
------------
 | 4 | 6 |
------------
B.
------------
| 5 | 4 | 6 |
------------
C.
------------
 | 9 | 6 |
------------
D.
------------
| 9 | 3 | 2 |
------------


Q.39) The order of an algorithm that finds whether a given boolean function of 'n' variable produces a '1' is
A. constant
B. linear
C. logarithmic
D. exponential



Q.40) The average number of comparisions performed by merge sort alrotithm in merging two sorted list of length 2 is
A. 8/3
B. 8/5
C. 11/7
D. 11/6



Q.41) To arrange the books of library the best method is
A. Bubble sort
B. Quick sort
C. Merge sort
D. Heap sort



Q.42) Which of the following algorithm has n  log (n) time complexity
A. Heap sort
B. Quick sort
C. Insertion sort
D. Selection sort



Q.43) Which algorithm solves all pair shortest path problem
A. Dijkastra's algorithm
B. Floyd's algorithm
C. Prim's algorithm
D. Worshal's algorithm




Q.44) The centricity of node labeled 5 is

A. 6
B. 7
C. 2
D. 5



Q.45) The information about an array used in a program will be stored in
A. Symbol table
B. Dope vector
C. Register vector
D. Activation table



Q.46) In which of the following cases linked list implementaion of sparse matrices consumes same memory as a normal array
A. 5 x 6 matrix with 9 non-zero entries
B. 5 x 6 matrix with 8 non-zero entries
C. 6 x 5 matrix with 8 non-zero entries
D. 6 x 5 matrix with 9 non-zero entries


Q.47) The advantage of sparse matrix linked list representationn over dope vector method is, that the former is
A. Conceptually easier
B. Completely dynamic
C. Efficient in accessing an entry
D. Efficient if the sparse matr4ix is a band matrix



Q.48) If the address of (I,J)th entry, in dope vector representation, where it stores the position of first and last non-zero entries of each row is given by C, assume l(n) and f(n) represent the last and first non-zero entries in row x
i.

 

ii.

iii.

iv.

A. Correct answer is (i)
B. Correct answer is (ii)
C. Correct answer is (iii)
D. Correct answer is (iv)



Q.49) On which principle does stack work?
A. FILO
B. FIFO
C. LIFO
D. Both a and c above



Q.50) The order of binary search algorithm is
A. n
B. n2
C. n log n
D. log n