[Domande d'esame] Algoritmi e Strutture Dati

Per chi ha fatto già l'orale, quali sono gli argomenti più gettonati all'orale di Asd?

non ci sono argomenti fissi all'esame...diciamo che i prof solitamente fanno sempre fare una funzione per le liste, una per gli alberi e poi kiedono ad ogni funzione il calcolo della complessita computazionale...almeno cosi mi ricordo..

devi imparare tutti gli algoritmi notevoli delle liste degli alberi e delle tabelle hash e tutta la teoria che viene prima di essi.
Come già ti è stato detto non esistono argomenti più gettonati o meno...purtroppo devi fare tutto =D

E' fondamentale che ti studi la complessità computazionale delle funzioni e i metodi per calcolarla, sopratutto nel caso di funzioni ricorsive (metodo iterativo, per sostituzione, metodo dell'esperto).

Ad esempio l'anno scorso una domanda tipica è stata quella di calcolare la complessità computazionale di una funzione ricorsiva che accede ad un albero in cui ogni nodo ha 3 figli ed esegue una generica operazione su ogni nodo in un tempo costante.

Domanda 1: Memoria Virtuale;
Domanda 2: mi hanno disegnato un albero con elevata profondità e mi hanno chiesto quale fosse la sua complessità computazionale (e mi sembra che la risp fosse la profondità stessa);

Sinceramente l'altra non me la ricordo proprio...in caso mi venisse in mente ve lo farò sapere...

Domanda 1: il prof mi ha descritto una funzione ricorsiva che divideva la
struttura dati in due parti uguali, applicava la ricorsione su una
sola delle due parti ed aveva un tempo di combina logn e voleva
sapere la complessità computazionale. Quindi bisogna studiarsi
bene i metodi x il calcolo della comlpessità...
Domanda 2:mi ha chiesto la push e la pop della coda.

l'ho fatto un po' di tempo fa...nn ricordo perfettamente cosa mi han kiesto..dunque.....di scrivere una funzione con la ricorsione...e mi sembra anche una conversione in floating point. mi sembra solo questo....

non dimentichiamo gli algoritmi di ordinamento
oltre ad impararli a memoria, ma questo vale per tutti gli algoritmi, sappiate spiegare cosa fanno e come lo fanno.

bubble
selection
insertion
quick
merge

Allora...quando ho fatto io l'orale il prof disse questo:
"L'orale di ASD sulle stutture dati si basa su 12 funzioni, inserimento, ricerca e cancellazione, iterative e ricorsive in liste, alberi e tabelle hash."

Poi chiede la formula di ricorrenza di una qualsiasi funzione ricorsiva studiata, quindi un consiglio è, imparatele tutte quante. Chiede spesso le condizione di uscita da un ciclio while in una qualunque funzione di una qualunque struttura dati.
Chiede quick sort e simulazione dell'algoritmo partition, merge_vettori, ovvero la fusione tra due vettori.
Questo è quello ke ricordo.

mmm si parla di due anni fa...ricordo poco...Ricordo :

Ricorsione - Divide Impera et Combina e principio di induzione.

Scrittura a penna di una funzione in due versioni: iterativa e ricorsiva

complessità computazionale della funzione di ricerca in una tabella hash

E poi c'era la parte di sistemi operativi: gestione dei processi e scheduling, file system ecc.

ma cose tipo algoritmi delle liste doppie,circolari ecc...nn li kiedono?

Ragazzi per cortesia potete postare qui le domande ke vi hanno fatto(per ki lo ha fatto) dell'esame di oggi, cosi che chi deve farlo martedi si fa un idea di cosa gli aspetti? E se (sempre per contesia) dite anke chi vi ha esaminato.
Grazie in anticipo

Allora ragazzuoli, ho fatto ieri l'esame di ASD (alle 18 e 20... )
Ecco le domande che mi sono state poste:

-E' dato un albero binario di ricerca il cui nodo è costituito da un tipo strutturato TInfo con all'interno 4 campi: codice (chiave), tipologia, prezzo, anno.
Scrivere una funzione che dato l'anno di incisione in input dia come risultato la somma dei costi di tutti i CD presenti in archivio incisi quell'anno (ovviamente l'ho scritta ricorsiva).

-Analisi della funzione di cui sopra: quale è la fase di divide e cosa fa, quale è la fase di impera e cosa fa, quale è la fase di combina e cosa fa. Poi mi è stato chiesto di scrivere la funzione di ricorrenza e di calcolare la complessità computazionale, con qualche domanda sul perchè di alcuni passaggi (insomma, cercava di capire se avevo imparato a memoria il metodo oppure lo avevo capito)

-Cosa è una funzione di Hashing ed a cosa serve.

C'è da dire che ho fatto l'esame con il Prof.Conte, ma che comunque le domande fatte dagli altri prof erano grossomodo simili.
Ciao ed alla prossima!

Il prof.Tufano mi ha chiesto:

-Dato un'albero contenente le informazioni relative a degli studenti con campo chiave matricola e campo satellite contenente nome,cognome e media, implementare una funzione che cerca lo studente con la media più bassa( DA NON CONFONDERE CON LA RICERCA DEL MINIMO).

-Definizioni e aspetti generali della complessità computazionale; notazioni O-grande,Omega-grande,Theta-grande: definizioni matematiche e significato pratico;caso peggiore,caso medio e caso migliore; Poi mi ha fatto alcune domande varie: 1)mi ha scritto f1£O(n) e f2 £ Theta(n) e mi ha chiesto quale fosse l'algoritmo più veloce;2)quale caso conviene analizzare tra migliore....? 3)se dovessi scrivere un programma che gestisca dei robot che effettuini il cambio gomme in F1 quale caso analizzeresti? cmq per ogni cosa che dicevo mi chiedeva cosa fosse per vedere se avevo imparato a memoria o meno.

- Infine mi ha fatto disegnare una lista doppiamente concatenata e mi ha chiesto quali vantaggi presenta rispetto a una lista semplice.

-Dato un'albero contenente le informazioni relative a degli studenti con campo chiave matricola e campo satellite contenente nome,cognome e media, implementare una funzione che cerca lo studente con la media più bassa( DA NON CONFONDERE CON LA RICERCA DEL MINIMO).

scusa ma alla fine non si riduce alla ricerca di un valore minimo? perkè hai voluto sottolineare quello di cui sopra? Volevi dire ke nn bisogna rikiamare la tree_min_search?

scusa mi sono appena risposto alla domanda...in pratica nella ricerca del minimo effettui una ricerca in relazione alla chiave,cioe essendo ordinati gli elementi in base alla chiave allora sei sicuro ke il minimo sta nel sottoalbero di sinistra....invece la media minima puo anke stare in quello di destra.giusto?

Si tanux ti sei risposto da solo.

ma sulla domanda O(n) e teta(n) dato che uno è il limite superiore e l'altro medio hai dovuto specificare il caso per dire il più veloce, o dato che teta è il limite medio và lui oppure sono uguali?.....

chiedono anche la rappresentazione dei numeri reali?

Scusate ma oltre alle varie funzioni su alberi, t.hash, liste, stack, coda, complessità computazionale e ricorsione, cosa c'è da portare all'esame ???