Register

Test by Bikram | Algorithms | Test 2 | Question: 13

• retagged by
595 views

2 Answers

Best answer
1 1 vote

We can start either from vertex 4 or from vertex 6 because only these 2 have no incoming edge.

Therefore option B , D will be considered 

Starting from vertex 4, next vertex can be 5 or 6.(order: 4)

considering vertex 5, next vertex can be 2 or 6 (order: 4,5)             |    considering vertex 6, next vertex can be 5.(order:4,6)

considering vertex 6, next vertex can be 2(order: 4,5,6)                   |    considering vertex 5, next vertex will be 2.(order:4,6,5)

                               or                                                                                 |    considering vertex 2, next vertex can be 1,3(order:4,6,5,2)

considering vertex 2,next vertex can be 6(order:4,5,2)                     |  finally correct order can be (4,6,5,2,3,1) or (4,6,5,2,1,3)

considering order 4,5,6 next vertex 2: order(4,5,6,2)                        | no option

considering order 4,5,2, next vertex 6 : order (4,5,2,6)                     |

considering order(4,5,6,2)or(4,5,2,6) ,next vertex can be 1,3           |

finally correct order can be (4,5,6,2,1,3) or (4,5,6,2,3,1) or (4,5,2,6,1,3),(4,5,2,6,3,1)----------no option

therefore option B is wrong

Starting from vertex 6, next vertex will be 4.(order: 6)

considering vertex 4, next vertex will be 5.(order: 6,4)

considering vertex 5, next vertex will be 2.(order: 6,4,5)

considering vertex 2, next vertex can be 1,3.(order: 6,4,5,2)

finally correct order can be (6,4,5,2,1,3) or  (6,4,5,2,3,1)

The correct ans is option D. (6, 4, 5, 2, 1, 3)

• selected by
0 0 votes
the simple stack operation will be given by :

starting from the vertex 4

stack:(3,1,2,5,4,6) or  (1,2,3,5,4,6)

after popping from the stack : 6 4 5 2 1 3   or 6 4 5 3 2 1

option (D) is correct

Note: In topological sorting,a vertex having maximum incoming edges always at the last position
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Test by Bikram | Alg...Next → · Test by Bikram | Alg...
← Previous in category · Test by Bikram | Alg...Next in category → · Test by Bikram | Alg...
Position:
Show:

Related questions

3 3 votes
2 answers 2 answers
958
958 views
Bikram asked May 26, 2017
958 views
Test by Bikram | Algorithms | Test 2 | Question: 14
Match the following:$\begin{array}{|l|l|l|l|} \hline (1) & \text{Multistage graph} & (P) & \text{Divide and conquer}\\ \hline (2) & \text{Convex hull } & (Q) & \text{Dept...
0 0 votes
1 1 answer
942
942 views
Bikram asked May 26, 2017
942 views
Test by Bikram | Algorithms | Test 2 | Question: 30
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
1 1 vote
2 answers 2 answers
992
992 views
Bikram asked May 26, 2017
992 views
Test by Bikram | Algorithms | Test 2 | Question: 27
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
0 0 votes
2 answers 2 answers
1.3k
1.3k views
Bikram asked May 26, 2017
1,264 views
Test by Bikram | Algorithms | Test 2 | Question: 23
Matrix multiplication is associative and MCS ( matrix chain multiplication ) uses the following matrices:$\begin{array} \text{M1} & 10^* 100 \\ M2 & 100^* 5 \\ M3 & 5^* ...