Рубрики

ВОРОТА | GATE 2017 MOCK II | Вопрос 21

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

i) Предметы извлекаются и удаляются из коллекции в порядке FIFO.
ii) Не существует априорного ограничения на количество предметов в коллекции.
iii) Размер элемента большой по сравнению с объемом памяти, необходимым для адреса памяти.
(A) Односвязный список с указателями головы и хвоста
(B) двусвязный список только с указателем головы
(C) Двоичное дерево
(D) Хеш-таблица

Ответ: (А)
Пояснение: Головной и хвостовой указатели в списке одиночных ссылок сделают вставку и удаление за O (1) временной сложности, если мы получим доступ к элементам в порядке FIFO.

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

В двоичном дереве у нас есть только указатель на корень. Вставка и удаление в двоичном дереве будет
O (log n), поэтому не подходит.

Рекомендуемые посты:

ВОРОТА | GATE 2017 MOCK II | Вопрос 21

0.00 (0%) 0 votes