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