Test di autovalutazione 21
Domanda 1 :
Avendo la seguente rappresentazione parentetica di un albero binario: (5 (10(1 ()())(4()()))(7()(31()()))), visitato in preordine, quali elementi sono le foglie dell'albero?
10 4 31
1 4 31
1 10 7
10 4 7
Domanda 2 :
Un albero binario completo di profondita' p=5 : 1) quanti nodi possiede complessivamente? 2) nel livello j=3 quanti nodi vi sono? 3) quanti sono i nodi foglia?
1) 64 2) 16 3) 32
1) 32 2) 16 3) 31
1) 63 2) 8 3) 32
1) 63 2) 32 3) 8
Domanda 3 :
Quale e' la definizione di un albero binario di ricerca
un albero binario di ricerca e' un albero binario, in cui ogni nodo N dell'albero ha la seguente proprieta': tutti i nodi del sottoalbero destro sono minori od uguali del valore del nodo N e tutti i nodi del sottoalbero sinistro hanno un valore maggiore di quello del nodo N.
un albero binario di ricerca e' un albero binario, in cui ogni nodo N dell'albero ha la seguente proprieta': tutti i nodi del sottoalbero sinistro sono minori od uguali del valore del nodo N e tutti i nodi del sottoalbero destro hanno un valore minore di quello del nodo N.
un albero binario di ricerca e' un albero binario, in cui ogni nodo N dell'albero ha la seguente proprieta': tutti i nodi del sottoalbero sinistro sono minori od uguali del valore del nodo N e tutti i nodi del sottoalbero destro hanno un valore maggiore di quello del nodo N.
un albero binario di ricerca e' un albero binario, in cui il nodo N dell'albero ha la seguente proprieta': tutti i nodi del sottoalbero sinistro sono minori del valore del nodo N e tutti i nodi del sottoalbero destro hanno un valore maggiore od uguale di quello del nodo N.
Domanda 4 :
L'albero binario rappresentato in figura, nel caso in cui alle lettere corrispondano i numeri: A=19, B=11, C=26; D=5; E=13; ed F=30 cosa rappresenta?
un albero binario di ricerca se fosse completo
un albero binario con il nodo di livello uno pari a 19
un albero binario ordinato se fosse corretta l'associazione di numeri a lettere
un albero binario di ricerca
Domanda 5 :
Ricordando la definizione di albero binario con struct e puntatori della lezione 21, dite cosa fa la seguente funzione P(..) :
Booleano P(Tipo_Albero_bin alb, Tipo_atomi elem)
{if(alb==NULL) return FALSE;
else if (alb->info==elem)
return TRUE;
else {return(P(alb->sin, elem)|| P(alb->des, elem));}}
cerca l'info elem nell'albero binario e se la trova restituisce il valore TRUE, altrimenti il valore FALSE
verifica se e' presente l'info elem nei sottoalberi sinistro e destro e nel caso restituisce il valore TRUE altrimenti FALSE
cerca l'info elem ricorsivamente nell'albero binario e se la trova restituisce il valore TRUE, altrimenti continua a cercare in un ciclo infinito.
cerca l'info elem ricorsivamente nell'albero binario e se la trova restituisce il valore TRUE, altrimenti restituisce FALSE ma continua a cercare in un ciclo infinito fino a saturare la memoria RAM.
Domanda 6 :
Se un albero binario completo fosse rappresentato attraverso un array i cui elementi fossero nell'ordine:
10 20 30 40 50 60 70 la visita dell'albero in preordine quali elementi dell'array analizzerebbe.
10 20 40 50 30 60 70
10 20 30 40 50 60 70
40 20 50 10 60 30 70
40 50 20 60 70 30 10
Domanda 7 :
Cosa abbiamo definito con la seguente:
struct struttura {char info[81];
struct struttura *ptr_next;
struct struttura *ptr_back;
}strutt;
una lista doppia con due puntatori di tipo array di caratteri.
una struttura ricorsiva, contenente un campo info di tipo array contenente al max 81 caratteri e due campi , ptr_next e ptr_back, che fanno riferimento ad una struttura dello stesso tipo di quella in cui sono contenuti.
una struttura ricorsiva, contenente un campo info di tipo array contenente al max 80 caratteri e due campi di tipo puntatore, ptr_next e ptr_back, che fanno riferimento ad una struttura dello stesso tipo di quella in cui sono contenuti.
una lista doppia con due puntatori struct struttura ed un campo info di tipo carattere.
Domanda 8 :
Avendo le seguenti definizioni preliminari
typedef int TipoElemLista; struct StructLista { TipoElemLista info; struct StructLista *next; }; typedef struct StructLista TipoNodoLista; typedef TipoNodoLista *TipoLista;
cosa fa la seguente funzione:
void Lista(TipoLista *lis,TipoElemLista elem) { TipoLista punt; TipoLista paux; paux = malloc(sizeof(TipoNodoLista)); paux->info = elem; paux->next = NULL; if(*lis == NULL) *lis = paux; else { punt = *lis; while(punt->next != NULL) punt = punt->next; punt->next = paux; } }
inserisce l'elemento elem in testa alla lista semplice lis.
inserisce l'elemento elem in coda alla lista semplice lis.
cancella l'elemento elem dalla testa della lista semplice lis.
inserisce l'elemento elem nella posizione 2 della lista semplice lis.
___________________________________________________________
return to lesson 21