Sprawdzian pisany w dwóch grupach, z których każda miała inne zadania i dzieliła się na kolejne dwie grupy ( w zależności od nich wykonywało się podpunkt I lub II ).
Posortuj następujący ciąg liczb: 23, 27, 12, 53, 17, 8, 31:
niemalejąco, stosując sortowanie przez proste wybieranie
nierosnąco, stosując sortowanie przez proste wstawianie
Wyjaśnij (słownie) zasadę działania oraz określ i uzasadnij złożoność algorytmu:
sortowanie przez zliczanie
sortowanie pozycyjne
Zapisz stosując pseudokod optymalny algorytm:
stabilnego scalania posortowanych nierosnąco podciągów x1,x2…
podziału ciągu względem elementu osiowego i wyznaczenia pozycji elementu osiowego
Oszacuj złożoność algorytmu z powyższego zadania i uzasadnij otrzymany wynik
Zapisz stosując język C, optymalny i kompletny algorytm:
dodawania elementu jako elementu k-tego, do listy jednokierunkowej
usuwania elementu k-tego z listy (k - liczba określająca, którym z kolei elementem listy ma być element)
Podaj zawartość stosu po wykonaniu następujących instrukcji:
dla obu grup zbiór instrukcji pop() oraz push(x)
Wyjaśnij (słownie) zasadę działania oraz określ złożoność algorytmu:
sortowania przez wybieranie
sortowania przez wstawianie
Zapisz stosując pseudokod optymalny algorytm:
wyznaczania 1 statystyki w nieposortowanym ciągu danych liczbowych
wyznaczania i-tej statystyki w nieposortowanym ciągu danych liczbowych
Oszacuj złożoność algorytmu z powyższego zadania i uzasadnij otrzymany wynik
Zapisz stosując język C, optymalny i kompletny algorytm:
realizacji funkcji pop oraz push na stosie (realizacja na listach)
realizacji funkcji enqueue oraz dequeue w jednokierunkowej kolejce FIFO (realizacja na listach)
UWAGA: W zadaniu 3 oraz 5, należało opatrzyć całość komentarzami, w celu łatwiejszego zrozumienia przez prowadzącą.