Все вопросы

№	Вопрос	Действия
81	Алгоритм Хаффмана строит Σ-дерево снизу вверх, и на каждой итерации он объединяет два дерева, имеющие наименьшие суммы частот соответствующих символов. Сколько слияний выполнит жадный алгоритм Хаффмана до остановки? Число символов обозначается n = \|Σ\|	Открыть
82	Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути от исходной вершины до всех остальных. Каким будет время работы алгоритма как функции от m (числа ребер) и n (числа вершин)?	Открыть
83	Имеется куча с n объектами. Какую из следующих задач можно решить с помощью операций Вставить и Извлечь минимум с временем O(1) и дополнительной работы с временем O(1)?	Открыть
84	Предположим, что набор данных S вставляется в фильтр Блума, который использует m хеш-функций и битовый массив длины n. Первое допущение говорит, что для каждого ключа k, каждой хеш-функции hi и каждой позиции q∈ {0, 1, 2,..., n − 1} в массиве вероятность того, что hi (k) = q равна в точности 1/n. Второе допущение предполагает, что вероятность того, что hi (k1) = q, а также hj(k2) = r, равна произведению индивидуальных вероятностей, также рассчитываемая как 1/n2. Какова вероятность того, что первый бит массива равен 1 (с учетом эвристических допущений)?	Открыть
85	Какое из перечисленных ниже свойств не входит в определение хорошо спроектированной хеш-функции?	Открыть
86	Что выведет интерпретатор для следующей программы (версия Python 3.6+)? def get_name_and_decades(name, age): print(f"My name is {name} and I'm {age / 10:.5f} decades old.") get_name_and_decades("Leo", 31)	Открыть
87	Пусть G равно ориентированному графу, а Grev равно копии графа G, в котором каждое ребро развернуто в обратную сторону. Насколько сильно связные компоненты графов G и Grev связаны между собой?	Открыть
88	Из бочки вина перелили ложку вина в (неполный) стакан с чаем. А потом такую же ложку смеси из стакана –– обратно в бочку. Теперь и в бочке, и в стакане имеется некоторый объем посторонней жидкости (вина в стакане, чая в бочке). Где объем посторонней жидкости больше: в стакане или в бочке?	Открыть
89	Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Это слово набирают с помощью одного или нескольких дисков, на которых нанесены буквы (или цифры). Пусть на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?	Открыть
90	В Южной Америке есть круглое озеро, где 1 июня каждого года в центре озера появляется цветок Виктории Регии (стебель поднимается со дна, а лепестки лежат на воде, как у кувшинки). Каждые сутки площадь цветка увеличивается вдвое, и 1 июля он, наконец, покрывает все озеро, лепестки осыпаются, семена опускаются на дно. Какого числа площадь цветка составляет половину площади озера?	Открыть

81

Алгоритм Хаффмана строит Σ-дерево снизу вверх, и на каждой итерации он объединяет два дерева, имеющие наименьшие суммы частот соответствующих символов. Сколько слияний выполнит жадный алгоритм Хаффмана до остановки? Число символов обозначается n = |Σ|

Открыть

82

Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути от исходной вершины до всех остальных. Каким будет время работы алгоритма как функции от m (числа ребер) и n (числа вершин)?

Открыть

83

Имеется куча с n объектами. Какую из следующих задач можно решить с помощью операций Вставить и Извлечь минимум с временем O(1) и дополнительной работы с временем O(1)?

Открыть

84

Предположим, что набор данных S вставляется в фильтр Блума, который использует m хеш-функций и битовый массив длины n. Первое допущение говорит, что для каждого ключа k, каждой хеш-функции hi и каждой позиции q∈ {0, 1, 2,..., n − 1} в массиве вероятность того, что hi (k) = q равна в точности 1/n. Второе допущение предполагает, что вероятность того, что hi (k1) = q, а также hj(k2) = r, равна произведению индивидуальных вероятностей, также рассчитываемая как 1/n2. Какова вероятность того, что первый бит массива равен 1 (с учетом эвристических допущений)?

Открыть

85

Какое из перечисленных ниже свойств не входит в определение хорошо спроектированной хеш-функции?

Открыть

86

Что выведет интерпретатор для следующей программы (версия Python 3.6+)? def get_name_and_decades(name, age): print(f"My name is {name} and I'm {age / 10:.5f} decades old.") get_name_and_decades("Leo", 31)

Открыть

87

Пусть G равно ориентированному графу, а Grev равно копии графа G, в котором каждое ребро развернуто в обратную сторону. Насколько сильно связные компоненты графов G и Grev связаны между собой?

Открыть

88

Из бочки вина перелили ложку вина в (неполный) стакан с чаем. А потом такую же ложку смеси из стакана –– обратно в бочку. Теперь и в бочке, и в стакане имеется некоторый объем посторонней жидкости (вина в стакане, чая в бочке). Где объем посторонней жидкости больше: в стакане или в бочке?

Открыть

89

Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Это слово набирают с помощью одного или нескольких дисков, на которых нанесены буквы (или цифры). Пусть на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

Открыть

90

В Южной Америке есть круглое озеро, где 1 июня каждого года в центре озера появляется цветок Виктории Регии (стебель поднимается со дна, а лепестки лежат на воде, как у кувшинки). Каждые сутки площадь цветка увеличивается вдвое, и 1 июля он, наконец, покрывает все озеро, лепестки осыпаются, семена опускаются на дно. Какого числа площадь цветка составляет половину площади озера?

Открыть