Algorithm Solved MCQs- Part 2

http://freepdf-books.com
 Algorithm Solved MCQs- Part 2

A binary tree with 27 nodes has _______ null branches.

54
27
26
None of the above

_________________________________________________________
____________________________
The complexity of multiplying two matrices of order m*n and n*p is

mnp
mnq
mpq
npq

_________________________________________________________
____________________________
A graph is planar if and only if

it does not contain sub graphs homeomorphic to K5 and K3,3

it does not contain sub graphs isomorphic to K5 or K3,3
it does not contain sub graphs isomorphic to K5 and K3,3
it does not contain sub graphs homeomorphic to K5 or K3,3

_________________________________________________________
____________________________
One can convert a binary tree into its mirror image by traversing it in

Inorder
Preorder
Postorder

http://freepdf-books.com
 Any order

_________________________________________________________
____________________________
Time complexities of three algorithms are given. Which should
execute the slowest for large values of N?

(12)ON
O(N)
O(log N)
None of these

_________________________________________________________
____________________________
Which of the following sorting procedure is the slowest?

Quick sort
Heap sort
Shell sort
Bubble sort

_________________________________________________________
____________________________
The space factor when determining the efficiency of algorithm is
measured by

Counting the maximum memory needed by the algorithm

Counting the minimum memory needed by the algorithm
Counting the average memory needed by the algorithm
Counting the maximum disk space needed by the algorithm

_________________________________________________________
____________________________
A hash function f defined as f(key) = key mod 7, with linear probing
used to resolve collisions. Insert the keys 37, 38, 72, 48, 98 and 11
into the table indexed from 0 to 6. What will be the location of 11 ?

http://freepdf-books.com
 3
4
5
6

_________________________________________________________
____________________________
In ______, the difference between the height of the left sub tree and
height of the right tree, for each node, is almost one

Binary search tree

AVL tree
Complete tree
Threaded binary tree

_________________________________________________________
____________________________
A BST is traversed in the following order recursively: Right, root,
left.The output sequence will be in

Ascending order
Descending order
Bitomic sequence
No specific order

_________________________________________________________
____________________________
A sorting technique which uses the binary tree concept such that
label of any node is larger than all the labels in the subtrees, is
called

Selection sort
Insertion sort
Heap sort
Quick sort

http://freepdf-books.com
 _________________________________________________________
____________________________
In order to get the information stored in a Binary Search Tree in the
descending order, one should traverse it in which of the following
order?

Left, root, right

Root, left, right
Right, root, left
Right, left, root

_________________________________________________________
____________________________
If x is a string then xR denotes the reversal of x. If x and y are strings,
then (xy)R =

xyR
yxR
yRx
yRxR

_________________________________________________________
____________________________
When representing any algebraic expression E which uses only
binary operations in a 2-tree,

The variable in E will appear as external nodes and operations in

internal nodes
The operations in E will appear as external nodes and variables in
internal nodes
The variables and operations in E will appear only in internal nodes
the variables and operations in E will appear only in external nodes

_________________________________________________________
____________________________
A sort which uses binary tree concept such that any number is larger
than all the numbers in the subtree below it,is called

http://freepdf-books.com
 Selection sort
Insertion sort
Heap sort
Quick sort

_________________________________________________________
____________________________
Which one of the following is the tightest upper bound that
represents the time complexity of inserting an object into a binary
search tree of n nodes?

O(1)
O(log n)
O(n)
O(n log n)

_________________________________________________________
____________________________
In a Heap tree

Values in a node is greater than every value in left sub tree and
smaller than right sub tree
Values in a node is greater than every value in children of it
Both of above conditions applies
None of above conditions applies

_________________________________________________________
____________________________
In worst case Quick Sort has order

O (n log n)
O (n2/2)
O (log n)
O (n2/4)

_________________________________________________________

http://freepdf-books.com
____________________________
Which of the following algorithms solves the all pair shortest path
problem?

Dijkstra algorithm
Floyd algorithm
Prim algorithm
Warshall algorithm

_________________________________________________________
____________________________
Tree

Is a bipartite graph
With n node contains n-1 edges
Is a connected graph
All of these

_________________________________________________________
____________________________
A graph in which all nodes are of equal degrees is known as

Complete graph
Regular graph
Non regular graph
Multi graph

_________________________________________________________
____________________________
What is the postfix form of the following prefix *+ab–cd

ab+cd–*
abc+*–
ab+*cd–
ab+*cd–

http://freepdf-books.com
 _________________________________________________________
____________________________
Which of the following sorting method is stable?

Straight insertion sort

Binary insertion sort
Shell sort
Heap sort

_________________________________________________________
____________________________
FIRST(1st) TRUE statement in following is

Linear linked list are more space efficient(i.e. require less memory) for
storing a list of 1000 names than having a plain flat array
Linear linked lists are less time efficient(i.e. require more time) for
maintaining (i.e updating) a growing list of over 1000 names (sorted in
alphabetic order) than having a plain flat array
Array are more versatile(i.e dynamically reconstructable) than linked
lists
A data structure with two links offers more geometrical configuration
than data structure with one link

_________________________________________________________
____________________________

A
B
C
D

_________________________________________________________
____________________________

A
B
C

http://freepdf-books.com
 D

_________________________________________________________
____________________________
The complexity of searching an element from a set of n elements
using Binary search algorithm is

O(n)
O(log n)
O(n2)
O(n log n)

_________________________________________________________
____________________________
Assuming P ? NP, which of the following is TRUE?

NP-complete = NP
NP-completenP=theta
NP-hard = NP
P = NP-complete

_________________________________________________________
____________________________
Using the standard algorithm ,what is the time required to determine
that a number n is prime?

Constant time
Quadratic time
Logarithmic time
Linear time

_________________________________________________________
____________________________
The data structure required for breadth first traversal on a graph is

Queue

http://freepdf-books.com
 Stack
Array
Tree

_________________________________________________________
____________________________
A binary tree can easily be converted into q 2-tree

by replacing each empty sub tree by a new internal node

by inserting an internal nodes for non-empty node
by inserting an external nodes for non-empty node
by replacing each empty sub tree by a new external node

_________________________________________________________
____________________________
The number of vertices of odd degree in a graph is

Always zero
Either even or odd
Always odd
Always even

_________________________________________________________
____________________________
The minimum number of multiplications and additions required to
evaluate the polynomial P = 4x3+3x2-15x+45 is

6&3
4&2
3&3
8&3

_________________________________________________________
____________________________
Number of ordered trees with 3 nodes A,B,C is

http://freepdf-books.com
 16
12
13
14

_________________________________________________________
____________________________

A program that checks spelling works in the following way. A hash

table has been defined in which each entry is a Boolean variable
initialized to false. A hash function has been applied to each word in
the dictionary, and the appropriate entry in
the hash table has been set to true. To check the spelling in a
document, the hash function is applied to every word in the
document, and the appropriate entry in the table is examined. Which
of the following is (are) correct?
I. true means the word was int the dictionary.
II. false means the word was not in the dictionary.
III. Hash table size should increase with document size.

I only
II only
I and II only
II and III only

_________________________________________________________
____________________________
Id one uses straight two way merge sort algorithm to sort the
following elements in ascending order
20,47,15,8,9,4,40,30,12,17
then order of these elements after the second pass of the algorithm
is

8,9,15,20,47,4,12,17,30,40
8,15,20,47,4,9,30,40,12,17
15,20,47,4,8,9,12,30,40,17

http://freepdf-books.com
 4,8,9,15,20,47,12,17,30,40

_________________________________________________________
____________________________
The upper bound of computing time of m coloring decision problem
is

O(nm)
O(nm)

O(nmn)
O(nmmn)

_________________________________________________________
____________________________
Leaves of which of the following trees are at the same level ?

Binary tree
B-tree
AVL-tree
Expression tree

_________________________________________________________
____________________________
Quick sort is also known as

Merge sort
Heap sort
Bubble sort
None of these

_________________________________________________________
____________________________
If every node u in G is adjacent to every other node v in G, A graph is
said to be

Isolated

http://freepdf-books.com
 Complete
Finite
Strongly Connected

_________________________________________________________
____________________________
The pre order and post order traversal of a Binary Tree generates the
same output. The tree can have maximum

Three nodes
Two nodes
One node
Any number of nodes

_________________________________________________________
____________________________

A
B
C
D

_________________________________________________________
____________________________
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an
undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an
undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic
polynomial time algorithm to solve A.

1,2 and 3
1 and 2 only
2 and 3 only

http://freepdf-books.com
 1 and 3 only

_________________________________________________________
____________________________
A simple graph in which there exists an edge between every pair of
vertices is called

Complete graph
Euler graph
Planar graph
Regular graph

_________________________________________________________
____________________________
Two isomorphic graphs must have

Equal number of vertices

Same number of edges
Same number of vertices
All of the above

_________________________________________________________
____________________________
The Worst case occur in linear search algorithm when

Item is somewhere in the middle of the array

Item is not in the array at all
Item is the last element in the array
Item is the last element in the array or is not there at all

_________________________________________________________
____________________________
The most common hash functions use the__________to compute
hash address.

Division method

http://freepdf-books.com
 Union method
Subtraction method
None of the above

_________________________________________________________
____________________________
If h is any hashing function and is used to hash n keys in to a table of
size m, where n<=m, the expected number of collisions involving a
particular key x is

less than 1
less than n
less than m
less than n/2

_________________________________________________________
____________________________
If each node in a tree has value greater than every value in its left
subtree and has value less than every in the its right subtree ,the tree
is called

Complete tree
Full binary tree
Binary search tree
Threaded tree

_________________________________________________________
____________________________
Every cut set of a connected euler graph

No such characterization
Atleast three edges
An even number of edges
An odd number of edges

http://freepdf-books.com