16 / 24
www.
edises
.it
6
Parte Prima
Competenze disciplinari
15) Si consideri la seguente grammatica, di cui sono date le produzioni, il cui
simbolo iniziale (o simbolo distinto) è
S
ed in cui
Ø
denota la stringa vuota.
S
→
Ø
|
ASB
A
→
0
B
→
1
Quale linguaggio genera tale grammatica?
A. {0
n
1
m
:
n
> 0,
m
> 0}
U
{Ø}
B. {0
n
1
n
:
n
> 0}
U
{Ø}
C. {0
n
1
n
:
n
> 0}
U
{Ø}
D. {(01)
n
:
n
> 0}
U
{Ø}
16) Un algoritmo ricorsivo è trasformabile in modo efficiente in uno
iterativo adottando come struttura dati:
A. un albero
B. una coda
C. uno stack
D. un grafo orientato
17) Il numero minimo di semplici confronti di chiavi che ci si possa
aspettare in un metodo di ordinamento efficiente per un problema di
dimensione
N
è dell’ordine di:
A.
N
B.
N
2
C. 2
N
D.
N
log
2
N
18) È dato il seguente albero:
Qual è la sequenza che si ottiene attraversando l’albero in preordine?
A. = A + + bc/ − 3.6 + dcf"4
B. = A + + bc/ − 3.6 + dc" f4
C. A = bc + + 3.6 dc + −/f4"
D. A = bc + + 3.6 cd + − /4f"
$
E
+
+
´
I
F
F
G