Zadania na egzamin praktyczny z ASD
(wersja końcowa)
Cześć A: Zadania sprawdzające umiejętność stosowania metod
konstrukcji algorytmów
Podczas tego etapu egzaminu student będzie losował jedno z poniższych zadań
programistycznych. Po jego rozwiÄ…zaniu student odpowie na trzy pytania dotyczÄ…ce
przedstawionego rozwiązania. Odpowiedzi na te pytania będą podstawą do wystawianie
oceny od dst do bdb.
1. Problem plecakowy decyzyjny algorytmem brutalnej siły przeglądającym wszystkie podzbiory
przedmiotów z plecaka.
2. Problem produkcji lodów wszystkich smaków metodą przeszukiwania z nawrotami.
3. Problem plecakowy decyzyjny metodÄ… przeszukiwania z nawrotami.
4. Problem odgadywania liczby metodą dziel i zwyciężaj.
5. Problem obliczania wartości dwumianu Newtona metodą programowania dynamicznego.
6. Problem plecakowy decyzyjny algorytmem zachłannym (dowolna heurystyka).
7. Problem kosmonautów algorytmem zachłannym (dowolna heurystyka).
8. Problem plecakowy decyzyjny metodÄ… Monte Carlo.
9. Binarne wyszukiwanie elementu w tablicy posortowanej liczb całkowitych (wersja iteracyjna).
10. Binarne wyszukiwanie elementu w tablicy posortowanej liczb całkowitych (wersja rekurencyjna).
11. Sortowanie tablicy metodÄ… bÄ…belkowÄ….
12. Sortowanie tablicy metodÄ… przez wstawianie.
13. Sortowanie tablicy metodą przez wybór.
14. Sortowanie tablicy metodÄ… quicksort.
15. Sortowanie tablicy metodÄ… scalania.
Cześć B: Zadania sprawdzające znajomość implementacji konkretnych
struktur danych
Podczas tego etapu egzaminu będą dostępne niepełne implementacje konkretnych struktur i
trzeba je będzie uzupełnić (np. dopisać metodę wstawiania, usuwania lub wyszukiwania
danych w strukturze).
1. Implementacja tablicy dynamicznej (dst  tablica liczb całkowitych, db  tablica wartości
opakowanych np. klasami Integer, Double, Float lub obiektów typu String, bdb  tablica
złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię nazwisko,
wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł, wydawnictwo, rok
wydania] itp.)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów z relokacjÄ… lub bez,
dorobić usuwanie elementów, dorobić liniowe wyszukiwanie elementów.
2. Implementacja uporządkowanej tablicy dynamicznej (dst  tablica liczb całkowitych, db
 tablica wartości opakowanych np. klasami Integer, Double, Float lub obiektów typu
String, bdb  tablica złożonych obiektów zdefiniowanych przez użytkownika, np. tablica
osób [imię nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów z relokacjÄ… lub bez,
dorobić usuwanie elementów, dorobić binarne wyszukiwanie elementów.
3. Implementacja listy powiązanej liczb całkowitych (dst  lista powiązana jednostronna,
db  lista powiÄ…zana dwustronna, bdb  lista powiÄ…zana dwukierunkowa)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów, dorobić usuwanie
elementów, dorobić wyszukiwani elementów, dorobić iterator listy.
4. Implementacja listy powiązanej uporządkowanej liczb całkowitych (dst  lista
powiÄ…zana jednostronna, db  lista powiÄ…zana dwustronna, bdb  lista powiÄ…zana
dwukierunkowa)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów, dorobić usuwanie
elementów, dorobić wyszukiwani elementów, dorobić iterator listy.
5. Implementacja drzewa BST liczb całkowitych (dst  jedna funkcjonalność, db  dwie
funkcjonalności, bdb  trzy funkcjonalności)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów, dorobić usuwanie
elementów (osobno trzy przypadki), dorobić wyszukiwanie elementów, dorobić
wizualizację tekstową drzewa, dorobić iterator drzewa.
6. Implementacja tablicy mieszającej metodą łańcuchową (dst  jedna funkcjonalność, db
 dwie funkcjonalności, bdb  trzy funkcjonalności)
·ð PrzykÅ‚adowe polecenia: dorobić wstawianie elementów, dorobić usuwanie
elementów, dorobić wyszukiwanie elementów.
Cześć C: Zadania sprawdzające umiejętność implementowania
abstrakcyjnych struktur danych przy wykorzystaniu własnych
implementacji struktur konkretnych
·ð Przy implementacji można bÄ™dzie stosować metody: przez modyfikacjÄ™, przez osadzanie
oraz przez dziedziczenie, w zależności od upodobań studenta.
·ð Podczas tego etapu egzaminu bÄ™dÄ… dostÄ™pne klasy implementujÄ…ce konkretne struktury
danych omawiane na wykładzie i laboratoriach.
1. Implementacja stosu za pomocą tablicy dynamicznej (dst  stos liczb całkowitych, db 
stos wartości opakowanych np. klasami Integer, Double, Float lub obiektów typu String,
bdb  stos złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
a. Wykonać następujący eksperyment ze strukturą w której bierze udział 5 różnych
elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę, wstawiamy
do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E; usuwamy
wszystkie elementy wypisujÄ…c je na ekran.
2. Implementacja kolejki za pomocą tablicy dynamicznej (dst  kolejka liczb całkowitych,
db  kolejka wartości opakowanych np. klasami Integer, Double, Float lub obiektów typu
String, bdb  kolejka złożonych obiektów zdefiniowanych przez użytkownika, np. tablica
osób [imię nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
a. Wykonać następujący eksperyment ze strukturą w której bierze udział 5 różnych
elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę, wstawiamy
do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E; usuwamy
wszystkie elementy wypisujÄ…c je na ekran.
3. Implementacja listy z bezpośrednim dostępem do każdego elementu poprzez podanie
jego numeru za pomocą tablicy dynamicznej (dst  lista liczb całkowitych, db  lista
wartości opakowanych np. klasami Integer, Double, Float lub obiektów typu String, bdb
 lista złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
a. Wykonać następujący eksperyment ze strukturą w której bierze udział 6 różnych
elementów A, B, C, D, E, F (). Przebieg eksperymentu: tworzymy strukturę,
wstawiamy do listy A, B, C, D; wypisujemy elementy listy; usuwamy element
drugi i trzeci; wypisujemy elementy listy; wstawiamy E i F; wypisujemy elementy
listy.
4. Implementacja zbioru za pomocą tablicy dynamicznej (dst  zbiór liczb całkowitych, db 
zbiór wartości opakowanych np. klasami Integer, Double, Float lub obiektów typu String,
bdb  zbiór złożonych obiektów zdefiniowanych przez użytkownika, np. zbiór osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
a. Wykonać następujący eksperyment ze strukturą w której bierze udział 5 różnych
elementów a, b, c, d, e. Przebieg eksperymentu: tworzymy zbiory A i B, wstawiamy
do A elementy a, b, c, d oraz do B elementy c, d, e; wyliczamy i wypisujemy zbiory:
iloczyn A i B, suma A i B, różnica A\B; usuwamy ze zbioru A element c i ze zbioru B
element e; powtórnie wyliczamy i wypisujemy zbiory: iloczyn A i B, suma A i B,
różnica A\B.
5. Implementacja grafu skierowanego.
Cześć D: Zadania sprawdzające umiejętność implementowania
abstrakcyjnych struktur danych przy wykorzystaniu standardowych
konkretnych struktur danych
Przy implementacji można będzie stosować metody: przez osadzanie lub przez dziedziczenie,
w zależności od upodobań studenta.
1. Implementacja stosu za pomocą klasy ArrayList (dst  stos liczb całkowitych, db 
stos wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb 
stos złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę,
wstawiamy do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E;
usuwamy wszystkie elementy wypisujÄ…c je na ekran.
2. Implementacja stosu za pomocą klasy LinkedList (dst  stos liczb całkowitych, db 
stos wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb 
stos złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę,
wstawiamy do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E;
usuwamy wszystkie elementy wypisujÄ…c je na ekran.
2. Implementacja kolejki za pomocą klasy ArrayList (dst  kolejka liczb całkowitych, db
 kolejka wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb
 kolejka złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę,
wstawiamy do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E;
usuwamy wszystkie elementy wypisujÄ…c je na ekran.
3. Implementacja kolejki za pomocą klasy LinkedList (dst  kolejka liczb całkowitych,
db  kolejka wartości opakowanych np. klasami Double, Float lub obiektów typu String,
bdb  kolejka złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób
[imię nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy strukturę,
wstawiamy do struktury A, B, C; usuwamy dwa elementy; wstawiamy D i E;
usuwamy wszystkie elementy wypisujÄ…c je na ekran.
4. Implementacja listy z bezpośrednim dostępem do każdego elementu poprzez podanie
jego numeru za pomocą klasy ArrayList (dst  lista liczb całkowitych, db  lista
wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb  lista
złożonych obiektów zdefiniowanych przez użytkownika, np. tablica osób [imię nazwisko,
wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł, wydawnictwo, rok
wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 6
różnych elementów A, B, C, D, E, F (). Przebieg eksperymentu: tworzymy
strukturÄ™, wstawiamy do listy A, B, C, D; wypisujemy elementy listy; usuwamy
element drugi i trzeci; wypisujemy elementy listy; wstawiamy E i F;
wypisujemy elementy listy.
5. Implementacja listy dwustronnej za pomocÄ… klasy LinkedList (dst  lista liczb
całkowitych, db  lista wartości opakowanych np. klasami Double, Float lub obiektów
typu String, bdb  lista złożonych obiektów zdefiniowanych przez użytkownika, np.
tablica osób [imię nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne],
książek [tytuł, wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów A, B, C, D, E. Przebieg eksperymentu: tworzymy listę L,
wstawiamy do listy L elementy A, B i C od lewej strony; wypisujemy elementy
listy; wstawiamy do listy L elementy D i E od prawej strony; wypisujemy
elementy listy; usuwamy element z lewej strony i element z prawej strony;
wypisujemy elementy listy; sprawdzamy, czy na liście jest element B i
wypisujemy wynik testu; sprawdzamy, czy na liście jest element E i
wypisujemy wynik testu.
6. Implementacja zbioru za pomocą klasy ArrayList (dst  zbiór liczb całkowitych, db 
zbiór wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb 
zbiór złożonych obiektów zdefiniowanych przez użytkownika, np. zbiór osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów a, b, c, d, e. Przebieg eksperymentu: tworzymy zbiory A i
B, wstawiamy do A elementy a, b, c, d oraz do B elementy c, d, e; wyliczamy i
wypisujemy zbiory: iloczyn A i B, suma A i B, różnica A\B; usuwamy ze zbioru A
element c i ze zbioru B element e; powtórnie wyliczamy i wypisujemy zbiory:
iloczyn A i B, suma A i B, różnica A\B.
7. Implementacja zbioru za pomocą klasy TreeSet (dst  zbiór liczb całkowitych, db 
zbiór wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb 
zbiór złożonych obiektów zdefiniowanych przez użytkownika, np. zbiór osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów a, b, c, d, e. Przebieg eksperymentu: tworzymy zbiory A i
B, wstawiamy do A elementy a, b, c, d oraz do B elementy c, d, e; wyliczamy i
wypisujemy zbiory: iloczyn A i B, suma A i B, różnica A\B; usuwamy ze zbioru A
element c i ze zbioru B element e; powtórnie wyliczamy i wypisujemy zbiory:
iloczyn A i B, suma A i B, różnica A\B.
8. Implementacja zbioru za pomocą klasy HashSet (dst  zbiór liczb całkowitych, db 
zbiór wartości opakowanych np. klasami Double, Float lub obiektów typu String, bdb 
zbiór złożonych obiektów zdefiniowanych przez użytkownika, np. zbiór osób [imię
nazwisko, wiek], punktów ma płaszczyz
nie [dwie współrzędne], książek [tytuł,
wydawnictwo, rok wydania] itp.).
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 5
różnych elementów a, b, c, d, e. Przebieg eksperymentu: tworzymy zbiory A i
B, wstawiamy do A elementy a, b, c, d oraz do B elementy c, d, e; wyliczamy i
wypisujemy zbiory: iloczyn A i B, suma A i B, różnica A\B; usuwamy ze zbioru A
element c i ze zbioru B element e; powtórnie wyliczamy i wypisujemy zbiory:
iloczyn A i B, suma A i B, różnica A\B.
9. Implementacja słownika (mapy) za pomocą klasy HashMap (dst  słownik par: klucz
całkowity + wartość typu String, db  słownik par: klucz typu String + wartość opakowana
(np. klasami Integer, Double, Float), bdb  słownik par: klucz typu String + wartość
będąca złożonym obiektem zdefiniowanym przez użytkownika (np. osoba [imię nazwisko,
wiek], punkt ma płaszczyz
nie [dwie współrzędne], książka [tytuł, wydawnictwo, rok
wydania] itp.
·ð Wykonać nastÄ™pujÄ…cy eksperyment ze strukturÄ… w której bierze udziaÅ‚ 3 różne
pary:, (ka,a), (kb,b), (kc,c). Przebieg eksperymentu: tworzymy słownik S,
wstawiamy do S pary (ka,a) i (kb,b); sprawdzamy, czy jest para dla klucza ka i
wypisujemy wynik sprawdzenia; sprawdzamy, czy jest para dla klucza kc i
wypisujemy wynik sprawdzenia; sprawdzamy, czy jest para z wartością b i
wypisujemy wynik sprawdzenia; sprawdzamy, czy jest para z wartością c i
wypisujemy wynik sprawdzenia; wstawiamy do S parÄ™ (kc,c); sprawdzamy,
czy jest para dla klucza kc i wypisujemy wynik sprawdzenia; sprawdzamy, czy
jest para z wartością c i wypisujemy wynik sprawdzenia; usuwamy parę dla
klucza ka; sprawdzamy, czy jest para dla klucza ka i wypisujemy wynik
sprawdzenia;