CS502 - Fundamentals of Algorithms Online Solved Quizzes/MCQ's File No 1



In in-place sorting algorithm is one that uses arrays for storage :
Select correct option:
An additional array
No additioanal array
Both of above may be true according to algorithm
More than 3 arrays of one dimension.
 

 Vukwl- Virtual Education Solution


Which sorting algorithn is faster :
Select correct option:
O(n^2)
O(nlogn)
O(n+k)
O(n^3)

 In in-place sorting algorithm is one that uses arrays for storage :
An additional array
No additional arrayBoth of above may be true according to algorithm
More than 3 arrays of one dimension.
 The running time of quick sort depends heavily on the selection of
No of inputs
Arrangement of elements in array
Size o elements
Pivot element 
In stable sorting algorithm
One array is used
In which duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative position after sorting.
 Which sorting algorithn is faster :
O(n^2)
O(nlogn)
O(n+k)O(n^3) 
 
In stable sorting algorithm:
Select correct option:
One array is used
In whcih duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative posistion after sorting.
 


Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
right-complete
tree nodes
tree leaves

Sieve Technique can be applied to selection problem?
False

A heap is a left-complete binary tree that conforms to the ___________
increasing order only
decreasing order only
(log n) order

A (an) _________ is a left-complete binary tree that conforms to the heap order
binary tree
binary search tree
array



Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
Selection

In Sieve Technique we do not know which item is of interest

False
 
Counting sort has time complexity:
Select correct option:
O(n)
O(n+k)
O(k)
O(nlogn)

Counting sort is suitable to sort the elements in range 1 to k:
Select correct option:
K is large
K is small
K may be large or small
None
 
 
Memoization is :
Select correct option:
To store previous results for further use.
To avoid unnecessary repetitions by writing down the results of recursive calls and looking them again if needed later
To make the process accurate.
None of the above

 Vukwl- Virtual Education Solution

 
The running time of quick sort depends heavily on the selection of
Select correct option:
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements
 
Which may be stable sort:
Select correct option:
Bubble sort
Insertion sort
Both of above



Memorization is?
1. To store previous results for future use
2. To avoid this unnecessary repetitions by writing down the results of
recursive calls and looking them up again if we need them later
3. To make the process accurate
4. None of the above

Which sorting algorithm is faster
1. O (n log n)
2. O n^2
3. O (n+k)
4. O n^3

Quick sort is
1. Stable & in place
2. Not stable but in place
3. Stable but not in place
4. Some time stable & some times in place

One example of in place but not stable algorithm is
1. Merger Sort
2. Quick Sort
3. Continuation Sort

4. Bubble Sort


 
In Quick sort algorithm,constants hidden in T(n lg n) are
Select correct option:
Large
Medium
Not known
small


In in-place sorting algorithm is one that uses arrays for storage :
 An additional array
No additioanal array
Both of above may be true according to algorithm
More than 3 arrays of one dimension.
Which sorting algorithn is faster :
O(n^2)
O(nlogn)
O(n+k)
O(n^3)

What algorithm technique is used in the implementation of Kruskal solution for the MST?
Greedy Technique   Divide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques
 Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few
TrueFalse
A digraph is strongly connected under what condition?
A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v .
A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa.A digraph is strongly connected if for at least one pair of vertex u, v e V,  u can reach v and vice versa.
A digraph is strongly connected if  at least  one third pair  of vertices u, v e V, u can reach v and vice versa.
 The relationship between number of back edges and number of cycles in DFS is,
Both are equal
Back edges are half of cycles
Back edges are one quarter of cycles
There is no relationship between no. of edges and cycles
 What algorithm technique is used in the implementation of Kruskal solution for the M     ST?
Greedy Technique Divide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques

The running time of quick sort depends heavily on the selection of
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements
Which may be stable sort:
Bubble sort
Insertion sort
Both of above


For the Sieve Technique we take time
T(nk)T(n / 3)
n^2
n/3

 
Quick sort is
Select correct option:
Stable and In place
Not stable but in place
Stable and not in place
Some time in place and snd some time stable

Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|)



In Quick Sort Constants hidden in T(n log n) are
1. Large
2. Medium
3. Small
4. Not Known

 Vukwl- Virtual Education Solution


Continuation sort is suitable to sort the elements in range 1 to k
1. K is Large
2. K is not known
3. K may be small or large
4. K is small

In stable sorting algorithm.
1. If duplicate elements remain in the same relative position after sorting
2. One array is used
Imrangee
3. More than one arrays are required
4. Duplicating elements not handled
Question # 8 of 10 Total M - 1
Which may be a stable sort?
1. Merger
2. Insertion
3. Both above
4. None of the above

An in place sorting algorithm is one that uses ___ arrays for storage
1. Two dimensional arrays
2. More than one array
3. No Additional Array
4. None of the above

Continuing sort has time complexity of ?
1. O(n)
2. O(n+k)
3. O(nlogn)
4. O(k)

Node of a B- Tree is stored in memory block and Traversing a B-tree
involves ____ page faults?
O (n^2)
O (n)
O (n log n)
O (log n)

The growth of master files and magnetic tapes exploded around the mid
1960
1970
1980
1990

Is an application of information & data
Intelligence
Education
Knowledge
Power

 Vukwl- Virtual Education Solution


Need to synchronize data upon updation is called?
Data Limitation
Data Manipulation
Data Coherence
Data Replication

Suppose the amount of data recorded in an organization is doubled every
year, this is called?
Linear
Quadratic
Exponential
Logarithmic
Imrangee

Relational databases allow you to navigate the data in _____ direction that is
appropriate using the primary, foreign key structure?
Forward
One
Backward
Any

The input to the data warehouse can come from OLTP or transactional
systems or other third party databases.
True
False

Naturally Evolving Architecture occurred when an organization had a
______ approach to handling the whole process of hardware and software
architecture?
Good
Relaxed
Not Relaxed
None

____ modeling technique is more appropriate for data warehousing
Dimensional
Physical
Entity Relationship
None

______ gives total view of an organization?
OLTP
OLAP
Data warehousing
Database
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________. 
Select correct option: 
pointers
constants
variables
functions

 Vukwl- Virtual Education Solution


A (an) _________ is a left-complete binary tree that conforms to the heap order 
Select correct option: 
heap
binary tree
binary search tree
array


Divide-and-conquer as breaking the problem into a small number of 
Select correct option: 
pivot
Sieve
smaller sub problems
Selection


Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree, 
Select correct option: 
left-complete
right-complete
tree nodes
tree leaves

For the sieve technique we solve the problem, 
Select correct option: 
recursively
mathematically
precisely
accurately

A heap is a left-complete binary tree that conforms to the ___________ 
Select correct option: 
increasing order only
decreasing order only
heap order
(log n) order


We do sorting to, 
Select correct option: 
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order

 Vukwl- Virtual Education Solution

How many elements do we eliminate in each time for the Analysis of Selection algorithm? 
Select correct option: 
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements



In Quick sort algorithm,constants hidden in T(n lg n) are
Large
Medium
Not known
Small
 Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solution.No work is needed to combine the sub-arrays, the array is already sorted
Merging the subarrays
None of above.
 There is relationship between number of back edges and number of cycles in DFS
Both are equal.
 Cycles are half of back edges.
 Cycles are one fourth of back edges.
There is no relationship between back edges and number of cycle
 You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?
(V+E) V.E
 V
 E 
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?
?(V + E) ?(V E)
?(V)
?(V^2)
What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?
log (V)V.V
E.E
log (E)



The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
16
10
3231

In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,
linear
arithmetic
geometric 
exponent

For the heap sort, access to nodes involves simple _______________ operations.
arithmetic
binary
algebraic
logarithmic

For the sieve technique we solve the problem,
recursivelymathematically
precisely
accurately

The sieve technique works in ___________ as follows
phases
numbers
integers
routines

Slow sorting algorithms run in,
T(n^2)T(n)
T( log n)

A (an) _________ is a left-complete binary tree that conforms to the heap order
heap
binary tree
binary search tree
array

In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n)
T(n / 2)
log n
n / 2 + n / 4

The sieve technique is a special case, where the number of sub problems is just
5
many
1
few

In which order we can sort?
increasing order only
decreasing order only
increasing order or decreasing order
both at the same time

Analysis of Selection algorithm ends up with,
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

The analysis of Selection algorithm shows the total running time is indeed ________in n,
arithmetic
geometric
lineaorthogonal

How many elements do we eliminate in each time for the Analysis of Selection algorithm?
n / 2 elements (n / 2) + n elements
n / 4 elements
2 n elements

For the heap sort we store the tree nodes in
level-order traversal
in-order traversal
pre-order traversal
post-order traversal
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
pointersconstants
variables
functions
Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
smaller sub problemsSelection

How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n)

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquerdecrease and conquer
greedy nature
2-dimension Maxima
The number of nodes in a complete binary tree of height h is
2^(h+1) – 1
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items
phases
pointers
constant
Memorization is?
To store previous results for future use
To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them laterTo make the process accurate
None of the above
 Which sorting algorithm is faster
O (n log n)
O n^2
O (n+k)O n^3
 Quick sort is
Stable & in place
Not stable but in placeStable but not in place
Some time stable & some times in place 
One example of in place but not stable algorithm is
Merger Sort
Quick SortContinuation Sort
Bubble Sort
 In Quick Sort Constants hidden in T(n log n) are
Large
Medium
SmallNot Known 
Continuation sort is suitable to sort the elements in range 1 to k
K is Large
K is not known
K may be small or large
K is small
 In stable sorting algorithm.
If duplicate elements remain in the same relative position after sortingOne array is used
More than one arrays are required
Duplicating elements not handled
 Which may be a stable sort?
Merger
Insertion
Both above
None of the above
 An in place sorting algorithm is one that uses ___ arrays for storage
Two dimensional arrays
More than one array
No Additional ArrayNone of the above
We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order 
In Sieve Technique we donot know which item is of interest
TrueFalse
 Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
loweraverage
log n 
The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquerdecrease and conquer
greedy nature
2-dimension Maxima
Analysis of Selection algorithm ends up with,
T(n)T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

Dijkstra’s algorithm :
Has greedy approach to find all shortest paths
Has both greedy and Dynamic approach to find all shortest paths
Has greedy approach to compute single source shortest paths to all other vertices Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.
What algorithm technique is used in the implementation of Kruskal solution for the MST?
Greedy TechniqueDivide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques 
Which is true statement in the following.
Kruskal algorithm is multiple source technique for finding MST.
Kruskal’s algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)
Both of above
Kruskal's algorithm (choose best non-cycle edge) is better than Prim's  (choose best Tree edge) when the graph has relatively few edges )
The relationship between number of back edges and number of cycles in DFS is,
Both are equal
Back edges are half of cycles
Back edges are one quarter of cycles
There is no relationship between no. of edges and cycles
Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges
True False
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
O(|V |^2)
O(|V | |E|)O(|V |^2|E|)
O(|V | + |E|)
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2) Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)

What general property of the list indicates that the graph has an isolated vertex?
There is Null pointer at the end of list.
The Isolated vertex is not handled in list.
Only one value is entered in the list.
There is at least one null list.
A dense undirected graph is:
A graph in which E = O(V^2)A graph in which E = O(V)
A graph in which E = O(log V)
All items above may be used to characterize a dense undirected graph
 In digraph G=(V,E) ;G has cycle if and only if
The DFS forest has forward edge.
The DFS forest has back edgeThe DFS forest has both back and forward edge
BFS forest has forward edge
Back edge is:
(u, v) where v is an ancestor of u in the tree.(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None of above
Using ASCII standard the string “abacdaacacwe” will be encoded with __________ bits
64
12896
120
Cross edge is :
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another(u, v) where u and v are either ancestor or descendent of one another. 
Which statement is true?
If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.
Both of above None of above

If you find yourself in maze the better traversel approach will bEA dense undirected graph is:
A graph in which E = O(V^2)A graph in which E = O(V)
A graph in which E = O(log V)
All items above may be used to characterize a dense undirected graph
Which is true statement.
Breadth first search is shortest path algorithm that works on un-weighted graphsDepth first search is shortest path algorithm that works on un-weighted graphs.
Both of above are true.
None of above are true.
Forward edge is:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree.(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
In digraph G=(V,E) ;G has cycle if and only if
The DFS forest has forward edge.
The DFS forest has back edgeThe DFS forest has both back and forward edge
BFS forest has forward edge
 If you find yourself in maze the better traversel approach will be :
BFS
BFS and DFS both are validLevel order
DFS



How much time merge sort takes for an array of numbers? 
Select correct option: 
T(n^2)
T(n)
T( log n)
T(n log n)


The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of, 
Select correct option: 
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima

 Vukwl- Virtual Education Solution


Post a Comment

Previous Post Next Post