Estructuras de datos y algoritmos | conjunto 3 – Part 8

Las siguientes preguntas se han hecho en el examen GATE CS.

1. Suponga que le dan una array s[1…n] y un procedimiento inverso (s,i,j) que invierte el orden de los elementos en a entre las posiciones i y j (ambas inclusive). ¿Qué significa la siguiente secuencia

do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);

(GATE CS 2000)
(a) Rota s hacia la izquierda k posiciones
(b) Deja s sin cambios
(c) Invierte todos los elementos de s
(d) Ninguno de los anteriores

Respuesta: (a)
El efecto de las 3 inversiones anteriores para cualquier k es equivalente a la rotación a la izquierda de la array de tamaño n por k. Por favor vea esta publicación para más detalles.
Si rotamos una array n veces para k = 1 a n, obtenemos la misma array nuevamente.

2. La mejor estructura de datos para comprobar si una expresión aritmética tiene paréntesis equilibrados es (GATE CS 2004)
a) cola
b) pila
c) árbol
d) lista

Respuesta(b)
Hay tres tipos de paréntesis [ ] { }(). A continuación se muestra un segmento de código arbitrario c que tiene paréntesis de los tres tipos.

void func(int c, int a[])
{
   return  ((c +2)  + arr[(c-2)]) ; 
}

Stack es una opción sencilla para comprobar si los paréntesis izquierdo y derecho están equilibrados. Aquí hay un algoritmo para hacer lo mismo.

/*Return 1 if expression has balanced parentheses */
bool areParenthesesBalanced(expression )
{ 
   for each character in expression
   {
      if(character == ’(’ || character == ’{’ || character == ’[’) 
        push(stack, character);
      if(character == ’)’ || character == ’}’ || character == ’]’) 
      {
         if(isEmpty(stack))  
           return 0; /*We are seeing a right parenthesis  
                       without a left pair*/
  
         /* Pop the top element from stack, if it is not a pair
             bracket of character then there is a mismatch. 
             This will happen for expressions like {(}) */
         else if (! isMatchingPair(pop(stack), character) ) 
           return 0;   
      }
   }
    
   if(isEmpty(stack))
     return 1; /*balanced*/
   else  
     return 0;  /*not balanced*/   
} /* End of function to check parentheses */
  
/* Returns 1 if character1 and character2 are matching left
   and right parentheses */
bool isMatchingPair(character1, character2)
{
   if(character1 == ‘(‘ && character2 == ‘)’)
     return 1;
   else If(character1 == ‘{‘ && character2 == ‘}’)
     return 1;
   else If(character1 == ‘[‘ && character2 == ‘]’)
     return 1;
   else 
     return 0;
}

3. El recorrido en orden de nivel de un árbol enraizado se puede realizar comenzando desde la raíz y realizando (GATE CS 2004)
a) recorrido en orden previo
b) recorrido en orden
c) búsqueda primero en profundidad
d) búsqueda primero en amplitud

Respuesta (d)
Ver esta publicación para más detalles

4. Dada la siguiente entrada (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) y la función hash x mod 10, ¿cuáles de las siguientes afirmaciones son verdaderas?
i. 9679, 1989, 4199 hash al mismo valor
ii. 1471, 6171 tiene el mismo valor
iii. Todos los elementos tienen el mismo valor
iv. Cada elemento tiene un valor hash diferente
(GATE CS 2004)

a) solo i
b) solo ii
c) solo i y ii
d) iii o iv

Respuesta (c)

5. Recorrido posterior al orden de un árbol de búsqueda binario dado, T produce la siguiente secuencia de claves
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
¿Cuál de las siguientes secuencias de claves puede ser el resultado de un recorrido en orden del árbol T? (GATE CS 2005)
a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Respuesta (a)
El recorrido en orden de un BST siempre da elementos en orden creciente. Entre las cuatro opciones, a) es la única secuencia de orden creciente.