Compito di Esame di giugno
Soluzioni degli Esercizi Proposti

Soluzione degli Esercizi del Compito A         Sia L una lista i cui elementi possono essere 0 ed 1 in modo che L rappresenti un numero
        binario. La lista L è implementata con puntatori doppi (ogni elemento punta al precedente
        e al successivo, se esitono). Si scriva una procedura o una funzione che incrementi di 1
        il valore rappresentato da L. Ad esempio, se
                    L->[1]<-->[1]<-->[1]<-->[1]
        la funzione deve modificare L come segue
                    L->[1]<-->[0]<-->[0]<-->[0]<-->[0]

          Inizialmente e' chiamata con r=1 (r e' il riporto).

    type
      booleano=(0,1);
      ListaB = ^Nodo;
      Nodo = record
        val: booleano;
        next: ListaB;
        prec:ListaB
       end;

    procedure annulla(l:lista);
    begin
        if (l<>nil) then begin
        l^.val:=0;
        annulla(l^.next)
        end
    end;
    procedure incrementa(var l:lista;var r:integer);
    var q:lista;
    begin
    if (l<>nil) then begin
        incrementa(L^.next,r);
        if (r=1) then
            if (l^.val=0) then begin
                r:=0;
                l^.val:=1;
                annulla(l^.next)
            end
            else if (l^.prec=nil) then begin
                r:=0;
                new(q);
                q^.val:=1;
                q^.next:=l;
                q^.prec:=nil;
                l^.prec:=q;
                l:=q;
                annulla(l^.next)
            end
    end
    end;
 

        Data una lista di caratteri T ed una lista di caratteri P si dice che P è una sottosequenza di
        T se i caratteri di P compaiono tutti all'interno di T nello stesso ordine, eventualmente
        intervallati da altri caratteri. Ad esempio se
                    T:B,C,A,F,P,X,E,Z,Y
                    e
                    P: A,P,E
        allora P è una sottosequenza di T, mentre se
                    T:B,C,A,F
        e
                    P:A,B,C
        non lo è. Si scriva una funzione booleana che, date le due liste di caratteri T e P, verifichi se
        P è una sottosequenza di T.

          type
            Listachar= ^Nodochar;
            Nodochar=record
            c:char;
            next:Listachar
            end;

     function verifica (T,P: Listachar):boolean;
     begin
      if (P=nil) then verifica:=true
      else if (T=nil) then verifica:=false
      else if (P^.c = T^.c) then
        verifica:=verifica(T^.next,P^.next)
      else verifica:=verifica(T^.next,P)
     end;

        Un albero n-ario è un albero in cui ciascun nodo può avere un numero qualsiasi di figli.
        Un modo conveniente di rappresentare tali alberi è di far puntare il padre al primo dei
        figli e poi far puntare ciascun figlio a suo fratello (se esiste). Vale a dire, i figli di un
        nodo x sono organizzati in una lista a puntatori, con x che punta al primo elemento di tale
        lista (v. Figura 1).

        Figura1

        Dopo aver definito l'opportuna struttura dati si scriva una funzione che, dato un albero n-ario
        ne calcoli la profondita'.

      type
      AlberoN = ^Nodo;
      Nodo = record
        info: integer;
        figlio: AlberoN;
        fratello: AlberoN
       end;

   function profondita (T: AlberoN): integer;
    var count,count2:integer;
    a:AlberoN;
    begin
      if (T=nil) then profondita:=0
      else begin
        a:=T^.figlio;
        count:=profondita(a);
        while (a<>nil) do begin
            a:=a^.fratello;
            count2:=profondita(a);
            if count < count2 then count:=count2
        end;
        profondita:=count+1
     end
    end;


Soluzione degli Esercizi del Compito B
          Un pettine è una struttura dati che consiste di una lista di liste, vale a dire abbiamo
        una lista P in cui ciascun elemento consiste di due campi: (a) un puntatore al successivo
        elemento di P e (b) un puntatore ad una lista. Ad esempio, questo è un pettine:

        Figura

        Il contenuto delle liste non ha importanza. Un pettine si dice di alta moda se ogni lista è
        piu' lunga della precedente. Ad esempio il pettine in figura non è di alta moda perchè la
        terza lista non è più lunga della seconda.

        1) Si dia l'opportuna definizione di tipo
        2) Si scriva una funzione lunghezza (l:lista): integer che restituisce la lunghezza della lista l
        (suggerimento: fatela ricorsiva);
        3) Si scriva una funzione che, dati in input un pettine, verifichi se è di alta moda.

      type
      Lista = ^Nodo;
      Nodo = record
        val:integer;
        next:Lista
      end;
      Pettine = ^Elem;
      Elem = record
        NextL: Lista;
        NextP: Pettine
       end;

     function lunghezza (L: Lista): integer;
     begin
      if (L = nil) then
       lunghezza := 0
      else lunghezza:=lunghezza(L^.next)+1
     end;

     function altamoda (P: Pettine): boolean;
     begin
      if (P = nil) then altamoda:=true
      else
        if (P^.NextP = nil) then altamoda:=true
        else
            altamoda:=(altamoda(P^.NextP) and
            (lunghezza(P^.NextL)<lunghezza(P^.NextP^.NextL)))
      end;

       Si scriva una funzione booleana ricorsiva che, prese due liste a puntatori semplici A e B,
       restituisce vero se B è una sottolista di A e falso altrimenti. Ad esempio, se

        A->1->10->12->27->13->10->12->3->51

        B->10->12->3

        la funzione restituisce vero mentre con

         A->1->10->12->27->13->10->12->3->51

        B->10->3->51

        la funzione restituisce falso.

     function controlla (A,B: lista):boolean;
     begin
        if (B=nil) then controlla:=true
        else if (A=nil) then controlla:=false
        else
            if (A^.val=B^.val) then
                controlla:=controlla(A^.next,B^.next)
            else
                controlla:=false
    end;

     function sottolista (A,B: lista):boolean;
     begin
        if (A=nil) then sottolista:=false
        else if (B=nil) then sottolista:=true
        else
            if (controlla(A,B)) then
                sottolista:=true
            else
                sottolista:=sottolista(A^.next,B)
    end;
 

        Un albero n-ario è un albero in cui ciascun nodo può avere un numero qualsiasi di figli.
        Un modo conveniente di rappresentare tali alberi è di far puntare il padre al primo dei
        figli e poi far puntare ciascun figlio a suo fratello (se esiste). Vale a dire, i figli di un
        nodo x sono organizzati in una lista a puntatori, con x che punta al primo elemento di tale
        lista.

        Figura3

        Dopo aver definito l'opportuna struttura dati si scriva una funzione che, dato un albero n-ario
        T ed un intero k, calcoli il numero di nodi che sono a livello k (la radice è a livello 0).

      type
      AlberoN = ^Nodo;
      Nodo = record
        info: integer;
        figlio: AlberoN;
        fratello: AlberoN
       end;

   function NumNodi (T: AlberoN; k: integer): integer;
    var count:integer;
    begin
      if (T=nil) then NumNodi:=0
      else if (k<>0) then
        NumNodi:=NumNodi(T^.figlio,k-1)+
        NumNodi(T^.fratello,k)
      end
      else begin
         count:=1;
         while (T^.fratello<>nil) do begin
            count:=count+1,
            T:=T^.fratello
         end;
        NumNodi:=count
      end;
    end;
 
 


Soluzione degli Esercizi del Compito C
          Si scriva una funzione iterativa che, dati in input un albero di ricerca T ed un intero x,
        verifichi se x è presente in T o meno.

      type
      AlberoR = ^Nodo;
      Nodo = record
        val: integer;
        Sin: AlberoR;
        Des: AlberoR
       end;

    function find(T: alberoR; x:integer):boolean;
    var
    a:alberoR;
    t1:boolean;
    begin
        a:=T;
        t1:=false;
        while ((a<>nil) and not t1)do
            if (a^.val=x) then t1:=true
            else
                if x<a^.val then a:=a^.Sin
                else a:=a^.Des;
        find:=t1
    end;
 

        Una mesh è una struttura a puntatori di questo tipo:

        Figura 4

        i cui elementi sono interi. Una mesh si dice connessa se a partire dal punto di entrata ogni nodo
        è raggiungibile. La mesh in figura ad esempio è connessa. Si scriva una procedura ricorsiva
        che, data una mesh connessa M ed un intero x, verifichi se x è presente nella mesh. Si dia anche
        l'opportuna definizione di tipo.

            La procedura inmesh sotto descritta sara' richiamata dal programma principale con parametri
            una mesh M', un intero da cercare x', e la varabile booleana a false. All'uscita dalla procedura
            la variabile booleana passata come parametro conterra' true se l'intero è stato trovato, false
            altrimenti.

     type
     Mesh= ^NodoM;
     NodoM=record
        val:integer;
        des:Mesh;
        giu:Mesh
     end;

     procedure inmesh (M: mesh; x: integer;var b:boolean);
     begin
        if(not b and (M<>nil)) then begin
            if (M^.val= x)then
                b:=true
            else begin
                inmesh(M^.des,x,b);
                inmesh(M^.giu,x,b)
            end
        end
     end;

        Si scriva una funzione booleana iterativa che, dati in input un albero binario di interi T ed
        un intero x, verifichi se x è presente in T oppure no. Nel risolvere l'esrcizio dovete fare
        uso delle seguenti funzioni e procedure per la manipolazione di una pila:


    type

      PuntNodo = ^Nodo;
      Nodo = record
        info: integer;
        Sin: PuntNodo;
        Des: PuntNodo
       end;
       Pila=...

       var P:Pila;

     function find2 (T: PuntNodo;x:integer): boolean;
      var
       a:PuntNodo;
       t1:boolean;
     begin
        t1:=false;
        if (T<>nil) then begin
            Push(T);
            while (not t1 and not isEmpty()) do begin
                a:=Pop();
                if (a^.val = x)then t1:=true
                else begin
                    if (a^.Sin<>nil) then Push(a^.Sin);
                    if (a^.Des<>nil) then Push(a^.Des)
                end
            end
        end;
        find2:=t1
    end;


Soluzione degli Esercizi del Compito D
          Un albero giallo-verde è un albero binario i cui vertici sono colorati di giallo oppure di verde. Un albero
        giallo-verde è accidioso se in ogni sottoalbero  il numero di nodi verdi è maggiore di quello dei
        nodi gialli. Scrivere una funzione booleana che verifichi se un nodo giallo-verde è accidioso o meno. Si
        possono utilizzare qualsivoglia funzioni di appoggio.

        Si utilizza come funzione di appoggio la funzione diff, precedentemente vista, che dato un albero giallo-verde
        calcola la differenza tra il numero di nodi verdi ed il numero di nodi gialli. Si vedano le soluzioni del primo
        esonero per il codice di tale funzione.
        Nota: A rigore si sarebbe dovuto specificare che si sta parlando di alberi non vuoti. Notare pero' che
        se si assume che un albero vuoto viola la condizione allora l'esercizio diventa banale in quanto nessun
        albero può essere accidioso. In generale  la seguente regola è sempre implicitamente assunta: se una
        struttura non viola una condizione allora la soddisfa.

    type
    AlberoGV=^NodoGV;
    NodoGV=record
        giallo:boolean;
        sin:AlberoGV;
        des:AlberoGV
    end;

    function diff(T:AlberoGV):integer;

    function accidioso(T:AlberoGV):boolean;
    var t1:integer;
    begin
      if (T = nil) then accidioso:=true
      else begin
        if not T^.giallo then t1:=1 else t1:=-1;
        accidioso:=accidioso(T^.sin) and accidioso(T^.des)
        and (diff(T^.sin)+diff(T^.des)+t1>0)
      end
    end;

         Sia L una lista di interi implementata con puntatori semplici (ogni elemento punta al successivo se
        esiste). Una lista si dice straripante se ogni elemento è maggiore della somma di tutti gli elementi
        successivi. Ad esempio se
        L-->[100]-->[16]-->[4]-->[1]
        la lista è straripante, mentre se
        L-->[100]-->[16]-->[14]-->[2]
        non lo è in quanto 16=14+2. Si scriva una funzone booleana ricorsiva che verifichi se la lista di input
        è straripante oppure no.

        Si fa uso di una funzione ricorsiva di appoggio somma che data una lista restituisce la somma dei
        valori dei suoi elementi.

         function somma(L:Lista):integer;
     begin
      if (L=nil) then somma:=0
      else somma:=L^.val+somma(L^.next)
     end;

    function straripante (L:Lista):boolean;
    begin
    if (L=nil) then straripante:=true
    else straripante:=(straripante(L^.next) and (somma(L^.next)<L^.val))
    end;

        Un albero n-ario è un albero in cui ciascun nodo può avere un numero qualsiasi di figli.
        Un modo conveniente di rappresentare tali alberi è di far puntare il padre al primo dei
        figli e poi far puntare ciascun figlio a suo fratello (se esiste). Vale a dire, i figli di un
        nodo x sono organizzati in una lista a puntatori, con x che punta al primo elemento di tale
        lista.

        Figura 5

        Un albero n-ario è minimalista se ogni nodo è minore di ogni suo figlio. Dopo aver definito
        l'opportuna struttura dati si scriva una funzione booleana che, dato un albero n-ario
        verifichi se esso è minimalista.

      type
      AlberoN = ^Nodo;
      Nodo = record
        info: integer;
        figlio: AlberoN;
        fratello: AlberoN
       end;

   function minimalista (T: AlberoN):boolean;
    var t1:boolean;
    a:AlberoN;
    begin
      if (T=nil) then minimalista:=true
      else begin
        t1:=true;
        a:=T^.figlio;
        while ((a<>nil)and t1)do begin
            t1:=t1 and minimalista(a)and (a^.info>T^.info);
            a:=a^.fratello
        end;
        minimalista:=t1
      end
    end;

Per favore segnalate eventuali errori alla Dott.ssa Chiara Petrioli