• Non ci sono risultati.

Esercizio 1 (8 punti)

N/A
N/A
Protected

Academic year: 2021

Condividi "Esercizio 1 (8 punti)"

Copied!
2
0
0

Testo completo

(1)

Prova scritta del 03 settembre 2018 di Fondamenti di Informatica II (prof. Di Gaspero) Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 2 ORE

A pena di annullamento immediato della prova:

1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.

2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula

Esercizio 1 (8 punti)

Si consideri un grafo diretto rappresentato attraverso le liste di adiacenza. Si riportano le definizioni del descrittore e della struttura dati utilizzata di seguito:

typedef struct _nodo_adiacenza { int vertice;

float peso;

struct _nodo_adiacenza* succ;

} nodo_adiacenza;

typedef struct { int n;

nodo_adiacenza **adiacenti;

bool diretto;

} grafo;

Scrivere una funzione in linguaggio C grafo inverti_archi(grafo g) che inverta la direzione degli archi. La funzione deve restituire un nuovo grafo in cui la direzione degli archi è invertita. Ad esempio, se nel grafo g è presente l’arco

(2,5)

nel grafo risultante l’arco dovrà essere

(5,2)

(si veda la figura).

Esercizio 2 (12 punti)

Un modo per rappresentare le espressioni aritmetiche è attraverso degli alberi binari in cui ciascuna sottoespressione corrisponde ad un sottoalbero in cui l’operatore aritmetico utilizzato è la radice del sottoalbero e le ulteriori sottoespressioni (costanti numeriche oppure sottoespressioni complesse) sono rappresentati dai sottoalberi sinistro e destro.

Ad esempio, l’espressione 3 * (4 + 1) - 5 / 2 è rappresentata dall’albero riportato nella figura.

Vogliamo definire l’implementazione di un tipo di dato astratto espressione che gestisca le strutture dati necessarie per questa rappresentazione. Per farlo, c’è la necessità di adattare la definizione dei nodi di un albero binario, che

chiameremo nodo_espressione, in modo da rappresentare entità di tipo differente (numeri interi e operatori).

2 5

1 0

3 4

2 5

1 0

3 4

-

*

3 +

4 1

/

5 2

(2)

Le operazioni possibili sono le seguenti:

• espressione crea_espressione(): crea una nuova espressione vuota

• void rimpiazza_albero(espressione* e, nodo_espressione *r) modifica l’espressione e, rimpiazzando il nodo_espressione attualmente memorizzata nel descrittore distruggendo l’albero attualmente presente e rimpiazzandolo con quello passato alla funzione; in particolare se il nodo_espressione passato come parametro è NULL il risultato dovrà essere un espressione vuota

• int calcola_risultato(espressione e) calcola il risultato dell’espressione eeffettuando tutte le operazioni descritte nell’albero; ad esempio nel caso dell’espressione in figura il risultato dovrà essere 13

• void elimina_espressione(espressione* e): elimina le strutture dati utilizzate nella memorizzazione dell’espressione e

In aggiunga si considerino le seguenti operazioni sulla struttura nodo_espressione

• nodo_espressione* crea_costante(int valore) che crea un nodo_espressione che rappresenta la costante il cui valore è passato come parametro

• nodo_espressione* crea_operazione(char operatore, nodo_espressione* se_sx, nodo_espressione* se_dx) a partire da due sottoespressioni crea una nuova espressione con alla radice l’operatore passato come parametro

• Si definisca il descrittore per il tipo di dato espressione (in altre parole la typedef struct {}

espressione) e la struct nodo_espressione

• Si implementino in linguaggio C le operazioni di manipolazione descritte in precedenza. Qualora fosse necessario si assuma l’esistenza delle funzioni di manipolazione delle strutture dati utilizzate nel descrittore, scelte fra quelle studiate durante il corso.

Esercizio 3 (10 punti)

L’algoritmo counting sort è un’algoritmo di ordinamento non basato sul confronto che può essere usato per ordinare numeri interi non negativi. Dato un vettore a da ordinare, l’idea alla base dell’algoritmo è quella di tenere un array di contatori c di dimensione pari al massimo valore presente nell’array (quindi con gli indici da 0 a max(a)). L’algoritmo esamina ciascun elemento a[i] del vettore a e incrementa di uno il contatore c[a[i]] corrispondente. Successivamente il vettore c viene scandito. Se il valore c[j] è maggiore di zero, nel vettore ordinato a' verrà inserito il

valore j esattamente c[j] volte.

Un esempio di esecuzione è riportato nella figura seguente:

Si scriva il codice C dell’algoritmo così descritto e se ne discuta informalmente la complessità computazionale.

Nota: si osservi che per dimensionare correttamente il vettore c è necessario conoscere il valore massimo del vettore a.

5 2 2 3 5 3 2 4 5

a

0 0 3 2 1 3

c

2 2 2 3 3 4 5 5 5

a’

Riferimenti

Documenti correlati

Il campo rango conterrà il rango del valore x nell’insieme i, ovvero il numero di elementi minori di x (alternativamente, la posizione di x nella sequenza ordinata), mentre il

• espressione rimpiazza_albero(nodo_espressione *r) rimpiazza l’espressione attualmente memorizzata nel descrittore distruggendo l’albero attualmente presente e rimpiazzandolo

Holzhey-Kunz (Hg.), Ludwig Binswanger und Erwin Straus, cit., in particolare alle pp. Straus, Vom Sinn der Sinne, cit., p. 1, dove si ricorda che Binswanger aveva distinto già

Le questioni cui il collegio è stato chiamato a dare risposta sono sostanzialmente due, ossia se possa ritenersi “pubblica” la foto inserita nel profilo di un social-network,

Usiamo il metodo dei moltiplicatori

ISTITUZIONI DI ANALISI MATEMATICA.

Le parti facoltative vanno fatte dopo aver svolto tutte le altri parti e non servono per ottenere la sufficienza.... ISTITUZIONI DI

(b-c) La funzione f ` e sempre continua, poich` e lo sono p|x| − 1 e arccos, tuttavia `e derivabile ovunque eccetto in 0, in quanto arccos ` e ovunque derivabile in [−1, 1] ma |x| non