Рубрики

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

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

1 В куче из n элементов с наименьшим элементом в корне 7-й наименьший элемент может быть найден во времени (GATE CS 2003)
а) Θ (n log n)
б) Θ (н)
c) Θ (log n)
г) Θ (1)

Ответ (г)
7-й самый маленький элемент должен быть в первых 7 уровнях. Общее число узлов в любой двоичной куче на первых 7 уровнях составляет не более 1 + 2 + 4 + 8 + 16 + 32 + 64, что является константой. Поэтому мы всегда можем найти 7-й наименьший элемент за время Θ (1).


2. Предположим, что числа 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 вставлены в этом порядке в изначально пустое двоичное дерево поиска. Бинарное дерево поиска использует обычный порядок на натуральных числах. Какова последовательность обхода по порядку результирующего дерева? (GATE CS 2003)

а) 7 5 1 0 3 2 4 6 8 9
б) 0 2 4 3 1 6 5 9 8 7
в) 0 1 2 3 4 5 6 7 8 9
г) 9 8 6 4 2 3 0 1 5 7

Ответ (с)
Упорядоченный обход BST дает элементы в порядке возрастания. Так что ответ с верен без сомнений.


3. Пусть S будет стеком размером n> = 1. Начиная с пустого стека, предположим, что мы последовательно помещаем первые n натуральных чисел, а затем выполняем n всплывающих операций. Предположим, что операции Push и Pop занимают X секунд каждая, а Y секунд проходит между окончанием одной такой операции стека и началом следующей операции. Для m> = 1 определите срок жизни стека m как время, прошедшее с конца Push (m) до начала операции pop, которая удаляет m из S. Средняя продолжительность стека элемента этого стека равна (GATE CS 2003)

а) n (X + Y)
б) 3Y + 2X
в) n (X + Y) -X
г) Y + 2X

Ответ (с)
Мы можем легко получить результат, взяв несколько примеров.

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

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

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

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

0.00 (0%) 0 votes