Основы программирования - обучения основам - тест 12

Упражнение 1:

---

Номер 2

На базе какой структуры данных удобно реализовать
стек?

Ответ:

---

Номер 3

На базе какой структуры данных удобно реализовать очередь?

Ответ:

---

Упражнение 2:

---

Номер 1

Рассмотрим непрерывную реализацию множества с помощью
бинарного поиска. Пусть множество содержит миллион элементов.
Сколько операций сравнения может быть выполнено при поиске
элемента?

Ответ:

---

Номер 2

Элементы множества хранятся в массиве в возрастающем
порядке. Пусть множество содержит 12 элементов.
Сколько операций сравнения достаточно выполнить,
чтобы найти произвольный элемент в множестве или убедиться в его
отсутствии?

Ответ:

---

Номер 3

Элементы множества хранятся в массиве в возрастающем
порядке. Пусть множество содержит 10 элементов.
Сколько операций сравнения достаточно выполнить,
чтобы найти произвольный элемент в множестве или убедиться в его
отсутствии?

Ответ:

---

Упражнение 3:

---

Номер 1

Пусть требуется реализовать упорядоченный
набор различных элементов, при этом элементы можно
добавлять и удалять. Какая структура данных
лучше всего подходит для этого?

Ответ:

---

Номер 2

Пусть требуется реализовать упорядоченный набор элементов,
причем элемент может повторяться в наборе несколько раз.
Элементы можно добавлять к набору и удалять из набора. Какая
структура данных лучше всего подходит для этого?

Ответ:

---

Номер 3

Текст представляет собой последовательность строк.
При этом строки можно изменять, удалять и добавлять
в любое место текста. Какая структура данных
лучше всего подходит для хранения и редактирования
такого текста?

Ответ:

---

Упражнение 4:

---

Номер 1

Как оценивается сверху высота h сбалансированного (почти
сбалансированного) бинарного дерева в зависимости от числа
вершин n?

Ответ:

---

Номер 2

Бинарное дерево называется полным, если
длины всех путей к внешним (нулевым) вершинам одинаковы.
(Это означает, что у каждой нетерминальной вершины ровно
два сына, и длины всех путей от корня к терминальным вершинам
одинаковы и равны высоте дерева.) Высотой дерева называется
число вершин в пути максимальной длины от корня к
некоторой терминальной вершине, включая первую и последнюю вершины
пути. Сколько вершин в полном бинарном дереве высоты 10?

Ответ:

---

Номер 3

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

Ответ:

---

Упражнение 5:

---

Номер 1

Пусть в красно-черном дереве число черных вершин
(не включая внешние, или нулевые, вершины) равно 21.
Какое максимальное количество красных вершин может
быть в дереве?

Ответ:

---

Номер 2

Может ли в красно-черном дереве
длина одного пути от корня к терминальной вершине
равняться 20, длина другого — 10?

Ответ:

---

Номер 3

Может ли в красно-черном дереве число красных вершин
более чем в два раза превышать число черных вершин?

Ответ:

---

Упражнение 6:

---

Номер 1

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

Ответ:

---

Номер 2

В хеш-реализации множества хеш-функция принимает 4 различные
значения с равной вероятностью, т.е. множество представляется
в виде объединения четырех непересекающихся подмножеств. Пусть
множество содержит 4 элемента. Какова вероятность того,
что все подмножества будут непустыми?

Ответ:

---

Номер 3

В хеш-реализации множества хеш-функция принимает 5 различных
значений с равной вероятностью, т.е. множество представляется
в виде объединения пяти непересекающихся подмножеств. Пусть
множество содержит 3 элемента. Какова вероятность того,
что все они попадут в разные подмножества?

Ответ:

---