Pages: [1] 2   Go Down
Print
Author Topic: domanda su HEAP  (Read 1742 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« on: 18-02-2012, 14:34:32 »

siano A e B due max-heap di interi e sia x un intero più grande sia degli elementi di A che di quelli di B. Allora

a. l'albero binario di radice x, sottoalbero di sinistra A e sottoalbero di destra B è una max-heap.
b. l'array ottenuta concatenando le tre array xAB è una max-heap
c. Le array xA e xB sono entrambe max heap
d. Nessuna delle precedenti affermazioni è necessariamente vera


secondo voi qual è la risposta?
« Last Edit: 18-02-2012, 14:38:27 by manuelP84 » Logged
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #1 on: 18-02-2012, 14:39:15 »

facendo delle prove a me risultano vere sia la A che la C


Logged
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #2 on: 18-02-2012, 15:20:16 »

la C dovrebbe essere a trabocchetto... quella corretta è la A a mio avviso
Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #3 on: 18-02-2012, 15:38:54 »

Invece secondo me la corretta è solo la c), la a) non può esserlo perche se x esempio abbiamo B come una heap di 8 elementi e A come una heap di 3 elementi, quello che si ottiene dal punto a) non è un albero binario completo da sx a dx, quindi non è una heap. La c) invece dovrebbe sempre verificare la regola della max-heap dato che stiamo moltiplicando degli interi positivi..
Logged
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #4 on: 18-02-2012, 15:45:59 »

la c dice: le array [x]A e [x]B sono entrambe delle max heap
« Last Edit: 18-02-2012, 15:47:40 by manuelP84 » Logged
manuelP84
Apprendista Forumista
**
Offline Offline

Posts: 172


« Reply #5 on: 18-02-2012, 15:48:48 »

a questo punto non sto capendo se la c dice che x moltiplica l'array A e B oppure sono concatenazioni...  testate
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #6 on: 18-02-2012, 15:50:17 »

Credo sia prodotto, sennò diceva come nel punto a) di inserire x come radice
Logged
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #7 on: 18-02-2012, 15:53:50 »

mi sa ke quella corretta allora è la D.. non avevo pensato a quello che ha detto Zlatan.. poi la c non può essere per me in quanto non è sicuro che mantenga la proprietà della maxheap, cioè A >= max(A[2i],A[2i+1])
Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #8 on: 18-02-2012, 15:54:58 »

a questo punto non sto capendo se la c dice che x moltiplica l'array A e B oppure sono concatenazioni...  testate
io la capisco come concatenazione.. anche perchè nella risposta B indica concatenazione l'array xAB.. quindi anche per la C la intendo come concatenazioni.. poi casomai basta specificare di quale caso si tratti e si può dar la risposta..
« Last Edit: 18-02-2012, 15:58:11 by thomas89 » Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #9 on: 18-02-2012, 15:58:51 »

poi la c non può essere per me in quanto non è sicuro che mantenga la proprietà della maxheap, cioè A >= max(A[2i],A[2i+1])

perchè non dovrebbe essere rispettata? parliamo di numeri interi positivi.. se a>b sicuro xa>xb con x positivo..
Logged
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #10 on: 18-02-2012, 16:04:04 »

devi guardare le array singolarmente e provare se aggiungendo un nuovo massimo, la x in questo caso, all'array A per esempio, la proprietà di maxheap sia ancora soddisfatta..
Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #11 on: 18-02-2012, 16:05:42 »

Inoltre non ti dice nulla sugli elementi, ossia se il numero di elementi di A e B è lo stesso... Quindi, secondo me nessuna delle precedenti.. Poi se si fa un ipotesi che il numero di elementi in A e B è lo stesso, allora per me dovrebbe essere la A.
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #12 on: 18-02-2012, 16:10:24 »

Se la c è intesa come concatenazione allora la risposta è la d.. però a primo impatto io avrei pensato al prodotto, si dovrebbe chiedere al prof per torgliersi il dubbio..
Logged
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #13 on: 18-02-2012, 16:22:36 »

ho fatto delle prove.. la risp giusta dovrebbe essere la D, in quanto anche la risp C è sbagliata (nel caso che nella risposta C xA sia intesa come concatenazione... la prova che ho fatto:

A[24,4,10,2,3,7,2]

new A[30,24,4,10,2,3,7,2]
Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
france_88
Apprendista Forumista
**
Offline Offline

Posts: 119



« Reply #14 on: 18-02-2012, 17:53:58 »

secondo me è la c , perchè nella b specifica che xAB è una concatenazione di array , mentre nella c non lo specifica quindi è un prodotto tra uno scalare e un array
« Last Edit: 18-02-2012, 17:56:59 by france_88 » Logged
Pages: [1] 2   Go Up
Print
Jump to: