Informatyka zaoczna eaie :: Przegląd tematu

Autor

Wiadomość

Alchemiko

Wysłany: Sob 11:51, 12 Maj 2007 Temat postu: Zadania do kolosa III

Zadania z przedmiotu „Algorytmy i struktury danych”
Zestaw 3

1. Stos zaimplementowano w postaci jednokierunkowego łańcucha odsyłaczowego.

Kod:

stos = ^ element;
element = record
w : integer;
nast : stos;
end;

Napisać funkcje:
inicjującą stos;
zwracającą true jeżeli stos jest pusty;
odkładającą element na stos;
pobierającą element ze stosu;
zwracającą liczbę elementów stosu.

2. Stos zaimplementowano przy użyciu tablicy. Napisać funkcje z poprzedniego zadania.

3. Kolejkę zaimplementowano w postaci jednokierunkowego łańcucha odsyłaczowego.

Kod:

pelement = ^ element;
element = record
         w : integer;
   nast : pelement;
end;
kolejka = record
      pierwszy,ostatni : pelement;
end;

Napisać funkcje:
inicjującą kolejkę;
zwracającą true jeżeli kolejka jest pusta;
dołączającą element do kolejki;
pobierającą element z kolejki;
zwracającą liczbę elementów kolejki;
łączącą dwie kolejki w jedną.

4. Kolejkę zaimplementowano przy użyciu tablicy. Napisać funkcje z poprzedniego zadania.

5. Dana jest kolejka. Przy użyciu standardowych operacji zdefiniować operacje:
przesuwającą ostatnio wstawiony element na początek kolejki;
usuwającą ostatnio wstawiony do kolejki element;
odwracający kolejność elementów w kolejce.

6. Dany jest stos. Przy użyciu standardowych operacji zdefiniować operacje:
przesuwającą ostatnio wstawiony element na dno stosu;
usuwającą element z dna stosu;
odwracający kolejność elementów stosie.

7. Napisać funkcję dokonującą numeryzacji klucza klucza fn(klucz:string):word metodą:
sumowania arytmetycznego;
obliczania funkcji xor.

8. Dana jest tablica rozproszona t:array[0..max-1] of element, gdzie element jest typu:

Kod:

element = record
klucz : string;
zajęty : boolean;
end

Dostępne są funkcja numeryzacji klucza fn(klucz:string):integer oraz funkcja rozpraszająca hash(kn,i:integer):integer. Napisać funkcje:
zwracającą liczbę wystąpień rekordu o zadanym kluczu;
zwracającą numer działki tablicy w której występuje rekord o zadanym kluczu;
zwracającą stopień wypełnienia tablicy.

9. Dane jest drzewo binarne.

Kod:

drzewo = ^ element;
element = record
w : integer;
lewy, prawy : drzewo;
end;

Napisać operacje:
wypisującą zawartość drzewa;
usuwającą drzewo z pamięci.

Napisać funkcje:
zwracającą liczbę węzłów w drzewie;
zwracającą liczbę liści w drzewie;
zwracającą wysokość drzewa;
liczbę będącą stosunkiem liczby liści do liczby wszystkich węzłów;

Napisać powyższe funkcje bez użycia rekurencji.

10. Dane jest drzewo binarne zaimplementowane w postaci tablicy.

Kod:

element = record
w : integer;
lewy, prawy : integer;
end;
drzewo = array[1..max] of element;

Napisać funkcje z poprzedniego zadania.