Soluzioni alcuni esercizi di fondamenti di informatica del 14.09.2015


----
Quale di queste uguaglianze e` VERA

   a)   X *  Y *  Z =  (X + Y + Z)
   b)   X +  Y +  Z = /(X * Y * Z)
   c)  /X * /Y * /Z =  (X + Y + Z)
   d)  /X + /Y + /Z = /(X + Y + Z)
   e)  /X * /Y * /Z = /(X + Y + Z)

Applicando il teorema di de morgan si trova che
la risposta esatta e` la E

----

Un sommatore elementare in base 2 ha ingressi X, Y e Ci,
e uscite S e Co.  Gli ingressi X e Y sono collegati insieme.
Quale linea rappresenta il comportamento del sommatore:

   a)   S = X + Ci  ; Co = X * Ci
   b)   S = X * Ci  ; Co = X + Ci
   c)   S = Ci      ; Co = X
   d)   S = X       ; Co = Ci
   e)   S = X + Ci  ; Co = Ci

Quando X e Y sono collegati assieme la tabella di verita` del sommatore diventa

     X (e Y)  Ci     S    Co    somma
   ---------------------------
      0       0      0     0    zero
      0       1      1     0    uno
      1       0      0     1    due
      1       1      1     1    tre

quindi la risposta corretta e` C


---- C1 1 A -----------------
Un calcolatore rappresenta i numeri naturali su 8 bit
A quale numero corrisponde la rappresentazione 1101 0110
(a sinistra la cifra piu` significativa):

    a) duecentoquattordici
    b) millecentouno
    c) cinque
    d) millecentosette
    e) centodieci

Le cifre rappresentano le potenze di due quindi si ha
  2^7 + 2^6 + 2^4 + 2^2 + 2^1 = duecentoquattordici
(incidentalmente, su 8 bit si possono rappresentare solo
i numeri da 0 a 255 quindi le risposte b e d non sono possibili)


----
Quanto vale x dopo l'esecuzione di questo frammento di Javascript

    var i, x = 0, a = [1], b = a;
    for (i = 0; i < 10; i++) a[i] = i;
    x = b.length;

    a) 0
    b) 1
    c) 10
    d) 45
    e) 100

Il ciclo for() crea 10 elementi nel vettore a, e siccome b e`
un riferimento al vettore a il risultato corretto e` 10

----
Un vettore V di lunghezza 12 contiene numeri interi compresi tra 1 e N
V non e` ordinato. Qual'e' la complessita` della ricerca del massimo valore ?

    a) O(1)   b)  O(log N)   c)  O(N)   d)   O(N log N)   e)  O(N^2)

Il vettore ha lunghezza fissa per cui la ricerca richiede comunque un
tempo costante, ovvero O(1) , indipendentemente dall'essere ordinato o meno.


----
Quante volte viene eseguito il corpo del for nel seguente
frammento di codice Javascript:

        for (y = 0; y > 0; y = 1) { y = y + 1; continue; }

        a) 0    b) 1    c) 2    d) 10   e) infinite

il test y > 0 fallisce subito quindi il corpo non viene mai eseguito.

----
Sia dato un vettore che contiene elementi interi.
Scrivere una funzione sd(v) che riceve in ingresso v e restituisce
un nuovo vettore contenente tutti gli elementi di indice dispari in v

    function sd(v) {
	var i, ret = [];
	for (i = 1; i < v.length; i += 2) {
	    ret.push(v[i]);
	}
	return ret;
    }

----
Sia dato un vettore che contiene elementi interi.
Scrivere una funzione eoc(v) che riceve in ingresso v e restituisce
"true" se v e` ordinato in senso crescente, "false" altrimenti.

E` sufficiente confrontare ogni elemento con il precedente,
terminando subito con false se l'ordine e` violato.
Se si arriva in fondo senza errori allora il vettore e`
ordinato e si puo` ritornare true.

    function eoc(v) {
	var i;
	for (i = 1; i < v.length; i++) {
	    if (v[i] < v[i+=1) {
		return false; /* ordine crescente violato */
	    }
	}
	return true; /* tutti i valori sono non decrescenti */
    }

----
Sia dato un vettore v che contiene dati della forma
      { nome: <stringa>, ... }
Si vuole realizzare una funzione comuni(v) che riceve in ingresso v e
restituisce un vettore che contiene i tre nomi che appaiono piu`
volte nel vettore.
Descrivere a) l'algoritmo seguito, b) la sua complessita` e infine
scrivere la funzione.

Si opera in due fasi: nella prima si usa una mappa per memorizzare
tutti i nomi diversi con il numero di occorrenze, nella seconda si
selezionano i nomi con numero di occorrenze maggiori.
Essendo la scelta limitata a 3 elementi non serve fare un sort completo
ma conviene ripetere tre volte la selezione del maggiore, eliminando ogni
volta l'elemento trovato.
La complessita` di ogni passo e` O(N) quindi complessivamente O(N)

    function comuni(v) {
	var m = {}, ret = [], i, n, cand;

	/* conta occorrenze di ciascun nome */
	for (i = 0 ; i < v.length; i++) {
	    n = v[i].nome;
	    m[n] = (m[n] == undefined) ? 1 : m[n] + 1;
	}
	/* seleziona il maggiore, tre volte */
	for (n = 0; n < 3; n++) {
	    cand = null;
	    for (i in m) {
		if (cand == null || m[i] > m[cand]) {
		    cand = i; /* nuovo candidato */
		}
	    }
	    ret[n] = cand; /* salva il nome con maggiori occorrenze */
	    m[cand] = 0; /* azzera valore in modo da non riprenderlo */
	}
	return ret;
    }


---- R 1 x --- albero -----------
Un albero binario con nodi nodi della forma
    { D: <stringa>; Left, Right: <riferimenti a nodi figli> }
e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha
        Left.D < D <= Right.D
Scrivere una funzione ins(n, X) che riceve in ingresso un riferimento alla radice
di un albero non vuoto e vi inserisce la stringa X

La funzione richiesta e` la canonica funzione di inserimento, semplificiata
dal fatto che l'albero e` non vuoto e non si deve ritornare la radice.

    function ins(n, x) {
	while (true) {
	    if (x < n.D) {
		if (n.Left == null) {
		    n.Left = { D:X, Left: null, Right: null};
		    break;
		} else {
		    n = n.Left;
		}
	    } else {
		if (n.Right == null) {
		    n.Right = { D:X, Left: null, Right: null};
		    break;
		} else {
		    n = n.Right;
		}
	    }
	}
    }

Versione piu` compatta (ma meno leggibile):

    function ins(n, x) {
	/* crea il nuovo elemento da inserire */
	var e = { D:X, Left: null, Right: null}; /* elemento da inserire */
	/* ripete fino a quando non si raggiunge il nuovo elemento */
	while (n != e) {
	    if (x < n.D) {
		/* vado a sinistra o inserisco a sinistra */
		n = n.Left = (n.Left == null) ? e : n.Left;
	    } else { /* altrimenti opero a destra */
		n = n.Right = (n.Right == null) ? e : n.Right;
	    }
	}
    }



----
Un albero binario con nodi nodi della forma
    { D: <stringa>; Left, Right: <riferimenti a nodi figli> }
e` ordinato in modo che in ogni nodo, se Left e/o Right esistono, si ha
        Left.D < D <= Right.D
Scrivere una funzione l(n) che riceve in ingresso un riferimento alla radice
di un albero e restituisce una lista con tutte le stringhe contenute nell'albero.

La soluzione richiede l'esplorazione ricorsiva dell'albero con aggiunta alla
lista degli elementi via via trovati. Si risolve bene con una funzione di appoggio
che usa un ulteriore argomento, la lista contenente i risultati parziali

    function l(n) {
	return l1(n, null)
    }

    function l1(n, ret) {
	if (n == null) {
	    return ret;
	}
	ret = l1(n.left, ret); /* esplora a sinistra */
	ret = { D: n.D, next: ret }; /* aggiunge elemento corrente */
	ret = l1(n.right, ret); /* esplora a destra */
    }

In questo modo la funzione ritorna la lista ordinata come nell'albero originale.