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 ÎÅš
Wyszukiwarka
Podobne podstrony:
algorytmy pytania na egzamin pytania wyklad4algorytmy pytania na egzamin pytania wyklad7algorytmy pytania na egzamin pytania wyklad1algorytmy pytania na egzamin pytania wyklad1algorytmy pytania na egzamin pytania wyklad6wykłady pytania na egzaminachPKC pytania na egzaminPrzykładowe pytania na egzaminiePytania na egzaminPytania na egzamin — NotatnikPytania ogólne na egzamin magisterski UPH Siedlce ZARZĄDZANIEPytania specjalności zarządzanie finansami na egzamin magisterski UPH Siedlce ZARZĄDZANIEkzu pytania na egzamin opracowaniepytania na egzamin cz 1więcej podobnych podstron