Рубрики

Структуры данных | Бинарные деревья | Вопрос 9

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

Ответ: (Д)
Объяснение: Пусть максимально возможная высота дерева с п узлами представлена Н (п).

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

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

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


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

Тест на этот вопрос

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

Структуры данных | Бинарные деревья | Вопрос 9

0.00 (0%) 0 votes