plik


��ARKUSZ ZAWIERA INFORMACJE PRAWNIE CHRONIONE DO MOMENTU ROZPOCZCIA EGZAMINU! Miejsce na naklejk MIN-R1_1P-082 EGZAMIN MATURALNY MAJ Z INFORMATYKI ROK 2008 POZIOM ROZSZERZONY CZZ I Czas pracy 90 minut Instrukcja dla zdajcego 1. Sprawdz, czy arkusz egzaminacyjny zawiera 13 stron (zadania 1  3). Ewentualny brak zgBo[ przewodniczcemu zespoBu nadzorujcego egzamin. 2. Rozwizania i odpowiedzi zamie[ w miejscu na to przeznaczonym. 3. Pisz czytelnie. U|ywaj dBugopisu/pi�ra tylko z czarnym tuszem/atramentem. Za rozwizanie 4. Nie u|ywaj korektora a bBdne zapisy wyraznie przekre[l. wszystkich zadaD 5. Pamitaj, |e zapisy w brudnopisie nie podlegaj ocenie. mo|na otrzyma 6. Na karcie odpowiedzi wpisz swoj dat urodzenia i PESEL. Bcznie Nie wpisuj |adnych znak�w w cz[ci przeznaczonej 40 punkt�w dla egzaminatora. {yczymy powodzenia! WypeBnia zdajcy przed rozpoczciem pracy KOD PESEL ZDAJCEGO ZDAJCEGO 2 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I Zadanie 1. Potgi (14 pkt) W poni|szej tabelce podane s warto[ci kolejnych potg liczby 2: k 0 1 2 3 4 5 6 7 8 9 10 2k 1 2 4 8 16 32 64 128 256 512 1024 Cig a=(a0, a1, a2,...) definiujemy nastpujco: ak = reszta z dzielenia liczby 2k przez 10 dla k = 0, 1, 2, .... a) Korzystajc z definicji, podaj 16 pierwszych wyraz�w cigu a. Wyniki umie[ w poni|szej tabelce: k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ak Uwaga: w dalszej cz[ci tego zadania mo|esz przyj, |e operacje arytmetyczne na liczbach caBkowitych (dodawanie, odejmowanie, mno|enie, dzielenie caBkowite, reszta z dzielenia) wykonywane s w czasie staBym, niezale|nie od wielko[ci argument�w. b) W wybranej przez siebie notacji (lista krok�w, schemat blokowy lub jzyk programowania) podaj algorytm, kt�ry dla danej nieujemnej liczby caBkowitej k wyznacza reszt z dzielenia liczby 2k przez 10. Np. dla k = 15 wynikiem dziaBania Twojego algorytmu powinno by 8. Przy ocenie Twojego rozwizania bdzie brana pod uwag zar�wno poprawno[ zaproponowanego algorytmu, jak i jego zBo|ono[ czasowa, czyli liczba operacji arytmetycznych wykonywanych w trakcie obliczania wyniku. Specyfikacja: Dane: Liczba caBkowita k e" 0. Wynik: Reszta z dzielenia 2k przez 10. Algorytm Egzamin maturalny z informatyki 3 Poziom rozszerzony  cz[ I 4 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I c) Podaj w wybranej przez siebie notacji (lista krok�w, schemat blokowy lub jzyk programowania) algorytm obliczania liczby an , gdy a jest liczb caBkowit, natomiast n jest potg liczby 2 ( n = 2k dla pewnej liczby caBkowitej k e" 0). Przy ocenie Twojego rozwizania bdzie brana pod uwag zBo|ono[ czasowa (w zale|no[ci jedynie od n) zaproponowanego algorytmu, czyli liczba operacji arytmetycznych wykonywanych w trakcie obliczania wyniku. n n 2 2 Wskaz�wka: zauwa|, |e an = a �" a , dla n>1. Specyfikacja: Dane: Liczby caBkowite a i n, gdzie n = 2k dla pewnej liczby caBkowitej k e" 0. Wynik: Liczba an . Algorytm Egzamin maturalny z informatyki 5 Poziom rozszerzony  cz[ I Nr zadania 1 a) 1 b) 1 c) WypeBnia Maks. liczba pkt 2 5 7 egzaminator! Uzyskana liczba pkt 6 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I Zadanie 2. SBowa (14 pkt) Niech A = {a,b} bdzie dwuliterowym alfabetem. Napisem nad alfabetem A nazywamy skoDczony cig znak�w z tego alfabetu o dBugo[ci wikszej od zera. Np. takimi napisami s: a, ab, aba, baba, aaaa DBugo[ napisu w bdziemy oznacza przez w . Zatem aba = 3. Je|eli w1 i w2 s napisami, to przez w1w2 bdziemy oznaczali napis zbudowany z napisu w1 i z nastpujcego po nim napisu w2. Np. dla w1 = ab i w2 = aa , w1w2 = abaa . Zdefiniujemy teraz napisy 2-regularne. Ka|dy napis zBo|ony tylko z jednej litery jest 2-regularny. Je|eli napis w jest 2-regularny, to napis ww jest te| 2-regularny. {adne inne napisy nie s 2-regularne. Oto procedura rekurencyjna 2REG(w), kt�ra sprawdza, czy dany napis w nad alfabetem A jest 2-regularny. Specyfikacja: Dane: napis w o dBugo[ci n (n e" 1), skBadajcy si z liter nale|cych do alfabetu A. Wynik: odpowiedz TAK, je[li napis w jest napisem 2-regularnym; odpowiedz NIE, je[li napis w nie jest napisem 2-regularnym. 2REG(w); krok 1: je[li w = 1, to wynikiem jest TAK krok 2: je[li w > 1 i w jest nieparzyste, to wynikiem jest NIE krok 3: je[li w > 1 i w jest parzyste, to: krok 3.1: podziel napis w na dwa napisy w1 i w2 o takiej samej dBugo[ci i takie, |e w = w1w2 krok 3.2: je[li w1 `" w2 , to wynikiem jest NIE krok 3.3: wynikiem jest wynik wywoBania 2REG(w1) a) Wypisz parametry wszystkich wywoBaD rekurencyjnych funkcji 2REG dla poni|szych napis�w oraz podaj wynik jej dziaBania: i. aabbaabb ii. aaaaaaaa iii. bbbbbbbbbbbbbbbbbbbb np.: dla napisu w = abab, parametry wszystkich wywoBaD rekurencyjnych funkcji 2REG i wynik jej dziaBania s nastpujce: abab�!ab�!NIE Egzamin maturalny z informatyki 7 Poziom rozszerzony  cz[ I b) Jakiej dBugo[ci s napisy 2-regularne? Odpowiedz uzasadnij. 8 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I c) Ile jest napis�w 2-regularnych o dBugo[ci n (n e" 1) nad alfabetem A? Odpowiedz uzasadnij. d) Pewnym uog�lnieniem napis�w 2-regularnych s napisy 3-regularne. Ka|dy napis jednoliterowy jest 3-regularny. Je[li napis w jest 3-regularny, to ka|dy z napis�w wxw, wwx, gdzie x jest dowolnym napisem nad alfabetem A i takim, |e dBugo[ x jest taka sama jak dBugo[ w, jest napisem 3-regularnym. {aden inny napis nie jest 3-regularny. PrzykBadowymi napisami 3-regularnymi s: a, aba, abaabaaaa. Ale aaaabaaba nie jest 3-regularny. Napisz w wybranej przez siebie notacji (lista krok�w, schemat blokowy lub jzyk programowania) algorytm zgodny ze specyfikacj, kt�ry sprawdza 3-regularno[ danego napisu. Specyfikacja: Dane: napis w, o dBugo[ci n (n e" 1), skBadajcy si z liter nale|cych do alfabetu A. Wynik: odpowiedz TAK, je[li napis w jest napisem 3-regularnym; odpowiedz NIE, je[li napis w nie jest napisem 3-regularnym. Algorytm Egzamin maturalny z informatyki 9 Poziom rozszerzony  cz[ I Nr zadania 2 a) 2 b) 2 c) 2 d) WypeBnia Maks. liczba pkt 3 2 2 7 egzaminator! Uzyskana liczba pkt 10 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I Zadanie 3. Test (12 pkt) Podpunkty a)  l) zawieraj po trzy odpowiedzi, z kt�rych ka|da jest albo prawdziwa, albo faBszywa. Zdecyduj, kt�re z podanych odpowiedzi s prawdziwe (P), a kt�re faBszywe (F). Zaznacz znakiem X odpowiedni rubryk w tabeli. a) Dla poni|szego algorytmu dane stanowi skoDczony cig liczbowy zawierajcy co najmniej jedn liczb: 1. i := 0 2. wynik := 0 3. dop�ki nie przetworzono wszystkich liczb w cigu wykonuj: i. x := kolejna liczba ii. wynik := (i*wynik+x)/(i+1) iii. i := i+1 4. wypisz wynik Uwaga:  := oznacza instrukcj przypisania. Wynikiem dziaBania tego algorytmu jest P F suma podanych liczb. [rednia arytmetyczna podanych liczb. [rednia geometryczna podanych liczb. b) Poszukujc numeru telefonu w ksi|ce telefonicznej wiele os�b korzysta z nastpujcego algorytmu: otwieramy ksi|k mniej wicej w poBowie. Je[li szukane nazwisko w kolejno[ci alfabetycznej jest wcze[niej ni| nazwisko, na kt�re trafili[my, otwieramy ksi|k w poBowie, liczc od pocztku do miejsca, w kt�rym si znajdujemy. W przeciwnym przypadku bierzemy pod uwag drug poBow ksi|ki. Postpujemy 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 postpowania jest zastosowaniem w praktyce strategii P F dziel i zwyci|aj. zachBannej. porzdkowania cigu element�w. c) Urzdzenie, kt�re pobiera dane cyfrowe z komputera i zamienia je na sygnaBy analogowe przesyBane w sieci telefonicznej to P F karta sieciowa. router. modem. Egzamin maturalny z informatyki 11 Poziom rozszerzony  cz[ I d) Zapis 1010(p) oznacza, |e 1010 jest zapisem pewnej liczby w systemie pozycyjnym o podstawie p. Zaznacz, kt�ra z poni|szych r�wno[ci jest prawdziwa: P F 1010(2) = 10(10) 12(10) = 1110(2) 67(10) = 1000011(2) e) Kod ASCII znaku zero wynosi 48, a kodem maBej litery  a jest 97. P F Kodem znaku  3 jest liczba 00110100(2). Kodem znaku  4 jest liczba 01100000(2). Kodem maBej litery  f jest liczba 01100110(2). f) Poni|szy schemat blokowy opisuje instrukcj powtarzania, w kt�rej I prawda faBsz warunek P F liczba powt�rzeD instrukcji I nie zale|y od warunku warunek. instrukcja I jest wykonywana co najmniej raz. je[li warunek nie jest speBniony, to nastpuje zakoDczenie powtarzania. g) Do szyfrowania informacji sBu|y P F algorytm RSA. algorytm Euklidesa. algorytm Hornera. h) Adresy IP skBadaj si z czterech liczb z zakresu od 0 do 255, kt�re zapisuje si oddzielone kropkami, np. 130.11.121.94. Pierwsza z liczb zapisana binarnie na o[miu bitach pozwala okre[li, do jakiej klasy nale|y adres. Adresy klasy B maj na dw�ch pierwszych bitach (liczc od lewej strony) warto[ci odpowiednio 1 i 0. Adresy klasy C maj na pierwszych trzech pozycjach warto[ci 1, 1 i 0. P F Adres 128.12.67.90 nale|y do klasy B. Adres 191.12.56.1 nale|y do klasy C. Adres 192.14.56.10 nale|y do klasy B. 12 Egzamin maturalny z informatyki Poziom rozszerzony  cz[ I i) Skr�tem nazwy protokoBu sieciowego jest P F FTP. SSH. OSI. j) Plik graficzny zawiera obrazek o rozmiarach 1024 na 768 pikseli zapisany z u|yciem 256 kolor�w. Do zapisania tego pliku (bez u|ycia kompresji) potrzebne jest P F 786432 bit�w. 786432 bajt�w. 786432 kilobajt�w. k) Nazw no[nika pamici zewntrznej jest P F pByta CD. pami flash. pami cache. l) Asymetryczne metody szyfrowania wymagaj P F u|ywania takich samych kluczy do szyfrowania i deszyfrowania wiadomo[ci. u|ywania r�|nych kluczy do szyfrowania i deszyfrowania wiadomo[ci. ujawniania klucza sBu|cego do szyfrowania. Nr zadania 3 a) 3 b) 3 c) 3 d) 3 e) 3 f) 3 g) 3 h) 3 i) 3 j) 3 k) 3 l) WypeBnia Maks. liczba pkt 1 1 1 1 1 1 1 1 1 1 1 1 egzaminator! Uzyskana liczba pkt Egzamin maturalny z informatyki 13 Poziom rozszerzony  cz[ I BRUDNOPIS

Wyszukiwarka

Podobne podstrony:
Podstawy informatyki Cz I
Teoretyczne podst inform cz VI
technik informatyk cz praktyczna z dnia 16 06 09
Teoretyczne podst inform cz V
Teoretyczne podst inform cz IV
Informacje o Amigdalinie , witaminie B17 cz 2
0 Informacje techniczne cz 1id19
3 Kurs Photoshop Techniki pracy cz 3(informacje)
Makrofotografia dla każdego, cz I Informacje wstępne
Zrodla informacji o nieruchomosciach cz 2
Informatyka arkusz rozsz cz II
Informatyka arkusz podst cz I
2 Kurs Photoshop Techniki pracy cz 2(informacje)
433 (B2007) Informacja dodatkowa cz II

więcej podobnych podstron