Инструменты, алгоритмы и структуры данных

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

Номер 1

Что такое хеширование?

Ответ:

(1) приготовление блюда из нижней части коровьих ног

(2) оплата наличными

(3) выделение памяти, играющей роль буфера

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

Номер 2

Хеш-функция f(k) отображает множество ключей в целочисленный интервал: K -> [a, b]. Пусть ключами являются имена, которые должны отображаться в интервал [0, 9]. В качестве хеш-функции выберем функцию, которая вычисляет сумму позиций в алфавите кириллицы первой и последней буквы имени, прибавляет длину имени и вычисляет остаток от деления на 10 (взятие по модулю от длины интервала). Для имени Яша эта функция выдаст значение 7. Каково число коллизий возникнет при применении этой функции для следующих 10 имен: Анна, Инна, Нина, Ольга, Екатерина, Владимир, Владислав, Виктор, Михаил, Яков?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 3

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

Ответ:

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

(2) для совершенной хеш-функции время доступа на чтение и на запись элемента в хеш-таблицу не зависит от числа элементов и определяется как O(1)

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

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

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

Номер 1

Какие утверждения справедливы для хеш-таблицы?

Ответ:

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

(2) для работы с хеш-таблицами в Eiffel предлагается библиотечный класс HASH_TABLE, представляющий универсальный класс с двумя родовыми параметрами, характеризующими тип ключа и тип элемента

(3) как и для списков, для хеш-таблиц определено понятие курсора и операций, связанных с курсором

(4) операции вставки и удаления элементов для хеш-таблиц реализуются эффективнее, чем для массивов

(5) операции вставки и удаления элементов для хеш-таблиц реализуются эффективнее, чем для списков

Номер 2

Эффективность работы с хеш-таблицами зависит от выбора хеш-функции (степени ее совершенства) и от способа разрешения конфликтов при совпадении значений. Укажите, как разрешаются конфликты в Eiffel библиотечном классе HASH_TABLE?

Ответ:

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

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

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

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

Номер 3

Какие из операций над хеш-таблицами в классе HASH_TABLE имеют временную сложность O(count), а не O(1)?

Ответ:

(1) extend

(2) has

(3) item

(4) force

(5) put

(6) replace

(7) remove

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

Номер 1

Распределитель - это контейнер - структура данных, характеризуемая тем, что:

Ответ:

(1) доступ к элементу и вставка элемента в контейнер выполняется с указанием ключа или индекса элемента

(2) доступ к элементу контейнера выполняется с указанием ключа или индекса элемента, а для вставки ключа не требуется

(3) вставка элемента в контейнер выполняется с указанием ключа или индекса элемента, а для доступа ключа не требуется

(4) для вставки элемента в контейнер и для доступа к нему указание ключа или индекса элемента не требуется

Номер 2

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

Ответ:

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

(2) экзамен принимают несколько преподавателей. Каждый из них вызывает по фамилии студента и принимает у него экзамен

(3) экзамен принимают несколько преподавателей. Студент выбирает, какому из преподавателей он хочет сдавать экзамен, и записывается к нему в очередь

(4) студенты по очереди заходят в аудиторию, где несколько преподавателей принимают экзамен. Студент сдает экзамен первому свободному преподавателю

Номер 3

Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом - преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена контейнер "студент"  можно отнести к распределителю, а контейнер "преподаватель" таковым не является?

Ответ:

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

(2) экзамен принимают несколько преподавателей. Каждый из них вызывает по фамилии студента и принимает у него экзамен

(3) экзамен принимают несколько преподавателей. Студент выбирает, какому из преподавателей он хочет сдавать экзамен, и записывается к нему в очередь

(4) студенты по очереди заходят в аудиторию, где несколько преподавателей принимают экзамен. Студент сдает экзамен первому свободному преподавателю

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

Номер 1

Какие из структур данных относятся к распределителям?

Ответ:

(1) массив

(2) стек

(3) список

(4) очередь

(5) очередь с приоритетом

(6) хеш-таблица

Номер 2

Какая из структур данных относится к распределителям с политикой "первым пришел, первым ушел"?

Ответ:

(1) массив

(2) стек

(3) список

(4) очередь

(5) очередь с приоритетом

(6) хеш-таблица

Номер 3

Какая из структур данных относится к распределителям с политикой "первым пришел в своей группе приоритетности, первым уйдешь в своей группе приоритетности"?

Ответ:

(1) массив

(2) стек

(3) список

(4) очередь

(5) очередь с приоритетом

(6) хеш-таблица

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

Номер 1

Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция put-записи операнда в стек?

Ответ:

(1) 7

(2) 6

(3) 13

(4) 12

Номер 2

Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: "2 3 4 5 + * - 6 7 8 - * +". Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция item-чтения операнда из стека?

Ответ:

(1) 7

(2) 6

(3) 13

(4) 12

Номер 3

Какие из утверждений справедливы в Eiffel для реализации стека на массивах?

Ответ:

(1) стек можно реализовать на массиве, растущем вверх

(2) стек можно реализовать на массиве, растущем вниз

(3) атрибут capacity, характеризующий емкость массива (число его элементов) и атрибут count для стека - эквивалентные понятия и имеют совпадающие значения

(4) для стека, реализуемого массивом в языке Eiffel, всегда требуется задавать емкость - максимальное число элементов, которые можно хранить в стеке. Емкость стека определяется емкостью массива

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

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

Номер 1

Для эффективного использования памяти на одном массиве можно реализовать стеков:

Ответ:

(1) 1

(2) 2

(3) 4

(4) 8

Номер 2

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

Ответ:

(1) put

(2) item

(3) remove

(4) is_empty

Номер 3

Какие утверждения справедливы для стеков в Eiffel?

Ответ:

(1) для работы со стеками в библиотеке EiffelBase имеется только один класс - ARRAYED_STACK

(2) для работы со стеками в библиотеке EiffelBase предлагается три класса - ARRAYED_STACK, BOUNDED_STACK, LINKED_STACK

(3) все классы Eiffel для работы со стеками имеют эквивалентный набор операций - запросов и команд

(4) только для класса ARRAYED_STACK среднее время выполнения всех операций - O(1), для других классов - O(count)

(5) для класса ARRAYED_STACK максимальное время выполнения операции вставки put - O(count), достигаемое в тех редких случаях, когда происходит перестройка массива

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

Номер 1

Какие утверждения являются частью постусловия операции вталкивания элемента в вершину стека - put(x)?

Ответ:

(1) x = 0

(2) item = x

(3) count = old count + 1

(4) is_empty = FALSE

Номер 2

Какие утверждения справедливы для очереди, реализуемой связным списком класса LINKED_QUEUE?

Ответ:

(1) операция вставки put(x) в очередь реализуется за время O(1) выполнением одной операции над списком put_front(x), которая помещает элемент x в начало списка

(2) операция удаления элемента из очереди – remove выполняется за время O(count), поскольку требует перемещения по всему списку, чтобы удалить элемент, стоящий в конце списка

(3) операция удаления элемента из очереди - remove выполняется за время O(1), поскольку достаточно выполнить операцию remove для списка, удаляя элемент, на который указывает курсор списка

(4) инвариантом класса LINKED_QUEUE является утверждение, что курсор всегда указывает на последний элемент списка - начало очереди

Номер 3

Какие утверждения справедливы для реализации очереди на массиве классом ARRAYED_QUEUE?

Ответ:

(1) очередь реализуется массивом, растущим вверх

(2) очередь реализуется массивом, растущим вниз

(3) очередь реализуется закольцованным массивом, представленным в виде бублика

(4) благодаря перестраиваемым массивам Eiffel очередь имеет практически неограниченную емкость

(5) все операции над очередью в среднем выполняются за время O(1)

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

Номер 1

Какие утверждения справедливы для очереди с приоритетами?

Ответ:

(1) справедлива политика "первым пришел, первым уйдешь"

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

(3) справедлива политика "первым пришел в свою группу приоритетности - первым уйдешь из этой группы"

(4) справедлива политика "уйдешь раньше тех, кто принадлежит группам приоритетности низшего ранга"

(5) справедлива политика "уйдешь позже тех, кто принадлежит группам приоритетности высшего ранга"

Номер 2

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

Ответ:

(1) распределители позволяют получать доступ, вставку и удаление элементов в строго определенном месте контейнера

(2) каждый вид распределителя задает свою политику, куда помещать приходящие элементы и какой элемент следует выдавать по запросу

(3) стеки и очереди - это распределители с одинаковой политикой доступа к элементам

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

Номер 3

Какими правилами можно характеризовать политику, применяемую для стеков:

Ответ:

(1) FIFO - первый пришел - первый ушел

(2) LIFO - последний пришел - первый ушел

(3) LILO - последний пришел - последний ушел

(4) FILO - первый пришел - последний ушел

Инструменты, алгоритмы и структуры данных - тест 7