Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 2 Febbraio 20171. Si vuole progettare una struttura dati, denominata rete, per memorizzare le informazioni di una rete sociale. La strutturaretepermette di categorizzare siautentiemessaggiche i legami fra essi. Com- pletare la specica direte, fornendo la specica semantica per mezzo di pre e post condizioni (specica costruttiva o modello astratto), rispetto alla seguente specica sintattica: domini: rete, utente, messaggio, integer, boolean operatori: (a) creaRete()!rete //crea un nuova rete (b) aggiungiUtente(rete, utente)!rete //aggiunge un nuovo utente al la rete (c) vuota(rete)!rs //verica se la rete e vuota (d) connetti(rete, utente, utente)!rete //lega due persone del la 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 al la rete un messaggio inserito da un utente (g) connessi(rete, utente, utente)!boolean //verica 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 specica sintattica e semantica degli operatoricancnodoecancarcoper la struttura dati grafo[3pt] 3. Spiegare il concetto dicol lisionee le corrispondenti tecniche di gestione perdizionari[5pt] 4. Spiegare la strategia di risoluzione per il problema della ricerca del cammino minimo in un grafoadottata da un algoritmo a scelta del candidato [11pt] 5. Data una sequenza dinnumeri interi (x 1; : : : ; x n) diciamo che ( x i; x i+1) e una coppia di numeri consecutivi sex i+1= x i+ 1. Ad esempio nella sequenza (12 ;13;24;25;26;35;67) ci sono 3 coppie di numeri consecutivi: (12;13), (24;25) e (25;26). Scrivere in pseudocodice un algoritmo che utilizzi la tecnicadivide-et-imperae che calcoli quante coppie di numeri consecutivi sono contenute in una sequenza dinnumeri interi (x 1; : : : ; x n) ricevuta in input. [7pt] 1