15 / 24
www.
edises
.it
Capitolo 1
Modelli dell’informatica
5
B. per ricoprire nel modo richiesto la scacchiera servono 31 tessere
C. per ricoprire nel modo richiesto la scacchiera servono 30 tessere
D. non è possibile riuscire a coprire la scacchiera nel modo richiesto
10) Quale delle seguenti fasi NON fa parte del processo di compilazione?
A. Analisi lessicale
B. Analisi semantica
C. Ottimizzazione del codice oggetto
D. Esecuzione del codice
11) Supponiamo di avere un array monodimensionale formato da
m
chiavi numeriche; quanti confronti sono richiesti, nel caso peggiore, per
scoprire se la chiave
k
è presente?
A. La parte intera superiore di log
2
(
m
)
B.
m
C. La parte intera inferiore di log
2
(
m
)
D.
m
– 1
12) Qual è la complessità computazionale dell’algoritmo di ordinamento
SelectionSort
(ordinamento con estrazione successiva dei minimi) in fun-
zione della lunghezza
n
del vettore da ordinare, rispettivamente nel caso
migliore e nel caso medio?
A. Caso migliore:
O
(
n
);
caso medio:
O
(
n
log
2
n
)
B. Caso migliore:
O
(
n
log
2
n
);
caso medio:
O
(
n
2
)
C. Caso migliore:
O
(
n
2
);
caso medio:
O
(
n
2
)
D. Caso migliore:
O
(
n
);
caso medio:
O
(
n
2
)
13) Quale delle seguenti cinquine di numeri NON può rappresentare i
gradi dei vertici di un grafo?
A. 1 0 0 0 1
B. 1 1 4 1 1
C. 2 2 2 2 2
D. 10 12 14 16 18
14) La grammatica
G
= [{
S
}, {
a
,
b
}, {
S
→
aaSb
,
S
→
ab
},
S
] produce frasi
del tipo:
A.
a
2
n
b
n
con
n
> 1
B.
a
2
n
–1
b
n
con
n
> 1
C.
a
2
n
–1
b
2
n
–1
con
n
> 1
D.
a
2
n
b
n
–1
con
n
> 1