Estructuras de datos y algoritmos | conjunto 2 – Part 9

Se han hecho las siguientes preguntas en el examen GATE CS.

1. Considere la función f definida a continuación.

struct item 
{ 
  int data; 
  struct item * next; 
}; 
  
int f(struct item *p) 
{ 
  return (
          (p == NULL) || 
          (p->next == NULL) || 
          (( P->data <= p->next->data) && f(p->next))
         ); 
} 

Para una lista vinculada dada p, la función f devuelve 1 si y solo si (GATE CS 2003)
a) la lista está vacía o tiene exactamente un elemento
b) los elementos en la lista están ordenados en orden no decreciente de valor de datos
c ) los elementos de la lista se ordenan en orden no creciente de valor de datos
d) no todos los elementos de la lista tienen el mismo valor de datos.

Respuesta (b)
La función f() funciona de la siguiente manera
1) Si la lista enlazada está vacía, devuelva 1
2) De lo contrario, si la lista enlazada tiene solo un elemento, devuelva 1
3) De lo contrario, si el Node->datos es menor que igual al Node->siguiente ->datos y lo mismo vale para el resto de la lista y luego devuelve 1
4) De lo contrario, devuelve 0

2. Considere las secuencias de etiquetas obtenidas por los siguientes pares de recorridos en un árbol binario etiquetado. ¿Cuál de estos pares identifica un árbol de forma única (GATE CS 2004)?
i) pre-pedido y post-pedido
ii) en-pedido y post-pedido
iii) pre-pedido y en-pedido
iv) nivel pedido y post-pedido

a) (i) únicamente
b) (ii), (iii)
c) (iii) únicamente
d) (iv) únicamente

Respuesta (b)
Consulte esta publicación para obtener una explicación.

3. Los siguientes números se insertan en un árbol de búsqueda binaria vacío en el orden dado: 10, 1, 3, 5, 15, 12, 16. ¿Cuál es la altura del árbol de búsqueda binaria (la altura es la distancia máxima de un Node hoja desde la raíz)? (GATE CS 2004)
a) 2
b) 3
c) 4
d) 6

Respuesta (b)
El árbol de búsqueda binario construido será…

                    10
                  /     \
                 1       15
                 \      /  \
                  3    12   16
                    \
                     5

4. Se requiere una estructura de datos para almacenar un conjunto de enteros de modo que cada una de las siguientes operaciones se pueda realizar en (log n) tiempo, donde n es el número de elementos en el conjunto.

   o    Deletion of the smallest element 
   o    Insertion of an element if it is not already present in the set

¿Cuál de las siguientes estructuras de datos se puede utilizar para este propósito?
(a) Se puede usar un montón, pero no un árbol de búsqueda binario balanceado
(b) Se puede usar un árbol de búsqueda binario balanceado, pero no un montón
(c) Se pueden usar tanto el árbol de búsqueda binario balanceado como el montón
(d) Ni la búsqueda binaria balanceada árbol ni montón puede ser utilizado

Respuesta (b)
Un árbol de búsqueda binario de equilibrio automático que contiene n elementos permite la búsqueda, inserción y eliminación de un elemento en O (log n) en el peor de los casos. Dado que es un BST autoequilibrado, podemos encontrar fácilmente el elemento mínimo en el tiempo O (inicio de sesión), que siempre es el elemento más a la izquierda (consulte Buscar el Node con el valor mínimo en un árbol de búsqueda binaria ).

Dado que Heap es un árbol binario equilibrado (o un árbol binario casi completo), la complejidad de inserción para el montón es O (logn). Además, la complejidad para obtener el mínimo en un montón mínimo es O (logn) porque la eliminación del Node raíz hace que una llamada se acumule (después de eliminar el primer elemento de la array) para mantener la propiedad del árbol del montón. Pero un montón no se puede usar para el propósito anterior como dice la pregunta: inserte un elemento si aún no está presente. Para un montón, no podemos averiguar en O(logn) si un elemento está presente o no. Gracias al juego por proporcionar la solución correcta.

5. Se utiliza una lista enlazada circularmente para representar una cola. Se utiliza una única variable p para acceder a la cola. ¿A qué Node debe apuntar p para que las operaciones enQueue y deQueue puedan realizarse en tiempo constante? (PUERTA 2004)

a) Node posterior
b) Node frontal
c) no es posible con un solo puntero
d) Node al lado del frente

Respuesta(a)
La respuesta no es “(b) Node frontal”, ya que no podemos retroceder desde el frente en O(1), pero si p es posterior podemos implementar tanto enQueue como deQueue en O(1) porque desde trasero podemos llegar al frente en O(1). A continuación se muestran funciones de muestra. Tenga en cuenta que estas funciones son solo una muestra y no funcionan. Falta el código para manejar los casos base.

/* p is pointer to address of rear (double pointer).  This function adds new 
   node after rear and updates rear which is *p to point to new node  */
void  enQueue(struct node **p, struct node *new_node)
{
    /* Missing code to handle base cases like *p is NULL */
       
     new_node->next = (*p)->next;
     (*p)->next = new_node;
     (*p) = new_node /* new is now rear */
     /* Note that p is again front and  p->next is rear */
 }
  
/* p is pointer to rear. This function removes the front element and 
    returns the new front */
struct node *deQueue(struct node *p)
{
    /* Missing code to handle base cases like p is NULL,
        p->next is NULL,...  etc */
  
    struct node *temp = p->next->next;
    p->next = p->next->next;
    return temp;
    /* Note that p is again front and  p->next is rear */
}