Ответ: Базовым случаем для бинарного поиска является массив, содержащий всего один элемент. Если искомый элемент совпадает с элементом массива – вы нашли его! В противном случае элемент в массиве отсутствует.
В рекурсивном случае для бинарного поиска массив делится пополам, одна половина отбрасывается, а для другой половины проводится бинарный поиск.
Запишите «O-большое» для каждой из следующих операций.
4.5 Вывод значения каждого элемента массива.
Ответ: O(n).
4.6 Удвоение значения каждого элемента массива.
Ответ: O(n).
4.7 Удвоение значения только первого элемента массива.
Ответ: O(1).
4.8 Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый элемент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т.д.
Ответ: O(n2).
Глава 5
Какие из следующих функций являются последовательными?
5.1 f(x) = 1 
Возвращает "1" для любых входных значений
Ответ: Функция последовательна.
5.2 f(x) = rand() Возвращает случайное число
Ответ: Функция непоследовательна.
5.3 f(x) = next_empty_slot() Возвращает индекс следующего пустого элемента в хеш-таблице
Ответ: Функция непоследовательна.
5.4 f(x) = len(x) Возвращает длину полученной строки
Ответ: Функция последовательна.
Предположим, имеются четыре хеш-функции, которые получают строки.
1. Первая функция возвращает «1» для любого входного значения.
2. Вторая функция возвращает длину строки в качестве индекса.
3. Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «a», хешируются в одну позицию, все строки, начинающиеся с «b», — в другую и т.д.
4. Четвертая функция ставит в соответствие каждой букве простое число: a = 2, b = 3, c = 5, d = 7, e = 11 и т.д. Для строки хеш-функцией становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3 + 2 + 17 % 10 = 22 % 10 = 2.
В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.
5.5 Телефонная книга, в которой ключами являются имена, а значениями — номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.
Ответ: Хеш-функции С и D обеспечивают хорошее распределение.
5.6 Связь размера батарейки с напряжением. Размеры батареек: A, AA, AAA, AAAA.
Ответ: Хеш-функции B и D обеспечивают хорошее распределение.
5.7 Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Home», «Watchmen».
Ответ: Хеш-функции B, С и D обеспечивают хорошее распределение.
Глава 6
Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.
6.1 Найдите длину кратчайшего пути от начального до конечного узла.
Ответ: Длина кратчайшего пути равна 2.
6.2 Найдите длину кратчайшего пути от «cab» к «bat».
Ответ: Длина кратчайшего пути равна 2.
6.3 Перед вами небольшой граф моего утреннего распорядка.
Для каждого из следующих трех списков укажите, действителен он или недействителен.
Ответы: A — недействителен; B — действителен; С — недействителен.
6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.
Ответ: 1 — Проснуться; 2 — Сделать зарядку; 3 — Принять душ; 4 — Почистить зубы; 5 — Одеться; 6 — Упаковать обед; 7 — Позавтракать.
6.5 Какие из следующих графов также являются деревьями?
Ответы: A — дерево; B — не дерево; C — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.
Глава 7
7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Ответы: A — 8; B — 60; C — каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).