Exmn Julio 2010 Ej3b

Exmn Julio 2010 Ej3b

de Tabare Ernesto Rivas Lamique -
Número de respuestas: 2
b) Implemente el TAD ColaPrioAcot en donde las operaciones obtenerMin y borrarMin tienen O(1) de
tiempo de ejecución en el peor caso, escribiendo la representación del TAD y el código de las
operaciones constructoras. Omita el código del resto de las operaciones del TAD.

TYPE
     Lista = POINTER TO Nodo;
           Nodo = RECORD
              sig : Lista;
              info : T;
              prio : CARDINAL
      END;
     ColaPrioAcot = POINTER TO Cabezal;
              Cabezal = RECORD
              lista : Lista;
              cant_elem : CARDINAL
     END;
CONST K = ...;

Dos preguntas: la primera sería si en este ejercicio existe algun impedimento para no poder insertar siempre al final y tener un puntero mas en el cabezal que marque cual es elemento de menor prioridad. En las soluciones contempla alguna que otra forma de hacerlo pero nunca dice nada de esta. 
La segunda es que si me piden una cola de prioridad acotada, el k no tendría que ir dado en el crearcola ya? CrearColaPrioridad(k:CARDINAL):Colaprioridad; de lo contrario nose en que momento se marca cual es el tope.
En respuesta a Tabare Ernesto Rivas Lamique

Re: Exmn Julio 2010 Ej3b

de Yasim Zeballos Rodríguez - INCO -
Respecto a la primera pregunta:
Mmm... podrías insertar siempre al final pero:
* Es claro que obtenerMin va a ser en O(1) como te pide la letra
* ¿Qué pasa con borrarMin? Si borrás a lo que apunta tu "puntero más"
tenés que tener cuidado de dejar bien enganchada la "lista". Eso te haría
ir por el camino de tener una lista doblemente encadenada.

Respecto a la segunda pregunta:
No. No tendría que ir así pues fijate de que la letra no solo te dice que es una cola acotada,
sino que ya te da la cota que es K.
Entonces es por eso que en la implementación está como constante. Eso implica que todas las colas
que crees van a tener K elementos a lo sumo sí o sí.

Otro cantar sería si la letra pidiera que en el TAD tuviera la operación que permita elegir cuantos
elementos van a tener las colas usadas (que eventualmente también se puede pedir que este número
sea menor que K), es un caso levemente más complicado pero no es lo que se pide en este caso.
En respuesta a Yasim Zeballos Rodríguez - INCO

Re: Exmn Julio 2010 Ej3b

de Sebastian Federico Fiamene Antelo -
Yo tengo otra pregunta.... porque en la definicion del TYPE, se define la prioridad de un elemento como CARDINAL y en la operacion InsertarCola al pasarla como parametro a ese PROCEDURE, se lo trata como un INTEGER?

Segundo: 
En la letra dice que el TAD ColaPrioAcot es de un tipo generico, nuevamente en el procedure InsertarCola se trata al campo "info" del RECORD de la informacion que guarda cada nodo de la lista como un INTEGER, cuando deberia de ser tratado como tipo "T" no?

Tercero:
   La linea "(eo^.lista^.prio > prio)" no deberia ser " (eo^.lista^.prio < prio)" ?

Ya que como está planteado en la solucion, si el que quiero insertar tiene una prioridad menor que la que tiene el primero de la lista, me lo insertaria al principio y eso NO es lo que se quiere, de acuerdo al criterio que se usa para ordenar la lista.

Saludos.