risposte esatte

[danilotrix]

qualcuno sa le risposte esatte del compito B?
saluti

[Syco]

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

[danilotrix]

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

[info]

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

[rob]

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

[rob]

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

[info]

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

[rob]

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

[Yngwie]

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  

[info]

grazie Yngwie, cmq vediamo se qlcuno conosce la risposta certa.
ciao

[bakks87]

ragazzi ma per il compito A ?
qualcuno che abbia verificato le domande da fonti attendibili?

[bakks87]

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)   

[info]

ma perchè hai escluso il Bucket Sort che è in tempo lineare?

[bakks87]

mmm
ho escluso la risposta esatta?

[goblin]

mmm
ho escluso la risposta esatta?

Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..