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!