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.
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:
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:
- 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).
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.
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.
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
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:
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.
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.
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:
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:
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.
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.
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.
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.
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.
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:
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.
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:
I dati sono memorizzati in un file INPUT.DAT secondo l’ordine
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:
Seconda parte
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:
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: