Aspire Faculty ID #18996 · Topic: UGC NET Computer Science Nov 2020 (Paper II) · Just now
UGC NET Computer Science Nov 2020 (Paper II)

Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$.

Consider the following statements.

Statement I: No edge of $G$ is a cross with respect to $T_D$.

Statement II: For every edge $(u,v)$ of $G$, if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$, then $|i-j|=1$.

In the light of the above statements, choose the correct answer from the options given below:

Solution

Statement I is true.

In DFS of an undirected graph, there are no cross edges.

Edges are generally tree edges or back edges.

So, no edge of $G$ is a cross edge with respect to DFS tree $T_D$.

Statement II is false.

In BFS tree, for every edge $(u,v)$, the depths of $u$ and $v$ differ by at most $1$.

So, the correct condition is:

$|i-j|\le 1$

But the statement says:

$|i-j|=1$

This is not always true because two adjacent vertices can also be at the same level in a BFS tree.

Therefore, Statement I is true and Statement II is false.

Previous 10 Questions — UGC NET Computer Science Nov 2020 (Paper II)

Nearest first
1
Given below are two statements:Statement I: Quality control involves the series of inspections, reviews and tests used …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
2
Assuming that the system call $fork()$ never fails, consider the following C programs $P1$ and $P2$ executed on a UNIX …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
3
Given below are two statements:If two variables $V_1$ and $V_2$ are used for clustering, then consider the following st…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
4
Given below are two statements:Statement I: Bezier curves are curves that interpolate all of their control points.State…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
5
Given below are two statements:Statement I: Hardwired control unit can be optimized to produce fast mode of operation.S…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
6
Given below are two statements:Statement I: $5$ divides $n^5-n$ whenever $n$ is a nonnegative integer.Statement II: $6$…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
7
Consider the following regular expressions:(a) $r=a(b+a)^*$(b) $s=a(a+b)^+$(c) $t=aa^*b$Choose the correct answer from …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
8
Consider the undirected graph below.Using Prim's algorithm to construct a minimum spanning tree starting with node $a$,…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
9
Arrange the following types of Cohesion from best to worst type.(A) Logical Cohesion(B) Sequential Cohesion(C) Communic…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
10
Given below are different properties of $3D$ projections from A-D. Identify the correct order on the basis of property …
Topic: UGC NET Computer Science Nov 2020 (Paper II)

Next 10 Questions — UGC NET Computer Science Nov 2020 (Paper II)

Ascending by ID
1
Given below are two statements:Statement I: The problem "Is $L_1\cap L_2=\phi$?" is undecidable for context sensitive l…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
2
Given below are two statements:Statement I: The laws of nature put two fundamental limits on the data rate of a channel…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
3
Given below are two statements:Statement I: In Caesar Cipher each letter of Plain text is replaced by another letter fo…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
4
Given below are two statements:Statement I: A genetic algorithm is a stochastic hill-climbing search in which a large p…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
5
concern a disk with a sector size of $512$ bytes, $2000$ tracks per surface, $50$ sectors per track, five double-sided …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
6
concern a disk with a sector size of $512$ bytes, $2000$ tracks per surface, $50$ sectors per track, five double-sided …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
7
concern a disk with a sector size of $512$ bytes, $2000$ tracks per surface, $50$ sectors per track, five double-sided …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
8
concern a disk with a sector size of $512$ bytes, $2000$ tracks per surface, $50$ sectors per track, five double-sided …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
9
concern a disk with a sector size of $512$ bytes, $2000$ tracks per surface, $50$ sectors per track, five double-sided …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
10
Consider the following table structures related to a university for the below questions. EMPLOYEE …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
Ask Your Question or Put Your Review.

loading...