Estructuras de datos y algoritmos | Conjunto 24

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

1. La siguiente función de C toma una lista de enlace simple como argumento de entrada. Modifica la lista moviendo el último elemento al frente de la lista y devuelve la lista modificada. Una parte del código se deja en blanco.

typedef struct node 
{
  int value;
  struct node *next;
}Node;
  
Node *move_to_front(Node *head) 
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL)) 
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL) 
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}

Elija la alternativa correcta para reemplazar la línea en blanco.
(A) q = NULO; p->siguiente = cabeza; cabeza = p;
(B) q->siguiente = NULL; cabeza = p; p->siguiente = cabeza;
(C) cabeza = p; p->siguiente = q; q->siguiente = NULL;
(D) q->siguiente = NULL; p->siguiente = cabeza; cabeza = p;

Respuesta (D)
Cuando finaliza el bucle while, q contiene la dirección del penúltimo Node yp contiene la dirección del último Node. Así que tenemos que hacer lo siguiente después del bucle while.
i) Establecer el siguiente de q como NULL (q->next = NULL).
ii) Establecer siguiente de p como cabeza (p->siguiente = cabeza).
iii) Hacer la cabeza como p (cabeza = p) El
paso (ii) debe realizarse antes del paso (iii). Si cambiamos la cabeza primero, perdemos la pista del Node principal en la lista enlazada original.
Consulte https://www.geeksforgeeks.org/?p=6850 para obtener más detalles.

2. Una tabla hash de longitud 10 utiliza direccionamiento abierto con función hash h(k)=k mod 10 y sondeo lineal. Después de insertar 6 valores en una tabla hash vacía, la tabla es como se muestra a continuación.

¿Cuál de las siguientes opciones da un orden posible en el que los valores clave podrían haberse insertado en la tabla?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33 , 23, 34, 52

Respuesta (C)
La secuencia (A) no crea la tabla hash ya que el elemento 52 aparece antes que el 23 en esta secuencia.
La secuencia (B) no crea la tabla hash ya que el elemento 33 aparece antes que el 46 en esta secuencia.
La secuencia (C) crea la tabla hash ya que 42, 23 y 34 aparecen antes que 52 y 33, y 46 aparece antes que 33.
La secuencia (D) no crea la tabla hash ya que el elemento 33 aparece antes que 23 en esta secuencia.

3. ¿Cuántas secuencias de inserción diferentes de los valores clave usando la misma función hash y sondeo lineal resultarán en la tabla hash que se muestra arriba?
(A) 10
(B) 20
(C) 30
(D) 40

Respuesta (C)
En una secuencia de inserción válida, los elementos 42, 23 y 34 deben aparecer antes de 52 y 33, y 46 debe aparecer antes de 33. ¡
Número total de secuencias diferentes = 3! x 5 = 30
En la expresión anterior, 3! es para los elementos 42, 23 y 34 ya que pueden aparecer en cualquier orden, y 5 es para el elemento 46 ya que puede aparecer en 5 lugares diferentes.

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.