Register

UPPCL AE 2018:56

• recategorized by
218 views
0 votes
0 votes

The Adjacency matrix of a directed graph $\text{G}$ is given below.

$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a &  0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ c & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ d & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ e & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ f & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ g & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ h & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ i & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{array}$

Which of the following is a valid topological sort of $\text{G}$?

  1. $(c, h, a, d, e, f, i, g, b)$
  2. $(h, e, i, f, c, d, a, b, g)$
  3. $(h, c, a, e, f, d, i, g, b)$
  4. $(c, a, d, e, f, g, h, i, b)$
• recategorized by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
admin asked Jan 5, 2019
296 views
UPPCL AE 2018:72
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution: $T(n) = O(\sqrt{n})$ $T(n) = O(\log n)$ $T(n) = O(n^{1/\log n})$ $T(n) = O(\log \log n)$
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution:$T(n) = O(\sqrt{n})$$T(n) = O(\log n)$$T(n) = O(n^{1/\log n})$$T(n) = O(\log \lo...
User Avatar
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
396 views
UPPCL AE 2018:55
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is $\Theta(n \log n)$ $\Theta(n/ \log n)$ $\Theta(1)$ $\Theta(\log n)$
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is$\Theta(n ...
User Avatar
0 votes
0 votes
1 answer
3
admin asked Jan 5, 2019
321 views
UPPCL AE 2018:53
Consider a hash table of size $7$ implemented using an array $A[0 \dots 6].$ A modulo hash function $\text{(MOD 7)}$ is used to map the keys, and open addressing is used to handle collisions. If $53, 32, 43, 51, 99$ ... $\text{EMPTY}, 43, 51, 99, 53, 32, \text{EMPTY}$ $\text{EMPTY}, 43, 99, 51, 32, 53, \text{EMPTY}$
Consider a hash table of size $7$ implemented using an array $A[0 \dots 6].$ A modulo hash function $\text{(MOD 7)}$ is used to map the keys, and open addressing is used ...
User Avatar
0 votes
0 votes
1 answer
4
admin asked Jan 5, 2019
495 views
UPPCL AE 2018:46
Which one of the following algorithms cannot sort $n$ numbers in $O(n)$ comparisons? Counting sort Radix sort Heap sort Bucket sort
Which one of the following algorithms cannot sort $n$ numbers in $O(n)$ comparisons?Counting sortRadix sortHeap sortBucket sort
User Avatar
Link Copied!