Niech n będzie nieujemną liczbą całkowitą, a T[1..n] – tablicą zawierającą n liczb całkowitych.
Dla n = 0 tablica T jest pusta (nie zawiera żadnego elementu).
Wykonaj analizę poniżej zapisanej funkcji d(x), która rozszerza tablicę T o liczbę całkowitą x,
a następnie przeprowadza pewną reorganizację zawartości tej tablicy.
d(x):
n ← n + 1
T[n] ← x
s ← n
dopóki ((s div 2) ≥ 1) oraz (T[s] > T[s div 2]) wykonuj
pom ← T[s]
T[s] ← T[s div 2]
T[s div 2] ← pom
s ← s div 2
Uwaga: w tym zadaniu przyjmujemy, że:
• tablica T może być powiększana;
• jeśli wartość lewego argumentu operatora oraz jest równa fałsz, to wartość prawego
argumentu nie jest wyliczana;
• div jest operatorem oznaczającym część całkowitą z dzielenia.
Zadanie 2.1. (0–2)
Uzupełnij tabelę – wpisz zawartość tablicy T po wykonaniu d(x) z podanym parametrem x:
| n | T[1..n] | x | T po wykonaniu d(x) |
| 4 | 26, 3, 5, –4 | 5 | 26, 5, 5, –4, 3 |
| 4 | 36, 15, 17, 3 | -5 |
|
| 7 | 27, 6, 13, 4, –3, –2, –3 | 30 |
|
Zadanie 2.2. (0–2)
Podaj zawartość tablicy T po wykonaniu wszystkich sześciu wywołań funkcji d kolejno z parametrami: 6, –4, 12, 27, 26, 8, przy początkowo pustej tablicy T.
................................................................................................................
Zadanie 2.3. (0–2)
Do początkowo pustej tablicy T wstawiono za pomocą funkcji d kolejno liczby całkowite od 1 do k – 1. Wstawiamy teraz do tablicy T kolejną liczbę k za pomocą d(k). Zapisz, ile razy w trakcie wykonywania d(k) sprawdzany jest warunek pętli dopóki: „((s div 2) ≥ 1) oraz (T[s] > T[s div 2])” dla podanych wartości k.
| k | Ile razy sprawdzany jest warunek pętli dopóki podczas wykonywania d(k)? |
| 4 | 3 razy |
| 16 | |
| 1025 |
Rozwiązanie
Zasady oceniania
2 pkt – za poprawną odpowiedź w obu wierszach.
1 pkt – za poprawną odpowiedź w jednym wierszu.
0 pkt – za podanie odpowiedzi niepoprawnej albo brak odpowiedzi.
Poprawna odpowiedź
| n | T[1..n] | x | T[1..n+1] |
| 4 | 26, 3, 5, –4 | 5 | 26, 5, 5, –4, 3 |
| 4 | 36, 15, 17, 3 | -5 | 36, 15, 17, 3, -5 |
| 7 | 27, 6, 13, 4, –3, –2, –3 | 30 | 30, 27, 13, 6, -3, -2, -3, 4 |
Zasady oceniania
2 pkt – za pełną poprawną odpowiedź.
1 pkt – za odpowiedź z jednym błędem (tzn. zamienione miejscami liczby z dwóch
dowolnych pozycji).
0 pkt – za podanie odpowiedzi niepoprawnej lub brak odpowiedzi.
Rozwiązanie 27, 26, 8, -4, 12, 6
Zasady oceniania
2 pkt – za pełną poprawną odpowiedź.
1 pkt – za poprawną odpowiedź w jednym wierszu.
0 pkt – za podanie odpowiedzi niepoprawnej lub brak odpowiedzi.
Poprawna odpowiedź
| k | Ile razy sprawdzany jest warunek pętli dopóki ? |
| 4 | 3 |
| 16 | 5 |
| 1025 | 11 |
Przykładowe rozwiązanie
n ← 4 + 1
T[5] ← 5
s ← 5
dopóki ((5 div 2) ≥ 1) oraz (T[5] > T[5 div 2]) wykonuj
pom ← T[5], pom ← 5
T[5] ← T[5 div 2], T[5] ← T[2], T[5] ← 3
T[5 div 2] ← 5 , T[2] ← 5
s ← 5 div 2, s ← 2
Poziom wykonania zadania
Zadanie 2.2. (0–2) - 33%
Zadanie 2.3. (0–2) - 40%