Рубрики

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

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

1. Предположим, вам дан массив s [1… n] и процедура reverse (s, i, j), которая меняет порядок элементов в позициях между позициями i и j (оба включительно). Что означает следующая последовательность

do, where 1 

(GATE CS 2000)
(а) вращается влево на k позиций
(б) оставляет без изменений
(c) Обращает все элементы
(d) Ничего из вышеперечисленного

Ответ: (а)
Эффект вышеупомянутых 3 обращений для любого k эквивалентен левому вращению массива размера n на k. Пожалуйста, смотрите этот пост для деталей.
Если мы повернем массив n раз для k = 1 до n, мы получим тот же массив обратно.

2. Лучшей структурой данных для проверки того, имеет ли арифметическое выражение сбалансированные скобки, является (GATE CS 2004)
очередь
б) стек
в) дерево
г) список

Ответ (б)
Есть три типа скобок [] {} (). Ниже приведен сегмент кода произвольного c, который содержит круглые скобки всех трех типов.

void func(int c, int a[])

{

   return  ((c +2)  + arr[(c-2)]) ; 

}

Стек является простым выбором для проверки сбалансированности левой и правой скобок. Вот алгоритм, чтобы сделать то же самое.

/ * Вернуть 1, если выражение имеет сбалансированные скобки * /

bool areParenthesesBalanced(expression )

   for each character in expression

   {

      if(character == ’(’ || character == ’{’ || character == ’[’) 

        push(stack, character);

      if(character == ’)’ || character == ’}’ || character == ’]’) 

      {

         if(isEmpty(stack))  

           return 0; / * Мы видим правильную скобку

                       без левой пары * /

  

         / * Вытолкнуть верхний элемент из стека, если это не пара

             скобка символа, то есть несоответствие.

             Это произойдет для выражений типа {(}) * /

         else if (! isMatchingPair(pop(stack), character) ) 

           return 0;   

      }

   }

    

   if(isEmpty(stack))

     return 1; / * * Сбалансирован /

   else  

     return 0;  / * не сбалансировано * /   

} / * Конец функции для проверки скобок * /

  
/ * Возвращает 1, если символ 1 и символ 2 совпадают слева

   и правильные скобки * /

bool isMatchingPair(character1, character2)

{

   if(character1 == ‘(‘ && character2 == ‘)’)

     return 1;

   else If(character1 == ‘{‘ && character2 == ‘}’)

     return 1;

   else If(character1 == ‘[‘ && character2 == ‘]’)

     return 1;

   else 

     return 0;

}


3. Уровень порядка обхода корневого дерева можно сделать, начиная с корня и выполняя (GATE CS 2004)

а) предзаказ обхода
б) в порядке обхода
в) поиск в глубину
г) поиск в ширину

Ответ (г)
Смотрите этот пост для деталей


4. Учитывая следующие данные (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) и хеш-функцию x mod 10, какое из следующих утверждений является истинным?
я. 9679, 1989, 4199 хэшей с тем же значением
II. 1471, 6171 имеет одинаковое значение
III. Все элементы хэшируются с одинаковым значением
внутривенно Каждый элемент хеширует свое значение
(GATE CS 2004)

а) я только
б) только II
c) только i и ii
г) iii или iv

Ответ (с)

5. Обращение по заданному бинарному поисковому дереву по порядку: T выдает следующую последовательность ключей
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Какая из следующих последовательностей ключей может быть результатом обхода по порядку дерева T? (GATE CS 2005)

а) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
б) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
в) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
г) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Ответ (а)
Обход по порядку следования BST всегда дает элементы в порядке возрастания. Среди всех четырех вариантов а) является единственной возрастающей последовательностью заказов.

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

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

0.00 (0%) 0 votes