Wyższa Szkoła Technologii Informatycznych w Katowicach

http://www.wsti.edu.pl    e-mail: wsti@wsti.edu.pl

Zagadnienia tematyczne i pytania z przedmiotu Algorytmy i struktury danych cz.2

1)     Co to jest algorytm?

2)     Jakie znasz sposoby zapisu algorytmów?

3)     Przedstaw za pomocą SCHEMATU BLOKOWEGO algorytm

a)      dzielenia dwóch liczb

b)     sumowania N elementów (N oraz elementy podaje użytkownik)

c)      obliczający iloczyn N elementów

d)     obliczający sumę oraz średnią arytmetyczną N elementów

e)      obliczający sumę nieznanej liczby elementów. Elementem kończącym proces jest liczba 0 (zero)

f)       obliczający sumę i średnią arytmetyczną nieznanej liczby elementów. Elementem kończącym proces jest liczba 0 (zero)

g)     obliczający pierwiastki równania kwadratowego. Udowodnij poprawność algorytmu.

h)     obliczający n! (silnię z n)

i)       obliczający potęgę: PW , gdzie Podstawa P jest rzeczywista a Wykładnik W całkowity

j)       obliczający wartości dla zadanego wyrażenia E=mv2/2 (lub innego) oraz zadanej wartości początkowej vp, końcowej vk, oraz kroku narastania vkrok

k)     wyświetlający z jednowymiarowej tablicy N elementowej elementy parzyste (lub nieparzyste)

l)       wyświetlający z jednowymiarowej tablicy N elementowej elementy o indeksach parzystych (lub nieparzystych)

m)   zliczający liczbę wystąpień w tablicy jednowymiarowej / dwuwymiarowej elementu szukanego

n)     wyszukujący w tablicy jednowymiarowej element maksymalny wraz z pozycją jego występowania (przy założeniu, że tablica jest różnowartościowa)

o)     wyszukujący w tablicy jednowymiarowej element minimalny wraz z pozycją (pozycjami) jego występowania (przy założeniu, że tablica nie jest różnowartościowa)

p)     sumujący elementy położone na obu przekątnych tablicy kwadratowej

q)     sumujący elementy pod wskazaną przekątną w tablicy kwadratowej

r)       sumujący elementy brzegowe w tablicy prostokątnej

s)      sortujący metodą bąbelkową (prostej zamiany) tablicę jednowymiarową

4)     Przedstaw za pomocą pseudokodu algorytm

a)      obliczający n! (silnię z n)

b)     obliczający potęgę: PW , gdzie Podstawa P jest rzeczywista a Wykładnik W całkowity

c)      obliczający wartości dla zadanego wyrażenia E=mv2/2 (lub innego) oraz zadanej wartości początkowej vp, końcowej vk, oraz kroku narastania vkrok

d)     zliczający liczbę wystąpień w tablicy dwuwymiarowej elementu szukanego

e)      wyszukujący w tablicy jednowymiarowej element maksymalny wraz z pozycją jego występowania (przy założeniu, że tablica jest różnowartościowa)

f)       wyszukujący w tablicy jednowymiarowej element minimalny wraz z pozycją (pozycjami) jego występowania (przy założeniu, że tablica nie jest różnowartościowa

g)     wyszukujący w tablicy uporządkowanej zadany element metodą podziałów połówkowych

h)     sortujący metodą bąbelkową (prostej zamiany) tablicę jednowymiarową

i)       sortujący zmodyfikowaną metodą bąbelkową ze wskaźnikiem tablicę jednowymiarową

j)       sortujący metodą prostego wyboru tablicę jednowymiarową

k)     sortujący metodą wstawiania tablicę jednowymiarową

5)     Jakie znasz modyfikacje sortowania bąbelkowego? Wykaż zalety i wady względem metody klasycznej.

6)     Przedstaw algorytm sortowania Shella i jego warianty.

7)     Przedstaw algorytm sortowania stogowego (drzewiastego).

8)     Przedstaw algorytm sortowania szybkiego (przez podział).

9)     Oszacuj złożoność obliczeniową algorytmu

a)      sumującego N elementów

b)     przeszukującego tablicę prostokątną o wymiarach: X, Y

c)      obliczającego wartości dla zadanego wyrażenia E=mv2/2 (lub innego) oraz zadanej wartości początkowej vp, końcowej vk, oraz kroku narastania vkrok

d)     obliczający potęgę: PW , gdzie Podstawa P jest rzeczywista a Wykładnik W całkowity

e)      sortowania bąbelkowego

f)       sortowania przez wybieranie

g)     sortowania przez wstawianie

h)     sortowania Shella

i)       sortowania szybkiego

j)       wyszukującego w tablicy uporządkowanej zadany element metodą podziałów połówkowych