ASD e 02 2005 1

ASD e 02 2005 1



Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko............................................. Nr studenta............Nr grupy.........

Zadanie l(lOpunktów) Wyobraźmy sobie "nieskończona" strukturę danych S przechowująca liczby całkowite. Jest ona wyposażona w operację get(i), gdzie i może być dowolnie dużą liczbą naturalną; operacja S.get(i) zwraca liczbę całkowitą przechowywaną w strukturze S "pod indeksem" i, przy czym:

1)    pod każdym indeksem znajduje się dokładnie jedna liczba całkowita.

2)    przechowywane liczby są posortowane rosnąco, tzn. jeśli i < j, to S.get(i)<S.get(j),

3)    pierwsza liczba w strukturze (tzn. S.get(O)) jest ujemna.

4)    operacja S.get(i) ma koszt 0(1) dla dowolnego naturalnego i.

Opis zadania: Przy powyższych założeniach opracuj algorytm find(), możliwie najszybszy(asymptotycznie), który odnajduje najniższy indeks w strukturze S, pod którym znajduje się liczba dodatnia (tzn. minimalne i, takie że get(i)>0). Jedynym środkiem do sprawdzania zawartości pod indeksem i jest operacja S.get(i).

Polecenia:

(a)    Podaj możliwie krótki opis algorytmu find().

(b)    Napisz pseudokod algorytmu find().

(c)    Oszacuj złożoność czasową algorytmu, przy czym dokładnie opisz składniki złożoności, jeśli algorytm składa się z kilku faz. Nie zapomnij precyzyjnie określić co stanowi argument funkcji złożoności (czyli co jest parametrem, od którego zależy złożoność)

Przykład:

S: get(O) = -3, get(l ) = -1, get(2) = 0, get(3) = 3, get(4) = 10,... algorytm S.find(), powinien zwrócić liczbę 3.


Wyszukiwarka

Podobne podstrony:
ASD e 02 2005 4 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
ASD e 02 2005 2 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 6 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 3 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 4 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
ASD e 02 2005 5 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 7 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 1 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
genetyka z5 2. 3. 4. 5. 6. 7. 8.EGZAMIN GENETYKA STUDIA DZIENNE II ROK ROLNICTWO ZESTAW V W jak

więcej podobnych podstron