Робочий аркуш «Структури даних» з відповідями

Висоту дерева зазвичай визначають як:

1. AЗагальну кількість вузлів у дереві, враховуючи корінь і кожен листок
2. BКількість листків у дереві
3. CКількість дітей кореня
4. DКількість ребер на найдовшому шляху від кореня до листка

Яку структуру зазвичай використовують для реалізації черги з пріоритетом?

1. AСтек
2. BРядок
3. CНевпорядкований однозв'язний список
4. DКупу

Як елементи масиву зберігаються в пам'яті?

1. AУ дереві сторінок пам'яті
2. BОдним суцільним блоком, один за одним
3. CРозкидано, зв'язані вказівниками
4. DУ випадкових місцях, обраних гешем

Застосунку потрібен швидкий пошук, а також виведення ключів у відсортованому порядку та відповіді на запити діапазону. Яка структура підходить найкраще?

1. AГеш-таблиця
2. BСтек
3. CЗбалансоване бінарне дерево пошуку
4. DНевідсортований зв'язний список

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

1. AЦе повне бінарне дерево, тож позиції визначаються простими формулами індексів
2. BУсі ключі в купі однакові
3. CМасиви автоматично зберігають ключі відсортованими, тож вказівники не потрібні
4. DКупи ніколи не містять понад 100 елементів

Скільки пам'яті використовує список суміжності для графа з V вершинами та E ребрами?

1. AO(V + E)
2. BO(V × E)
3. CO(E²)
4. DO(V²)

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

1. A70
2. B40
3. C80
4. D60

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

1. AO(α(n))
2. BO(log n)
3. CO(1)
4. DO(n)