Egzamin ze Wst_{}epu do Informatyki, 28 sierpnia 2000

Zadanie 1 Dana jest tablica A[1..n,1..m] of integer posortowana rosn _{}aco wierszami i kolumnami oraz liczba x. Napisać program sprawdzaj _{}acy czy x wyst_{}epuje w A. Należy zwrócić uwag_{}e na efektywność programu. Preferowane s _{}a rozwi _{}azania działaj _{}ace w czasie O(n+m). Rozwi _{}azania rz_{}edu O(n*m) b_{}ed _{}a punktowane w skali 0-4pkt.

Zadanie 2 Wektor rzadki x = (x_{1},…, x_{n}) reprezentowany jest jako lista niezerowych elementów x_{i}. Element tej listy jest zadeklarowny jako:

 type
   wsk=^elem;
   elem =record
          wart: real;
          ind: integer;
          nast: wsk
         end;

wart oznacza wartość x_{ind}, a nast – dowi _{}azanie do nast_{}epnego niezerowego elementu. Lista jest uporz _{}adkowana wegług rosn _{}acej kolejności indeksów.

Napisać w pascalu funkcj_{}e: function ilskal(x,y:wsk):real, której wartości _{}a jest iloczyn skalarny wektorów rzadkich x i y.

Zadanie 3 Drzewo binarne jest zdefiniowane nast_{}epuj _{}aco:

drzewo = ^wezel;
wezel = record
        klucz: integer;
        lewy, prawy: drzewo
end;

Napisz funkcj_{}e rowne(d1,d2: drzewo):boolean, która zwraca true, jeśli drzewa d1 i d2 s _{}a jednakowe (taka sama struktura i te same wartości w odpowiednich w_{}ezłach), a false w przeciwnym przypadku.