Pascal e strutture dati
Tipi Di Dato
1) Descrivere il tipo di dato INTEGER :
Si tratta di variabili costituite da 2 byte e pertanto possono assumere valori compresi tra -215 e 215-1. Su di essi si possono eseguire le seguenti operazioni:
+ addizione
- sottrazione
* moltiplicazione
DIV restituisce la parte intera del quoziente
MOD restituisce il resto della divisione infatti il valore restituito da A MOD B è il minimo intero non negativo che può essere sottratto ad A per ottenere un multiplo intero di B.
succ(x) restituisce il seguente n° intero
pred(x) restituisce il n° intero precedente
2) Descrivere il tipo di dato REAL :
È un tipo di dato implementato per identificare i numeri reali, è espresso in virgola mobile. Datosi che è un tipo non ordinale sono impossibili le operazioni pred e succ mentre si rendono necessarie delle operazioni di arrotondamento:
trunc(x) restituisce la parte intera del n° reale x
round(x) restituisce l´intero più vicino al n° reale x
3) Descrivere il tipo CHAR :
È utilizzato per implementare i caratteri immessi da tastiera, su di esso sono possibili le seguenti operazioni :
ord(c) restituisce il codice ASCII associato al carattere c
chr(i) restituisce il carattere associato al codice ASCII i
succ(c) restituisce il codice ASCII successivo a quello corrispondente al carattere c
pred(c) restituisce il codice ASCII precedente a quello corrispondente al carattere c
4) Descrivere il tipo di dati BOOLEAN:
È un tipo di dato che consente la manipolazione di operazioni logiche, normalmente è associato a variabili che fungono da Flag ad esempio per l´uscita dal ciclo quando una determinata condizione è vera. Può assumere soltanto i valori VERO o FALSO, 1 oppure 0. Un caso particolare di utilizzo sui numeri interi è :
Odd(x) è vera se il n° è dispari
5) Come si definisce il tipo di dati enumerato:
È un tipo di dati definito così :
TYPE nome = ( tipo_1 , tipo_2 , ... , tipo_n )
i tipi possono ad esempio essere i giorni della settimana o i semi di un mazzo di carte etc...
Il definire il tipo di dato enumerato consente l´utilizzo delle funzioni succ(x) , pred(x) e ord(x) quest´ultima sfrutta il fatto che ad ogni tipo viene associato un n° intero N da 0 ad N e restituisce quindi questo numero.
6) Descrivere il tipo intervallo :
La definizione di questo tipo consente di scegliere un intervallo di un insieme ordinale già definito, ciò si rende possibile tramite la TYPE nome = limite inferiore .. limite superiore
gli insiemi già definiti sono i numeri interi, il set di caratteri ‘A´ .. ‘Z´ ed il corrispondente minuscolo ‘a´ .. ‘z´ e si possono anche utilizzare parte degli insiemi definiti tramite il tipo di dato enumerato. La maggiore utilità di questa istruzione è di rendere disponibile solo ciò che è realmente necessario il che può essere una complicazione per il programmatore ma è anche una agevolazione nell´individuare eventuali trabocchi delle variabili.
7) Come vengono utilizzati i tipi per la definizioni di variabili e costanti :
Per le costanti non vengono utilizzati i tipi in quanto vengono direttamente inizializzate al valore, la sintassi è :
CONST nome_costante = valore
Per le variabili debbono prima essere definiti i tipi e poi le variabili che li utilizzano, la sintassi è :
VAR nome_variabile : tipo_variabile
8) Cosa sono i tipi record e come si definiscono :
Si tratta di un tipo in grado di conglobare tipi non omogenei i quali descrivono però un´unica entità come la data che è costituita da un intero per il giorno una stringa per il mese ed un altro intero per la anno. Si definiscono tramite la :
TYPE tipo_record = RECORD
variabile_1 : tipo_variabile_1 ;
.............
variabile_n : tipo_variabile_n
END ;
Questo tipo è spesso alla base degli array infatti tramite esso si può definire la costituzione della singola riga della array.
9) Come si può cambiare il contenuto di un record :
Tramite l´istruzione : nome_record.nome_campo := nuovo_valore
10) Descrivere il tipo di dati ARRAY :
Gli array sono strutture che consentono di raggruppare variabili con caratteristiche in comune, in particolare le righe della array sono tutte uguali e possono essere costituite da un insieme di più variabili anche di tipo diverso.
11) In che modo si può definire una variabile di tipo array bidimensionale:
Direttamente Þ VAR nome_array : ARRAY [ tipo_intervallo_1 , tipo_intervallo_2 ] of tipo_righe
Indirettamente Þ si definisce prima il nuovo tipo tramite la istruzione
TYPE tipo_array = ARRAY [ tipo_intervallo1 , tipo_intervallo_2 ] of tipo_righe
e poi si dichiara una variabile di quel tipo VAR nome_array : tipo_array
dove tipo_righe può essere sia un tipo normale che un record.
12) Come si può modificare un elemento di un array:
Tramite l´istruzione nome_array[ riga , colonna ] : = nuovo_valore
13) Descrivere il tipo di dato Insieme:
È un tipo di dato che consente l´implementazione del calcolo insiemistico, si definisce un insieme tramite la :
TYPE nome_insieme := SET OF tipo_elementi
Le operazioni eseguibili sugli insiemi sono le seguenti :
A + B Þ restituisce l´insieme unione di A e B
A * B Þ restituisce l´insieme intersezione di A e B
A - B Þ restituisce l´insieme dei valori che sono in A ma non in B
A := A + [X] Þ aggiunge l´elemento X all´insieme A
A := A - [X] Þ elimina l´elemento X dall´insieme A
I test eseguibili sugli insiemi sono i seguenti :
A = B Þ A è uguale a B ?
A<> B Þ A è diverso da B ?
A <= B Þ A è contenuto in B ?
A >= B Þ A contiene B ?
el IN B Þ l´elemento el è contenuto in B ?
14) Descrivere il tipo di dato Puntatore :
È un tipo di dato avente lo scopo di ospitare indirizzi di memoria rendendo possibile implementazioni di liste ed alberi tramite una gestione dinamica della memoria. Essendo che dati diversi occupano in memoria spazi diversi ne consegue che il tipo di dato puntato dal puntatore deve essere specificato tramite l´istruzione :
TYPE puntatore = ^ tipo_di_dato_puntato
15) Quali istruzioni consentono di associare un elemento ad un puntatore oppure di disassociarlo:
NEW(nome_puntatore) Þ chiede al Sysop un elemento da associare al puntatore
DISPOSE(nome_puntatore) Þ cede al Sysop lo spazio occupato dall´elemento associato al puntatore.
16) Come si fa ad associare un valore al campo dati del record puntato da PUNT:
Tramite l´istruzione : punt^ .dati := valore
in generale si utilizza punt per operazioni sul puntatore e si usa invece punt^ per operazioni sull´elemento puntato dal puntatore.
17) Quale istruzione si utilizza per l´immissione di un valore da parte della utente e quale per la stampa a video:
Input read(variabile);
Output write(‘testo´,variabile);
Strutture di controllo
18) Quali sono le istruzioni strutturate:
Istruzione composta Þ sono gruppi di istruzioni che vanno eseguite nell´ordine in cui son scritte iniziano con BEGIN e finiscono con END.
Istruzione ripetitiva Þ sono i gruppi (WHILE condizione DO) , (REPEAT istruzioni UNTIL condizione) e la ( FOR contatore := n to m DO istruzioni)
Istruzione condizionale Þ Sono i gruppi (IF condizione THEN istruzione_1 ELSE istruzione_2) e (CASE variabile OF caso_1 : istruzione_1 ; caso_2 : istruzione_2 ; .... ; caso_n
: istruzione_n END)
Istruzione WITH Þ Serve con variabili di tipo record laddove si voglia accedere ai campi di uno stesso record per modificarli e si vuole evitare di utilizzare sempre la struttura : nome_record.nome_campo := nuovo_valore
Si utilizza invece la sintassi WITH nome_record Do nome_campo := nuovo_valore ;
19) Caratteristiche del ciclo WHILE :
È un ciclo che potrebbe anche non essere mai eseguito visto che la condizione è in testa, si esce dal ciclo nel caso che la condizione è falsa.
20) Caratteristiche del ciclo REPEAT :
È un ciclo il quale viene sempre eseguito almeno una volta visto che la condizione ne è l´ultima istruzione, si esce dal ciclo unicamente se la condizione è vera. Da notare che non occorrono BEGIN ed END se le istruzioni che sono tra REPEAT ed UNTIL sono più di una in quanto quest´ultimi fungono già di per se da delimitatori.
21) Quale è il maggiore utilizzo della istruzione CASE :
Si utilizza laddove si voglia evitare l´utilizzo di istruzioni IF THEN ELSE nidificate, ciò che si fa è invece prendere una variabile e definire cosa si deve fare per ognuno dei diversi valori che essa può assumere.
Procedure e funzioni
22) A cosa serve e quale è il formato di una procedura:
La procedura o sottoprogramma serve a rendere più leggibili i programmi e ben si adatta ad una filosofia di sviluppo TOP-DOWN nella quale prima si definiscono le funzionalità generali e poi si scende nello specifico. Un esempio è
PROCEDURE nome_procedura( parametro_formale_1, ... , parametro_formale_n) ;
VAR variabile_locale : tipo ;
BEGIN
istruzioni ;
END;
un esempio di chiamata di questa procedura è : nome_ procedura( parametro_formale_1, ... , parametro_formale_n)
23) A cosa serve e quale è il formato di una funzione:
La funzione è un caso particolare di procedura la quale restituisce un solo valore e lo restituisce attraverso il suo nome che si comporta quindi come una variabile. Un esempio è
FUNCTION nome_funzione( parametro_formale_1, ... , parametro_formale_n) : tipo_di_dato_restituito ;
VAR variabile_locale : tipo ;
risultato : tipo_di_dato_restituito ;
BEGIN
istruzioni ;
risultato := nome_funzione;
END;
un esempio di chiamata di questa funzione è : a := nome_ funzione( parametro_formale_1, ... , parametro_formale_n) ;
dove a è una variabile dello stesso tipo restituito dalla funzione.
24) Cosa si intende per parametri formali e parametri attuali:
I parametri formali sono dei parametri generici oggetto della elaborazione della procedura o della funzione, generici in quanto una procedura o funzione non accetta in ingresso una determinata variabile bensì una tipologia di variabile il che la rende utilizzabile in più contesti. In particolare :
Parametri formali Þ sono quelli generici su cui lavora la procedura o funzione
Parametri attuali Þ sono quelli reali che il programma fornisce alla procedura o funzione e questa ne sostituisce il valore ai parametri formali.
25) Quante tipologie di passaggio dei parametri vi sono:
a) passaggio per valore Þ Viene fornita alla procedura solo una copia della variabile e non la variabile stessa la quale quindi non può essere modificata dalla procedura la quale può soltanto modificare la copia.
Ad esempio : PROCEDURE nome_procedura( parametro_formale_1: tipo_variabile)
non può alterare il valore della variabile X fornita dalla istruzione nome_ procedura( X )
b) passaggio per variabile Þ Viene fornita alla procedura la variabile la quale quindi non può essere modificata dalla procedura. Si utilizza questa modalità ogniqualvolta sia necessario ottenere dei valori di ritorno da una procedura. Ad esempio :
PROCEDURE nome_procedura( VAR parametro_formale_1: tipo_variabile);
può alterare il valore della variabile X fornita dalla istruzione nome_ procedura( X )
26) Cosa si intende per ricorsione:
È una metodologia di programmazione che tende ad estrinsecare un modo di ragionare che è poi quello della induzione matematica, in pratica si tratta di una funzione la quale tra le sue istruzioni ne ha anche una che richiama la funzione stessa. È da notare che ogni volta che la funzione richiama se stessa la funzione chiamante è solo interrotta e riprenderà la sua esecuzione una volta che sarà ultimata l´esecuzione della funzione chiamata. Ogni chiamata ricorsiva inoltre genera variabili le quali hanno lo stesso nome ma sono completamente differenti dalle variabili della funzione chiamante.
27) Quando una variabile è locale e quando invece è globale:
Una variabile è locale alla procedura quando è definita tra la definizione della procedura ed il BEGIN della stessa, è invece globale quando è definita esternamente alla procedura.
Files
28) Cosa si intende per File e quante tipologie ve ne sono:
Un file è un insieme di dati che è talmente esteso da non poter risiedere in memoria, ve ne sono sostanzialmente 2 tipi:
a) File interni Þ Si tratta di Files di uso temporaneo il cui contenuto può andar perso al termine del programma
b) File esterni Þ Si tratta di Files il cui contenuto non può andar perso al termine del programma e pertanto necessitano di essere memorizzati su supporti fisici quali nastri e floppy disk.
Nelle implementazioni al file fisico si associa una variabile buffer che funge da interfaccia.
29) Come si assegna un file ad una variabile buffer:
Una variabile buffer consente di leggere i valori contenuti nel file, è assimilabile ad una interfaccia logica, la si assegna tramite l´istruzione ASSIGN(nome_buffer,´NOME_FILE.DAT´)
dove nome_buffer deve essere preventivamente stato dichiarato tramite la VAR nome_buffer : FILE OF tipo_elementi
30) Come si prepara un file per la scrittura:
Tramite il comando REWRITE(buffer_file) il quale cancella il contenuto del file e si prepara a scriverlo ponendosi sul 1° elemento dello stesso.
31) Come si può scrivere un file:
Occorre la seguente coppia di comandi :
buffer_file^ := valore_da_scrivere Þ scrive il valore sulla variabile_buffer
PUT(G) Þ Trascrive il valore dal buffer al file.
Dato il ricorrente uso della coppia delle precedenti è stata predisposta una istruzione che le congloba :
WRITE(buffer_file, valore) Þ scrive il valore sul file
32) Come si prepara un file per la lettura:
Tramite il comando RESET(buffer_file) il quale pone nel buffer il 1° elemento letto dal file.
33) Come si può leggere un file:
Occorre la seguente coppia di comandi :
variabile := buffer_file^ Þ assegna il valore sul buffer ad una variabile
GET(G) Þ associa al buffer il valore della successiva componente del file G
Dato il ricorrente uso della coppia delle precedenti è stata predisposta una istruzione che le congloba :
READ(buffer_file, variabile) Þ legge un valore dal file e lo assegna alla variabile
34) Come si chiude un file:
Tramite il comando Close(buffer_file).
Strutture di dati
35) Quante e quali strutture dati sono possibili:
Strutture lineari Lista Þ rappresentazione sequenziale
rappresentazione collegata Þ semplice
circolare
simmetrica
Pila
Coda
Strutture alineari Albero Þ Binario Þ semplice
Þ di ricerca
N-ario
Grafo
Liste
36) Cosa è una lista e quali operazioni debbono essere consentite su ogni tipo di lista:
Una lista è un insieme di dati tutti dello stesso tipo caratterizzati da una relazione d´ordine. Le operazioni tipiche sono :
cons Þ inserimento di un elemento in testa alla lista
car Þ legge il valore del 1° elemento della lista
cdr Þ elimina il 1° elemento della lista e ne restituisce il valore
null Þ verifica se il riferimento ad inizio lista è NIL (puntatori), 0 (matrici) oppure no.
Inserimento di un elemento in una posizione qualsiasi della lista.
Eliminazione di un elemento da una posizione qualsiasi della lista.
37) Descrivere la rappresentazione sequenziale delle liste ed i suoi svantaggi:
È una rappresentazione che generalmente viene implementata tramite un record di nome LISTA costituito da un campo di tipo array unidimensionale contenente gli elementi nell´ordine, un campo PRIMO che identifica il 1° elemento della lista sulla array ed un campo LUNGHEZZA indicante la lunghezza della lista stessa.
Gli svantaggi sono che le dimensione della array debbono essere definite a priori e non dinamicamente in base alla reale occupazione della lista, ciò può generare spreco di memoria o trabocco della capacità di ospitare elementi, inoltre ogni volta che si immette o toglie un elemento da una posizione intermedia occorre far scorrere tutti gli altri elementi.
38) Descrivere la rappresentazione collegata delle liste:
Di questa rappresentazione ve ne sono 2 possibili implementazioni :
tramite Matrici Þ Risolve il problema del dover far scorrere tutti gli elementi quando si immette o toglie un elemento intermedio della lista.
tramite Puntatori Þ Consente di occupare unicamente lo spazio di memoria necessario.
Entrambe i metodi sono basati sull´idea di associare ad ogni elemento della lista oltre al dato anche la posizione dove trovare il successivo elemento della lista.
39) Descrivere la rappresentazione collegata delle liste implementate su array :
Si ha un array costituito da records ognuno dei quali è formato da un campo DATO contenente l´informazione e da un campo SUCCESSIVO contenente la posizione nella array del successivo elemento, l´ultimo elemento della lista conterrà il valore 0 nel campo SUCCESSIVO mentre la posizione nella array del 1° elemento della lista è identificata da una variabile. Viene poi definita una lista libera la quale coopera con la lista reale in quanto le fornisce elementi quando si voglia aggiungere un elemento alla lista reale mentre quando si vuole eliminare un elemento dalla lista reale, è quest´ultima a cedere il record interessato alla lista libera. Entrambe le liste sono descritte da un record di tipo LISTA i cui campi sono LUNGHEZZA e PRIMO.
40) Descrivere la rappresentazione collegata delle liste implementate tramite puntatori :
Ogni elemento della lista è implementato su di un record formato da un campo DATO contenente l´informazione e da un campo SUCCESSIVO di tipo puntatore il quale punta alla locazione di memoria dove inizia il record successivo. L´ultimo elemento della lista è caratterizzato da un valore NIL nel campo SUCCESSIVO ad indicare che non punta nulla. Allorchè si renda necessario un nuovo record per aggiungere un elemento alla lista, se ne fa richiesta al Sysop tramite l´istruzione NEW(puntatore) la quale associa alla variabile puntatore l´indirizzo della locazione da utilizzare per memorizzare un nuovo elemento. Allorché si voglia invece eliminare un elemento è buona norma restituire il record alla diretta gestione del Sysop tramite il comando DISPOSE(puntatore). È necessaria inoltre una variabile PRIMO di tipo punta_elemento_lista atta ad identificare sempre il 1° elemento della lista.
Pila
41) Cosa è una struttura a pila:
Si tratta di una struttura lineare di tipo LIFO assimilabile ad una pila di piatti dove l´ultimo che è stato immesso sarà anche il 1° ad essere rimosso. Le operazioni tipiche su questa struttura sono :
Top Þ Restituisce l´elemento affiorante ossia quello inserito per ultimo
Push Þ Inserisce un valore nella pila
Pop Þ Elimina dalla pila l´elemento affiorante e ne restituisce il valore del campo DATI
Test_Pila_Vuota Þ Controlla se il riferimento al 1° elemento della pila è NIL(puntatori), 0 (matrici) oppure no.
Crea_Pila Þ Pone a NIL(puntatori) o 0 (matrici) il riferimento al 1° elemento della pila
42) In quanti modi è possibile l´implementazione di una struttura a pila:
Trattandosi di una struttura lineare ordinata, è molto simile alla lista della quale anzi risulta essere soltanto una limitazione nel senso che in una pila è consentito aggiungere ed eliminare elementi soltanto ad un estremo della stessa.
In virtù di ciò sono quindi possibili le implementazioni sia tramite matrici che tramite puntatori.
Coda
43) Cosa è una struttura a coda:
Si tratta di una struttura lineare di tipo FIFO assimilabile alla coda che si fa in un ufficio postale svizzero. Le operazioni tipiche su questa struttura sono :
Primo Þ Restituisce l´elemento inserito per primo nella coda e che quindi sarà il primo ad uscire.
In_coda Þ Inserisce un elemento nella coda si dovrà quindi aggiornare il riferimento ULTIMO
Out_coda Þ Elimina l´elemento della coda puntato da PRIMO e ne restituisce il valore del campo DATI
Test_Coda_Vuota Þ Controlla se il riferimento al 1° elemento della coda è NIL(puntatori), 0 (matrici) oppure no.
Crea_Coda Þ Pone a NIL(puntatori) o 0 (matrici) i riferimenti PRIMO ed ULTIMO .
44) In quanti modi è possibile l´implementazione di una struttura a coda:
Trattandosi di una struttura lineare ordinata, è molto simile alla lista, in virtù di ciò sono quindi possibili le implementazioni sia tramite matrici che tramite puntatori, entrambe debbono possedere dei riferimenti sia al 1° elemento della coda che all´ultimo elemento della coda tramite un record CODA | PRIMO | ULTIMO |
Albero
45) Cosa è un albero e quanti tipi ve ne sono:
Si tratta di una struttura non lineare particolarmente adatta a rappresentare situazioni a carattere gerarchico.
Gli elementi rappresentano i nodi della albero, da ogni nodo possono dipanarsi altri elementi che sono detti figli mentre il nodo genitore è detto padre o radice nel caso che non abbia padri, se un nodo non genera figli allora viene detto foglia in quanto terminale. Il livello di un nodo è pari al n° di nodi da percorrere per raggiungere la radice. La struttura in tal modo descritta si presta molto bene ad essere analizzata in forma ricorsiva .
I tipi di albero sono :
Albero binario Þ ogni nodo può avere al massimo 2 figli
Albero N-ario Þ ogni nodo può avere n figli
46) Quali sono le operazioni tipiche sugli alberi binari:
Costruisci Þ Restituisce un albero formato da una radice e da un sottoalbero sinistro ed uno destro.
Radice Þ Restituisce il valore associato alla radice
Sinistro Þ Restituisce il sottoalbero sinistro della albero binario
Destro Þ Restituisce il sottoalbero destro della albero binario
Test_Albero_Vuoto Þ Controlla se la albero è vuoto o meno
47) Descrivere le visite in Preordine, in Postordine, Simmetriche :
Preordine Þ analizza la radice quindi il sottoalbero sinistro infine il sottoalbero destro
Postordine Þ analizza il sottoalbero sinistro, poi il sottoalbero destro ed infine analizza la radice
Simmetrica Þ Analizza prima il sottoalbero sinistro quindi la radice ed infine il sottoalbero destro.
48) Dare l´esito delle 3 tipologie di visita sul del seguente albero :
Preordine : ETA, CARLO, MARIA, MARGHE, LISA, BETSY, GENNY, BARBARA, CRISTIANA.
Postordine : MARIA, LISA, BETSY, MARGHE, CARLO, BARBARA, CRISTIANA, GENNY, ETA.
Simmetrica : MARIA, CARLO, LISA, MARGHE, BETSY, ETA, BARBARA, GENNY, CRISTIANA.
49) Descrivere la rappresentazione collegata, tramite records e puntatori, di un albero binario:
Ogni elemento e quindi ogni nodo della albero è simulato da un record costituito di 3 campi :
SINISTRO Þ è un puntatore al sottoalbero sinistro, è NIL se il sottoalbero sinistro è vuoto
VALORE Þ contiene l´informazione associata al nodo
DESTRO Þ è un puntatore al sottoalbero destro, è NIL se il sottoalbero destro è vuoto
È poi necessaria una variabile che punti alla radice della albero.
50) Cosa è un albero binario di ricerca:
È un albero binario caratterizzato dal fatto che ogni nodo è tale che i nodi del sottoalbero di sinistra contengono valori minori o uguali rispetto al nodo considerato mentre i nodi del sottoalbero di destra contengono valori maggiori rispetto allo stesso nodo. Viene definito albero binario di ricerca in quanto abbassa in maniera considerevole i tempi necessari per la ricerca di un valore in quanto ad ogni passo della ricerca si eliminano metà degli elementi.
Grafo
51) Cosa è un Grafo:
Si tratta di una struttura non lineare particolarmente adatta a rappresentare relazioni binarie su di un insieme di elementi, ad esempio ben si presta al problema del percorso migliore per passare da una stanza di un labirinto ad un´altra stanza. Si distingue dagli alberi sostanzialmente per la possibilità di raggiungere uno stesso nodo tramite 2 percorsi diversi il che rende necessario una marcatura dei nodi visitati.
52) Che tipi di visite sono possibili su di un Grafo:
In profondità Þ Si analizza il nodo di partenza e per ogni successore si fa la stessa cosa
In Ampiezza Þ Si analizzano tutti i successori di un nodo e poi si analizzano i successori dei successori.
53) Come si rappresenta un grafo su un elaboratore:
Si fà riferimento ad una matrice delle adiacenze dove ci sono tante righe e tante colonne quanti sono i nodi, vi è un valore logico vero in una cella della matrice se vi è un ramo che unisce i 2 corrispondenti nodi. È poi necessario un altro vettore ad indicare se un determinato nodo è già stato visitato.