EGZAMIN

16 czerwca 2003

  1. Podstawowe struktury danych

    1. Z ilu wartości elementarnych składają się poniższe struktury:

      1. Pierwsza z 1224, druga z 3.

      2. Pierwsza z 1224, druga z 2.

      3. Pierwsza z 36, druga z 3.

      4. Pierwsza z 36, druga z 2.

Array[-1..10] of record

A: array[Boolean] of 1..100;

B: integer;

C: char;

End;

Record case Boolean of

False: (i1, i2: integer);

True: (i3: integer);

End;

    1. Poniższy algorytm oblicza ujemne potęgi liczby 2 i wypisuje je na ekranie. Zdefiniuj podany algorytm w postaci procedury lub funkcji z argumentami oraz zmień algorytm tak, żeby wypisanie ujemnych potęg liczby 2 było zrealizowane nie w procedurze (lub funkcji), a w programie głównym. Wykorzystaj do tego argumenty procedury (lub funkcji).

program abc;

const n=10;

type cyfra = 0..9;

var

i, k, r: integer;

d: array[1..n] of cyfra;

begin

for k:=1 to n do begin

write(`.');

r:=0;

for i:=1 to k-1 do begin

r:=10*r + d[i];

d[i]:=r div 2;

r:=r - 2*d[i];

write(chr(d[i]+ord(`0')))

end;

d[k]:=5;

writeln(`5');

end;

end.

    1. Pracownicy pewnej księgarni prowadzą komputerową kartotekę, w której umieszczają tytuł i nazwę wydawnictwa każdej sprzedanej książki. Dane trafiają do kartoteki w tej samej kolejności, w której książki są sprzedawane. Co dwa tygodnie właściciel księgarni oblicza ręcznie, ile sprzedano egzemplarzy każdego tytułu oraz książek każdego wydawcy. Następnie grupuje wyniki obliczeń według alfabetycznej listy wydawnictw i korzysta z nich przy zamawianiu kolejnych dostaw. Proszę o stworzenie programu wykonującego powyższe zadanie zgodnie z poniższym wzorcem..

Program prog;

Procedure wczytywanie; Begin Writeln(”Wczytywanie”); End;

Procedure sortowanie; Begin Writeln(”Sortowanie”); End;

Procedure zliczanie; Begin Writeln(”Zliczanie”); End;

Procedure drukowanie; Begin Writeln(”Drukowanie”); End;

Begin

Wczytywanie;

Sortowanie;

Zliczanie;

Drukowanie;

End.

    1. Zaznacz poprawne definicje typów.

      1. Odcinek = 0..1.0;

      2. Zakres = -0.1E20..+0.1E20;

      3. Znaki = 'a'..'9';

      4. T = 7..7;

      5. Figura = (trojkat, okrag, prosta, okrag);

    1. Poniżej dany jest algorytm przeszukiwania połówkowego. Zdefiniuj ten algorytm za pomocą procedury z argumentami dotyczącymi tablicy a i zastąp w nim pętlę repeat pętlą while. Wywołaj procedurę w programie głównym.

program progA;

const n=10;

type cyfra = 0..9;

var

i, j, k: integer;

a: array[1..n] of cyfra;

begin

i:=1; j:=n;

repeat

k:=(i+j) div 2;

if a[k] < x then i:=k

else j:=k;

until (a[k]=x) or (i>=j);

end.

    1. Zapisz poniższy algorytm w postaci programu komputerowego. S jest tekstem, lambda jest tekstem pustym, Głowa(X) jest operacją pobrania pierwszego znaku z tekstu X, Ogon(X) jest operacją usunięcia pierwszego znaku z tekstu X.

0x08 graphic

    1. Po wykonaniu poniższego programu zostaną wypisane następujące liczby:

      1. 0 i 2

      2. 1 i 2

      3. 0 i 0

      4. 1 i 0

Program p;

Var i, j: integer;

Procedure q(x: integer; var y: integer);

Begin

x:=y+1; y:=x+1;

End;

Begin

i:=0; j:=0; q(i,j);

Write(i: 2, j: 2);

End.

  1. Sortowanie

    1. Niech będą dane trzy algorytmy sortowania (Sortowanie stogowe, Sortowanie metodą Shella, Sortowanie przez proste wstawianie). Które z nich są stabilne?

      1. Tylko sortowanie metodą Shella.

      2. Tylko sortowanie metodą Shella i przez proste wstawianie.

      3. Tylko sortowanie stogowe.

      4. Wszystkie wymienione.

    1. Poniżej dany jest wektor liczb i jego zmiany w trakcie realizacji sortowania. Co to za algorytm sortowania?

      1. Przez proste wstawianie

      2. Przez proste wybieranie

      3. Przez prostą zamianę

4, 3, 5, 6, 7, 1, 2

1, 3, 5, 6, 7, 4, 2

1, 2, 5, 6, 7, 4, 3

1, 2, 3, 6, 7, 4, 5

1, 2, 3, 4, 7, 6, 5

1, 2, 3, 4, 5, 6, 7

    1. Poniżej dany jest algorytm sortowania przez wstawianie połówkowe. Algorytm ten będzie działał nadal poprawnie, jeżeli:

      1. W instrukcji while warunek l<=p zostanie zastąpiony warunkiem l<p

      2. Instrukcja p:=m-1; zostanie zastąpiona przez p:=m;

      3. Instrukcja l:=m+1; zostanie zastąpiona przez l:=m;

procedure wstawianiePolowkowe;

var

i, j, l, p, m: index; x: obiekt;

d: array[1..n] of cyfra;

begin

for i:=2 to n do

begin

x:=a[i]; l:=1; p:=i-1;

while l<=p do

begin

m:=(l+p) div 2;

if x.klucz<a[m].klucz

then p:=m-1

else l:=m+1

end;

for j:=i-1 downto l do a[j+1]:=a[j];

a[l]:=x;

end;

end.

  1. Algorytmy rekurencyjne

    1. Przy założeniu, że n jest liczbą całkowitą nieujemną, poniższy algorytm wykonuje:

      1. Sumowanie wartości zmiennych indeksowanych x[1], x[2], ..., x[n].

      2. Sumowanie wartości zmiennych indeksowanych x[1], x[2], ..., x[n-1].

      3. Sumowanie wartości zmiennych indeksowanych x[0], x[2], ..., x[n].

      4. Sumowanie wartości zmiennych indeksowanych x[0], x[2], ..., x[n-1].

function abc(x: tablica; n: integer);

begin

if n=0 then abc:=0

else abc:=x[n] + abc(n-1);

end;

    1. Sprawdź rekurencyjnie, czy słowo jest palindromem.

    2. Poniżej dany jest algorytm obliczający wartość funkcji silnia. Czy obie wersje są równoważne?

      1. tak

      2. nie

function silnia(n: integer): integer;

var i, s: integer;

begin

i:=0; s:=1;

while i>n do begin

i:=i+1; s := i * s;

end;

silnia := s;

end;

function silnia(n: integer): integer;

var i, s: integer;

begin

if n>0 then silnia := n * silnia(n-1)

else silnia := 1;

end

  1. Dynamiczne struktury informacyjne

    1. Poniżej dana jest funkcja wykonująca pewną operację na liście L. Niech head[L] będzie operacją, która zwraca początek listy, key[x] operacją, która zwraca klucz elementu listy wskazywanego przez wskaźnik x, a next[x] operacją, która zwraca wskaźnik do następnego elementu listy w stosunku do elementu wskazywanego przez wskaźnik x. Co ona wykonuje?

funkcja LIST (L, k)

argumenty wejściowe: L - lista, k - klucz;

zwraca: ?

x := head[L]

dopóki x<>NIL i key[x] <>k

x := next[x]

koniec dopóki

zwróć x

    1. Pokaż, jak odwrócić listę (w miejscu). Zmień na przykład listę (A, B, C, D) na (D, C, B, A). Zapisz algorytm w postaci procedury.

    2. Odwróć zawartość stosu używając jednej pomocniczej kolejki

    3. Napisz program, który korzystając z kolejki lub stosu dokona konwersji liczby z zapisu dziesiętnego na dwójkowy

    4. Poniżej dane są: definicja drzewa i procedura znajdująca element drzewa o danym kluczu x i wykonująca na nim określoną operację. Zamień w procedurze search instrukcję while na instrukcję repeat.

Type

wsk = ^drzewo;

drzewo = record

klucz: integer;

lewe, prawe: wsk;

end;

Function search (node: wsk, key: integer): wsk;

Var znaleziony: boolean;

Begin

Znaleziony := false;

while (node <> nil) and not znaleziony do begin

if (key = node^.klucz) then znalzeiony := true

else

if (key < node^.klucz)

node := node^.lewe;

else node := node^.prawe;

end;

write(node^.klucz);

search:=node;

end;

    1. Narysuj drzewo powstałe w wyniku działania poniższego algorytmu z wczytanego ciągu liczb (3, 7, 5, 9, 15, 8, 27, 53, 45, 13, 11). Jakie ciągi węzłów otrzymamy drukując drzewo? Podaj ciągi otrzymane w procedurze drukowania, gdyby w trakcie drukowania było wywołane przeglądanie wzdłużne, poprzeczne i wsteczne.

PROGRAM budujDrzewo;

TYPE

typElementu = integer;

wskaznik = ^wezel;

wezel= record

klucz: typElementu;

lewy, prawy: wskaznik;

end;

VAR

n: integer; korzen: wskaznik;

FUNCTION drzewo(n: integer): wskaznik;

VAR

nowyWezel: wskaznik;

x, nl, np: integer;

Begin

if n=0 then drzewo:=nil else

begin

nl:=n div 2;

np:=n-nl-1;

read(x);

new(nowyWezel);

with nowyWezel^ do

begin

klucz:=x;

lewy := drzewo(nl);

prawy := drzewo(np);

end;

drzewo := nowyWezel;

end;

End;

PROCEDURE drukujDrzewo(t: wskaznik; h: integer);

VAR

i: integer;

Begin

if t<>nil then

with t^ do

begin

drukujDrzewo(lewy, h+1);

for i:=1 to h do write (' ');

writeln(klucz);

drukujDrzewo(prawy, h+1)

end;

End;

Begin

read(n);

korzen := drzewo(n);

drukujDrzewo(korzen, 0);

End.

0x01 graphic