Nome
                       
Cognome
                       
Matricola
          
Soluzione esame 24/09/2024
DomandaRisposta
1

Spiegare a parole come possono venire memorizzati i seguenti dati. Scrivere le istruzioni C che lo fanno e che stampano poi il nome dello stato in cui si trova Roma. Scrivere sia le dichiazioni che le istruzioni che memorizzano e stampano.

+--------------+          
|    citta     |          +---------------+
+--------------+          |    stato      |
| nome  [Roma] |          +---------------+
| stato [  0-]-|--------> | nome [Italia] |
+--------------+          +---------------+

La città viene memorizzata come una strutture, e lo stato come un'altra. Sulla base del disegno:

  • la struttura citta ha due componenti nome e stato, una stringa e un puntatore alla seconda stato;
  • la struttura stato ha solo una componente nome, una stringa.
#include <stdlib.h>
#include <stdio.h>

struct stato {
	char *nome;
};

struct citta {
	char *nome;
	struct stato *stato;
};

Occorre memorizzare in una prima struttura citta il nome "Roma" e l'indirizzo della seconda. Occorre che la seconda struttura sia creata (con la dichiarazione) per poter ricavare il suo indirizzo.

int main() {
	struct stato italia;
	struct citta roma;

	roma.nome = "Roma";
	roma.stato = &italia;

	italia.nome = "Italia";

	printf("%s\n", roma.stato->nome);

	return EXIT_SUCCESS;
}

2

Scrivere i seguenti due numeri nella rappresentazione comune con la virgola.

  • primo numero: mantissa 300, esponente 2;
  • secondo numero: mantissa 500, esponente 1.

Sommarli nella rappresentazione normale, e poi usando solo le mantisse e gli esponenti.

Il primo numero è 0,300 moltiplicato per 102, quindi 0,300 × 102 = 0,300 × 100 = 30.

Il secondo numero è 0,500 moltiplicato per 101, quindi 0,500 × 101 = 0,500 × 10 = 5.

La somma vale quindi 30 + 5 = 35.

La somma si può ottenere anche dalle mantisse e dagli esponenti: si normalizzano i due numeri convertendo l'esponente minore in quello maggiore, e poi si sommano le mantisse. In questo caso, il numero 500 con esponente 1 diventa 050 con esponente 2. Si possono ora sommare le mantisse: 300 + 050 = 350. Il risultato è quindi il numero con mantissa 350 ed esponente 2, che vale in effetti 0,350 × 102 = 0,350 × 100 = 35.

3

Dire cos'è un multigrafo e cos'è un ipergrafo. Disegnare un esempio di multigrafo e un esempio di ipergrafo, entrambi non orientati.

Un multigrafo è come un grafo, ma può contenere più archi fra gli stessi nodi. Un ipergrafo contiene iperarchi, che sono insiemi di nodi invece di coppie.

Esempio di multigrafo:

   0 ---- 1 ---- 2
     ---- 

Esempio di ipergrafo:

   +----------+
   |1        2|
   |   +-+    |
   |   |3|    |
   +---+-+----+
       |4|
       +-+

4

Disegnare l'automa che accetta solo le strighe composte delle lettere nell'insieme {a,b,c} in cui il primo carattere della stringa non si trova anche nel resto della stringa. Anche la stringa vuota viene accettata.

Se il primo carattere è a, allora si va in uno stato in cui la stringa viene accettata, e si rimane in quello stato fino a che i caratteri successivi sono b oppure c.

     a
 +-------> [1]
 |        (bc)
 |    b
[0] -----> [2]
 |        (ac)
 |   c
 +-------> [3]
          (ab)

5

Dire qual è il costo del seguente codice in notazione O-grande. L'input è la lista v.

somma = 0
for x in v:
    for y in v:
        if y > x:
            somma += y

Le istruzioni del primo ciclo vengono eseguite una volta per ogni elemento della lista, quindi n volte. Una di queste istruzioni è un un altro ciclo, il cui corpo viene eseguito n volte ogni volta. Quindi le sue istruzioni sono eseguite n2. Essendo le istruzioni del ciclo più interno, sono le istruzioni dominanti. Il costo in notazione O-grande è quindi n2.

NOTA: risposte prive di esauriente motivazione (es. i passaggi delle operazioni numeriche) verranno considerate nulle.