Рубрики

Структуры данных и алгоритмы | Комплект 18

На экзамене GATE CS 2006 были заданы следующие вопросы.

1. Рассмотрим многочлен p (x) = a0 + a1x + a2x ^ 2 + a3x ^ 3, где ai! = 0, для всех i. Минимальное количество умножений, необходимое для оценки p на входе x:

(А) 3
(Б) 4
(С) 6
(D) 9

Ответ (А)

Умножения можно свести к минимуму, используя следующий порядок для оценки данного выражения.
p (x) = a0 + x (a1 + x (a2 + a3x))

2. Для реализации алгоритма кратчайшего пути Дейкстры на невзвешенных графах, чтобы он работал за линейное время, используется структура данных:
(Очередь
(B) Стек
(С) куча
(D) B-дерево

Ответ (A)
Кратчайший путь в невзвешенном графе означает наименьшее количество ребер, которые необходимо пройти, чтобы достичь пункта назначения в графе. Это та же проблема, что и при решении взвешенной версии, в которой все весовые коэффициенты равны 1. Если мы используем Очередь (FIFO) вместо Приоритетной очереди (Min Heap), мы получаем кратчайший путь за линейное время O (| V | + | E |). В основном мы делаем BFS обход графа, чтобы получить кратчайшие пути.

3. Трехкомпонентная максимальная куча похожа на двоичную максимальную кучу, но вместо 2 дочерних узлов узлы имеют 3 дочерних элемента. 3-арная куча может быть представлена массивом следующим образом: корень хранится в первом местоположении, a [0], узлы на следующем уровне, слева направо, сохраняются от [1] до [3 ]. Узлы со второго уровня дерева слева направо сохраняются с позиции [4] и далее. Элемент x можно вставить в 3-рядную кучу, содержащую n элементов, поместив x в местоположение a [n] и вытолкнув его вверх по дереву, чтобы удовлетворить свойство кучи.

Какой из следующих элементов является допустимой последовательностью элементов в массиве, представляющем 3-х максимальную кучу?
(А) 1, 3, 5, 6, 8, 9
(Б) 9, 6, 3, 1, 8, 5
(С) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1

Ответ (D)

                                      9
                                   /  |   \
                                /     |     \
                              5       6      8
                           /  |
                         /    |
                       3      1

4. Предположим, что элементы 7, 2, 10 и 4 вставлены в указанном порядке в допустимую 3-х максимальную кучу, найденную в приведенном выше вопросе. Какой из следующих элементов является последовательностью элементов в массиве, представляющих результирующую кучу ?
(А) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(В) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(С) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Ответ (A)

After insertion of 7
                                          9
                                      /   |   \
                                    /     |     \
                                  7       6       8
                               / | \
                             /   |  \
                            3    1    5    

После вставки 2

                                           9
                                      /    |   \
                                    /      |     \
                                  7        6       8
                               / | \       /
                             /   |  \     /
                            3    1    5  2

После вставки 10

                                 10
                             /    |   \
                           /      |     \
                        7         9       8
                    / | \       / |
                  /   |  \     /  |
                3    1    5  2    6

После вставки 4

                                 10
                             /   |   \
                           /     |     \
                         7        9       8
                      / | \      / | \
                    /   |  \    /  |   \
                  3    1    5  2   6    4

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

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

Структуры данных и алгоритмы | Комплект 18

0.00 (0%) 0 votes