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
Any order
      _____________________________________________________________________________________
Time complexities of three algorithms are given. Which should execute the slowest for large values of N?

( 1 2 ) O N
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 ?

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
      _____________________________________________________________________________________
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 

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)
      _____________________________________________________________________________________
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–
      _____________________________________________________________________________________
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
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
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

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
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
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
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
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
Previous Post Next Post