2011-gre-cs-practice-book.pdf/Q08

Ссылки сюда (1) →

Вопрос: Q08-08c765

Какая структура данных будет наиболее подходящей чтобы хранить элементы и иметь следующие три характеристики?

1. Элементы извлекаются и удаляются из коллекции в порядке FIFO (First-In-First-Out).
2. Нет априорного ограничения на количество элементов.
3. Размер элемента велик относительно хранилища, необходимого для прямой выделения памяти и адресации элементов.

Ответы

• Правильный ответ: Односвязный список с указателями на начало и конец
• Двусвязный список только с указателем на начало
• Массив
• Двоичное дерево
• Хэш-таблица

Объяснение

Исходники — вопрос 8 на 18 странице книги «2011-gre-cs-practice-book.pdf»

Приведем хотя бы одну причину, почему некоторые кандидаты не подходят:

• Односвязный список с указателями на начало и конец — эта структура данных позволяет извлекать и удалять элементы в порядке FIFO, поскольку она сохраняет порядок вставки. Она может вмещать любое количество элементов, поскольку нет априорного ограничения. Размер элемента, большой относительно хранилища, необходимого для адреса памяти, не влияет на выбор этой структуры данных.
• Двусвязный список, только с указателем на заголовок — наличие только указателя на заголовок затрудняет реализацию требования FIFO.
  • StasFomin: не затрудняет. Все тоже самое можно сделать что и с односвязным, просто лишняя трата памяти.
• Массив — накладывает априорное ограничение на размер коллекции, чего нет в других структурах данных.
  • StasFomin: ну тут просто потребуется большой непрерывный кусок памяти, это дорого.
• Двоичное дерево — не организует элементы таким образом, чтобы было удобно реализовать FIFO.
• Хеш-таблица — не сохраняет в общем порядок, то есть требование FIFO не удовлетворяется, да и с памятью беда, ведь придется каждый раз перезадавать размер, когда условно таблица будет заполняться.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.