Рубрики

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

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

1. Следующая функция C принимает просто связанный список в качестве входного аргумента. Он изменяет список, перемещая последний элемент в начало списка и возвращает измененный список. Некоторая часть кода оставлена пустой.

typedef struct node 

{

  int value;

  struct node *next;

}Node;

  
Node *move_to_front(Node *head) 
{

  Node *p, *q;

  if ((head == NULL: || (head->next == NULL)) 

    return head;

  q = NULL; p = head;

  while (p-> next !=NULL) 

  {

    q = p;

    p = p->next;

  }

  _______________________________

  return head;

}

Выберите правильный вариант, чтобы заменить пустую строку.
(A) q = NULL; р-> следующий = голова; голова = р;
(B) q-> next = NULL; голова = р; р-> следующий = голова;
(С) голова = р; p-> next = q; q-> next = NULL;
(D) q-> next = NULL; р-> следующий = голова; голова = р;

Ответ (D)
Когда цикл while заканчивается, q содержит адрес второго последнего узла, а p содержит адрес последнего узла. Таким образом, мы должны сделать следующие вещи после цикла while.
я) Установите следующий из q как NULL (q-> next = NULL).
ii) Установите следующее из p в качестве заголовка (p-> next = head).
iii) Сделать голову как р (голова = р)
Шаг (ii) должен быть выполнен до шага (iii). Если мы сначала изменим заголовок, то мы потеряем след узла заголовка в исходном связанном списке.
Смотрите http://espressocode.top/?p=6850 для более подробной информации.

2. Хеш-таблица длиной 10 использует открытую адресацию с хеш-функцией h (k) = k mod 10 и линейное зондирование. После вставки 6 значений в пустую хеш-таблицу таблица выглядит так, как показано ниже.

Какой из следующих вариантов дает возможный порядок, в котором значения ключей могли быть вставлены в таблицу?
(А) 46, 42, 34, 52, 23, 33
(В) 34, 42, 23, 52, 33, 46
(С) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52

Ответ (С)
Последовательность (A) не создает хеш-таблицу, так как элемент 52 появляется до 23 в этой последовательности.
Последовательность (B) не создает хеш-таблицу, поскольку элемент 33 появляется перед 46 в этой последовательности.
Последовательность (C) создает хеш-таблицу, поскольку 42, 23 и 34 появляются перед 52 и 33, а 46 появляется перед 33.
Последовательность (D) не создает хеш-таблицу, так как элемент 33 появляется перед 23 в этой последовательности.

3. Сколько различных последовательностей вставки значений ключа, использующих одну и ту же хеш-функцию и линейное зондирование, приведут к хеш-таблице, показанной выше?
(А) 10
(Б) 20
(С) 30
(D) 40

Ответ (С)
В правильной последовательности вставки элементы 42, 23 и 34 должны появляться до 52 и 33, а 46 должны появляться до 33.
Общее количество различных последовательностей = 3! х 5 = 30
В вышеприведенном выражении 3! для элементов 42, 23 и 34, поскольку они могут появляться в любом порядке, и 5 для элемента 46, поскольку они могут появляться в 5 разных местах.

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

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

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

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

0.00 (0%) 0 votes