SAOD_2_kurs_Grafy_2-_vtorye_shest_voprosov (1021521)

4677

Выберите неверныйспособ представления графа

Ответы:

- Матрицей смежности;

- Матрицей инцендентности;

- Списком смежности;

- Матрицей замыкания;

- Массивом дуг;

4678

Выберите неверныйтермин (тот, который не применим к графам)

Ответы:

- Ориентированный граф;

- Двудольный граф;

- Ациклический граф;

- Все термины верны;

- Циклический граф;

4679

Задача нахождения кратчайшего расстояния между двумя вершинами графа в случае отсутствия дуг отрицательного веса решается,

Ответы:

- используя алгоритм Дейкстры

- используя алгоритм Флойда

- используя алгоритм Дейкстры или алгоритм Флойда

- последовательно, сначала алгоритмом Дейкстры, затем алгоритмом Флойда

- используя алгоритм Флойда, он же алгоритм Дейкстры (т.е. алгоритм Флойда и алгоритм Дейкстры - это два различных названия одного и того же алгоритма)

4680

Классический алгоритм Дейкстры предназначен для

Ответы:

- нахождения кратчайшего расстояния между двумя вершинами ациклического графа при отсутствии дуг отрицательного веса

- нахождения кратчайшего расстояния между двумя вершинами в ациклическом взвешенном графе

- нахождения кратчайшего расстояния между двумя вершинами только в циклическом взвешенном графе

- нахождения кратчайшего расстояния между двумя вершинами в произвольном взвешенном графе при отсутствии дуг отрицательного веса

- нахождения расстояния между всеми вершинами в произвольном взвешенном графе

4681

Классический алгоритм Дейкстры предназначен для

Ответы:

- нахождения кратчайшего расстояния между всеми парами вершин ациклического графа в случае отсутствия дуг отрицательного веса

- нахождения кратчайшего расстояния от определенного узла (источника) до каждого из остальных узлов в ориентированном графе, если дуги имеют неотрицательный вес

- нахождения кратчайшего расстояния между двумя вершинами ациклического графа при отсутствии дуг отрицательного веса

- нахождения кратчайшего расстояния между двумя вершинами только в циклическом взвешенном графе

- нахождения расстояния между всеми вершинами в произвольном взвешенном графе

4682

Классический алгоритм Флойда предназначен для

Ответы:

- нахождения кратчайшего расстояния между всеми парами вершин графа в случае отсутствия дуг отрицательного веса

- нахождения кратчайшего расстояния между двумя вершинами в ациклическом взвешенном графе

- нахождения кратчайшего расстояния между двумя вершинами только в циклическом взвешенном графе

- нахождения кратчайшего расстояния между двумя вершинами в произвольном взвешенном графе

- нахождения расстояния между всеми вершинами в произвольном взвешенном графе

4683

Какая характеристика не применимак алгоритму Дейкстры

Ответы:

- «Жадный» алгоритм

- Алгоритм для нахождения оптимального решения

- Алгоритм для нахождения глобального оптимального решения

- Алгоритм использует переборную схему поиска решения с возвратом

- Алгоритм определяет кратчайшее расстояние от одного узла (источника) до всех остальных узлов графа

4684

Какая характеристика не применимак алгоритму Флойда

Ответы:

- Допускает наличия цикла в графе

- Допускает наличия петли на графе

- Допускает наличие отрицательного веса дуги графа

- Использует матрицу весов графа для вычисления кратчайшего расстояния между парой вершин (узлов) графа

- Использует матрицу весов графа для вычисления кратчайшего расстояния между всеми парами вершин (узлов) графа

4685

Транзитивное замыкание графа используется

Ответы:

- для определения существования кратчайшего пути между парой вершин

- для определения кратчайшего пути между парой вершин

- для определения существования какого-либо пути между парой вершин

- для определения центра графа

- для вычисления эксцентриситета графа

4686

Укажитеневерноевысказывание:

«Поиск в ширину на взвешенном неориентированном графе предназначен (может быть использован) для …»

Ответы:

- систематического обхода всех вершин (узлов) графа

- отыскания какого-либо цикла на заданном графе

- определения кратчайшего расстояния между парой узлов графа

- определения циклов на графе

- получения глубинного остовного леса

4687

Укажите неверноевысказывание:

«Поиск в ширину на не взвешенном неориентированном графе предназначен (может быть использован) для …»

Ответы:

- систематического обхода всех вершин (узлов) графа

- отыскания какого-либо цикла на заданном графе

- определения кратчайшего расстояния между парой узлов графа

- определения центра графа

- получения глубинного остовного леса

4688

Укажитеневерноевысказывание:

«Остовное дерево минимальной стоимости …»

Ответы:

- строится в ходе алгоритма Крускала

- строится в ходе алгоритма Прима

- строится в ходе алгоритма Дейкстры

- не содержит циклов

- содержит для каждого узла в обязательном порядке дугу, такую что эта дуга имеет минимальный вес из всех дуг, инцидентных этому узлу

4689

Алгоритм Хаффмана предназначен для

Ответы:

- Сортировки чисел;

- Сортировки символов;

- Построения упорядоченного дерева;

- Построения оптимального префиксного кода;

- Построения постфиксного кода, обеспечивающего сжатие символьной строки;

4690

Укажите неверное утверждение. «В ходе алгоритма Хаффмана происходит …»

Ответы:

- построение оптимального префиксного кода;

- построение сбалансированного дерева;

- построение бинарного дерева;

- сжатие строки символов;

- объединение очередной пары символов с наименьшей вероятностью появления в строке;

4691

Оптимальный префиксный код

Ответы:

- Должен начинаться с «1»;

- Должен начинаться с «0»;

- Последний бит оптимального префиксного кода содержит контрольное значение, вычисленное по алгоритму Хаффмана;

- Обеспечивает однозначное распознавание (декодирование) строки путем считывания слева направо префикса, который является кодом символа;

4692

Есть граф G= (V, Е). Подмножество его ребер, такое что никакие два ребра из этого подмножества не инциденты какой-либо одной вершине из V, называется …

Ответы:

- паросочетанием

- покрытием

- связной компанентой

- сильносвязной компанентой

- остовным деревом

- свободным деревом

- k-связанным

4693

Как называется задача, котораясводится к поиску в неориентированном графе с весовыми значениями ребер такого маршрута(простого цикла, включающего все вершины), у которого сумма весов составляющих его ребер будет минимальной.

Ответы:

- задача комивояжера

- задача нахождения гамильтонова цикла

- задача нахождения эйлерова цикла

- задача нахождения остовного дерева минимальной стоимости

- задача о максимальном паросочетании

- задача о минимальном покрытии

- задача нахождения минимального расстояния от источника до каждой из вершин

4694

Как называется задача, котораясводится к поиску в неориентированном графе любого простого цикла, включающего все вершины графа.

Ответы:

- задача комивояжера

- задача нахождения гамильтонова цикла

- задача нахождения эйлерова цикла

- задача нахождения остовного дерева минимальной стоимости

- задача о максимальном паросочетании

- задача о минимальном покрытии

- задача нахождения минимального расстояния от источника до каждой из вершин

4695

Как называется задача нахождения минимального (в смысле суммы весов дуг) гамильтонова цикла?

Ответы:

- задача комивояжера

- задача проверки ацикличности графа

- задача нахождения эйлерова цикла

- задача нахождения остовного дерева минимальной стоимости

- задача о максимальном паросочетании

- задача о минимальном покрытии

- задача нахождения минимального расстояния от источника до каждой из вершин