170216

Page 1

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 2 Febbraio 2017 1. Si vuole progettare una struttura dati, denominata rete, per memorizzare le informazioni di una rete sociale. La struttura rete permette di categorizzare sia utenti e messaggi che i legami fra essi. Com- pletare la specifica di rete, fornendo la specifica semantica per mezzo di pre e post condizioni (specifica costruttiva o modello astratto), rispetto alla seguente specifica sintattica: domini: rete, utente, messaggio, integer, boolean operatori: (a) creaRete() → rete // crea un nuova rete (b) aggiungiUtente(rete, utente) → rete // aggiunge un nuovo utente alla rete (c) vuota(rete) → rs // verifica se la rete ` e vuota (d) connetti(rete, utente, utente) → rete // lega due persone della rete con un legame di amicizia (e) sconnetti(rete, utente, utente) → rete // rimuove il legame di amicizia fra due persone (f) posta(rete, utente, messaggio) → rete // agginge alla rete un messaggio inserito da un utente (g) connessi(rete, utente, utente) → boolean // verifica se due utenti sono connessi (h) numAmici(rete, utente) → integer // resituisce il numero di amici di un utente (i) numMessaggi(rete, utente) → integer // resituisce il numero di messaggi inseriti da un utente [7pt] 2. Fornire la specifica sintattica e semantica degli operatori cancnodo e cancarco per la struttura dati grafo [3pt] 3. Spiegare il concetto di collisione e le corrispondenti tecniche di gestione per dizionari [5pt] 4. Spiegare la strategia di risoluzione per il problema della ricerca del cammino minimo in un grafo adottata da un algoritmo a scelta del candidato [11pt] 5. Data una sequenza di n numeri interi ( x1, . . . , xn) diciamo che ( xi, xi+1) ` e una coppia di numeri consecutivi se xi+1 = xi + 1. Ad esempio nella sequenza…