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.

___________________________________________________________

                 Esito test :                  

 

                        

Risposte esatte su domande affrontate

___________________________________________________________

return to lesson 21

___________________________________________________________