Examen #1 [solución]

      Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

 L->last ───────────────────────────────────────┐
                                                │
┌────────────┐   ┌────────────┐   ┌───────────┐ │
│            v   │            v   │           v v
│ ┌────────┬───┐ │ ┌────────┬───┐ │ ┌────────┬───┐
│ │ elem_1 │ ├─┼─┘ │ elem_2 │ ├─┼─┘ │ elem_3 │ ├─┼─┐
│ └────────┴───┘   └────────┴───┘   └────────┴───┘ │
│            ^               next              ^   │
│            │                                 │   │
│          first                             last  v
└───────<───────────────<────────────────<─────────┘

      La clase clist es una lista circular, en que el último nodo apunta al primero. A diferencia de una lista tradicional, en que en el Rep hay un puntero al primer nodo, en una lista circular el puntero del Rep apunta al último nodo, de manera que se pueden hacer inserciones eficientemente tanto al principio como al final de la lista.

1.a) [0 pts] Dibuje el modelo para la lista circular L=(3,2,1,4).

1.b) [0 pts] Implemente el método clist::Orden_3214() que reacomoda los nodos de la lista "L" de manera que queden ordenados usando únicamente instrucciones de asignación. No use otro tipo de sentencias; tampoco trate de escribir un algoritmo general: basta que las 6 asignaciones funcionen para esta lista "L". Use 6 o menos asignaciones de punteros, para que los nodos de la lista "L" queden en orden ascendente (1,2,3,4). En su solución usted puede usar sólo un puntero como variable temporal. Al hacer su solución debe mostrar el diagrama de la lista después de que se ejecuta cada instrucción.

1.c) [33 pts] Si usara una lista sencilla, en que el Rep tiene un puntero al primer nodo de la cadena de nodos, y en el último está el puntero nulo, ¿cómo quedaría implementado el algoritmo que debe usar para clist::Orden_3214()?

2.a) [6 pts] Escriba el archivo de encabezado "String_List.h" que contiene la abstracción y la especificación para la clase "String_List", que permite usar hileras implementadas como listas. Use el operador de suma "+" para concatenar hileras. No olvide incluir el Rep. Use la misma clase lista que utilizó en las tareas programadas, pero no se le meta al Rep de la lista.

2.b) [6 pts] Especifique e implemente el operador de asignación para la clase "String_List".

2.c) [6 pts] Especifique e implemente el constructor de copia para la clase "String_List".

2.d) [6 pts] Especifique e implemente el operador de asignación desde una hilera C++.

2.e) [9 pts] Especifique e implemente el operador de concatenación.

2.f) [0 pts] Especifique e implemente el convertidor de la clase "String_List" a "(char *)". Explique cómo se debe administrar la memoria dinámica del objeto retornado.

3) [33 pts] La aritmética con números de enteros de precisión arbitraria es muy atractiva.

3.a) [8 pts] Escriba la parte del archivo de encabezado "Bin_Num.h" que contiene la abstracción de la clase que sirve para usar números binarios de longitud arbitraria, pues están implementados de forma que si hacen falta más dígitos se le pueden agregar.

3.b) [8 pts] Describa 2 maneras diferentes de implementar esta clase. Incluya la definición del Rep para cada una de las opciones. También haga un diagrama explicativo de cómo queda implementada la clase.

3.c) [8 pts] Use la clase "Bin_Num" para escribir completo el archivo de encabezado de la clase "Bin_Racional", que contiene números racionales con numerador y denominador de precisión arbitraria.

3.d) [9 pts] Suponga que su clase "Bin_Racional" cuenta con los métodos Bin_Racional::num() y Bin_Racional::den() que sirven para obtener el numerador y denominador del número racional. Use estas 2 operaciones, junto con las otras operaciones aritméticas de la clase "Bin_Num", para implementar la función booleana check_ok(), que verifica la invariante de la clase sin acceder al Rep. Suponga que usted ya cuenta con la función mcd(p,q) que calcula el máximo común divisor de los 2 números racionales "p" y "q" y que también cuenta con la versión de check_ok() para racionales.

3.e) [0 pts] Explique qué limitaciones tiene su implementación de la función check_ok().

#include <string.h> // strlen() char *strrev(char *s) { unsigned len = strlen( s ); char *left = s, *right = &s[len-1]; if ( len != 0 ) { while (left != right) { char temp = *left; // swap *left = *right; *right = temp; left++; right--; // next } } return s; }

4.a) [5 pts] Haga la especificación para strrev().

4.b) [14 pts] Haga los casos y datos de prueba de caja negra para la función strrev().

4.c) [14 pts] Haga los casos y datos de prueba de caja blanca para la función strrev().

4.d) [0 pts] Critique esta implementación indique cómo corregirla.

Soluciones

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