5

Algorytmy i struktury danych I EF-DI — egzamin poprawkowy 2009 Nazwisko i    ...................Numer albumu....^.a.?..Se.......

Zadania
1) Zdefiniować jodnym zdaniem następujące pojęcia: a)    poprzednik wierzchołka (I) b)    operand typu * i w jeżyku maszyny RAM (1) c)    drzewo binarne pełne (1) d)    kopiec (1) e)    algorytm zachłanny11)	1 I 1 d) jftuAAzro du*gdr «y>Crv*r p»« d*frc-»^ł^’ •) ajUjsr^-z*- J “t*- r^twnMi Ano iły**^-* WtCMkUm
2) Zapisać w pseudojezyku algorytm, który znajdzie indeksy liczb równych liczbie szukanej. (Wczytujemy liczbę szukana i ciąg liczb zakończony zerem, wypisujemy indeksy i ilość liczb znalezionych lub komunikat o braku szukanej liczby) (3p).
3) Mamy dany algorytm: LOAD-50 STORĘ3 dopóki: READ I LOAD 1 AOD2 STORĘ 2 LOAD 3 SUB 2 JGTZ dopóki JZERO dopóki WRITE 2 HALT Rozważyć program i odpowiedzieć krótko na pytania a) - f) (6p)	a)    jaka jest waga logarytmiczna komendy STORĘ 3 w drugiej-linijce programu b)    jaka jest wartość operandu w komendzie z etykietą dopóki c)    jaka jest waga logarytmiczna komendy SUB 2 w czasie pierwszego wykonania d)    Jaki będzie wynik działania algorytmu, gdy na taśmie wejściowej są liczby: 25 10 48 32 g y e)    ile razy wykona się komenda SUB 2 0 ile rejestrów wykorzystano w obliczeniach
4) Stosując znany algorytm sortowania przez wybieranie proszę pokazać kolejne etapy działania algorytmu: (3p)
3 1 3 18 Fl2 I 20 li 3 1 2 1 13	TT251