Zadanie 3.h (1 pkt) Test

Poniższy schemat blokowy przedstawia pewien algorytm, w którym pominięto wprowadzenie danych i wyprowadzenie wyniku.

Algorytm ten przedstawia realizację

 obliczenia NWW dla dwóch liczb naturalnych.

 obliczenia NWD dla n liczb naturalnych.

 schematu Hornera.

Zadanie 3.f (1 pkt) Test

Spośród trzech algorytmów, o podanych niżej złożonościach, najbardziej wydajny jest algorytm o złożoności

 liniowej.

 wykładniczej.

 logarytmicznej.

Zadanie 3.d (1 pkt) Test

Poniżej przedstawiono rysunek obrazujący ideę sortowania pewnej struktury:

Rysunek przedstawia ideę sortowania

 szybkiego (ang. quicksort).

 przez wstawianie (ang. insert sort).

 przez scalanie (ang. merge sort). 

Zadanie 1.8 (1 pkt)

Spośród czterech algorytmów, o podanych niżej złożonościach, najbardziej wydajny jest algorytm o złożoności

a) liniowej.
b) wykładniczej.
c) kwadratowej.
d) logarytmicznej.

Zadanie 3.g Test (1 pkt)

Do szyfrowania informacji służy

		P	F
	algorytm RSA.
	algorytm Euklidesa.
	algorytm Hornera.

Zadanie 3.f Test (1 pkt)

Poniższy schemat blokowy opisuje instrukcję powtarzania, w której

		P	F
	liczba powtórzeń instrukcji I nie zależy od warunku warunek.
	instrukcja I jest wykonywana co najmniej raz.
	jeśli warunek nie jest spełniony, to następuje zakończenie powtarzania.

Zadanie 3.b Test (1 pkt)

Poszukując numeru telefonu w książce telefonicznej wiele osób korzysta z następującego algorytmu: otwieramy książkę mniej więcej w połowie. Jeśli szukane nazwisko w kolejności alfabetycznej jest wcześniej niż nazwisko, na które trafiliśmy, otwieramy książkę w połowie, licząc od początku do miejsca, w którym się znajdujemy. W przeciwnym przypadku bierzemy pod uwagę drugą połowę książki. Postępujemy podobnie dla tej części książki, którą wybraliśmy, aż do momentu, kiedy jesteśmy blisko szukanego nazwiska. Wtedy wystarczy już przejrzeć kilka stron. Ten sposób postępowania jest zastosowaniem w praktyce strategii

		P	F
	dziel i zwyciężaj.
	zachłannej.
	porządkowania ciągu elementów.

Zadanie 3.a Test (1 pkt)

Dla poniższego algorytmu dane stanowi skończony ciąg liczbowy zawierający co najmniej jedną liczbę:

1. i := 0

2. wynik := 0

3. dopóki nie przetworzono wszystkich liczb w ciągu wykonuj:

i. x := kolejna liczba

ii. wynik := (i*wynik+x)/(i+1)

iii. i := i+1

4. wypisz wynik

Uwaga: „:=” oznacza instrukcję przypisania.

Wynikiem działania tego algorytmu jest 

		P	F
	suma podanych liczb.
	średnia arytmetyczna podanych liczb​.
	średnia geometryczna podanych liczb.

Zadanie 1.e Test (1 pkt)

Schemat Hornera znajduje zastosowanie przy

		P	F
	obliczaniu pola powierzchni figur płaskich.
	obliczaniu wartości wielomianu przy minimalnej liczbie operacji mnożenia.
	szybkim sortowaniu dużych zbiorów danych.
	znajdowaniu najmniejszego elementu w zbiorze.

Zadanie 1.a Test (2 pkt)

 Przeanalizuj poniższy algorytm (:= oznacza instrukcję przypisania)

1. m:=0

2. n:=6

3. jeśli m>n to wykonaj krok 7.

4. m:=m+1

5. pisz m

6. przejdź do kroku 3.

7. stop

		P	F
	Wykonywanie algorytmu zakończy się po wypisaniu liczb od 1 do 7.
	Po pierwszym sprawdzeniu warunku w kroku 3. nie zostaną wykonane kroki: 4., 5., 6. i wykonywanie algorytmu zakończy się.
	Wykonywanie algorytmu zakończy się po wypisaniu liczb od 0 do 6.
	Sprawdzenie warunku m > n wykonane zostanie dokładnie 8 razy.

Zadanie 3.g Test (1 pkt)

 Rozważ poniższy algorytm.

Wynikiem działania tego algorytmu dla liczby całkowitej n > 0 jest wypisanie wartości wyrażenia

		P	F
	1+ 2 + 3 + ... + n .
	1 + 1/2 + 1/3 + ... + 1/n .
	1 * 1/2 * 1/3 *...* 1/n .

Zadanie 3.b Test (1 pkt)

 Algorytm

znajduje

		P	F
	NWW (a,b).
	NWD (a,b).
	liczbę pierwszą większą od a i mniejszą od b.

Zadanie 3.c Test (1 pkt)

 Algorytmy kryptograficzne dotyczą

1.	kompresji danych.	P	F
2.	szyfrowania danych.	P	F
3.	zapewnienia bezpieczeństwa przesyłanych informacji.	P	F
4.	przekształcania obrazów.	P	F

Zadanie 3.b Test (1 pkt)

Rozważ algorytm, który dla zadanego naturalnego n > 0 oblicza następującą sumę:

suma = 1¹ + 2² + 3³ + 4⁴ + ... + nⁿ

Algorytm:
krok 1. suma:= 1, i:= 2
krok 2. dopóki i <= n, wykonuj

a. j:=1, p:=1
b. dopóki j >= 1, wykonuj:

(i) p := p*i
(ii) j := j – 1

 c. suma := suma + p, i := i+1

Oceń prawdziwość stwierdzeń:

1.	Liczba instrukcji wykonana przez ten algorytm nie zależy od wielkości n.	P	F
2.	Liczba instrukcji wykonana przez ten algorytm jest funkcją kwadratową ze względu na n.	P	F
3.	Instrukcja w kroku 2. jest instrukcją iteracji.	P	F
4.	Wartość zmiennej j w kroku 2.b. zmienia się kolejno od 1 do i, przy n > 1.	P	F

Zadanie 3.b Test (1 pkt)

 Dane są dwie liczby całkowite a, b takie, że b > a oraz schemat algorytmu:

 

 

Wynikiem działania tego algorytmu jest wypisanie

• wyłącznie liczb parzystych z przedziału domkniętego〈a, b〉 .
• wyłącznie liczb nieparzystych z przedziału domkniętego〈a, b〉.
• wszystkich liczb z przedziału domkniętego〈a, b〉.

Zadanie 3.4. (1 pkt)

W celu posortowania rosnąco ciągu liczb [2, 1, 0, 3] wykonano porównania i ewentualnie zamieniono liczby w parach otoczonych owalami. Jakie to sortowanie?

1.	przez wstawianie	P	F
2.	bąbelkowe	P	F
3.	kubełkowe	P	F
4.	szybkie	P	F

Zadanie 3.5 (0–1)

 Algorytm zwany sitem Eratostenesa opierający się na „wykreślaniu” wielokrotności kolejnych (niewykreślonych wcześniej) liczb naturalnych służy wyznaczeniu 

1.	największego wspólnego dzielnika dwóch liczb.	P	F
2.	najmniejszej wspólnej wielokrotności dwóch liczb.	P	F
3.	liczb pierwszych z zadanego przedziału.	P	F
4.	potęg dwójki z zadanego przedziału.	P	F

Zadanie 3.6. (1 pkt)

Dla tablicy A [1..n] algorytm:

dla j=1,2, ... , n-1:

  dla i=1,2, ... , n-1:

    jeśli A[i] >A[i+1] to A[i] ↔ A[i+1]

(gdzie ↔ oznacza zamianę wartości elementów)

opisuje algorytm sortowania

A. szybkiego.

B. przez wybór.

C. przez wstawianie.

D. bąbelkowego.