2011-gre-cs-practice-book.pdf/Q08 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) (→Вопрос: Q08-08c765) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | == Вопрос: Q08-08c765 == | |
| − | + | Какая структура данных будет наиболее подходящей чтобы хранить элементы и иметь следующие три характеристики? | |
| − | + | # Элементы извлекаются и удаляются из коллекции в порядке FIFO (First-In-First-Out). | |
| − | + | # Нет априорного ограничения на количество элементов. | |
| − | + | # Размер элемента велик относительно хранилища, необходимого для прямой выделения памяти и адресации элементов. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | * Правильный ответ: Односвязный список с указателями на начало и конец | |
| − | + | * Двусвязный список только с указателем на начало | |
| + | * Массив | ||
| + | * Двоичное дерево | ||
| + | * Хэш-таблица | ||
| − | + | === Объяснение === | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|18|8}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | |
| − | + | Приведем хотя бы одну причину, почему некоторые кандидаты не подходят: | |
| − | + | * Односвязный список с указателями на начало и конец — эта структура данных позволяет извлекать и удалять элементы в порядке FIFO, поскольку она сохраняет порядок вставки. Она может вмещать любое количество элементов, поскольку нет априорного ограничения. Размер элемента, большой относительно хранилища, необходимого для адреса памяти, не влияет на выбор этой структуры данных. | |
| − | + | * Двусвязный список, только с указателем на заголовок — наличие только указателя на заголовок затрудняет реализацию требования FIFO. | |
| − | + | ** [[Участник:StasFomin|StasFomin]]: не затрудняет. Все тоже самое можно сделать что и с односвязным, просто лишняя трата памяти. | |
| + | * Массив — накладывает априорное ограничение на размер коллекции, чего нет в других структурах данных. | ||
| + | ** [[Участник:StasFomin|StasFomin]]: ну тут просто потребуется большой непрерывный кусок памяти, это дорого. | ||
| + | * Двоичное дерево — не организует элементы таким образом, чтобы было удобно реализовать FIFO. | ||
| + | * Хеш-таблица — не сохраняет в общем порядок, то есть требование FIFO не удовлетворяется, да и с памятью беда, ведь придется каждый раз перезадавать размер, когда условно таблица будет заполняться. | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 20:43, 18 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Структуры данных]] | |
Текущая версия на 20:44, 18 декабря 2024
Вопрос: Q08-08c765
Какая структура данных будет наиболее подходящей чтобы хранить элементы и иметь следующие три характеристики?
- Элементы извлекаются и удаляются из коллекции в порядке FIFO (First-In-First-Out).
- Нет априорного ограничения на количество элементов.
- Размер элемента велик относительно хранилища, необходимого для прямой выделения памяти и адресации элементов.
Ответы
- Правильный ответ: Односвязный список с указателями на начало и конец
- Двусвязный список только с указателем на начало
- Массив
- Двоичное дерево
- Хэш-таблица
Объяснение
Исходники — вопрос 8 на 18 странице книги «2011-gre-cs-practice-book.pdf»
Приведем хотя бы одну причину, почему некоторые кандидаты не подходят:
- Односвязный список с указателями на начало и конец — эта структура данных позволяет извлекать и удалять элементы в порядке FIFO, поскольку она сохраняет порядок вставки. Она может вмещать любое количество элементов, поскольку нет априорного ограничения. Размер элемента, большой относительно хранилища, необходимого для адреса памяти, не влияет на выбор этой структуры данных.
- Двусвязный список, только с указателем на заголовок — наличие только указателя на заголовок затрудняет реализацию требования FIFO.
- StasFomin: не затрудняет. Все тоже самое можно сделать что и с односвязным, просто лишняя трата памяти.
- Массив — накладывает априорное ограничение на размер коллекции, чего нет в других структурах данных.
- StasFomin: ну тут просто потребуется большой непрерывный кусок памяти, это дорого.
- Двоичное дерево — не организует элементы таким образом, чтобы было удобно реализовать FIFO.
- Хеш-таблица — не сохраняет в общем порядок, то есть требование FIFO не удовлетворяется, да и с памятью беда, ведь придется каждый раз перезадавать размер, когда условно таблица будет заполняться.