Pages: 1 [2] 3 4 5   Go Down
Print
Author Topic: Domanda compito  (Read 9293 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #15 on: 04-03-2010, 19:24:19 »

Anche secondo me è la C.
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #16 on: 04-03-2010, 21:08:20 »

si si è proprio la c. Perchè in ogni livello ci stanno al più 2^h nodi, nei precedenti (2^h)-1;
sommando 2^h+(2^h)-1;
con la messa in evidenza parziale, otteniamo (2*2^h)-1;
infine per le proprietà delle potenze 2^(h+1)-1.
Che è la C.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #17 on: 05-03-2010, 09:47:34 »

Grazie per avermi risposto  ok

Se invece riproponessi la stessa domanda di prima (quella della Heap) ma invece di considerare il numero massimo, consideriamo il numero minimo di nodi quale risposta sarebbe corretta?

a.   2^{h-1}

b.   2^{h-1} +1

c.   2^h

d.  2^h +1


Secondo me è la c.
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #18 on: 05-03-2010, 09:53:55 »

Anche secondo me è la c.

P.S: Gam, ma da dove li prendi questi esercizi??
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #19 on: 05-03-2010, 13:45:49 »

Qual'è il tempo di esecuzione di Heapsort su un array A di lunghezza n, già ordinata in ordine crescente?


a.   O(log n)

b.   O(n)

c.   O(nlog n)

d.   O(n^2)


Secondo me il tempo di esecuzione di Heapsort, indipendentemente dal fatto che l'array sia ordinato in senso crescente o decrescente è sempre O(nlog n);
ho pensato che se A è ordinato in senso crescente e nella procedura Heapsort c'è Build_Max-Heap significa che quest'ultima procedura dovrebbe ritornare l'array A completamente invertito (poichè gli elementi in A, originariamente erano ordinati dal più piccolo al più grande) questo dovrebbe avvenire in tempo \Theta(n) e quindi Heapsort comunque avrebbe un tempo O(nlog n). Analogamente penso che ciò avvenga se A fosse ordinato inizialmente in ordine decrescente.

Quindi direi c

E' forse sbagliato quello che dico?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #20 on: 05-03-2010, 14:55:16 »

la risposta corretta è c, perchè qualunque istanza di input viene ordinata con heapsort in tempo nlogn, in quanto l'algoritmo effettua sempre le stesse operazioni, indipendentemente dalla distribuzione dell'input
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #21 on: 05-03-2010, 14:57:41 »

la prima è giusta perchè basta prendere i nodi dei livelli precedenti e sommare uno.
anche la seconda è c. Indipendentemente dall'ordine, compi le stesse operazioni.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #22 on: 05-03-2010, 21:44:12 »

Data l'equazione di ricorrenza T(n)= T(n/2) +sqrt(n), la sua soluzione è (scegliere il bound più stretto)
a. T(n) =O(log n)
b. T'(nl=O(sqrt(n))
c. T(n)=O(sqrt(n) log n)
d. T(n) =O(n)


secondo voi quale può essere??

secondo me è la b per il terzo caso del teorema master


Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #23 on: 06-03-2010, 09:27:07 »

hai già risposto a questa domanda prima  cry
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #24 on: 06-03-2010, 13:11:44 »

Ahahahahah , hai ragione! scusami XD

Deve essere la stanchezza ormai sono arrivato al culmine , comunque ne metto un altra..

Sia T un albero binario di ricerca che contiene tutti e soli i numeri compresi tra 1 e 100. Supponete di volere
cercare il numero 50. Quanti numeri minori di 50 potete incontrare nella ricerca?

a. Tutti i numeri minori di 50
b. AI più la metà di tali numeri
c. Al.più log 50, numeri minori di 50
d. Nessuno dei precedenti


secondo voi potrebbe essere la c??

Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #25 on: 06-03-2010, 13:41:13 »

no! è proprio la A.
perchè l'albero binario dipende dall'inserimento. Potremmo trovarci nel caso di una catena sbilanciata ed incontrarli quindi tutti prima di arrivare al 50.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #26 on: 06-03-2010, 14:18:13 »

vero! non ci avevo pensato grazie cock^^
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #27 on: 06-03-2010, 14:42:11 »

Date le funzioni n^2/(n+ logn)  , n^3/(n+logn)^2 , 2^(n+2)/2^n , (n+logn)^2 /n , determinare quae coppia di funzioni rappresenta la prima e ultima in ordine asintotico crescente

secondo me è (n+logn)^2 / n e n^2 /(n+logn)
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #28 on: 06-03-2010, 15:34:06 »

hai le 4 opzioni?
dovrebbero essere rispettivamente:
O(n^2)
O(n^3)
O(1)
O(n)
se non mi abaglio.
quindi la prima e l'ultima in ordine asintotico crescente, dovrebbero essere:
n^3/(n+logn)^2,2^(n+2)/2^n.
Se non sbaglio eh?
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #29 on: 06-03-2010, 15:59:15 »

Un grafo orientato fortemente connesso se solo se...

a)esiste un cammino da un dato vertice u a 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 a un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

la risposta giustya è la d secondo me
Logged
Pages: 1 [2] 3 4 5   Go Up
Print
Jump to: