CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2009

$[\/]$

CI-1201 Programación II

Examen #2 [solución]

Duración: Ciento veinte minutos. 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 todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] 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=(2,1,4,3).

1.b) [33 pts] Implemente el método Lista::Orden_2143() 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) [0 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, ¿cambia mucho el algoritmo que debe usar para clista::Orden_2143()?

2) [33 pts] En esta pregunta usted trabajará con matrices ralas, o sea, con matrices que tienen una gran cantidad de valores iguales.

2.a) [8 pts] Escriba la declaración de la clase RMatriz que tiene las operaciones básicas para manejar matrices ralas. Use un vector de listas para representar los valores almacenados en cada fila de la matriz rala. Como valores almacenados en la lista puede usar elementos de la clase emplantillada "Trio<int,int,T>".

2.b) [5 pts] Especifique el método RMatriz::Traspuesta() que traspone la matriz.

2.c) [20 pts] Implemente el método RMatriz::Traspuesta(). Evite copiar los nodos de las listas que contienen las filas de la matriz.

3) [33 pts] Escriba el programa LNGST.c++ que lee un archivo y cuenta la cantidad de líneas que contiene, y que también indica cuál es la longitud de la línea más larga del archivo. El formato de salida del programa es el siguiente:

C:\> lngst <archivo.txt
lines: [max: 3225]
   40: 123456789.123456789.123456789.123456789
  850: 123456789.123456789.123456789.123456789. >>>
   26: El Pacuare está en peligro

Recuerde que un renglón puede ser arbitrariamente grande, de varios megabytes de longitud. Sin embargo, limítese a imprimir únicamente los primeros 40 caracteres del renglón. Cuando el renglón sea más largo, imprima los símbolos ">>>" al final.

Soluciones

$[/\]$