Тест по Computer Science — вопросы

Рассмотрим следующее рекуррентное соотношение: Какое из следующих утверждений является верным?

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

Рассмотрим следующее AVL-дерево:

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

• I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

• II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

Сколько вершин имеет дерево с 57 ребрами?

Существует несколько способов определить порядок умножения матриц A, B, C, D: (A(BC)D), A(B(CD)), (AB)(CD), ((AB)C)D), A((BC)D)

Эффективность умножения зависит от числа скалярных произведений, для (A(BC))D получится:

Для (A(B(CD))):

Какие размерности у матриц A, B, C, D соответственно?

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

Пусть G = (V, E) неориентированный граф, какие утверждения ниже являются верными?

• I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.

• II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.

• III. Удаление ребра из цикла не может сделать граф несвязным.