Newsgroup: it.comp.java
Titolo: [Spero non troppo OT] Ancora un test d'esame

Salve, avrei un altro test d'esame da sottoporvi, dato che mi ha 
lasciato piuttosto sorpreso. Spero che non sia troppo OT, in caso 
sareste gentili a consigliarmi un altro posto (ed in tal caso mi scuso 
anche).
Ho studiato come scrivere in java alcuni ADT semplici e su di un esempio 
di test d'esame ho trovato questa domdanda:
in una coda realizzata come catena a collegamento doppio:
1. gli inserimenti sono possibili solo in testa, ma le estrazioni sono 
possibili sia in testa che in coda.
2. gli inserimenti sono possibili solo in coda
3. gli inserimenti sono possibili sia in testa che in coda
4. gli inserimenti sono possibili solo in coda, ma le estrazioni sono 
possibili sia in testa che in coda.
io avrei detto 3, dato che teoricamente potrei inserire in testa e 
rimuovere in coda oppure fare il contrario. Però la risposta corretta è 
la 4, e come spiegazione il prof ha scritto sotto che in un ADT coda 
lò'inserimento è possibile solo in coda a prescindere 
dall'implementazione. Eppure io ho trovato la parte in cui si spiega 
questo e come ricordavo c'è scritto che questa soluzione è la sola ad 
avere prestazioni O(1), quindi la migliore, ma non la sola.
Voi che ne dite?
Scusate ancora nel caso in cui sia troppo OT.
Luca

 dall'implementazione.
Secondo me la risposta giusta non è nemmeno la 4. 
La 2 è sicuramente corretta. La 4 secondo me è sbagliata perché in una coda
(a prescindere dall'implementazione) si inserisce in coda e si toglie in
testa. Non "si inserisce in coda e si toglie dove ti pare" :)
Per quanto riguarda le implementazioni in questo caso non te ne deve fregare
niente. Stiamo parlando di un tipo di dato _astratto_, quindi la domanda è
sul suo comportamento non sulla sua realizzazione.
Poi puoi anche realizzare una coda con 14 alberi concatenati in qualche modo
curioso (se ci riesci :) basta che il primo oggetto che entra è il primo
che esce (ed il secondo è il secondo... e così via :). E non è che se
realizzo la coda con 14 alberi vuol dire che posso inserire in coda e
prelevare ovunque tra le foglie degli alberi perché tanto l'importante è
inserire in coda, come sostiene il tuo proff :)
E se sei della Sapienza vista la cazzata indovino pure chi é ;))
Ciao
Matteo
-- 
chi sono e soprattutto chi non sono:
http://www.ilnomedeldominio.it
un piccolo programma per studenti universitari:
http://inutility.ilnomedeldominio.it/imsv/

In una coda standard, l'inserimento avviene in coda, l'estrazione in 
testa. Ma la domanda si riferisce a una "coda realizzata come catena a 
collegamento doppio", detta piů propriamente "coda doppiamente 
concatenata". In questo caso l'inserimento e l'estrazione possono 
avvenire sia in coda che in testa, quindi la risposta giusta č la 3.
Mi sembra molto strano che un prof. sbagli una cosa cosě banale... a 
meno che non sia proprio un incompetente!
ciao

 ha scritto nel messaggio
news:XvmDb.216218$hV.84...@news2.tin.it...

secondo le mie attuali conoscenze in materia, nel TDA CODA l'inserimento è
possibile solamente in coda e l'estrazione in testa proprio perchè per
definizione una coda è una struttura dati FIFO. Il vincolo di inserimento
ed estrazione non è dato dall'implementazione della coda ma dalla
definizione di TDA CODA: nel caso classico un array o una lista linkata. La
lista doppiamente linkata invece si usa per la DEQUE che non è altro che
una CODA A DOPPIO INGRESSO dove è possibile fare estrazioni e inserimenti
sia dalla coda che dalla testa. Pertanto la domanda formulata nel test è
sbagliata perchè una coda a doppio collegamento può anche esistere ma
essendo TDA CODA deve rispettare il vincolo di inserimento in coda ed
estrazione in testa, indipendentemente dalla sua implementazione (lista
linkata, lista doppiamente linkata, array, ecc). quindi io avrei risposto
2. senza considerare le prestazioni ovviamente perchè qui il discorso
diventa un pò più complesso e la risposta potrebbe essere un'altra da un
certo punto di vista, ma visto che di complessità e prestazioni non se ne
parla nella domanda io avrei risposto sicuramente 2.

 concatenata". 
No no, sono due cose diverse. Qui si parla di CODA. Non di una coda doppia,
ma di una coda _realizzata_ con una "catena a collegamento doppio".
l'ADT è _coda_ quindi si mette in coda e si toglie in testa. Se non è questo
che il suo professore intendeva o la domanda è mal posta o Luca l'ha
scritta male.
Poi vorrei aggiungere che se effettivamente quello che c'é scritto nella
rispsta é:
"in un ADT coda l'inserimento è possibile solo in coda a prescindere
dall'implementazione"
Non capisco come da questo non segua che:
2.gli inserimenti sono possibili solo in coda
sia esatta. Quindi la due deve essere giusta per forza. E se la risposta
giusta deve essere una sola...


 testa. Non "si inserisce in coda e si toglie dove ti pare" :)
Io invece non sono d'accordo.
Le politiche di gestione della coda possono essere FIFO e LIFO.
Per quello "si inserisce in coda e si toglie dove ti pare".
Tu consideri solo la FIFO....
Luca Paganelli.

 Le politiche di gestione della coda possono essere FIFO e LIFO.
Una coda è FIFO per definizione.
Forse la confondi con la lista.


 Matteo
O una pila?
Inviato da 
www.mynewsgate.net


Una Pila. La lista entri esci aggiungi togli dove vuoi ;)
-- 
reply: remove .duh.spam
http://cthulhu.fastmail.fm

 Una Pila. La lista entri esci aggiungi togli dove vuoi ;)
Ho vinto qualche cosa?
 
Inviato da 
www.mynewsgate.net

gnazio wrote:

Hehe, si, una videolezione nettuno sulla Paleografia latina(che sfiga, manco in 
tema... ;)
Marco


 Marco
Fiiiiiiiiiiigo!
Cmq la mia era per 'correggere' matish insinuandogli il dubbio. ;-)
Inviato da 
www.mynewsgate.net


L'avevo immaginato, ma volevo fare la ruota come i pavoni :P


 O una pila?
Io mi riferivo a :
"Le politiche di gestione della coda possono essere FIFO e LIFO."
Questa non è una pila. Una pila è solo LIFO, la coda solo FIFO. La lista
come ti pare. Dato che nella frase qui sopra la coda sembra una cosa in cui
metti e togli come ti pare ho pensato che l'avesse confusa con la lista.
Ciao
Matteo


 Le politiche di gestione della coda possono essere FIFO e LIFO.
una coda è per definizione FIFO. se diventasse anche LIFO non la si
distinguerebbe da una PILA

 testa. Non "si inserisce in coda e si toglie dove ti pare" :)
Anche secondo me la 4 è sbagliata. Però c'è una cosa da dire che ho 
notato ora riguardando la domanda, mi pare che ti abbia inteso la coda 
diversamente da me. Quando si parla di inserimenti in coda o in testa 
non ha senso parlarne rispetto alla coda vera e propria, ma solo 
rispetto ad un tipo di struttura che usi per scriverla la coda, o 
sbaglio? Secondo me quindi, è assurdo dire aggiungere in coda ad una 
coda, perchè tutto dipende da cosa hai usato per scriverla, cioè un 
array o una lista concatenata oppure una doppiamente concatenata. Se lui 
mi dice inserimenti possibili solo in testa, io intendo in testa alla 
catena, oppure è sbagliato pensare in questo modo? Volendo io posso 
gestire la coda (FIFO) aggiungendo in coda alla catena e rimuovendo in 
testa, oppure fare l'esatto contrario, il comportamente rimane sempre FIFO.
Che ne dici del ragionamento?
Grazie mille delle tante risposte.
Luca

 sbaglio?
Stiamo parlando del comportamento di un tipo di dato _astratto_.
Per quello che importa a te una coda è una scatola nera di cui ti
interessano due estremità.
            +---------------+
        coda|    scatola    |testa
      ------>     nera      ------->
            |               |
            +---------------+
Scusa la rappresentazione schifosa ma la grafica con il testo appartiene
alla generazione precedente alla mia :)
Se vuoi puoi invertire le frecce, non importa quale sia la testa e quale la
coda. Quello che conta è la definizione del tipo:
1)Si estrae sempre e solo in testa.
2)Si inserisce sempre e solo in coda.
Quindi la coda è quella dove si mette, la testa è quella dove si toglie, a
prescindere da quello che c'é dentro la scatola (l'implementazione).
A questo punto capisci che fa differenza l'inserimento in testa o in coda
anche se non conosci l'implentazione delle struttura di dati.
(in effetti in testa non si potrebbe proprio).
Infatti se inserisci E in testa il prossimo elemento estratto sarà E.
Se lo inserisci in coda sarà l'ultimo estratto, preceduto da tutti gli
elementi eventualmente presenti nella coda. Il primo comportamento è detto
LIFO il secondo FIFO.
Una _coda_ è FIFO per definizione. Quindi si inserisce solo in coda a
prescindere dal contenuto della scatola.
Spero di essere stato chiaro


matish wrote:
Uffa... ora vedo il mio disegnino tutto storto...
Vabbeh, tanto credo che il senso si capiva cmq :)
Ciao
