PUERTA | Puerta TI 2008 | Pregunta 69

Un árbol de búsqueda binaria (BST) almacena valores en el rango de 37 a 573. Considere la siguiente secuencia de claves.

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 

Supongamos que se ha buscado sin éxito la clave 273 en el BST. ¿Cuáles de las secuencias anteriores enumeran los Nodes en el orden en que podríamos haberlos encontrado en la búsqueda?
(A) Solo II y III
(B) Solo I y III
(C) Solo III y IV
(D) Solo III

Respuesta: (D)
Explicación: Clave a buscar 273:

• I) 81, 537, 102, 439, 285, 376, 305 no es correcto
  No podemos ir a 376 desde 285 ya que 273 es menor que 285.
• II) 52, 97, 121, 195, 242, 381, 472 no es correcto.
  No podemos ir a 472 desde 381 porque 273 es más pequeño que 381.
• III) 142, 248, 520, 386, 345, 270, 307 es correcto
  
• 550, 149, 507, 395, 463, 402, 270 no es correcto.
  No podemos ir al 463 del 395 en busca del 273

La siguiente representación de los árboles de búsqueda binarios se da a continuación.

Quiz of this Question