Структуры данных: лист заданий с ответами

Что такое свойство max-кучи?

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

В односвязном списке каждый узел содержит:

1. AДанные и индекс
2. BДанные и ссылку на следующий узел
3. CДанные и ссылки на все остальные узлы
4. DТолько данные

Где находится наименьший элемент двоичной min-кучи?

1. AВ последней позиции массива
2. BВ самом левом листе
3. CВ каком-то листе, который придётся искать
4. DВ корне

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AВысоту O(log n) благодаря перебалансировке
2. BЧто ни у одного узла нет двух потомков
3. CХранение ключей в порядке вставки
4. DПоиск за константное время в любом случае

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AМножество без упорядочения
2. BСтек
3. CОчередь FIFO
4. DОчередь с приоритетом по минимуму

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(n)
2. BO(n²)
3. CРовно O(log n)
4. DO(α(n)), обратная функция Аккермана, практически константа

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A60
2. B80
3. C70
4. D40