NEW
Font size
S
M
L
XL
WorksheetsASD, 3 parte
Total questions: 20
Worksheet time: 10mins
Name
Class
Date
1.
Qualsiasi problema di ottimizzazione che soddisfa la proprieta' della sottostruttura ottima puo' essere risolto all'ottimo con la programmazione dinamica
a)
VERO
b)
FALSO
c)
dipende
d)
solo se P=NP
2.
I B Trees sono una struttura dati che ha l'obiettivo di
a)
massimizzare il numero di accesi alla memoria di massa
b)
minimizzare il numero di accessi alla memoria principale
c)
minimizzare il numero di accessi alla memoria di massa
d)
aiutare la memoria del programmatore
3.
Un B tree e' un albero
a)
che puo' essere molto sbilanciato
b)
in cui tutte le foglie hanno la stessa profondita'
c)
in cui ogni nodo interno ha la stessa profondita'
d)
binario (B tree sta per Binary tree)
4.
In un B tree, il grado minimo t e'
a)
il minimo numero di chiavi memorizzabili in un nodo
b)
il minimo numero di figli che un nodo interno puo' avere
c)
il massimo numero di chiavi memorizzabili in un nodo
d)
il minimo valore di temperatura di un nodo
5.
Avendo dati memorizzati con un B tree; il tempo di CPU necessario per recuperare un dato e':
a)
O(logt n)
b)
O(logn t)
c)
O(n logt n)
d)
O(t logt n)
6.
Lo split della radice di un B tree
a)
fa si' che l'albero abbia due radici
b)
fa si' che l'albero cresca (verso l'alto)
c)
fa si' che l'albero cresca (verso il basso)
d)
non modifica il numero complessivo dei nodi dell'albero
7.
La somma dei gradi di tutti i vertici di un grafo G=(V,E) e'
a)
uguale al doppio del numero dei vertici in V
b)
uguale al numero degli archi in E
c)
compresa fra |E| e 2|E|
d)
uguale al doppio del numero degli archi in E
8.
Un sottografo G* di un grafo G=(V,E) e'
a)
un sottinsieme dei vertici e degli archi di G
b)
un grafo che ha tutti i vertici in V ma solo un sottinsieme degli archi in E
c)
un grafo che ha tutti gli archi in E ma solo un sottinsieme dei vertici in V
d)
un sottinsieme connesso del grafo G
9.
L'algoritmo MST-Kruskal(G,w) utilizza le procedure
a)
Make-Set; Find-Set; Union
b)
Find-Arc; Insert-Arc
c)
Make-Set; Find-Arc; Compute-Cost
d)
Make-Set; Union; Compute-Cost
10.
La complessita' in tempo dell'algoritmo di kruskal e'
a)
O(E log* E)
b)
Θ(V log E)
c)
Θ(E log V)
d)
O(E log E)
11.
L'algoritmo MST-Prim(G,w,r)
a)
mantiene gli archi di G ordinati per costo decrescente
b)
mantiene gli archi di G ordinati per costo non crescente
c)
mantiene gli archi di G ordinati per costo non decrescente
d)
non necessita di particolari ordinamenti delegando alla Extract-Min la gestione dei costi degli archi di G
12.
La rappresentazione interna dei cammini nel problema dell'individuazione dei cammini minimi con sorgente singola e' analoga a quella
a)
delle CFC
b)
del hash con chaining
c)
dei cicli hamiltoniani
d)
degli alberi BFS
13.
L'algoritmo di Dijkstra con sorgente singola s
a)
percorre in maniera BFS il grafo G a partire dal vertice s
b)
percorre in maniera DFS il grafo G a partire dal vertice s
c)
associa ad ogni vertice v ∈ V una stima del rilassamento dell'arco (s,v) che porta in v
d)
mantiene un insieme S di vertici v per cui il costo del cammino minimo da s a v e' gia' stato determinato
14.
La complessita' di DAG-shortest-path e'
a)
O(V log E)
b)
O(E log V)
c)
O(V2)
d)
O(V+E)
15.
L'algoritmo di Floyd-Warshall
a)
accetta cicli di costo negativo
b)
assume che tutti gli archi abbiano costo non negativo
c)
assume che tutti gli archi abbiano costo non positivo
d)
accetta archi di peso negativo ma non cicli negativi
16.
I problemi decisionali sono la classe di problemi dove per ogni possibile ingresso un algoritmo deve
a)
trovare la corrispondente soluzione di costo minimo
b)
computare un'uscita corrsipondente alla stringa di input ricevuta in ingresso
c)
scegliere una fra due risposte possibili: "si" o "no"
d)
individuare la decisione che risolve il problema
17.
La classe delle funzioni corrispondenti a problemi decisionali e' quella delle funzioni
a)
computabili del tipo f: N -> {0;1}
b)
computabili del tipo f: N -> R
c)
computabili del tipo f: stringhe -> {"si";"no"}
d)
le funzioni non c'entrano niente
18.
Una k-CNF e'
a)
una CNF definita su k congiunti
b)
la disgiunzione di k CNF
c)
una CNF in cui ogni congiunto ha k termini
d)
non ricordo
19.
Si sa che
a)
NP ⊆ P
b)
P ⊆ NP
c)
P = NP
d)
P ≠ NP
20.
La prova di NP completezza del problema del sottografo completo (CSP) puo' essere fatta
a)
riducendo SAT a CSP
b)
riducendo CSP a SAT
c)
aumentando SAT a CSP
d)
aumentando CSP a SAT
Reset
