Pages: [1] 2 3 ... 12   Go Down
Print
Author Topic: risposte esatte  (Read 18491 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
danilotrix
Matricola
*
Offline Offline

Posts: 46



« on: 19-02-2009, 16:24:11 »

qualcuno sa le risposte esatte del compito B?
saluti
Logged
Syco
Matricola
*
Offline Offline

Gender: Male
Posts: 31


WWW
« Reply #1 on: 19-02-2009, 17:04:35 »

se postate anche le domande qualche anima pia potrebbe risolverli...così possono rispondere solo quelli che c'erano e se le ricordano...
Logged

danilotrix
Matricola
*
Offline Offline

Posts: 46



« Reply #2 on: 19-02-2009, 17:14:12 »

sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata

a)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[x]

b)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[left[x]]+1

c)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i-j)
con j=size[left[x]]+1

d)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i-j)
else
        return Select(right[x],i)
con j=size[left[x]]+1

grazie
Logged
info
Guest
« Reply #3 on: 19-02-2009, 17:21:35 »

e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad ogni altro vertice v
b)esiste un cammino da ogni vertice u ad un dato vertice v
c)esiste un cammino da un dato vertice u ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

grazie
ciao
Logged
rob
Apprendista Forumista
**
Offline Offline

Posts: 104



« Reply #4 on: 19-02-2009, 17:40:43 »

e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad ogni altro vertice v
b)esiste un cammino da ogni vertice u ad un dato vertice v
c)esiste un cammino da un dato vertice u ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

grazie
ciao
Risposta giusta d
Logged

"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
rob
Apprendista Forumista
**
Offline Offline

Posts: 104



« Reply #5 on: 19-02-2009, 17:46:24 »

sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata

a)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[x]

b)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[left[x]]+1

c)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i-j)
con j=size[left[x]]+1

d)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i-j)
else
        return Select(right[x],i)
con j=size[left[x]]+1

grazie
risposta esatta c
Logged

"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
info
Guest
« Reply #6 on: 19-02-2009, 18:13:41 »

ok grazie cm pensavo...cmq ormai che ci siamo, posto anche qste due su cui ho avuto dubbi:
======= ======= ======= ======= =======
si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n

======= ======= ======= ======= =======
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a


grazie ciao
Logged
rob
Apprendista Forumista
**
Offline Offline

Posts: 104



« Reply #7 on: 19-02-2009, 18:20:57 »

Quote
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a


grazie ciao
risposta esatta d
L'altra ancora non l'ho risolta.....è abbastanza rognosa
Logged

"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #8 on: 19-02-2009, 18:25:20 »


si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n

sono quasi sicuro che è la b...infatti sbagghiai  testate testate testate
Logged

info
Guest
« Reply #9 on: 19-02-2009, 19:01:29 »

grazie Yngwie, cmq vediamo se qlcuno conosce la risposta certa.
ciao
Logged
bakks87
Apprendista Forumista
**
Offline Offline

Posts: 162


« Reply #10 on: 19-02-2009, 19:58:34 »

ragazzi ma per il compito A ?
qualcuno che abbia verificato le domande da fonti attendibili?
Logged
bakks87
Apprendista Forumista
**
Offline Offline

Posts: 162


« Reply #11 on: 19-02-2009, 20:21:57 »

ad esempio nel compito A, domanda 8:
"Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?

a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort

io ho messo la b, poichè Insertion Sort è efficiente per piccoli input; a questo punto, la proposizione "piccoli numeri interi compresi tra 0 e 1000" , soddisfa la condizione *per piccoli input* ??
ho un dubbio in questo punto...forse la risposta esatta è una tra c) e d)   
Logged
info
Guest
« Reply #12 on: 19-02-2009, 20:28:24 »

ma perchè hai escluso il Bucket Sort che è in tempo lineare?
Logged
bakks87
Apprendista Forumista
**
Offline Offline

Posts: 162


« Reply #13 on: 19-02-2009, 20:29:09 »

mmm
ho escluso la risposta esatta?
Logged
goblin
Guest
« Reply #14 on: 19-02-2009, 20:42:24 »

mmm
ho escluso la risposta esatta?

Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..
Logged
Pages: [1] 2 3 ... 12   Go Up
Print
Jump to: