ZSI I. 21.12.2002
                             Egzamin z WP
                                   

Zad 1 (13 pkt.)
Dana  jest  staàa  caàkowita N (N > 0) i typ  TTab  =  array[1..N]  of
integer.  Tablic©  A typu TTab nazwiemy dwuspadow•, jeòli  istniej•  w
niej takie indeksy 1<= i<=j<=N, æe:
    -  A[1]  >  A[2] >  > A[i] < A[i+1] <  < A[j-1] < A[j] > A[j+1]  >
 > A[N] oraz
    - A[1] < A[N]
Napisz funkcj©:
    function IleMniejszych(A: TTab): integer;
obliczaj•c•  liczb©  element¢w tablicy A o wartoòciach  mniejszych  od
A[1].

Zad 2 (13 pkt.)
Dana jest staàa N (N>0) i typ:
    TCiag = record
            start: integer;
            elty: array[1..N] of boolean;
           end;
Zmienne  typu TCiag reprezentuj• N-elementowe ci•gi liczbowe,  kt¢rych
pierwszym elementem jest start, zaò i-ty element ci•gu (1<i<=N) jest o
jeden  wi©kszy (gdy elty[i])  lub mniejszy (gdy not elty[i]) od (i-1)-
szego.

Napisz procedur©:
    procedure Wypisz(c1, c2: TCiag);
kt¢ra  wypisze  na standardowe wyjòcie wszystkie liczby wyst©puj•ce  w
obu ci•gach c1 i c2.
(Zakàadamy, æe wszystkie elementy ci•g¢w c1 i c2 s• reprezentowalne  w
typie integer).

Zad 3 (7 pkt.)
Dana jest gramatyka G = ({a, b, c}, {A, B}, P, A), przy czym:
    P= {     A -> aAc | bAc | cAa | cAb | B | í
            B -> AA }

a. Podaj wyprowadzenia nast©puj•cych sà¢w lub uzasadnij, æe nie da si©
  ich wyprowadziÜ:
   a) abbacccc
   b) acbc
   c) acaccb
   d) acbcc
b. Scharakteryzuj j©zyk generowany przez t© gramatyk©.
c. Co si© zmieni, jeòli jako symbol pocz•tkowy we´miemy B zamiast A?

Zad 4 (7 pkt.)
a. Zapisz binarnie liczb© 21 binarnie.
b.  Liczb© -103 przedstaw w reprezentacji uzupeànieniowej do 2 przy 8-
miu bitach.
c.  Uàamek  1/7  przedstaw  w zapisie zmiennopozycyjnym,  z  4  bitami
mantysy  (zapisanej w systemie znak-moduà) i 3 bitami cechy (zapisanej
uzupeànieniowo  do dwu). Czyli caàa liczba ma 7 bit¢w.  Zakàadamy,  æe
najpierw  jest  cecha, potem mantysa. Mantysa jest  znormalizowana.  W
czasie konwersji stosujemy zaokr•glanie.

Kaæde  zadanie  na  osobnej,  podpisanej  kartce.  Rozwi•zania  naleæy
uzasadniÜ, w przypadku program¢w naleæy dodatkowo oszacowaÜ  zàoæonoòÜ
rozwi•zania.

Powodzenia!