infn egz

Informatyka

Matematyka, rok I i II, sem. 1 4 lutego 2011 r.

Egzamin

Zad. 1. Rozważmy następujący 6-elementowy ciąg liczb naturalnych, posiadający strukturę kopca:

6, 42, 12, 55, 94, 18.

Opisać poszczególne kroki (wraz z rezultatami) algorytmu sortowania przez kopcowanie, zastosowanego do powyższego ciągu.

Zad. 2. Ile razy w poniższym algorytmie zostanie wykonana instrukcja oznaczona symbolem (*)? Odpowiedź uzasadnić, for i = 1 to 10 {

j = i;

while j <= 2*i do

{

if j > i then

print("Hurra!");    (*)

>

Zad. 3. Rozważmy następującą funkcję operującą na parametrze n, będącym dodatnią liczbą naturalną: function CoToJest(n)

{

if n < 2 then return(l) else return(2*CoToJest(n-l)+l);

>

Jaką wartość zwróci instrukcja CoToJest(7)? Odpowiedź uzasadnić. Zad. 4. W trakcie sortowania 8-elementowego ciągu liczb naturalnych: 44, 55, 12, 42, 94, 18, 6, 67, otrzymano następujący ciąg częściowo uporządkowany:

6, 12, 18, 42, 94, 55, 44, 67.

Który z prostych algorytmów sortowania (bąbelkowe, wstawianie, wybieranie) mógł zostać w tym przypadku zastosowany? Odpowiedź uzasadnić.

Zad. 5. Rozważmy alfabet A = {a, bj oraz wzorzec X — aabaa. Podać przykład tekstu Y o długości 20, w którym wzorzec X występuje jedynie na pozycjach o numerach 4, 7 i 15.