Рубрики

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

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

1. Число листовых узлов в укорененном дереве из n узлов, причем каждый узел имеет 0 или 3 дочерних узла:
а) н / 2
б) (н-1) / 3
в) (н-1) / 2
г) (2n + 1) / 3

Ответ (г)

Пусть L будет числом листовых узлов, а I будет числом внутренних узлов, тогда для вышеупомянутого дерева справедливо следующее соотношение (Подробнее см. Вопрос 3 в http://espressocode.top/data-structures-and-algorithms- набор-11 / )

  L = (3-1)I + 1 = 2I + 1

Общее количество узлов (n) является суммой листовых узлов и внутренних узлов

  n = L + I 

После решения вышеупомянутых двух мы получаем L = (2n + 1) / 3

2. Время работы следующего алгоритма

  Procedure A(n)  
  If n );

лучше всего описывается
а) O (n)
б) O (log n)
в) O (1og log n)
г) О (1)

Ответ (с)
Для объяснения, пожалуйста, см. Вопрос 5 http://espressocode.top/data-structures-and-algorithms-set-11/

3. Сбалансированное дерево — это двоичное дерево, в котором для каждого узла. Количество узлов в левом поддереве составляет, по меньшей мере, половину и самое большее, вдвое больше количества узлов в правом поддереве. Максимально возможная высота (количество узлов на пути от корня до самого дальнего листа) такого дерева на n узлах лучше всего описывается каким из следующих?
а) log 2 n
б) журнал 4/3 n
в) журнал 3 н
г) журнал 3/2 н

Ответ (г)

Пусть максимально возможная высота дерева с n узлами представлена H (n).

Максимально возможное значение H (n) может быть приблизительно записано с использованием следующей рекурсии:

   H(n) = H(2n/3) + 1     

Решение вышеупомянутого повторения является log 3/2 n. Мы можем просто получить его, нарисовав дерево рекурсии.


4. Рассмотрим следующий алгоритм поиска заданного числа x в несортированном массиве A [1..n], имеющем n различных значений:

1)    Choose an i uniformly at random from 1..n; 
2)    If A[i] = x then Stop else Goto 1; 

Предполагая, что x присутствует в A, каково ожидаемое количество сравнений, выполненных алгоритмом до его завершения?
а) н
б) нл
в) 2n
г) н / 2

Ответ (а)

Если вы помните вопросы о монетах и игральных костях, вы можете просто угадать ответ на вышеуказанный вопрос.

Ниже приведено доказательство ответа.

Пусть ожидаемое количество сравнений равно E. Значение E представляет собой сумму следующего выражения для всех возможных случаев.

number_of_comparisons_for_a_case * probability_for_the_case 

Дело 1

  If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n

Дело 2

  If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n

Дело 3

  If A[i] is found in the third attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*(n-1)/n*1/n

На самом деле таких случаев бесконечно много. Итак, мы имеем следующие бесконечные ряды для E.

E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)

Умножив уравнение (1) на (n-1) / n, получим

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Вычитая (2) из (1), получим

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

Выражение справа — это GP с бесконечными элементами. Применим формулу суммы (a / (1-r))

  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n

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

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

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

0.00 (0%) 0 votes