Examen Parcial #2

      Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la buena presentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Use su lenguaje preferido. ¡No haga más de lo que se le pide!

1) [25 pts] Considere el contenedor Arbol Binario Ordenado, que sirve para representar multi-conjuntos ordenados, esto esto es, conjuntos en que un mismo elemento aparece más de una vez. En el multi-conjunto [1, 1, 2, 3] el valor "1" está dos veces, y la cantidad de elementos almacenados es cuatro. Una forma de implementar el multi-conjunto es usar el tipo TOrdBinTree definido de la siguiente forma:

TYPE                            TYPE
  TNode = OBJECT                  TOrdBinTree = OBJECT
    _val   : LONGINT;               _root    : ^TNode; { raíz }
    _count : WORD;                  ...
    _left,                          PROCEDURE Insert (l:LONGINT);
    _right : ^TNode;                PROCEDURE Print;
  END;                            END; { TOrdBinTree }

      El campo "_count" contiene la cantidad de veces que aparece el valor "_val" en el multi-conjunto. Los punteros a los nodos hijos están en los campos "_left" y "_right". Si al insertar un nuevo valor "l" el método TOrdBinTree.Insert(l) encuentra un nodo que ya contiene a "l", entonces lo que hace es incrementar la cuenta de valores "_count" del nodo.

      Otra forma de implementar el multi-conjunto es eliminar del nodo al campo "_count", y en su lugar implementar la inserción de forma que el árbol pueda contener varios nodos con el mismo valor.

      La operación TOrdBinTree.Insert(l) es ESTABLE si siempre que un nodo es insertado en el árbol ANTES que otro, entonces siempre ocurrirá que su valor será impreso primero por TOrdBinTree.Print().

1.a [10 pts] Implemente la operación TOrdBinTree.Insert(l) para un árbol binario ordenado en que el mismo valor puede aparecer en más de un nodo. Incluya las declaraciones de tipos que usted use. Trate de que su implementación sea estable. No use recursividad.

1.b) [10 pts] Diga si su implementación del punto anterior es estable. Si lo es, entonces muéstrelo fehacientemente. Si no lo es, entonces explique porqué es imposible lograr una implementación estable.

1.c) [5 pts] Compare las ventajas y desventajas de implementar el multi-conjunto con y sin usar el campo "_count" en cada nodo. Calcule la complejidad de ambas alternativas, en tiempo y espacio.

2) [25 pts] Considere las matrices triangulares, que tiene una de las dos siguientes formas:

                               M2[6 x 4] [Sup:21]
M1[4 X 7] [Inf:0]                    1 2 3 4
   1 . . . . . .                     . 5 6 7
   2 3 . . . . .                     . . 8 9
   4 5 6 . . . .                     . . . 0
   7 8 9 0 . . .                     . . . .
                                     . . . .

      La matriz M1 es una matriz triangular inferior [4 x 7]; cada puntito que aparece sobre la diagonal representa el valor 0 (cero). La matriz M2 es una matriz triangular superior [6 x 4], y bajo la diagonal hay 14 valores iguales; cada puntito representa el valor 21 (veintiuno). Asuma que los valores de la matriz son de tipo REAL.

2.a) [5 pts] Escriba la definición de tipos para el objeto TMatrizTriangular, que sirve para implementar matrices triangulares. Incluya todos los tipos auxiliares que necesite. Defina también los métodos que necesite.

      Suponga que usted usará un vector unidimensional "_val" con índices en el rango [0..MxDim-1], para almacenar los valores de la matriz pero evite almacenar los valores repetidos (0 en el caso de M1 y 12 en el caso de M2) Almacene los valores de la matriz AL FINAL del vector, y no al principio. Incluya diagramas en su respuesta.

2.b) [10 pts] Derive una fórmula que sirva para transformar dos índices (i,j) en la posición dentro del vector "_val" en que está almacenado el valor M[i,j]. Recuerde que los valores quedan almacenados desde la parte de atrás del vector hacia adelante. Defina las restricciones que necesite sobre los valores (i,j). Tome en cuenta que los valores de la matriz están almacenados AL FINAL del vector, y no al principio.

2.c) [5 pts] Use la fórmula que usted derivó en el punto anterior para implementar el método TMatrizTriangular.Get(i,j) : REAL; que devuelve el valor almacenado en la posición (i,j) de la matriz triangular. Genere un error en tiempo de ejecución si (i,j) está fuera de rango.

2.d) [5 pts] Diga cuál puede ser la utilidad de almacenar los valores de la matriz al final del vector en lugar de la principio, como es lo usual.

3) [25 pts] Calcule la complejidad del algoritmo Búsqueda Binaria si la particion que se hace NO es por la mitad (low+high)/2 sino mas bien en las 2/3 partes: 2*(low+high)/3. Diga cuál de las dos formas de partir resulta en un algoritmo mejor. Comente el impacto que tiene esta forma diferente de partir el intervalo en la complejidad del algoritmo.

4) [25 pts] Los programas manipulan dos tipos de memoria: la estática y la dinámica. Para implementar el acceso a memoria dinámica lo usual es especificar dos operaciones básicas: GetMem(p,sz) y FreeMem(p,sz) en Pascal, o malloc(p,sz) y free(p,sz) en C.

4.a) [0 pts] Especifique las dos operaciones de manejo de memoria dinámica.

4.b) [10 pts] Para manejar los bloques disponibles particione la memoria dinámica disponible en K diferentes segmentos, cada uno con capacidad de almacenar bloques contiguos de tamaño 2^K; incluya restricciones adicionales sobre los bloques si es necesario. Escriba la definición de tipos para el objeto TDinaMem, que sirve para implementar la memoria dinámica. Incluya todos los tipos auxiliares que necesite, y los métodos. Haga diagramas que expliquen cómo está organizada la memoria.

4.c) [5 pts] Calcule la complejidad de tiempo y espacio cada una de las operaciones de asignación y liberación de memoria.

4.d) [5 pts] Implemente las operaciones del punto anterior.

4.e) [5 pts] Proponga un esquema que mejore el propuesto en la parte b) de esta pregunta. Explique porqué su esquema es mejor. Calcule la complejidad de tiempo y espacio de su esquema.

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1996
Derechos de autor reservados © 1996