MCA-3, Algorithm and Graph Theory
Note : Answers are at the end of this paper.
1. The
space requirement S (p) of any algorithm p may be written as ………….
A) T
(P) = c + Tp B) S (P) = c + Sp C) S (P) = Sp D) S (P) = T (P) + C+SP
2.
The total number of steps required by the algorithm is determined to be ……….
A) 2n B) 3n + 2n C) 2n + 2 D) 2n + 3
3. A data
structure known as ………… in which a location of an item is determined directly
as a function of the item itself, rather than a sequence or trail and error
comparisons
A) Stack B) Queue C) Heap D) Hash-table
4. An Average
case element comparison in max and Min. Algorithm is ……………
A) n - 1 B) 2( n – 1 ) C) 3( n - 1) D) None of
the above.
5. In ……….. the
division into two sub arrays is made so that the sorted sub arrays do not need
to merg later.
A) Quick sort B) Merge
sort C) bubble sort D) Heap
sort
6. The time
complexity of merge sort is ………….
A) O (n log n) B) O
(n2) C) n log n D) O (n3)
7. ……….. Algorithm
determined the length of the shortest path from v0 to all other vertices in G
A) Dijkstra’s algorithm B) Knapsack algorithm C) Greedy
algorithm D) None of the above
8. The Greedy
method simply requires storing the problems in non decreasing order to their
lengths. This ordering can be carried out in ----
A) O (log n) B) n
O (log n) C) O (n log n) D) None of the
above
9. The Greedy
Knapsack algorithm requires ---------- time.
A) O (n)
B) O (n log n) C) O (n2) D) O (n3)
10 Computing time
for Tree is ----------
A O (1) B)
(n2) C) O (n log n) D) Dashed
11. A
multistage graph G = (V, E) is a ---------in which the vertices are partitioned
into 2 disjoint sets
A) Undirected graph B) Directed
graph C) Multistage
graph D) None of the above
12. ----------
States that satisfiability is in p if and only if p = NP
A) Cook’s algorithm B) Euler
algorithm C) Crock algorithm D) Kook’s algorithm
13. Determining
whether a planer is three colorable is --------
A) NP complete B) NP-hard C) Both A) &B) D) None of the above
14. Obtaining
whether a planer graph is three colorable Is ------
A) NP-hard
B) NP complete C) Both A) &B) D) None
of the above
15. The
total number of edge in G is --------------
A) n
(n+1)/2 B) n
(n-1)/2 C) (n-1)/2 D) (n+1)/2
16. Sub
graphs that do not even have vertices in common are said to be --------
A) Vertex disjoint B) Edge disjoint C) Vertex joint D) Edge
joint
17. Every
connected graph has at least on --------
A) Tree B) Spanning
Tree C) Graph
D) None
of the above
18. The
total number of different Hamiltonian Circuits in a complete graph on n
vertices can be shown to be
A) n!/2 B) (n+1)!/2
C) (n-1)!/2 D) None of the above
19. A
graph consisting of only isolated vertices is ------
A) 1-chromatic B) 2- chromatic C) 3-chromatic
D) r-
chromatic
20. A--------is
the expression of an algorithm in a programming language.
A) Program
B) Software
C) Computational procedures D) None
of the above
21. The
-------- of a node all the nodes along the path froth the root to that node.
A) Forest B) Siblings C) Degree
D) Ancestors
22. An
optimal a job, one has to process the job on a machine for ---------- unit of
time.
A) Maximum B) Minimum C) Equal D) None
of the above
23. The greedy method for knapsack problem
takes ------ time to determine the solutions
A) O(n2)
B) O(n log n) C) n log n D) O(n2)
24. In
dynamic programming --------- sequences may be generated.
A) One decision B) Two decision C) Many decision D) Only
one
25. The
average number of comparison in an unsuccessful binary search using divide and
conquer method is
A) U(n)=1+1/n B) U(n)=1+E/n C) U(n)=E/(n+1)
D) U(n)=I/(n+1)
26. The
average case to find the maximum element in a set of n elements is
A) (n-1) comparisons B) 2(n-1) comparisons
C) 3(n-1) comparisons D) 3(n-1) comparisons
27. O
(2n) is called
A) linear
B) Quadratic C) Cubic
D) Exponential
28. In
the worst case, the time taken to insert a new element in a heap of n elements
is
A) O(n)
B) O(n 2) C) O( log n)
D) O(n log n)
29. For
quick sort, the worst-case time is
A) O(n)
B) O(n 2) C) O(n log n) D) O( log n)
30. The
greed knapsack algorithm requires time.
A) O (n) B) Ө (n) C) Ω(n) D) None
of these
31. The
worst case complexity for traveling salesperson is
A) O(n22) B) O(n222) C) O(n22n) D) O(n
log n2)
32. Obtaining
minimum finish time schedule on m, m >= 2, identical processors is ---------
A) NP complete B) NP-hard
C) Lower boundary D) Ordered
searching
33. The
total number of different Hamiltonian circuits in a complete graph of five
vertices is -------
A) (n-1)/2 B) (n-1)!
C) (n-1)!/2 D) 2(n-1)!
34. A
drawing of a geometric representation is called -------
A) Debugging B) embedding C) Geometric
graph D) Planar
graph
35. ---------
states that a connected planar graph with n vertices and e edges has e-n+2
regions.
A) Kurtosis first graph B) Kurtosis
2nd graph
C) Euler’s formula D) Chromatic
polynomial
36. a
complete asymmetric digraph of n vertices contains ---------edges.
A) n(n-1) B) n(n-1)/2 C) (n-1)/2 D) (n-1)!
37. The
length of the path is?
A) No of circuits B) Number
of loops
C) No of vertices D) No
of edges
38. A
disconnected graph with _______component has a spanning forest consisting of k
spanning trees
A) k B) k-1 C) (k-1)/2 D) k(k-1)/2
39. The
total no of different Hamiltonian circuits in a complete graph of n vertices
are
A) (n-1)/2 B) (n-1)! /2 C) (n-1)/2!
n (n-1)!/2
40. A
Connected planar graph with n vertices and e edges has ----------- regions
A) e-n+2 B) n-e+2 C) e+n-2 D) n+e-2
41. The
vertices of every planar graph can be properly colored with------- colors
A) 3 B) 4
C) 5 D) any
42. Which algorithm
traverses the edges of a given such that every edge is traversed exactly once
and each vertex is visited at least once.
A) Depth-first-search B) Breadth-first-search
C) Planarity testing D) Circuit-path
decomposition
43. If
more than one edge is associated within given pair of vertices, it is referred
as
A) Self loop B) Loop C) Parallel edge D) Hamiltonian edge
44. What
does the following program do?
1) # define MAX_CHAR 10 //maximum key
length
2) # define TABLE_ SIZE 13
3) typedef struct
4) {
5) Char key [MAX_CHAR];
6) //other fields
7) } element
8) Element ht [TABLE_SIZE];
A) Creation of hash function transforms B) Hash table creation
C) Apple of the Hash function D) Hash table initialization
45. For
Quick sort, the worst-case time is ------- the average time is only -----
A) O (n), O(n log n) B) O(n
log n), C) O (n log n),O (n2) D) O(n2), O(n log n)
46. Identify
the following statement is true or false
a) In greedy method many decision sequence
is generated
b) In dynamic programming only one
decision sequence is generated
A) a-true, b-true B) a-true, b-false C) a-false,
b-false D) a-false, b-false
47. In branch and
terminology, a BFS like state space search will be called __________search as
the list of live node is _______list
A) FIFO,FIFO B) LIFO,LIFO C) FIFO,LIFO D) LIFO,LIFO
48. Identify the following
theorems are true or false
a) The clique problem is polynomials
transformable to the vertex cover problem.
b) The bin packing problem is NP-hard
A) a-t, b-f B) a-f, b-t C) a-f,
b-t D) a-f,
b-f
49. Hamiltonian
circuit in a graph of --------- vertices consists of exactly --------edges
A) n, n B) n-1,n-1 C)
n, n-1 D)
n-1, n
50. Every planar graph is ---------colorable and
bipartite graph is ---------- colorable
A) 2,4 B) 4,2 C) 2,2 D) 4,4
51. The traveling
sales person and the knapsack problems for witch the best algorithms have
Complexities
---------and ---------respectively
A)
O(n22n),O(2 n/2) B)
O(2 n/2),O(n22n) C) O(n22n)/2,
O(2 n/2)/2 D) none of the above
52.
Expand MRT
A) More retrieval time B) Maximum retrieval time
C) Mean Retrieval time D) minimum retrieval time
53. From
the following pick the true statement
i) Euler graph is always connected except
.for any isolated vertices the graph may have
ii) A given connected graph G is
Euler
iii) A connected graph is a Euler graph is
a if and only if it ca be decomposed into circuits.
iv) An Euler graph G is arbitrarily
traceable from vertex v in G if and only if every circuits.
A) i B) i, iv C) i, iii,iv D) i, ii,iii,iv
54. Let
G = (V, E) be an undirected connected graph. A sub graph T = (V, E) of g is a
spanning tree of G, ___
A) If T is a tree B) Iff T is a
tree C) If T is a sub graph D) None of the above
55. To
formulate a greedy- based algorithm p is the sum of the ___ and ____
A) Multistage solution B) Optimization measure
C) Multistage solution & optimization
measure D) Optimal solution
56. If
f (n) is the time for some algorithm, then we write ____ to mean that g (n) is
a lower bound for f(n).
A) l f(n)l ( l g(n) l B) f(n)=
g(n) C) f(n) = (g(n)) D) None of
the above
57. Constrains
in back tracing method are divided into two categories are ____ & _____.
A) Implicit, explicit B) Internal,
external C) DML, DDL D) User define, system defined
58. Which
of the followed are true?
1) Part is a open walk.
2) No vertex appears more than once
3) No edge traversed more than once
4) Path does not intersect if self
A) 1, 2 and 3 B) 1,3and 4 C) 2,3
and 4 D) All of the above
59. Which
of the following statements are true?
1) A given connected graph G is Euler
graph If and only if all vertices of G are of odd degree.
2) A connected graph G is an Euler
Graph if and only if it can be decomposed into components
3) An Euler graph
G is arbitrarily traceable from any vertex in G if and only if every component
in g contains v.
A) 2 and 3 B) 1
and 3 C) All
of the above D) None of the above
60 About
incidence matrix A, which observation are true?
1) Two groups G1 & G2
are isomorphic if & only if their incidence matrices A (G1)
& A(G2) are same by permutation of rows and columns
2) A row with all Os, represent an
isolated vertex
3) Parallel edge in a graph produces
identical columns in its incidence matrix
A) 1 and 2 B) only 2 C) 1
and 3 D) All
of above
61. How
do you check that the queue is empty?
A) Front = = 0 B) rear = = 0 C) front
= = rear D) front = = rear mod m
62. The
complexity divide and conquer algorithm is given by the recurrence of the form
A) T (n) = {aT (n/b) +f (n) n > 1 C) T (n) = {T (an/b) +f (n) n > 1
B) T (n) = {aT (an/b) +f (n) n > 1 D) T (n) = {aT (n/b) +f (n) n > 1
63. Witch
of the following is true?
1. All NP – complete problems are NP- hard
2. Some NP- hard are not know to be NP-
complete
3. NP-hard
problem can be solved in polynomial time if and only if all other NP-complete
problem can be solved in polynomial time
A) 1 and 2 B) 2
and 3 C) 1
and 3 D) All
of the above
64 Which
of the following is true for tress?
1. A spanning tree is the minimal tree of
a graph
2. Spanning tree is defined only for a
connected graph
3. Each component of a disconnected graph
has a spanning tree
4. A disconnected graph with k component
has a spanning forest consisting of k-1 spanning trees
A) 1 and 2 B) 2 and 3 C) 1
and 4 D) All of the above
65. Which
of the following is true?
A) O(1)<O(log n )<O(n )<O(n log
n)<O(n2)<O(n3)<O(2n)
B) O(1)<O(n)<O(log n )<O(n log
n)<O(n2)<O(n3)<O(2n)
C) O(1)<O(n)<O(log n )<O(n log
n)<O(2n)<O(n2)<O(n3)
D) O(1)<O(log n )<O(n )<O(n log
n)<O(2n)<O(n2)<O(n3)
66. for
the given algorithm to insert an element into a heap. What is the error in the
algorithm?
1) Algorithm Insert (a, n)
2) {
3) //Insert a[n] into the heap which is
stored in a [1:n-1)]
4) i: =n; item: = a[n];
5) While ((item > 1) and (a [ei /cu^]
< item)) do
6) {
7) a[i]:=a[i/2]; i = [I /2];
8) }
9) a[i]: = item; return true;
10) }
A) Line 5 B) Line 4 C) Line
6 D) No
Error
67. Related
to typed of digraphs state whether the following statements are true or false
a. Digraphs in which for every edge (a,
b) there is also an edge (b,a) is Asymmetric Digraph
b. Digraphs that have at most one directed edge between a pair of vertices, but are allowed to have self
b. Digraphs that have at most one directed edge between a pair of vertices, but are allowed to have self
Loops are called antisymmetric
c. A digraph that has self loop or parallel
edges is called a simple digraph
d. A complete symmetric digraph is a simple digraph
is a simple digraph in which there is exactly one
Edge between every pair of vertices
A) a- True, b- True, c-True, d-True B) a-
True, b- True, c-False, d-True
C) a- False, b- False, c-False, d-False D) a-
True, b- False, c-False, d-True
68. State
whether the following statements are true or false
a.A problem that is NP- Complete has the
property that it can not be solved in polynomial time if any
Only if all
Other NP- complete problem can also
be solved in polynomial time
b.
If an NP-hard problem can be solved in
polynomial time, then all NP- complete problem can be solved in
Polynomial time
c. All NP- complete problem are
NP-hard, but some NP-hard problem are to be NP-Complete
d. The Clique problem is NP- Complete
A) a- T, b – F, c – T, d – F B) a- F, b – F, c – T, d – T
C) a- T, b – F, c – F, d – T C) a- F, b – T, c – F, d – T
69. A
Bipartite Graph is
1. Its vertex set v can be decomposed into
disjoint subsets V1 and V2 such every edge in G joins a
Vertex in V1 with a vertex in V2.
2.
A tree
3.
Can have self loop.
4.
2- Colorable.
A.) 1, 2,3 only B) 2,
3, 4 only C) 1, 2, 4 only D) All
of the above
70. Properties
common to the two graphs of kuraltowski. These are
1. Both are regular graphs.
2. Both are planar.
3. Removal of one edge or a vertex makes
each a non planar graph.
4. Kuratowki’s first graph is the planar
graph with the smallest number of vertices
5. Planer graph with the smallest number
of edges.
A) 1- only B) 1, 2,
3, only C) 1, 2 only D) All of
the above
71. Which
of the following are true?
1. An algorithm is a infinite set of
instructions that, if followed, accomplishes particular task
2. Program that are definite and effective
are also called Computational procedures
3. A program is the expression of
computational procedures in a programming language results
4. Occurred if so, to correct them I
5. Debugging is the process of executing a
correct program on data sets and measuring the and
space it takes to compute the results
A) 2, 3, 4, 5, only B) 1,
2, 3, 4, only C) 4, 5 only D) All of the above
72. Identify
the following properties of trees which are correct
1. There is one and only one path between
every pair of vertices in a tree.
2. If in a graph G there is one and only
one path between every pair of vertices, G is a tree
3. A tree with n vertices has n edges
4. Any connected graph with n vertices and
n-1 edges is a tree
5. A graph is a tree if and only if is
maximally connected
6. A graph G with n vertices, n-1 edges,
and no circuit is connected
A) 1, 2, 4, 6 B) 1, 2, 3,
4, C) 1, 3, 4, 5, 6 D) All of the above
73. In
the following algorithm which algorithm does the deletion of an element from
the Queue?
A) 1. Algorithm DeleteQ (item)
2. {
3. rear : = (rear + 1) mode n;
4.
item : = q[rear]
5. return true :
6. }
B) 1. Algorithm DeleteQ(item)
2. {
3. q[rear]: = item
4. return true: 5.
}
C) 1. Algorithm DeleteQ(item)
2. {
3. q[rear] := item
4.return
true:
5. }
D) 1. Algorithm DeleteQ(item)
2. {
3. front := (front + 1) mode n;
4.
item := q[front]
5. return true;
6. }
74. Which
of the following are instances of trees
1. The genealogy of family
2. A river with it tributaries and sub
tributaries
3. The sorting of mail according to zip
code and the punched cards
4. The family is represented by means of
graph
A) 1, 2, 4 only B) 2,
3, 4 only C) 1, 2, 3 only D) All
of the above
75. Match
the following
SET
A
a.
Input b. output c. Definiteness
d. Effectiveness
SET
B
1. Zero or more quantities are externally
supplied
2. At least one quantity is produces
3. Each instruction is clear and
unambiguous.
4. Algorithm
should terminates after finite no of times
5. Must be feasible
A) a- 1, b – 2, c – 3, d - 4, e – 5 B) a- 2, b – 1, c – 3, d - 4, e – 5
C) a- 1, b – 2, c – 4, d - 3, e – 5 D) a- 2, b – 1, c – 4, d - 3, e - 5
76. Choose
the valid algorithm for creation for creation of hash function transform.
A) int transform ( char * key )
{
Int number = 0
Number
+ = * key ++ ;
Return(number);
}
B) int transform ( char * key )
{
Int
number = 0
Number
+ = *&key ++ ;
Return(number);
}
C) int number = 0;
{
Int number = 0
Number + = * *key ++ ;
Return(number);
}
D) int transform ( char * key )
{
Int number = 0
*key ++ = number
Return(number);
}
77. Match
the following
SET
A
a. simple graph b. self graph c. simple digraphs d. Asymmetric digraphs
SET
B
1. An edge having the same vertex as both
its end vertices.
2. Graph that has neither self – loops nor
parallel edges.
3. A digraph that has no self – loop or
parallel edges
4. Digraphs in which for every edge (a,b)
there is also an edge (b,a)
5. digraphs that have at most one directed
edge between a pair of vertices.
78. Match
the following.
a.
Queue 1. Computes remainder
b.
Hashing 2. Describes
hash table creation.
c.
Heap 3. An ordered list
d.
Built in module operator 4. Used to provide faster searching
5. A complete
blinary tree
A) a – 3, b -4, c -5, d – 1 B)
a – 3, b -2, c -4, d – 1
C) a – 3, b -4, c -2, d – 1 D)
a – 1, b -2, c -3, d – 5
79 Select
true statements regarding trees
i There is one and only one path
between every pair of vertices in a tree.
ii A tree with n vertices has n-1 edges.
iii Any connected graph with n vertices
and n- 1 edges is a tree.
iv A graph is a tree if and only if it is
minimally connected.
v.
A graph G with n vertices n-1 edges and
no circuit is connected.
A) i, ii, v B) i,
ii, iv, v C) i, ii, iii, v D) i,
ii, iii, iv, v
80. Select
true statements
i. A graph that can not be drawn on a
without a crossover between its edges is called non- planer
ii Thee complete graph of five vertices
is non – planar
iii A connected planer graph with n
vertices and e edges has e-n+2 regions.
iv The vertices of every planar if there
exists some geometric representation of G.
A) i, ii, iv B) i, ii, iv, v C) i,
ii, iii, iv D) i, ii, iii, v
81. If
the size of p is n and the sizes of the k sub problems are n1, n2,…… ,nk ,
respectively, then the
Computing
time of DANDC is described by the recurrence relation is ______.
A) T(n) = g(n) n small B) T(n) = g(n) n small
2T(n/2) otherwise 2T(n
/ 2) + f(n) otherwise
C) T(n) = g(n) n small D) T(n) =
g(n) n
small
T(n
/ 2) + f(n) otherwise 2T(n
/ 2) + f(n) otherwise
82. Which
of the following is true?
1. Every graph is its own sub graph
2. A sub graph of need not be a sub graph
of g(where gis a sub graph of G)
3. A single vertex in a graph G is a sub –
Graph of G
4. A single edge in G together with its
end vertices is a sub graph of G
A) 2, 3 and 4 B) 1, 2, and 3 C) 1, 3, and 4 D) All of the above
83. Which
of the following problem can be solved using ordering paradigm of greedy
method?
1. Optimistic storage on tapes 2. Knapsack problem
3. Job sequencing with deadlines 4. Optimal
merge pattern
5. Single source shortlist paths
A) 1, 2 and 3 B) 2,
3 and 4 C) 1, 4 and 5 D) 3,
4 and 5
84. Choose
the correct code to insert an element into a circular queue.
A) If (rear = n – 1) than rear: = 0 B) If (rear = n ) them rear : = 1
Else
rear = rear + 1 Else
rear = rear + 1
C) If (rear = n + 1) them rear: = 0 D) If
(rear = n ) them rear = 1
Else rear = rear + 1 Else
rear = rear - 1
85. The
asymptotic complex of the given algorithm is
Algorithm
Sum (a,n)
{
S:
0.0;
For
I : = 1 to n do
S:
= s + a [I];
return
s;
}
A) q(1) B) q(n) C) q(n2 ) D) q(2n+3)
86. Which
of the following is false for trees?
1. A graph G with n vertices, n-1 edges
with circuit is a tree
2. it is a connected graph
3. There should be one and only one path
between every pair of vertices of the graph
A) 2 and 3 B) only 2 C) only
1 D) All
of the above
87. Using the
greedy algorithm for sequencing unit time jobs with deadlines and profits, such
that n = 5, (P1, P2, P3, P4, P5) = 20, 15, 10, 5, 1) and (d1, d2, d3, d4, d5) =
(2, 2, 1, 3, 3). The optimal solution is
A) J= {1, 2, 3} with profit of 45 B) J= {1, 2,
4} with profit of 40
C) J= {1, 2, 3, 4} with profit of 30 D) J= {3, 4, 5} with profit of 16
88. Using the
Knapsack algorithm where number of object is 3, capacity of Knapsack is 20.
Profits, such that (P1, P2, P3) =
(25,24,15) and weights(w1, w2, w3) = (18,15,10).Using Greedy method, the
optimal solution is
A) (1/2, 1/3, ¼) B) (1, 2/15, 0) C) (0, 2/3, 1) D) (0,
1, ½)
89. The average
number of element comparison for successful search using divide and conquer
method is,
A.) ( 1+ n) B) 1 + I/n C) E/(n+1) D)
I + E/n
90. Which of the
following are true for trees?
1) There is one and only one path
between every pair of vertices in a tree.’
2) A tree with n vertices has n edges.
3) A graph is a tree if and only if it
is minimally connected.
A. 1 and 2 B) 2 and 3 C) 1
and 3 d) 1,2
,and 3
91. Given the
following algorithm, determine the step count.
Algorithm Sum
( a, n)
{
S
= 0.0;
For
I : = 1 to n do
S
: = S + a[i];
Return S;
}
A).n+1 B).2n + 1 C)n + 3 D)2n + 3
ANSWER:
- b
- d
- d
- c
- a
- a
- a
- d
- a
- c
- d
- a
- b
- a
- b
- a
- b
- b
- a
- a
- d
- b
- b
- c
- c
- d
- d
- c
- b
- a
- c
- b
- c
- d
- c
- b
- d
- a
- b
- a
- c
- a
- c
- b
- d
- d
- a
- c
- c
- b
- a
- c
- c
- b
- c
- c
- a
- b
- d
- b
- b
- d
- a
- b
- a
- a
- b
- d
- c
- d
- a
- a
- d
- d
- a
- a
- c
- a
- d
- d
- b
- c
- c
- a
- b
- c
- a
- b
- b
- c
- d
No comments:
Post a Comment