Рубрики

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

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

1. Рассмотрим хеш-таблицу седьмого размера с нулевым начальным индексом и хеш-функцией (3x + 4) mod7. Предполагая, что хеш-таблица изначально пуста, что из следующего является содержимым таблицы, когда последовательность 1, 3, 8, 10 вставляется в таблицу с использованием закрытого хеширования? Обратите внимание, что «_» обозначает пустое место в таблице.

(A) 8, _, _, _, _, _, 10
(B) 1, 8, 10, _, _, _, 3
(C) 1, _, _, _, _, _, 3
(D) 1, 10, 8, _, _, _, 3

Ответ (Б)
Пожалуйста, смотрите http://lcm.csa.iisc.ernet.in/dsa/node38.html для закрытого хеширования и зондирования.

Положим значения 1, 3, 8, 10 в хэш размера 7.

Изначально хеш-таблица пуста

    -    -    -   -   -   -   -
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 1 равно 0, поэтому давайте поместим значение в 0

    1    -    -   -   -   -   -
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 3 равно 6, поэтому давайте поместим значение в 6

    1    -    -   -   -   -   3
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 8 равно 0, но 0 уже занято, поместим значение (8) в следующее доступное пространство (1)

    1    8    -   -   -   -   3
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 10 равно 6, но 6 уже занято, поместим значение (10) в следующее доступное пространство (2)

    1    8   10   -   -   -   3
    0    1   2    3   4   5   6


2. В невзвешенном неориентированном связном графе кратчайший путь от узла S к каждому другому узлу вычисляется наиболее эффективно с точки зрения сложности времени

(A) Алгоритм Дейкстры, начиная с S.
(B) алгоритм Варшалла
(C) Выполнение DFS, начиная с S.
(D) Выполнение BFS, начиная с S.

Ответ (D)

 * Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)  
 * Time Comlexity of the Warshall’s algorithm is O(|V|^3)
 * DFS cannot be used for finding shortest paths
 * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

3. Полное n-арное дерево — это дерево, в котором у каждого узла есть n дочерних элементов или нет дочерних. Пусть I будет числом внутренних узлов, а L будет количеством листьев в полном n-арном дереве. Если L = 41, а I = 10, каково значение n?
(А) 3
(Б) 4
(С) 5
(D) 6

Ответ (С)
Для n-арного дерева, где у каждого узла есть n дочерних или нет дочерних, выполняется следующее соотношение

    L = (n-1)*I + 1

Где L — количество листовых узлов, а I — количество внутренних узлов.

Давайте выясним значение n для заданных данных.

  L = 41 , I = 10
  41 = 10*(n-1) + 1
  (n-1) = 4
  n = 5

4. В следующей функции C пусть n> = m.

int gcd(n,m)

{

  if (n%m ==0) return m;  

  n = n%m;

  return gcd(m,n);

}

Сколько рекурсивных вызовов выполняется этой функцией?
(A) Θ (logn)?
(B) Ω (n)
(C) Θ (логлогния)
(D) Θ (sqrt (n))

Ответ (А)
Вышеприведенный код представляет собой реализацию евклидова алгоритма для нахождения наибольшего общего делителя (GCD).
Пожалуйста, смотрите http://mathworld.wolfram.com/EuclideanAlgorithm.html для сложности времени.

5. Какова временная сложность следующей рекурсивной функции:

int DoSomething (int n) 

{

  if (n <= 2)

    return 1;

  else  

    return (DoSomething (floor(sqrt(n))) + n);

}

(A) Θ (n)
(B) Θ (nlogn)
(C) Θ (logn)
(D) Θ (журнал)

Ответ (D)
Рекурсивное отношение для DoSomething ()

  T(n) =  T(√n) + C1 if n > 2  

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

  Let n = 2^m,  T(n) = T(2^m)
  Let T(2^m) =  S(m)

  From the above two, T(n) = S(m)

  S(m) = S(m/2) + C1  /* This is simply binary search recursion*/
  S(m)  = O(logm)      
          = O(loglogn)  /* Since n = 2^m */
  
  Now, let us go back to the original recursive function T(n) 
  T(n)  = S(m) 
          = O(LogLogn)

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

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

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

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

0.00 (0%) 0 votes