Рубрики

Структуры данных и алгоритмы | Набор 10

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

1. Высота бинарного дерева — это максимальное количество ребер в любом пути от корня к листу. Максимальное количество узлов в двоичном дереве высотой h составляет:
(А) 2 ^ ч -1
(B) 2 ^ (ч-1) — 1
(С) 2 ^ (ч + 1) -1
(D) 2 * (ч + 1)

Ответ (С)
Максимальное количество узлов будет там для полного дерева.
Количество узлов в полном дереве высотой h = 1 + 2 + 2 ^ 2 + 2 * 3 +…. 2 ^ h = 2 ^ (h + 1) — 1

2: Максимальное количество бинарных деревьев, которые могут быть сформированы с тремя немечеными узлами, равно:
(А) 1
(Б) 5
(С) 4
(D) 3

Ответ (Б)

             O
          /     \
        O        O
           (i)

            O             
          /                             
       O                 
     /                      
   O                         
        (ii)

         O
       / 
     O
        \
          O
       (iii)

  O                      
     \                        
       O                     
          \                  
           O                                                         
    (iv)

       O
          \
            O
          /
       O               
    (v)

Обратите внимание, что узлы немаркированы. Если узлы помечены, мы получаем больше деревьев.

3. Какой из следующих алгоритмов сортировки имеет наименьшую сложность в худшем случае?
(A) сортировка слиянием
(B) пузырьковая сортировка
(С) Быстрая сортировка
(D) Выбор сортировки

Ответ (А)

В худшем случае сложности для вышеупомянутых алгоритмов сортировки следующие:
Сортировка слиянием — nLogn
Bubble Sort — n ^ 2
Быстрая сортировка — n ^ 2
Сортировка выбора — n ^ 2

4. Следующее постфиксное выражение с однозначными операндами оценивается с помощью стека:

              8 2 3 ^ / 2 3 * + 5 1 * - 

Обратите внимание, что ^ является оператором возведения в степень. Два верхних элемента стека после первого * оцениваются:
(А) 6, 1
(Б) 5, 7
(С) 3, 2
(D) 1, 5

Ответ (А)
Алгоритм вычисления любого постфиксного выражения довольно прост:

1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.

Источник для алгоритма: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm

Запустим приведенный выше алгоритм для данного выражения.
Первые три токена являются значениями, поэтому они просто выдвигаются. После нажатия 8, 2 и 3 стек выглядит следующим образом

    8, 2, 3  

Когда ^ читается, верхние два выталкиваются и вычисляется мощность (2 ^ 3)

    8, 8 

Когда / читается, верхние два выталкиваются и выполняется деление (8/8)

    1 

Следующие два токена являются значениями, поэтому они просто выдвигаются. После нажатия 2 и 3 стек выглядит следующим образом

    1, 2, 3

Когда * приходит, две верхние появляются и умножение выполняется.

    1, 6


5. Обход по бинарному дереву по порядку и порядку — это dbeafcg и abdecfg соответственно. Обращение по порядку бинарного дерева:

(A) debfgca
(B) edbgfca
(С) edbfgca
(D) defgbca

Ответ (А)

Below is the given tree.
                              a 
                           /    \
                        /          \
                      b             c
                   /   \          /   \
                 /       \      /       \
               d         e    f          g

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

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

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

Структуры данных и алгоритмы | Набор 10

0.00 (0%) 0 votes