plik


��1 ZBo|ono[ obliczneniowa Zad. 1 Korzystajc z twierdzenia o rekurencji uniwersalnej podaj oszacowanie asymp- totyczne dla: " T (n) = 4T (n/4) + n " T (n) = 2T (n/3) + n " T (n) = 6T (n/4) + n2 " T (n) = 2T (2n) + n " T (n) = 3T (n/3) + n log(n) Zad. 2 Napisz pseudokod operacji kolejki priortetowej (INSERT, MAXIMUM, EXTACT- MAX) dla zwykBej kolejki (zaimplementowanej dla tablicy). Mo|na korzysta z procedur ENQUEUE i DEQUEUE. Oszacuj zBo|ono[ obliczeniow operacji. Zad. 3 Napisz pseudokod procedury INSERT (Q, i, key), kt�ra bdzie wstawiaBa na i-tej pozycji kolejki warto[ key. Operacja ma si odbywa bez nadpisywania |adnego z element�w (oraz bez zmieniania kolejno[ci). Oszacuj zBozono[ obli- czeniow takiej operacji. Zad. 4 Napisz pseudokod funkcji EXT RACT (Q, i), kt�ra bdzie usuwaBa element z i-tej pozycji kolejki oraz zwracaBa jego warto[. Oszacuj zBozono[ obliczeniow operacji. 2 Sortowanie Zad. 5 Algorytmy sortowania QUICKSORT i MERGESORT to algorytmy typu dziel i zwyci|aj. Kt�ry z nich ma mniejszy koszt scalania, dlaczego? Zad. 8 Wykonaj algorytm PODZIAL na poni|szej tabeli. 3 4 9 2 5 1 4 6 procedure PODZIAL (A, p, r) x �! A[r] i �! p - 1 for j �! p to r - 1 do if A[j] x then i �! i + 1 A[i] �! A[j] A[i + 1] �! A[r] return i + 1 1 Zad. 9 Zmodyfikuj algorytm BUBBLE-SORT tak aby sortowaB nierosnco. for i �! 1 to n do for j �! n downto i + 1 do if A[j] <� A[j - 1] then A[j] �! A[j - 1] 3 Kopce Zad. 11 Czy lista posortowana malejco jest kopcem typu MAX. Dlaczego? Zad. 12 Czy lista posortowana rosnco jest kopcem typu MAX. Dlaczego? Zad. 13 Czy cig element�w jest kopcem typu MAX. a) 21, 15, 19, 9, 10, 11, 12, 5, 4, 1, 6, 2, 4 b) 21, 15, 19, 12, 15, 11, 12, 5, 4, 1, 6, 2, 4 c) 21, 15, 19, 8, 15, 11, 12, 9, 4, 1, 6, 2, 4 Zad. 14 Co stanie si z pierwszym el. tabeli je[li wywoBamy HEAPIFY(A,1)? a) 7, 25, 19, 19, 20, 11, 12, 6, 14, 11, 16, 2, 4 MAX-HEAPIFY(A, i) l �! LEFT(i) r �! RIGHT(i) if (l heap-size[A]) and (A[l] > A[i]) then L �! l else L �! i if (r heap-size[A]) and (A[r] > A[L]) then L �! r if L = i then A[i] �! A[L] MAX-HEAPIFY(A, L) 2

Wyszukiwarka

Podobne podstrony:
Złożoność obliczeniowa Zadania 2
Złożoność obliczeniowa trudne zadania
złożoność obliczeniowa algorytmu Maszyny Turinga
MIARY ZLOZONOSCI OBLICZENIOWEJ
obliczenia zadania 5
obliczenia zadania 2
Algorytmy i struktury danych 02 Rekurencja i złożoność obliczeniowa
niweleta obliczenia rzednych luku pionowego teoria zadania1
reakcje zlozone zadania
Zadania obliczeniowe
obliczenia cwiczenia 1 zadania z odpowiedziami niestacjonarne
Zadanie 2 Wykresy sił przekrojowych w belce złożonej
Zadania ze zlozonosci algorytmicznych

więcej podobnych podstron