• Non ci sono risultati.

ESERCIZIO DI ASD DEL 3 NOVEMBRE 2008

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "ESERCIZIO DI ASD DEL 3 NOVEMBRE 2008"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

ESERCIZIO DI ASD DEL 3 NOVEMBRE 2008

Modifica nella Heap

Sia A un vettore contenente una max-heap di interi di dimensione n. Sia k un numero intero ed i un indice nella heap, ovvero 1 ≤ i ≤ n. Si consideri il problema di modificare l’i-esimo elemento della heap A aggiungendogli k, ovvero A[i] viene sostituito con A[i] + k, e di ripristinare la max-heap.

a.1 Si scriva lo pseudo-codice di una procedura ricorsiva per risolvere il proble- ma proposto.

a.2 Si scriva lo pseudo-codice di una procedura non ricorsiva per risolvere il problema proposto.

a.3 Si dimostri la correttezza della procedura non ricorsiva proposta.

a.4 Si determini la complessit`a della procedura non ricorsiva proposta.

Date: 3 Novembre 2008.

1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 34.68 KB )

Documenti correlati

Esercizio 1. Si consideri la matrice reale simmetrica 3 × 3, dipendente da un parametro reale k:

Una base di autovettori ortogonale in R 3 per il prodotto scalare standard sar` a anche una base ortogonale per il prodotto scalare definito da M 2.. Il determinante del minore

Puntatori e Heap

Appena il programma viene caricato in memoria per essere eseguito la memoria apparirebbe come mostrato dalla seguente figura:. A seguito dell'esecuzione del main(), l'area Heap

Puntatori e Heap in C

Si noti che la funzione free() , de-alloca l'area puntata dal puntatore, ma non annulla il puntatore, ossia esso non viene posto a NULL, ma viene lasciato al valore

Esercizio 1. Si consideri l’applicazione lineare f k : R 3 → R 3 , k ∈ R, definita da

Università degli Studi di Trento Corso di Laurea in

(1)ESERCIZIO DI ASD DEL 3 NOVEMBRE 2008 Modifica nella Heap Versione Ricorsiva

Il ciclo while che costituisce NoRicCorreggi2(A, i) termina sem- pre perch´ e tra le guardie del ciclo abbiamo la condizione i > 1 e l’unica istruzione all’interno del ciclo

Heap e code di priorità

Le code di priorità possono essere realizzate usando degli heap: a seconda del fatto che sia usato un min- heap o un max-heap, si possono avere code a min-priorità e code

(1)Esercizio 1 Sia k ∈ N con k &gt

[r]

Heap Sort

 Focusing of the task of sorting, the heap sort ordering algorithm, is implemented through 3 functions.  heapify