Рубрики

Структуры данных и алгоритмы | Комплект 8

Следующие вопросы были заданы на экзамене GATE CS.

1. Рассмотрим следующие функции


Какие из следующих утверждений верно? (GATE CS 2000)

(а) h (n) равно 0 (f (n))
(b) h (n) равно 0 (g (n))
(c) g (n) не равно 0 (f (n))
(d) f (n) равно 0 (g (n))

Ответ (г)
g (n) = 2 √n Log n = n √n

f (n) и g (n) имеют одинаковый асимптотический порядок, и следующие утверждения верны.
f (n) = O (g (n))
g (n) = O (f (n)).

(a) и (b) ложны, потому что n! имеет асимптотически более высокий порядок, чем n √n .


2. Пусть G — неориентированный связный граф с различным весом ребер. Пусть emax будет ребром с максимальным весом, а emin — ребром с минимальным весом. Какое из следующих утверждений является ложным? (GATE CS 2000)

(а) Каждое минимальное остовное дерево группы G должно содержать emin
(б) Если emax находится в минимальном остовном дереве, то его удаление должно отключить G
(c) Ни одно минимальное связующее дерево не содержит emax
(d) G имеет уникальное минимальное остовное дерево

Ответ (с)
(а) и (б) всегда верны.
(в) ложно, потому что (б) верно.
(d) верно, потому что все веса ребер различны для G.


3. Пусть G — неориентированный граф. Рассмотрим прохождение в глубину G, и пусть T будет результирующим деревом поиска в глубину. Пусть u будет вершиной в G, и пусть v будет первой новой (не посещенной) вершиной, посещенной после посещения u в обходе. Какое из следующих утверждений всегда верно? (GATE CS 2000)

(a) {u, v} должно быть ребром в G, а u является потомком v в T
(b) {u, v} должно быть ребром в G, а v является потомком u в T
(c) Если {u, v} не является ребром в G, то u является листом в T
(d) Если {u, v} не является ребром в G, то u и v должны иметь одного и того же родителя в T

Ответ (с)
См. Http://geeksquiz.com/data-structures-graph-question-20/ для объяснения.


4. Рассмотрим неориентированный невзвешенный граф G. Пусть обход G в ширину выполняется с узла r. Пусть d (r, u) и d (r, v) — длины кратчайших путей от r до u и v соответственно, в G. Если u посещается до v во время обхода в ширину, какое из следующих утверждений правильно? (GATE CS 2001)

а) d (r, u) d (r, v)
c) d (r, u)
5. Сколько неориентированных графов (необязательно связанных) можно построить из заданного множества V = {V 1, V 2,… V n} из n вершин? (GATE CS 2001)
а) n (nl) / 2
б) 2 ^ н
в) п!
d) 2 ^ (n (n-1) / 2)

Ответ (г)
В неориентированном графе может быть максимум n (n-1) / 2 ребер. Мы можем выбрать (или не иметь) любое из n (n-1) / 2 ребер. Таким образом, общее количество неориентированных графов с n вершинами равно 2 ^ (n (n-1) / 2).

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы обнаружите, что какие-либо ответы / объяснения неверны или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Структуры данных и алгоритмы | Комплект 8

0.00 (0%) 0 votes