2004-gre-cs-practice-book.pdf/Q60

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

Вопрос: Q60-4c9f66

Рассмотрите следующие возможные структуры данных для набора из n различных целых чисел:

1. Минимальная куча
2. Односвязный список длиной n, отсортированный в порядке возрастания
3. Сбалансированное дерево бинарного поиска.

Для какой из этих структур данных требуется количество шагов O(logn) в наихудшем случае, чтобы найти и удалить 7-й по величине элемент?

Ответы

• Только 1
• Только 2
• 1 и 2
• 1 и 3
• Правильный ответ: 2 и 3

Объяснение

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

• Минимальная куча — бинарное дерево, где минимальный элемент корневой. Найти конкретный по счету элемент — O(1), но будет проблема потом после удаления все перестроить — там будет O(n).
• «Односвязный отсортированный список» — легко. В оригинале был «массив», но это не билось с ответом, ибо удаление из массива во многих языках — это перестройка массива, заменил на список.
• SBBST (красно-черное или AVL) — да, и быстрый поиск и ребаланс за лог.

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

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

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