Fondamenti di Informatica
Corso di Laurea di Ingegneria Elettronica
Raccolta di esercizi d'esame


Gli esercizi seguenti sono una raccolta degli esercizi d'esame degli aa.aa. 98-99 e 99-00.

La prova d'esame è suddivisa in due parti, che si tengono consecutivamente nella stessa giornata. La prima, la cui durata è di 2 ore, è relativa alla risoluzione di un problema tramite un programma C (valore della prova 18 punti). La seconda, la cui durata è di 1 ora, comprende tre domande da 4 punti.

L'elaborato è poi discusso successivamente in un sessione orale.

La raccolta mantiene la stessa divisione dell'esame: una parte è una collezione di testi d'esame relativi alla prima prova (18 punti), l'altra contiene una raccolta esercizi da 4 punti.

Prima parte

Esercizio

Il file di testo Torneo.txt, memorizzato su disco, contiene la rappresentazione parentetica di un albero binario completo, etichettato sui nodi con numeri interi. Tale albero rappresenta a sua volta il tabellone di un torneo di tennis appena concluso, e contiene nella radice il numero corrispondente al vincitore del torneo.

Scrivere un programma C che contenga:
1)  le dichiarazioni in C da utilizzarsi per risolvere i due punti successivi;
2)   le istruzioni necessarie alla sua esecuzione;
3)  una (o più) funzione(i) C che, ricevendo come parametro il file Torneo.txt, restituisca in uscita un nuovo file di testo, Vinti.txt, contenente i numeri corrispondenti ai giocatori incontrati (e battuti) dal vincitore del torneo;
4) una (o più) funzione(i) C che, ricevendo come parametro il file Torneo.txt, restituisca in uscita il numero totale di incontri che si sono disputati nel torneo.
Si supponga di avere già definito una funzione crea_allbero.

Esempio

Esercizio

Si supponga dato in memoria un albero binario B che descrive parzialmente l’albero genealogico della famiglia De Facilis, estintasi nel secolo scorso.

I nodi dell’albero rappresentano alcuni membri maschi della famiglia secondo le seguenti regole:

In ogni nodo sono contenute le seguenti informazioni: nome, anno di nascita e anno di morte della persona.
  1. Si scrivano le dichiarazioni necessarie a rappresentare tale albero.
  2. Scrivere una funzione C cha crei, a partire dall’albero B, una lista formata da tutti i membri della famiglia che sono vissuti almeno 70 anni. Gli elementi della lista devono mantenere informazioni sul nome, anno di nascita ed età.
  3. Scrivere una funzione C che calcoli il numero delle generazioni nella famiglia.
Esempio di B


 
 
 
 

Esercizio

Al termine di una giornata di corse in un ippodromo i dati sui risultati sono memorizzati in un file. In particolare, su ogni riga del file sono memorizzate tre informazioni:

- nome di un cavallo (una stringa alfanumerica di al più 30 caratteri);

- numero d'ordine della corsa cui il cavallo ha partecipato (un intero da 1 a 8)

- posizione in cui il cavallo si è classificato nella corsa (un intero).

I dati nel file sono ordinati per ordine alfabetico del nome dei cavalli.

Per rappresentare in memoria centrale i dati contenuti nel file si adotta la seguente struttura dati: un array, il cui i-esimo elemento è il puntatore all'inizio della lista di risultati della corsa i-esima, ordinati per posizione d'arrivo.

Riferendosi alla figura, a sinistra si vede una porzione del file di risultati e a destra l'array di liste in cui sono rappresentate le classifiche delle 8 corse. Ad esempio, la TERZA componente dell'array è il puntatore all'inizio della classifica della TERZA corsa. Abbiamo lasciato indicati con … i cavalli non presenti nella porzione di file visibile in figura.

  1. Definire i tipi di dato adeguati a risolvere i problemi di cui ai due punti successivi. In particolare sia GIORNATA il nome del tipo C definito per l'array di cui si è detto.
  2. Scrivere una funzione COSTRUISCI che, ricevendo come parametri un file di risultati, formattato come descritto sopra, e un array di tipo GIORNATA, riempia opportunamente l'array con le classifiche delle corse.
  3. Scrivere una funzione che, ricevendo come parametri un array di tipo GIORNATA e il nome di un cavallo, restituisca in opportuni parametri di output il numero d'ordine della corsa in cui il cavallo ha gareggiato e la posizione in cui si è classificato.
(Si supponga che non ci siano cavalli omonimi nella giornata e che ciascun cavallo gareggi in una sola corsa).
 
Esercizio

Per lo svolgimento di un esame scritto di Fondamenti di Informatica, un docente prepara una lista degli studenti iscritti.
La lista è rappresentata mediante record e puntatori.
Ogni nodo della lista contiene le seguenti informazioni relative ad uno studente:
- nome (stringa di al più 20 caratteri)
- cognome (stringa di al più 20 caratteri)
- matricola (stringa di 8 caratteri)
- numero_fila (intero: la fila di banchi in cui lo studente si siede)
- posiz_fila (carattere indicante il posto della fila dove lo studente si siede)

Gli studenti vengono fatti entrare nell'aula dello scritto seguendo la lista. La lista viene modificata assegnando ad ogni studente presente una posizione nell'aula (es. 2D = quarto posto della seconda fila). Se uno studente iscritto è assente, nei campi numero_fila e posiz_fila si mette 0.
 
 

1) Definire un programma C contenente le dichiarazioni e le funzioni adeguate a risolvere i problemi di cui ai successivi punti 2) e 3).

Chiamare TIPOLISTA_APPELLO il tipo della lista di studenti descritta sopra.

2) Scrivere una funzione ELIMINA_ASSENTI che, ricevendo come parametro una lista L di tipo TIPOLISTA_APPELLO, trattata come sopra descritto, elimini da essa tutti gli studenti che risultano assenti.

3) Scrivere una funzione che, ricevendo come parametri una lista L di tipo TIPOLISTA_APPELLO, trattata come sopra descritto e due numeri di matricola, stampi un messaggio di "warning" se gli studenti corrispondenti sonocontigui.

NB Due studenti sono contigui se

- occupano posizioni vicine sulla medesima fila oppure se - occupano la medesima posizione su file adiacenti Ad esempio, 2A e 2B sono contigui; 2A e 2C no; 4C e 3C sono contigui; 4C e 3D no
Il messaggio di warning è del tipo "ATTENZIONE: STUDENTI CONTIGUI".
 
 

Esercizio

Le vetture parcheggiate in un deposito ferroviario sono organizzate secondo una lista rappresentata attraverso record e puntatori. Ogni nodo della lista contiene un char che rappresenta l’informazione sulla vettura. I caratteri utilizzati sono i seguenti:

Ogni mattina il deposito riceve due file DEPOSITO_TRENI.TXT e COMP_TRENI.TXT.
  1. Scrivere un programma C contenente le dichiarazioni e le funzioni adeguate a risolvere i problemi di cui ai punti 2) e 3). Chiamare TIPOLISTA_VETTURA il tipo della lista delle vetture descritto sopra.
  2. Scrivere una funzione AGGIORNA_DEPOSITO che ricevendo come parametri (1) una lista DEPOSITO di tipo TIPOLISTA_VETTURE e (2) il file DEPOSITO_TRENI.TXT aggiunga a DEPOSITO le vetture presenti nel file DEPOSITO_TRENI.TXT.
  3. Scrivere una funzione FORMA_TRENO che ricevendo come parametri
    1. una lista DEPOSITO di tipo TIPOLISTA_VETTURE e
    2. il file COMP_TRENO.TXT
restituisca

una lista TRENO di TIPOLISTA_VETTURE contenente la composizione del treno descritta in COMP_TRENO.TXT. I nodi utilizzati in TRENO dovranno essere eliminati da DEPOSITO. Se il treno non può essere formato per mancanza delle vetture richieste, la procedura ritorna TRENO uguale a nil e gli eventuali nodi già eliminati dalla lista DEPOSITO devono essere reinseriti.

ESEMPIO

DEPOSITO_TRENI.TXT : RMLLPSA

COMP_TRENI.TXT: LPRSSAAML

DEPOSITO: [R]->[M]->[L]->[P]->[P]->[A]->[S]->[S]->[S]->[M]

Dopo l’esecuzione di AGG_DEPOSITO

DEPOSITO:

[R]->[M]->[L]->[P]->[P]->[A]->[S]->[S]->[S]->[M]->[R]->[M]->[L]->[L]->[P]->[S]->[A]

Dopo l’esecuzione di FORMA_TRENO

TRENO: [L]->[P]->[R]->[S]->[S]->[A]->[A]->[M]->[L]

DEPOSITO: [R]->[M]->[P]->[S]->[M]->[L]->[P]->[S]
 
 
 
 

Esercizio

Una tabella è rappresentata usando una lista a tre campi valori, in cui per ogni elemento viene dato il campo informazione, la riga e la colonna che tale elemento occupa nella tabella. Un singolo elemento è costituito dal campo informazione, da due campi che contengono la riga e la colonna occupati nella tabella e il puntatore all'elemento successivo:

struct ElementoTabella {
    int info;
     int riga, colonna;
     ElementoTabella *altro;

};

Supponiamo che una tabella sia stata memorizzata nella lista TABLE seguendo l’ordinamento per righe e all’interno della singola riga per colonne.

1) Scrivere una funzione che restituisca la somma di tutti gli elementi che si trovano sulla diagonale principale della tabella;

2) Scrivere una funzione che elimini dalla lista tutti gli elementi che sono preceduti da un elemento di valore minore o uguale (si tenga presente che l’ultimo elemento di una riga precede il primo elemento della riga successiva; l’elemento in posizione [1, 1] non viene mai eliminato);

3) Scrivere una funzione che costruisca una lista contenente tutti gli elementi per cui la somma della riga e della colonna sia pari ad un valore ELIM, eliminando tale elementi da TABLE.
 
 

Si suggerisce di scrivere un’unica procedura di eliminazione di elementi da una lista che possa essere usata negli esercizi 2) e 3).

Esempio:
 
52
5
0
7
89
0
12
34
78
1
19
33
27
43
9
11
2
13
17
6

Esercizio

Si supponga in memoria un albero binario NATALE che descriva un albero di natale dove in ogni nodo sia presente una pallina ed una luce. Luce e pallina sono caratterizzati da un campo char ciascuno. Tali campi contengono il colore della pallina e della luce. I colori utilizzati sono i seguenti:

Le luci di uguale colore sono collegate da dei fili elettrici.
  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione del punto successivo.
  2. Scrivere una funzione che crei una lista, a partire dall’albero NATALE, formata da tutti i nodi che hanno la luce dello stesso colore della radice (ovvero tutte le luci connesse elettricamente alla luce della radice);

 

Esercizio

Tutte le informazioni sugli studenti iscritti ad un corso di laurea sono memorizzate in un file. Per ogni studente , i seguenti dati sono contenuti su una riga:

- matricola (8 caratteri alfanumerici)
- numero_esami_sostenuti
- media dei voti riportati
  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei  due punti successivi.
  2. Scrivere una funzione che, ricevendo come parametri di input il nome del file contenente le informazioni sugli studenti costruisca (e restituisca come parametro di output) una lista di tali studenti, rappresentata mediante record e puntatori, ordinata per media dei voti.
  3. Scrivere una funzione che, ricevendo una lista di studenti (come quella costruita al punto 2) e un valore V, produca e restituisca un’altra lista contenente i soli studenti che hanno una media di voti superiore a V.
Esercizio

Il file di testo Testo.txt, memorizzato su disco, contiene un brano letterario. La lista L è composta da lettere minuscole dell’alfabeto che formano una parola di senso compiuto.

  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei punti 2) e 3)
  2. Scrivere una funzione che, ricevendo come parametro il file Testo.txt ed il puntatore iniziale della lista L, verifichi se la parola rappresentata in L è contenuta in Testo.txt e restituisca in uscitaun valore booleano (vero se la parola e' contenuta, falso altrimenti). ATTENZIONE: una parola è contenuta nel testo anche se è una sottostringa di un'altra parola. Per esempio, se L contiene la parola "lato" ed in Testo.txt è presente la parola "alato", la procedura deve restituire valore vero. Inoltre, non si deve distinguere tra maiuscole e minuscole. Per esempio, se L contiene la parola "cani" ed in Testo.txt è presente la parola "Cani", la procedura deve restituire valore vero.
  3. Scrivere una funzione che, ricevendo come parametro il file Testo.txt, restituisca in uscita il numero di occorrenze del carattere alfabetico che appare più spesso nel testo (senza distinzione tra maiuscolo e minuscolo) ed il carattere stesso.
Esercizio

Si vogliono rappresentare i trenta corsi di una scuola di musica mediante un array di liste, a loro volta rappresentate mediante record e puntatori.
Nella i-esima componente dell'array sono memorizzati il nome dell'i-esimo corso (una stringa di 30 caratteri) ed il puntatore alla lista degli studenti iscritti a quel corso.
In ogni elemento della lista sono memorizzati il numero di matricola dello studente (4 cifre intere) e l'informazione circa il loro profitto espresso nume~icamente con voti da 6 a 15.

  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei
  2. scrivere una funzione che, dato come parametro 1'array di liste, crei una nuova lista, rappresentata mediante record e puntatori, che, per ogni corso, riporti l'informazione sul numero di studenti iscritti al corso stesso;
  3. scrivere una funzione che, dato come parametro l'array di liste, elimini dalle liste degli iscritti tutti gli studenti che abbiano riportato un giudizio inferiore a 10.
Esercizio

Una Società di Las Vegas ha istituito una lotteria telematica. Il gioco consiste nell'indovinare uno dei 1023 numeri di venti cifre ciascuno che la Società ha rappresentato come albero binario di ricerca completo (di profondità 9, naturalmente).

I giocatori devono inviare un file in cui sono memorizzati i numeri che si vogliono giocare. Si vince se si indovina almeno un numero memorizzato nell'albero di ricerca. Indovinare più numeri non aumenta l'importo della vincita. Un giocatore può giocare quanti numeri desidera: la vincita consisterà nel montepremi diviso il numero di numeri giocati. Ogni giocatore può inviare un solo file a settimana.

  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei punti 2) e 3)
2) Si scriva una funzione che, dati come parametri di input l'albero binario di ricerca completo ed il nome fisico di un file di giocate, verifichi se su quel file è memorizzato almeno un numero vincente;

3) Si scriva una funzione che, dati come parametri di input il nome fisico di un file di giocate e l'importo del montepremi, restituisca l'importo della vincita nel caso che nel file sia memorizzato almeno un numero vincente.
 
 

Esercizio

Un torneo di calcio è suddiviso in 4 gironi. Ogni girone è composto da quattro squadre: gli incontri sono ad eliminazione diretta. In ogni girone le squadre si affrontano a coppie, formate dopo un sorteggio, e dall'incontro tra le vincitrici delle prime due partite esce la vincente del girone. Gli incontri sono rappresentati in un albero binario. Le informazioni riportate nei nodi sono il nome della squadra e il numero di goal fatti nell'incontro con la squadra rappresentata nel nodo "fratello". La radice rappresenta la squadra vincitrice del girone e al suo campo goal è assegnato il valore -1.

I gironi sono rappresentati in una lista GIRONI, i cui elementi contengono il nome del girone (A, B, C o D) e un puntatore all'albero rappresentante gli incontri del girone.

1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei punti 2) e 3). Supponiamo che la lista GIRONI sia già costruita in memoria.

2. Scrivere una funzione che, dati come parametri il nome di una squadra e la lista GIRONI, restituisca una lista composta da elementi contenenti i nomi delle squadre incontrate dalla squadra in input e i goal che tali squadre hanno subito.

3. Scrivere una funzione che, dati come parametri la lista GIRONI e il nome di un girone, restituisca il nome della squadra che ha segnato il maggior numero di goal in quel girone.
 
 

Esercizio

Il magazzino di un ferramenta memorizza le vendite di fine giornata in una tabella MAGAZZINO che contiene il nome del prodotto (lunghezza massima ammessa 12 caratteri), il suo codice alfanumerico (massimo 5 caratteri), la quantità di pezzi venduti (disponibilità per ogni prodotto di 250 pezzi), il suo prezzo unitario (costo massimo dei prodotti L. 230.000) e l’incasso totale per quel prodotto.

I dati vengono letti dal file VENDITE che contiene in ogni linea i seguenti dati relativi ad un singolo prodotto: nome, codice, numero di pezzi e prezzo unitario. L’immissione dei prodotti non segue nessun ordine particolare. Lo studente può usare indifferentemente un file di testo o un file di record.
 

1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei punti 2) e 3).

2. Scrivere una o più procedure/funzioni che, ricevuto come input il file VENDITE, costruisca la tabella MAGAZZINO immettendo solo i dati relativi ai prodotti per cui siano stati venduti più di 200 pezzi.

3. Scrivere una o più procedure/funzioni che, dato come input la tabella MAGAZZINO del punto 2., costruisca la lista ORDINI formata dai prodotti per cui siano stati venduti più di 230 pezzi. Le informazioni da memorizzare sono le stesse della tabella.
 

Esercizio

La Società che gestisce i trasporti nella città X ha istituito un servizio di monitoraggio sul numero di passeggeri di ciascuna linea. Al termine del periodo di monitoraggio, la Società ha prodotto, per ogni linea, un file (nome fisico: MEZZI.DAT) in cui sono riportati i seguenti dati:

Si risolvano i seguenti problemi: 1) Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei punti 2) e 3).

2) Scrivere una funzione che, dati come parametri una stringa s ed un intero k, costruisca, a partire dal file MEZZI.DAT, una lista (rappresentata mediante record e puntatori) costituita da tutte le linee che hanno s come capolinea di partenza ed hanno trasportato mediamente più di k passeggeri in un giorno. Nella lista devono essere memorizzati soltanto la denominazione della linea e la lunghezza del percorso.

3) Scrivere una funzione che, dati come parametri la lista costruita al punto precedente ed un carattere c, memorizzi in un file (nome fisico: LINEA.DAT) tutte le linee presenti nella lista la cui denominazione inizi per il carattere c. Nel file LINEA.DAT devono essere memorizzate soltanto le denominazioni delle linee.

Esercizio

Un istituto di statistica deve raccogliere pareri su un prodotto di nuova commercializzazione che è stato testato su un certo numero di persone. Il numero di persone non è noto. Ad ogni intervistato è stata chiesta:

  1. una valutazione sulla bontà del prodotto (un intero da 0 a 30),
  2. una valutazione sulla sua efficacia (un intero da 0 a 30)
  3. una valutazione sulla frequenza d’uso (A per "molto spesso", B per "spesso", C per "qualche volta", D per "mai");
  4. una valutazione sulla confezione (A per "ottima", B per "buona", C per "media", D per "sufficiente", E per "scarsa").
Ogni intervistato è contraddistinto da un numero di codice (5 caratteri).

I dati sono memorizzati in un file INPUT.DAT secondo l’ordine

  1. codice,
  2. valutazione sulla bontà del prodotto,
  3. valutazione sulla sua efficacia,
  4. valutazione sulla frequenza,
  5. valutazione sulla confezione.
  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei due punti successivi.
  2. Scrivere uno o più funzioni che, dato in input il file INPUT.DAT:

  3. -  Costruiscano la lista INFO (usando record e puntatori) con le informazioni riguardanti le interviste. I record devono contenere gli stessi dati del file.
    - Calcolino il valore medio delle valutazioni sulla bontà e sulla efficacia del prodotto.
  4. Scrivere uno o più funzioni che, dato come input la lista INFO (che deve rimanere inalterata), costruiscano una lista MIGLIORI che contengono solo i record relativi ai prodotti che sono stati valutati  A o B per la frequenza d’uso e  A, B o C per la confezione.
Esercizio

Una autofficina, che effettua tagliandi di controllo per auto di marca X, invia settimanalmente alla Direzione Amministrativa di X un file TAG.DAT in cui sono riportati i seguenti dati, per ogni auto controllata nella settimana:

  1. Scrivere un programma C contenente le dichiarazioni e le funzioni necessarie a rappresentare tale albero e alla soluzione dei due punti successivi.
  2. Scrivere uno o più funzioni che, dato il file TAG.DAT, costruiscano (mediante record e puntatori) una lista AUTO in cui memorizzare soltanto i dati delle auto la cui targa inizia per le lettere AB e termina per le lettere YZ; ogni elemento della lista dovrà contenere solo il codice del cliente, l’intera targa dell’auto ed il costo dell’intervento.
  3. Scrivere una (o più) funzione che, dato come parametro la lista AUTO di cui al punto precedente (che deve rimanere inalterata), memorizzi in un file ECONOMI.DAT i soli record relativi alle auto per le quali il costo dell’intervento è risultato inferiore a 24.75 euro. In ogni record del file ECONOMI.DAT devono essere memorizzati gli stessi dati contenuti negli elementi della lista AUTO.

Seconda parte

Esercizio
Siano G ed M rispettivamente il giorno ed il mese di nascita del candidato. Dopo aver convertito in binario G ed M, effettuare, sempre in binario, l'operazione G-M.

Esercizio
Descrivere il tipo di dato pila e le sue principali realizzazioni concrete in C

Esercizio
Descrivere il tipo di dato lista e le sue possibili rappresentazioni in C.

Esercizio
Descrivere la gestione della pila di attivazione in C nel caso di funzione ricorsiva. Si consideri l’esempio del fattoriale di 3.

Esercizio
Descrivere il tipo ALBERO BINARIO. Descrivere inoltre solo i principali algoritmi di visita (mostrando un esempio significativo per ciascuno).

Esercizio
Cosa stampa il seguente programma, quando in ingresso legge prima la penultima e poi l’ultima cifra del numero di matricola del candidato/a?
Per giustificare la risposta mostrare l'evoluzione della pila dei record di attivazione allocati durante l'esecuzione.

#include <stdio.h>

void B (int);
void A (int *);

int x = 8;
int y = 2;

int main (void) {
    int x, y;

    scanf("%d", &x); /*penultima cifra del numero di matricola*/
    scanf("%d", &y); /*ultima cifra del numero di matricola*/
    A (&y);
    printf("%3d %3d", x, y);

    return 0;
}

void B (int z)
{
    x = x+5;
    z = y+2;
    printf("%3d %3d %3d", x, y, z);
}

void A (int *x) {
    int y;

    y = *x+10;
    B ( y );
    printf("%3d %3d", *x, y);
}
 
 

Esercizio
Descrivere la rappresentazione di un numero intero relativo in complemento a 2 su n bit. Specificare qual è l’intervallo di numeri interi relativi rappresentabile in complemento a 2 con n bit.

Sia ora G il giorno di nascita del candidato/a. Se è di una sola cifra, mettere un 1 davanti. (es, chi è nato/a il 3 Agosto userà 13). Scrivere la rappresentazione in complemento a due su 8 bit del numero negativo -G. Mettere chiaramente in evidenza il procedimento usato per rispondere al quesito.

Esercizio
Descrivere il tipo di dato CODA. Specificare le diverse possibili rappresentazioni. Scrivere l'implementazione in C di almeno una funzione base per ciascuna rappresentazione descritta.

Esercizio
Cosa si intende precisamente quando si dice che un programma ha complessità O(f(n))? Cos'è "n"? Illustrate le principali regole per trovare la complessità di un programma.
A proposito di istruzione dominante, fare un esempio, scrivendo una funzione e discutendone la complessità.

Esercizio
Descrivere i principali registri di un'unità centrale, ed il funzionamento elementare dell'elaboratore durante l'esecuzione di una generica istruzione.

Esercizio
Descrivere il tipo di dato LISTA e la sua rappresentazione collegata mediante record e puntatori.

Esercizio
Descrivere l’algoritmo di merge-sort (fornendo anche il codice) e discutere la sua complessità.

Esercizio
Descrivere gli algoritmi di ordinamento e confrontare la complessità.

Esercizio
Descrivere le funzionalità dell’unità centrale e i suoi componenti fondamentali.

Esercizio
Dato il seguente programma:

#include <stdio.h>
int ritorna (int *a);
void calcola (int z, int y);

int main (void)
{
    int x, y, z=1;
    scanf("%d", &x);
    scanf("%d", &y);
 
    y = ritorna (&x);
    printf("%3d %3d", y, x);
    calcola(y, z);
    printf("%d", y);
 
    return 0;
}

int ritorna (int *a)
{
    int y;
    scanf ("%d", &y);
    *a = y + 2;

    return (y+*a);
}

void calcola (int z, int y)
{
    z=y+2;
    printf("%3d", z);
}

Calcolare il suo output per le seguenti terne di input: (2 1 2), (1 1 1), (4 5 6). Spiegare perché.

Esercizio
Effettuare le seguenti operazioni trasformando i numeri in base 2 (usando la rappresentazione in in complemento a due con 8 bit ):
45 —78, -99 +1, 44+12, -34 - 130
 

Esercizio
Descrivere le modalità con le quali in un programma C, la funzione main e le altre funzioni possono scambiare informazioni tra loro. Fornire almeno un esempio di applicazione di ciascuna modalità descritta.

Esercizio
Siano G ed M rispettivamente il giorno ed il mese di nascita del candidato. Dopo aver convertito in binario G ed M, effettuare, sempre in binario, l'operazione G-M.
 
 

Esercizio
Si descrivano le fasi di cui si compone il ciclo di vita di un programma, indicando anche le qualità che un programma deve avere.

Esercizio
Descrivere inoltre la rappresentazione mediante record e puntatori, di un albero binario fornendo le funzioni C per rappresentare:

Esercizio
Si consideri il seguente programma:
#include <stdio.h>
void uno (int *a);
void due (int b, int *c);

int main (void)
{
    int x, y;

    scanf("%d %d", &x, &y);
    if (x > y) {
        uno (&x);
        printf("%3d %3d", x, y);
      }
    else {
        uno(&y);
        due(y, &x);
        printf("%3d %3d", x, y);
    }
    return 0;
}

void uno (int *a)
{
    int x;

    scanf("%d", &x);
    if (x = 5 )
        *a= *a+3;
    else
        *a=*a-3;
}

void due (int b, int *c)
{
    if (b < (*c)) {
        b = *c;
        *c = b ;
        printf("%3d %3d", b, *c);}
    else
        printf("%3d %3d", b, *c);

}

Si indichi, con adeguate motivazioni, cosa produce il programma prova quando vengono fomite in input le seguenti tre sequenze di valori: 2 2 5, 15 2 5 , 2 16 2

Esercizio
Rappresentate in complemento a due il vostro giomo e mese di nascita e calcolatene la somma e la differenza

Esercizio
Si illustri il tipo di dato 'lista semplice', fornendone la specifica astratta ed una sua possibile rappresentazione in C, descrivendo almeno tre operazioni primitive.

Esercizio
Siano date le seguenti dichiarazioni di dato e di funzione:

#define DIM 3
typedef char TipoElemVettore;
typedef TipoElemVettore TipoVettore[DIM];

void Stampa_ric(TipoVettore V, int i)
{
    if (i!=DIM)
        stampa_ric (V, i+1);
    printf(V[i]);
}

Sia W[ ] una variabile di tipo TipoVettore che abbia il seguente valore: [S H N]
Sia k una variabile di tipo intero (int).

Il candidato indichi e motivi l'effetto di ciascuno dei seguenti frammenti di programma:

1)    k=1;
      Stampa_ric(W,k);

2)    k=3;
      Stampa_ric(W,k);

3)    k =1;
      while (k!=3) {
            Stampa_ric(W,k);
            k++;
}
 

Esercizio
Descrivere le modalità di passaggio dei parametri tra programmi. Descrivere inoltre le regole di visibilità delle variabili globali e locali.
 

Esercizio
Descrivere le trasformazioni a cui viene sottoposto un programma scritto in un linguaggio ad alto livello per arrivare alla sua forma eseguibile.

Esercizio
Dato il programma seguente, descrivere le modalità di passaggio di parametri adottate e il suo output. Illustrare inoltre la successione delle chiamate nello stack di attivazione e i valori assunti dalle variabili.

#include <stdio.h>
#include <math.h>
int largest (int x, int y);
void low (int *x, int *y);

int main (void)
{
    int a=30, b =50;
    printf("%4d %4d %4d", largest (sqrt(a), b), a, b);
    return 0;

}

int largest (int x, int y)
{
    int temp;
 
    if (x > y)
        temp = x;
    else
        temp = y;
    if (x != y) {
        x =y;
        y = y-2;
        low (&x, &y);
    }
    return temp;
}

void low (int *x, int *y)
{
    if (*x > *y) {
        printf ("%4d", *x);
        *x=(*x)*2;
        }
    else
        printf ("%4d", *y);
}
 
 

Esercizio
Si indichi cosa si intende per software di base e si illustrino alcuni dei suoi principali costituenti.

Esercizio
Si illustrino i concetti relativi all'algoritmo per la ricerca dicotomica. Se ne fornisca inoltre una versione sotto forma di funzione C.
 

Esercizio
Descrivere il tipo di dato albero binario la sua rappresentazione. Fornire anche le funzioni principali.

Esercizio
Eseguire, adottando il sistema di calcolo in complemento a due, le seguenti operazioni:

Esercizio
Utililizzando il linguaggio C, dichiarare un tipo di dati adatto a descrivere un albero binario etichettato con valori di tipo char e scrivere le funzioni per effettuarne la visita in preordine, in postordine e per livelli.