PYTANIA NA EZGAMIN
Poprawność algorytmów

1.Mówimy, że algorytm jest semantycznie poprawny względem warunków wejściowych A i wyjściowych B wtedy i tylko wtedy gdy :

a) kończy działanie w określonym czasie
b) daje poprawne wyniki
c) obie odpowiedzi a i b sÄ… poprawne
d) żadna odpowiedź nie jest poprawna

2.Określ złożoność asymptotyczną podanego algorytmu :
Suma(A,n)
1 for i = 1 to n
2 do sum = sum + A[i]
3 return sum

a) O(n2)
b) O(n log n)
c) O(n)
d) O(1)

3.Określ złożoność asymptotyczną podanego algorytmu :
Sumy (A,n)
1 for i = 1 to n
2 do sum = A[1]
3 for j = 2 to i
4 do sum = sum + A[j]
5 wypisz(sum)

a) O(n)
b) O(1)
c) O(n2)
d) O(n log n)

4.Określ złożoność asymptotyczną podanego algorytmu :
Sumy3(A,n)
1 for i = 4 to n
2 do sum = A[i-3]
3 for j = i – 2 to i
4 do sum = sum + A[j]
5 wypisz(sum)

a) O(n)
b) O(1)
c) O(n2)
d) O(log n)

5.Określ złożoność asymptotyczną podanego algorytmu :
Szukaj(A,n,k)
1 sortuj(A)
2 a = 1, b = n
3 while a < n
4 do c = (a+b)/2
5 if k < A[c]
6 b = c
7 else if A[c] < k
8 a = c + 1
9 else return c

a) O(n)
b) O(1)
c) O(n2)
d) O(log n)

6.Określić złożoność obliczeniową następującej pętli :
for(wynik = 0, i = 1; i <= n; i*=2)
for(j = 1; j <= n; j++)
wynik++;

a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)

7.Najlepszym możliwym oszacowaniem dla funkcji (50 n log n) jest:

a) O(n)
b) O(log n)
c) O(n log n)
d) O(n3)

8.Która z podanych złożoności czasowych jest najszybsza:

a) O(1)
b) O(n2)
c) O(log n)
d) O(n)

9.Która z podanych złożoności czasowych jest najwolniejsza:

a) O(n log n)
b) O(n2)
c) O(n)
d) O(n!)

10. Która z wymienionych równości jest zawsze prawdziwa, jeżeli wiadomo, że g(n)=O(f) i h(n)=O(f)

a) g(n) + h(n) = O(f)
b) g(n) * h(n) = O(f)
c) f(n) + g(n) = O(f)
d) g(n) = h(n)

11. Warunek, który nie jest konieczny dla poprawności działania algorytmu:

a) Warunek dyskretności
b) Warunek efektywności
c) Warunek jednoznaczności
d) Warunek uniwersalności

12. Który z podanych ciągów, złożoności czasowej jest ustawiony rosnąco ?

a) O(n), O(n log n), O(log n), O(1)
b) O(1), O(n), O(n log n), O(n2)
c) O(log n), O(n), O(n log n), O(n2)
d) O(1), O(n), O(log n), O(n2)

13. Który z podanych ciągów, złożoności czasowej jest ustawiony malejąco ?

a) O(1), O(n), O(n log n), O(n!)
b) O(n2), O(log n), O(n log n), O(1)
c) O(n!),O(n100), O(log n), O(1)
d) O(n100), O(n!), O(log n), O(1)

14. Przyrost wykładniczy reprezentuje :

a) Szereg harmoniczny
b) Szereg artmetyczny
c) Szereg geometryczny
d) Każdy z podanych

15. Przyrost kwadratowy reprezentuje :

a) Szereg artmetyczny
b) Szereg geometryczny
c) Szereg harmoniczny
d) Każdy z podanych

16. Najmniejszą do osiągnięcia złożonością czasową jest :

a) O(n log n)
b) O(nn)
c) O(n)
d) O(1)

17. Największą do osiągnięcia złożonością czasową jest :

a) O(n log n)
b) O(nn)
c) O(n)
d) O(n!)

18. Warunek "Algorytm musi dać się zastosować do rozwiązywania całej klasy zagadnień, a nie jednego konkretnego zadania" to :

a) Warunek dyskretności
b) Warunek efektywności
c) Warunek jednoznaczności
d) Warunek uniwersalności

19. Do notacji asymptotycznej nie należy :

a) Notacja O
b) Notacja ÎÅš
c) Notacja Ω
d) Notacja ÎÅš

20. Wskaż parę notacji asymptotycznych dolnych :

a) Notacja O, Notacja Ω
b) Notacja o, Notacja ÎÅš
c) Notacja ÎÅš, Notacja ω
d) Notacja Ω, Notacja ω

21. Wskaż parę notacji asymptotycznych górnych :

a) Notacja O, Notacja Ω
b) Notacja o, Notacja ÎÅš
c) Notacja ÎÅš, Notacja ω
d) Notacja o, Notacja O

22. Notacją asymptotyczną dokładną jest :

a) Notacja O
b) Notacja ÎÅš
c) Notacja o
d) Notacja Ω

23. Co nie ma wpływu na złożoność pamięciową :

a) Liczba zmiennych
b) Ilość miejsca potrzebna dla danych
c) Liczba instrukcji
d) Rozmiar danych

24. Co nie ma wpływu na złożoność czasową :

a) Liczba instrukcji
b) Liczba zmiennych
c) Liczba operacji artmetycznych
d) Liczba wywołań procedury

25. Najlepszy czas wykonania algorytmu QuickSort (sortowanie szybkie) to:

a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)


26. Åšredni czas wykonania algorytmu QuickSort (sortowanie szybkie) to:

a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)

27. Pesymistyczny czas wykonania algorytmu QuickSort to :

a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)

28. Niezmiennik nie jest :

a) prawdziwy na początku albo na końcu algorytmu
b) na końcu algorytmu poprawny
c) wykorzystywany jest do wykazywania poprawności algorytmów
d) prawdziwy przed pierwszÄ… iteracjÄ…

29. Z której notacji korzysta się przy analizie najgorszego przypadku:

a) Notacja O
b) Notacja ω
c) Notacja Ω
d) Notacja ÎÅš

30. Która notacja opisuje najlepsze możliwe zachowanie się algorytmu :

a) Notacja O
b) Notacja o
c) Notacja Ω
d) Notacja ÎÅš