Estructuras de datos y algoritmos | conjunto 4

Se han hecho las siguientes preguntas en el examen GATE CS. 
1. Considere el siguiente segmento de programa C

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
 
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

El valor devuelto por la función HacerAlgo cuando se pasa como argumento un puntero a la raíz de un árbol no vacío es (GATE CS 2004) 
a) El número de Nodes hoja en el árbol 
b) El número de Nodes en el árbol 
c) El número de Nodes internos en el árbol 
d) La altura del árbol
Respuesta: (d) 
Explicación: HacerAlgo() devuelve max(altura del hijo izquierdo + 1, altura del hijo izquierdo + 1). Entonces, dado que el puntero a la raíz del árbol se pasa a DoSomething(), devolverá la altura del árbol. Tenga en cuenta que esta implementación sigue la convención donde la altura de un solo Node es 0. 

2. Supongamos que ejecutamos el algoritmo de ruta más corta de fuente única de Dijkstra en el siguiente gráfico dirigido ponderado por borde con el vértice P como fuente. ¿En qué orden se incluyen los Nodes en el conjunto de vértices para los cuales se finalizan las distancias de camino más cortas? (GATE CS 2004)
a) P, Q, R, S, T, U 
b) P, Q, R, U, S, T 
c) P, Q, R, U, T, S 
d) P, Q, T, R, U, S
 

Respuesta (b)

3. Suponga que cada conjunto se representa como una lista enlazada con elementos en orden arbitrario. ¿Cuál de las operaciones entre unión, intersección, membresía, cardinalidad será la más lenta? (GATE CS 2004) 
a) solo unión 
b) intersección, membresía 
c) membresía, cardinalidad 
d) unión, intersección
Respuesta: (d) 
La cardinalidad y la membresía definitivamente no son las más lentas. Para la cardinalidad, solo cuente la cantidad de Nodes en una lista. Para la membresía, simplemente recorra la lista y busque una coincidencia.
Para obtener la intersección de L1 y L2, busque cada elemento de L1 en L2 e imprima los elementos que encontramos en L2. 
Puede haber muchas formas de conseguir la unión de L1 y L2. Uno de ellos es el siguiente 
a) Imprime todos los Nodes de L1 e imprime solo aquellos que no están presentes en L2. 
b) Imprimir Nodes de L2.

4. La complejidad temporal de la siguiente función C es (suponga que n > 0 (GATE CS 2004) 

int recursive (mt n)
{
   if (n == 1)
     return (1);
   else
     return (recursive (n-1) + recursive (n-1));
}

a) 0(n) 
b) 0(nlogn) 
c) 0(n^2) 
d) 0(2^n)
Respuesta: (d) 
Explicación: 
La expresión recursiva para el programa anterior será. 

T(n) = 2T(n-1) + c
T(1) = c1.

Vamos a resolverlo. 

T(n) = 2(2T(n-2) + c) + c        = 4T(n-2) + 3c
T(n) = 8T(n-3) + 6c + c          =  8T(n-3) + 7c
T(n) = 16T(n-4) + 14c + c        =  16T(n-4) + 15c
...................................................
...................................................
T(n) = (2^(n-1))T(1) +  (2^(n-1) - 1)c
T(n) = O(2^n)

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones anteriores es incorrecta.