1. Wymień cechy algorytmu informatycznego. (2p)

2. Wymień formy przedstawiania algorytmu informatycznego. (1p)

3. Schemat oznacza (1p)

A. blok iteracyjny warunkowy: „dopóki”

B. blok iteracyjny warunkowy: „aż do”

4. Algorytm sortowania przez wstawienie jest: (1p)

A. efektywny dla niewielkiej liczby elementów

B. efektywny dla średniej liczby elementów

5. Mówimy, że algorytm K jest semantycznie poprawny względem warunków początkowego i końcowego ß, jeżeli: (1p)

A. dla każdych danych wejściowych spełniających warunek α obliczenia algorytmu K

dochodzą do punktu końcowego;

B. końcowe wartościowanie zmiennych spełnia warunek ß.

6. Metoda niezmienników polega na: (2p)

A. wyróżnieniu w programie pewnych szczególnych miejsc

B. przypisaniu do nich warunków na wartościowanie zmiennych algorytmu

C. udowodnieniu, że jeżeli początkowy stan obliczenia spełnia warunek początkowy α, to ilekroobliczenie algorytmu dochodzi do wyróżnionego miejsca, zawsze przyporządkowany temuwarunek jest spełniony przez aktualne wartościowanie zmiennych.

D. gdy dochodzi do punktu końcowego, to wartościowanie zmiennych spełnia warunek ko

7. Czy ocena sprawności algorytmu przy pomocy kryteriów sprzętowych jest oceną

obiektywną! (1p)

A. tak

B. nie

8. Miarą uniwersalną, która ma decydujący wpływ na czas wykonywania określonego (1p)

algorytmu jest;

A. rozmiar danych wejściowych

B. rozmiar danych wyjściowych

C. liczba operacji dominujących

9. Dla n=10 danych wejściowych szybszy jest algorytm o złożoności obliczeniowej: (1p)

A. n log n

B. n

10. Algorytm o liniowej złożoności jest najszybszy dla ilości danych wejściowych: (1p)

A. 10 < n <58

B. n > 1024

11. Przez pesymistyczną złożoność czasową algorytmu rozumie się funkcję: (1p)

gdzie: sup - kres górny zbioru

- zbiór wszystkich możliwych zestawów danych wejściowych rozm - liczba operacji dominujących dla zestawu danych wejściowych d

12. Im większe wartości ∆(n) i δ(n), tym algorytm jest (1p)

A. bardziej wrażliwy na dane wejściowe

B. tym bardziej jego zachowanie w wypadku rzeczywistych danych może odbiegaopisanego funkcjami W(n) i A(n).

13. Metody sortowania stabilnego to: (1p)

A. Sortowanie bąbelkowe (ang. Bubblesort)

B. Sortowanie przez wybieranie (ang. selection sort)

C. Sortowanie przez wstawianie (ang. insertion sort)

D. Sortowanie szybkie (ang. quicksort)

14. Na czym polega metoda dziel i zwyciężaj? (2p)

15. Najczęściej stosowane strategie wyboru elementu osiowego w algorytmA. wybranie pierwszego elementu tablicy;

B. wybranie dowolnego elementu

C. wybranie elementu znajdującego się pośrodku tablicy

16. Stos jest: (1p)

A. specjalnym przypadkiem listy jednokierunkowej, a jego cechą charakterystyczną jest to, że dane są

zapisywane i pobierane metodą LIFO

B. specjalnym przypadkiem listy jednokierunkowej, a jego cechą charakterystyczną jest to, że dane są

zapisywane i pobierane metodą FIFO

C. strukturą liniowo uporządkowanych danych, z których jedynie ostatni element, zwany

wierzchołkiem, jest w danym momencie dostępny.

17. Dlaczego algorytm Quicksort nazywa się algorytmem sortowania szybkiego? (2p)

A. pesymistyczna wrażliwość czasowa jest równa O(n

)

B. asymptotyczna oczekiwana złożoność czasowa wynosi n log n

Z tych poniżej 9 zadań proszę o rozwiązania 1 zadania.

Zadanie 1

Mamy tablicę n liczb - długości patyków. Napisz algorytm sprawdzający czy z każdej trójki patyków można zbudować trójkąt. Policz złożoność obliczeniową algorytmu.

Zadanie 2

Zaprojektuj algorytm, który dla dowolnej liczby naturalnej wyznaczy jej rozkład na czynniki pierwsze. Policz złożoność obliczeniową algorytmu.

Zadanie 3

Zaprojektuj algorytm, który dla dowolnej liczby naturalnej n pozwoli wczytać n liczb, a następnie wypisze je w odwróconej kolejności. Policz złożoność obliczeniową algorytmu.

Zadanie 4

Zaprojektuj algorytm rozwiązania układu trzech równań liniowych metodą eliminacji Gausa. Policz złożoność obliczeniową algorytmu.

Zadanie 5

Zaprojektuj algorytm, który oblicza sumę parzystych i iloczyn nieparzystych elementów ciągu arytmetycznego: 10,11 ...35. Policz złożoność obliczeniową algorytmu.

Zadanie 6

Zaprojektuj algorytm wyznaczania wyznacznika macierzy stopnia 5. Policz złożoność obliczeniową algorytmu.

Zadanie 7

Zaprojektuj algorytm wyznaczania wartości własnych dowolnej macierzy kwadratowej. Policz złożoność obliczeniową algorytmu.

Zadanie 8

Zaprojektuj algorytm wyznaczania k-tego elementu z n elementowej tablicy. Policz złożoność obliczeniową algorytmu.

Zadanie 9.

Mamy tablice liczb naturalnych. Napisz algorytm sprawdzający czy w tej tablicy są dwie komórki o tej samej wartości. Policz złożoność obliczeniową algorytmu.

Z tych poniżej 10 zadań proszę o rozwiązania 1 zadania.

Zadanie 1

Zaprojektuj algorytm, który pobiera kolejne liczby tak długo, aż suma ich wartości przekroczy 100.

Zadanie 2

Zaprojektuj algorytm, który dla dowolnej liczby naturalnej wyznaczy jej rozkład na czynniki pierwsze.

Zadanie 3

Zaprojektuj algorytm, który dla dowolnej liczby naturalnej n pozwoli wczytać n liczb, a następnie wypisze je w odwróconej kolejności.

Zadanie 4

Zaprojektuj algorytm rozwiązania układu trzech równań liniowych metodą eliminacji Gausa.

Zadanie 5

Zaprojektuj algorytm, który oblicza sumę parzystych i iloczyn nieparzystych elementów ciągu arytmetycznego: 10,11 ...35.

Zadanie 6

Zaprojektuj algorytm znajdowania pierwiastków równania kwadratowego.

Zadanie 7

Zaprojektuj algorytm rozwiązywania nierówności kwadratowej.

Zadanie 8

Zaprojektuj algorytm wyznaczania wyznacznika macierzy stopnia 5.

Zadanie 9

Zaprojektuj algorytm wyznaczania wartości własnych dowolnej macierzy kwadratowej.

Zadanie 10

Zaprojektuj algorytm badania przebiegu zmienności trójmianu kwadratowego.

DZIĘKUJĘ.