Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 69

Двоичное дерево поиска (BST) хранит значения в диапазоне от 37 до 573. Рассмотрим следующую последовательность ключей.


I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Предположим, что в BST был неудачно найден ключ 273. Какие из всех вышеперечисленных последовательностей перечисляют узлы в порядке, в котором мы могли бы встретить их при поиске?
(A) только II и III
(B) только I и III
(C) только III и IV
(D) III только

Ответ: (D)
Пояснение: Ключ для поиска 273:

  • I) 81, 537, 102, 439, 285, 376, 305 не правильно
    Мы не можем перейти к 376 из 285, так как 273 меньше, чем 285.
  • II) 52, 97, 121, 195, 242, 381, 472 не правильно.
    Мы не можем перейти к 472 из 381, так как 273 меньше, чем 381.
  • III) 142, 248, 520, 386, 345, 270, 307 правильно
  • 550, 149, 507, 395, 463, 402, 270 не правильно.
    Мы не можем перейти к 463 из 395 в поисках 273

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

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

ВОРОТА | Gate IT 2008 | Вопрос 69

0.00 (0%) 0 votes