Kolokwium algorytmy I struktury danych



Pobieranie 141,28 Kb.
Data04.11.2017
Rozmiar141,28 Kb.

WERSJA A1

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............

1. Które z wymienionych ciągów funkcji są, a które nie są uporządkowane niemalejąco ze względu na rząd wielkości:

(a) 3n, lg(n2), 3n+ lg(n!), TAK / NIE
(b) lg(n4), 0.01*n2 , 100n+ 2 3lg n TAK / NIE

(c) sqrt(n) , lg n , 20 n TAK / NIE

2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją n2, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 10 (na pewnym komputerze) wynosi 1 sek.


  1. Ile czasu zajmie wykonanie zadania 2 razy większego? Odp............................................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać przy pomocy
    tego algorytmu (na tym samym komputerze) w ciągu 100sek ? Odp. ....................................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 50 na komputerze
    5 razy szybszym? Odp........................................



3. Równoczesne wyszukiwanie mini­mum i maksimum w ciągu n elementowym można zrealizować ustawiając elementy ciągu w pary, a następnie wybierając element najmniejszy z mniejszych elementów par i element największy - z większych elementów par.


  1. Jaki jest koszt tego algorytmu, jeśli ciąg ma 6 elementów? Odp.:...............................

  2. Jaki jest koszt w przypadku, gdy ciąg ma n elementów i n jest liczbą parzystą? Odp.:...................

  3. Czy koszt tego algorytmu jest liniowy? TAK / NIE



4. Załóżmy, że x-stronicowa książka telefoniczna zawiera uporządkowaną leksykogra­ficznie listę nazwisk abonentów oraz, że otworzenie książki na stronie o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek.


  1. Ile, co najwyżej, czasu potrzeba do wyszukania strony z dowolnym nazwiskiem,
    jeśli x=1024, a do poszukiwań zastosowano metodę binarnych poszukiwań? Odp.: .....................................

  2. Ile co najwyżej osób figuruje w tej książce telefonicznej, jeśli wyszukanie metodą binarnych poszukiwań strony z dowolnym nazwiskiem zajmuje co najwyżej 6 sek., a na jednej stronie znajduje się dokładnie 25 nazwisk?
    Odp.: ..............................................

  3. Ile czasu zajęłoby wyszukiwanie nazwiska z ostatniej strony, jeśli x= 100,
    a do wyszukiwania zastosowaliśmy algorytm „skoki co 10” ? Odp.: ...........................

5. Niech P będzie problemem wyszukiwania elementu k-tego co do wielkości w danym n-elementowym zbiorze.



  1. Koszt średni algorytmu Hoare rozwiązywania problemu P wynosi O(lg n). TAK / NIE

  2. Algorytm naiwny rozwiązywania tego problemu ma złożoność O(k+n). TAK / NIE

  3. Jeśli k=2, to problem można rozwiązać wykonując n+lg n –2 porównań. TAK / NIE



6. Niech A będzie algorytmem Quick Sort (jako medianę wybieramy zawsze pierwszy element sortowanego aktualnie ciągu) zastosowanym do ciągu n elementowego.


    1. Podaj zawartość tablicy [5,3,6,4,7,1,8,2] po pierwszym wykonaniu rozdzilania
      algorytmem SPLIT (stosowanym w algorytmie A) . Odp. ..............................................

    2. W najgorszym razie A wykona O(n2) porównań. TAK / NIE

    3. Koszt algorytmu A jest w najgorszym razie taki jak koszt algorytmu Merge Sort. TAK / NIE

7.


(a) Wypisz stany tablicy pomocniczej po wykonaniu kolejnych pętli podczas sortowania tablicy (1,1,2,0,3,2,0,1) algorytmem Counting Sort (sortowania przez zliczanie)
Odp. :..................................................................................................

(b) Operacją dominującą w algorytmie Radix Sort jest porównywanie elementów. TAK / NIE

(c) Podać przykłady algorytmów działających zgodnie z zasadą "dziel i zwyciężaj".
Odp.: ..................................................................

8. Niech A będzie algorytmem sortowania ciągu metodą przez wybór (Selection Sort) w porządku niemalejącym.


  1. Ile przestawień elementów wykona algorytm A zastosowany do ciągu (1,4,8,3,2)?
    (Jedno przestawienie polega na zamianie miejscami dwóch elementów) Odp.:.....................................



  2. Ile porównań wykona algorytm A dla ciągu (1,4,8,3,2)? Odp.:...............................

  3. Złożoność algorytmu A jest liniowa względem rozmiaru danych . TAK / NIE

9. Niech n będzie liczbą naturalną, a x, a(0),..., a(n) ciągiem liczb rzeczywistych. Dla każdej z wymienionych zależności, dotyczących poniższego algorytmu, ustal, czy jest, czy nie jest prawdziwa.

begin

s := a(n) ; i := n;



while i>0 do

s := s*x + a(i-1);

i := i -1;

od

end



  1. Niezmiennikiem pętli „while” jest formuła ( i > 0). TAK / NIE

  2. Po wykonaniu algorytmu s = nj=0 a(j) x j . TAK / NIE

  3. Koszt czasowy tego algorytmu można z góry oszacować przez O(n2). TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Następująca formuła jest prawdziwa w każdej strukturze kolejek out(in(q,e)) = q . TAK / NIE

(b) Koszt operacji usuwania elementu z kolejki, zrealizowanej jako lista dynamiczna, jest stały


TAK / NIE

(c) Formuła push(e, pop(s)) = s jest prawdziwa dla dowolnego niepustego stosu. TAK / NIE


11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = (n) prawda / fałsz

22n = (2n) prawda / fałsz

n!= O(2n) prawda / fałsz

Podpis studenta ........................................................................................

WERSJA B1

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............

1. Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany niemalejąco, ze względu na rząd występujących w nim funkcji (nN):
n+ lg n , 2lg(2n) , 22lgn TAK / NIE
n1/2, lg n, n3 + lgn, n3 TAK / NIE
n !, 2n, 3n TAK / NIE


2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją n3, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 3 (na pewnym komputerze) wynosi 81 sek.





  1. Ile czasu zajmie wykonanie zadania 3 razy większego? Odp. ............................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 375sek ? Odp. ..............................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 9 na komputerze
    27 razy szybszym? Odp.........................................

3. Do równoczesnego znalezienia minimum i maksimum w pewnym n elementowym ciągu zastosowano metodę „dziel i zwyciężaj”



  1. Jaki jest dokładny koszt tego algorytmu, jeżeli ciąg ma 8 elementów. Odp.:...................

  1. Jaki jest koszt tego algorytmu w przypadku gdy n jest potęgą dwójki? Odp.:...........................



  2. Czy koszt tego algorytmu jest wielomianowy? TAK / NIE



4. W pewnym pliku znajduje się k rekordow uporządkowanych leksykograficznie. Przyjmijmy, że identyfikacja jednego rekordu zajmuje 1sek.


  1. Ile co najwyżej czasu potrzeba do odnalezienia poszukiwanego rekordu, jeśli k=4096 i przeglądamy plik sekwencyjnie ?
    Odp.: ...............

  2. Ile co najwyżej potrzeba czasu , jeśli zastosujemy algorytm poszukiwań binarnych i k=4096?. Odp.:....... .....

  3. Jeśli k=1024 i zużyliśmy 12 sek. do znalezienia właściwego rekordu, to jaki algorytm
    był zastosowany: sekwencyjny czy binarnych poszukiwań ? Odp.: ....................................

5. Niech A będzie algorytmem Hoare wyszukiwania elementu k-tego co do wielkości w n-elementowym ciągu.



  1. Algorytm Hoare A jest algorytmem rekurencyjnym. TAK / NIE

  2. Koszt pamięciowy algorytmu A nie zależy od k . TAK / NIE

  3. W najgorszym razie złożoność algorytmu A jest taka sama jak algorytmu naiwnego. TAK / NIE



6. Jeśli zastosujemy algorytm Merge Sort do ciągu n elementowego, to


          1. wykona on (n2) porównań w przypadku, gdy ciąg jest odwrotnie uporządkowany. TAK / NIE

          2. koszt czasowy Merge Sort nie zależy od wartości elementów. TAK / NIE


          3. Ile wynosi złożoność czasowa tego algorytmu Odp. ..............................................

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem Counting Sort
(sortowania przez zliczanie) tablicy (0,0,1,3,2,1,2,1).
Odp. :......................................................................................

(b) Jakiej struktury pomocniczej stosu czy kolejki trzeba użyć, aby algorytm


Radix Sort działał poprawnie. Odp.:..........................................

(c) Czy można posortować ciąg liczb z zadanego przedziału nie wykonując porównań elementów? TAK / NIE




8. Niech A będzie algorytmem sortowania danego n elementowego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona algorytm A zastosowany do ciągu (2,5,9,4,3)?
(Jedno przestawienie polega na zamianie miejscami dwóch elementów) Odp.:.....................................................

(b) Ile porównań wykona algorytm Insertion Sort zatosowany do tego samego ciągu ? Odp.:...............................

(c) W najgorszym razie algorytm A wykona O(n lg n) porównań. TAK / NIE

9. Rozważmy następujący algorytm w strukturze liczb rzeczywistych i niech n będzie liczbą naturalną.

begin

i := 0; s := a(0);



while i

if s >a(i) then s := a(i) fi;

i := i+1

od;


end

  1. Niezmiennikiem pętli „while” jest formuła (i ≤ n) TAK / NIE

  2. Po wykonaniu pętli „while” s jest najmniejszym elementem ciągu a(0),...,a(n). TAK / NIE

  3. Koszt tego algorytmu jest logarytmiczny względem rozmiaru danych. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Następująca formuła jest prawdziwa w każdej strukturze stosów

empty(s) pop(push(e,s))= s TAK / NIE

(b) Koszt operacji push , wstawiania elementu do stosu zrealizowanego jako lista dynamiczna,
jest proporcjonalny do wysokości stosu . TAK / NIE

(c) Program „while not empty(q) do q:= out(q); if not empty(q) then q := out(q) fi od”


nie zapętla się tylko dla kolejek q o parzystej liczbie elementów. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = (n) prawda / fałsz

32n = O(2n) prawda / fałsz

n = (lg n) prawda / fałsz

Podpis studenta ........................................................................................

WERSJA C1

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............

1. Które z wymienionych ciągów funkcji są, a które nie są uporządkowane niemalejąco ze względu na rząd wielkości:

(a) 3n, lg(n2), 3n+ lg(n!), TAK / NIE
(b) lg(n4), 0.01*n2 , 100n+ 2 3lg n TAK / NIE

(c) sqrt(n) , lg n , 20 n TAK / NIE

2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją n2, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 10 (na pewnym komputerze) wynosi 1 sek.


  1. Ile czasu zajmie wykonanie zadania 2 razy większego? Odp............................................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać przy pomocy
    tego algorytmu (na tym samym komputerze) w ciągu 100sek ? Odp. ....................................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 50 na komputerze
    5 razy szybszym? Odp........................................



3. Równoczesne wyszukiwanie mini­mum i maksimum w ciągu n elementowym można zrealizować ustawiając elementy ciągu w pary, a następnie wybierając element najmniejszy z mniejszych elementów par i element największy - z większych elementów par.


  1. Jaki jest koszt tego algorytmu, jeśli ciąg ma 6 elementów? Odp.:...............................

  2. Jaki jest koszt w przypadku, gdy ciąg ma n elementów i n jest liczbą parzystą? Odp.:...................

  3. Czy koszt tego algorytmu jest liniowy? TAK / NIE



4. Załóżmy, że x-stronicowa książka telefoniczna zawiera uporządkowaną leksykogra­ficznie listę nazwisk abonentów oraz, że otworzenie książki na stronie o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek.


  1. Ile, co najwyżej, czasu potrzeba do wyszukania strony z dowolnym nazwiskiem,
    jeśli x=1024, a do poszukiwań zastosowano metodę binarnych poszukiwań? Odp.: .....................................

  2. Ile co najwyżej osób figuruje w tej książce telefonicznej, jeśli wyszukanie metodą binarnych poszukiwań strony z dowolnym nazwiskiem zajmuje co najwyżej 6 sek., a na jednej stronie znajduje się dokładnie 25 nazwisk?
    Odp.: ..............................................

  3. Ile czasu zajęłoby wyszukiwanie nazwiska z ostatniej strony, jeśli x= 100,
    a do wyszukiwania zastosowaliśmy algorytm „skoki co 10” ? Odp.: ...........................

5. Niech P będzie problemem wyszukiwania elementu k-tego co do wielkości w danym n-elementowym zbiorze.



  1. Koszt średni algorytmu Hoare rozwiązywania problemu P wynosi O(lg n). TAK / NIE

  2. Algorytm naiwny rozwiązywania tego problemu ma złożoność O(k+n). TAK / NIE

  3. Jeśli k=2, to problem można rozwiązać wykonując n+lg n –2 porównań. TAK / NIE



6. Niech A będzie algorytmem Quick Sort (jako medianę wybieramy zawsze pierwszy element sortowanego aktualnie ciągu) zastosowanym do ciągu n elementowego.


    1. Podaj zawartość tablicy [5,3,6,4,7,1,8,2] po pierwszym wykonaniu rozdzilania
      algorytmem SPLIT (stosowanym w algorytmie A) . Odp. ..............................................

    2. W najgorszym razie A wykona O(n2) porównań. TAK / NIE

    3. Koszt algorytmu A jest w najgorszym razie taki jak koszt algorytmu Merge Sort. TAK / NIE

7.


(a) Wypisz stany tablicy pomocniczej po wykonaniu kolejnych pętli podczas sortowania tablicy (1,1,2,0,3,2,0,1) algorytmem Counting Sort (sortowania przez zliczanie)
Odp. :..................................................................................................

(b) Operacją dominującą w algorytmie Radix Sort jest porównywanie elementów. TAK / NIE

(c) Podać przykłady algorytmów działających zgodnie z zasadą "dziel i zwyciężaj".
Odp.: ..................................................................

8. Niech A będzie algorytmem sortowania ciągu metodą przez wybór (Selection Sort) w porządku niemalejącym.


  1. Ile przestawień elementów wykona algorytm A zastosowany do ciągu (1,4,8,3,2)?
    (Jedno przestawienie polega na zamianie miejscami dwóch elementów) Odp.:.....................................



  2. Ile porównań wykona algorytm A dla ciągu (1,4,8,3,2)? Odp.:...............................

  3. Złożoność algorytmu A jest liniowa względem rozmiaru danych . TAK / NIE

9. Niech n będzie liczbą naturalną, a x, a(0),..., a(n) ciągiem liczb rzeczywistych. Dla każdej z wymienionych zależności, dotyczących poniższego algorytmu, ustal, czy jest, czy nie jest prawdziwa.

begin

s := a(n) ; i := n;



while i>0 do

s := s*x + a(i-1);

i := i -1;

od

end



  1. Niezmiennikiem pętli „while” jest formuła ( i > 0). TAK / NIE

  2. Po wykonaniu algorytmu s = nj=0 a(j) x j . TAK / NIE

  3. Koszt czasowy tego algorytmu można z góry oszacować przez O(n2). TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Następująca formuła jest prawdziwa w każdej strukturze kolejek out(in(q,e)) = q . TAK / NIE

(b) Koszt operacji usuwania elementu z kolejki, zrealizowanej jako lista dynamiczna, jest stały


TAK / NIE

(c) Formuła push(e, pop(s)) = s jest prawdziwa dla dowolnego niepustego stosu. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = (n) prawda / fałsz

22n = (2n) prawda / fałsz

n!= O(2n) prawda / fałsz


Podpis studenta ........................................................................................

WERSJA D1

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............



1. Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany niemalejąco, ze względu na rząd występujących w nim funkcji (nN):
n+ lg n , 2lg(2n) , 22lgn TAK / NIE
n1/2, lg n, n3 + lgn, n3 TAK / NIE
n !, 2n, 3n TAK / NIE


2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją n3, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 3 (na pewnym komputerze) wynosi 81 sek.





  1. Ile czasu zajmie wykonanie zadania 3 razy większego? Odp. ............................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 375sek ? Odp. ..............................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 9 na komputerze
    27 razy szybszym? Odp.........................................

3. Do równoczesnego znalezienia minimum i maksimum w pewnym n elementowym ciągu zastosowano metodę „dziel i zwyciężaj”



  1. Jaki jest dokładny koszt tego algorytmu, jeżeli ciąg ma 8 elementów. Odp.:...................

  1. Jaki jest koszt tego algorytmu w przypadku gdy n jest potęgą dwójki? Odp.:...........................



  2. Czy koszt tego algorytmu jest wielomianowy? TAK / NIE



4. W pewnym pliku znajduje się k rekordow uporządkowanych leksykograficznie. Przyjmijmy, że identyfikacja jednego rekordu zajmuje 1sek.


  1. Ile co najwyżej czasu potrzeba do odnalezienia poszukiwanego rekordu, jeśli k=4096 i przeglądamy plik sekwencyjnie ?
    Odp.: ...............

  2. Ile co najwyżej potrzeba czasu , jeśli zastosujemy algorytm poszukiwań binarnych i k=4096?. Odp.:....... .....

  3. Jeśli k=1024 i zużyliśmy 12 sek. do znalezienia właściwego rekordu, to jaki algorytm
    był zastosowany: sekwencyjny czy binarnych poszukiwań ? Odp.: ....................................

5. Niech A będzie algorytmem Hoare wyszukiwania elementu k-tego co do wielkości w n-elementowym ciągu.



  1. Algorytm Hoare A jest algorytmem rekurencyjnym. TAK / NIE

  2. Koszt pamięciowy algorytmu A nie zależy od k . TAK / NIE

  3. W najgorszym razie złożoność algorytmu A jest taka sama jak algorytmu naiwnego. TAK / NIE



6. Jeśli zastosujemy algorytm Merge Sort do ciągu n elementowego, to


          1. wykona on (n2) porównań w przypadku, gdy ciąg jest odwrotnie uporządkowany. TAK / NIE

          2. koszt czasowy Merge Sort nie zależy od wartości elementów. TAK / NIE

          3. Ile wynosi złożoność czasowa tego algorytmu Odp. ..............................................

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem Counting Sort
(sortowania przez zliczanie) tablicy (0,0,1,3,2,1,2,1).
Odp. :......................................................................................

(b) Jakiej struktury pomocniczej stosu czy kolejki trzeba użyć, aby algorytm


Radix Sort działał poprawnie. Odp.:..........................................

(c) Czy można posortować ciąg liczb z zadanego przedziału nie wykonując porównań elementów? TAK / NIE




8. Niech A będzie algorytmem sortowania danego n elementowego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona algorytm A zastosowany do ciągu (2,5,9,4,3)?
(Jedno przestawienie polega na zamianie miejscami dwóch elementów) Odp.:.....................................................

(b) Ile porównań wykona algorytm Insertion Sort zatosowany do tego samego ciągu ? Odp.:...............................

(c) W najgorszym razie algorytm A wykona O(n lg n) porównań. TAK / NIE

9. Rozważmy następujący algorytm w strukturze liczb rzeczywistych i niech n będzie liczbą naturalną.

begin

i := 0; s := a(0);



while i

if s >a(i) then s := a(i) fi;

i := i+1

od;


end

  1. Niezmiennikiem pętli „while” jest formuła (i ≤ n) TAK / NIE

  2. Po wykonaniu pętli „while” s jest najmniejszym elementem ciągu a(0),...,a(n). TAK / NIE

  3. Koszt tego algorytmu jest logarytmiczny względem rozmiaru danych. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Następująca formuła jest prawdziwa w każdej strukturze stosów

empty(s) pop(push(e,s))= s TAK / NIE

(b) Koszt operacji push , wstawiania elementu do stosu zrealizowanego jako lista dynamiczna,
jest proporcjonalny do wysokości stosu . TAK / NIE

(c) Program „while not empty(q) do q:= out(q); if not empty(q) then q := out(q) fi od”


nie zapętla się tylko dla kolejek q o parzystej liczbie elementów. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = (n) prawda / fałsz

32n = O(2n) prawda / fałsz

n = (lg n) prawda / fałsz

Podpis studenta ........................................................................................

WERSJA A2

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............

1. Które z wymienionych ciągów funkcji są, a które nie są uporządkowane niemalejąco ze względu na rząd wielkości:

n1/2+ lg(n), lg(n2), 2 lg n, TAK / NIE

n1/2 , lg (n!), n2 , TAK / NIE

(2 lg n), 300n2 + n, n2 + n3 TAK / NIE

2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją lg n, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 32 (na pewnym komputerze) wynosi 25 sek.



  1. Ile czasu zajmie wykonanie zadania 2 razy większego? Odp..........................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 20sek? Odp.................................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 44 na komputerze 5 razy szybszym?
    Odp..........................

3. Niech A będzie optymalnym algorytmem wyszukiwania elementu największego w danym n elementowym ciągu.


  1. Ile co najmniej operacji porównywania elementów trzeba wykonać, jeśli ciąg ma 10 elementów? Odp. .........

  2. Jaki jest koszt tego algorytmu w przypadku gdy n = 2k? Odp. ......................

  3. Czy istnieje algorytm o koszcie logarytmicznym rozwiązujący ten problem? TAK / NIE

4. W uporządkowanych alfabetycznie słowniku zawierającym x haseł, chcemy wyszukać stronę z hasłem "sprawdzian". Na każdej stronie słownika znajdują się 32 hasła. Otworzenie książki na stronie o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek.



  1. Ile co najwyżej stron musimy obejrzeć zanim znajdziemy stronę z naszym hasłem, jeśli x=2048, a do wyszukiwania zastosowaliśmy algorytm binarnych poszukiwań?
    Odp.: ...........................................................

  2. Jeśli wyszukanie strony z dowolnym hasłem metodą binarnych poszukiwań
    zajmuje nie więcej niż 5 sek., to ile haseł jest w tym słowniku? Odp.: ........................................

  3. Ile co najwyżej czasu zajęłoby wyszukiwanie nazwiska z ostatniej strony, jeśli słownik ma 299stron, a do wyszukiwania właściwej strony zastosowaliśmy algorytm „skoki co 5” ? Odp.: ............

5. Niech A będzie algorytmem 'turniej' wyszukiwania elementu drugiego co do wielkości.



  1. Czy koszt czasowy algorytmu A zależy od kolejności elementów w ciągu? TAK / NIE

  2. Czy element największy zawsze znajduje się w korzeniu drzewa turniejowego? TAK / NIE

  3. Czy element drugi co do wielkości musi się znajdować na przedostatnim poziomie w drzewie turnieju? TAK / NIE

6. Niech SPLIT będzie algorytmem rozdzielania ciągu względem pierwszego elementu stosowanym w algorytmie sortowania Quick Sort.



  1. Podaj zawartość tablicy [6,1,8,2,9,3,4, 7] po jednokrotnym wykonaniu SPLIT?.
    Odp. ................ .................

  2. W algorytmie Quick Sort wywołujemy SPLIT średnio O(lg n) razy. TAK / NIE

  3. Koszt algorytmu SPLIT jest proporcjonalny do długości ciągu . TAK / NIE

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem Counting Sort (sortowania przez zliczanie) tablicy (2,1,3,2,2,1,3,1).
Odp. :.................................................................................................................

(b) Czy algorytm Radix Sort jest stabilny? TAK / NIE

(c). Który algorytm Merge Sort, czy Quick Sort ma gorszą złożoność w przypadku pesymistycznym?
Odp.: .................................................................................................................

8. Niech A będzie algorytmem sortowania danego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona ten algorytm podczas sortowania ciągu (6,7,8,9,10,1).
Jedno przestawienie polega na zamianie miejscami dwóch elementów? Odp.:......................................................

(b) Ile porównań wykona algorytm Insertion Sort zastosowany do tego samego ciągu . Odp.:............................

(c) Koszt algorytmu A, mierzony liczbą porównań elementów, jest liniowy. TAK / NIE

9. Niech n będzie liczbą naturalną, a x oraz e(0),..., e(n) dowolnymi liczbami rzeczywistymi. Przy każdej z wymienionych zależności dotyczących następującego algorytmu, zaznacz, czy jest czy nie jest prawdziwa.


begin
s := e(0); pom := x; i := 1

while ( i < n+1 ) do

s := s + e(i)* pom;

pom := pom *x;

i := i + 1;

od ;


end;

(a) Formuła (i < n+1) jest niezmiennikiem pętli w tym algorytmie. TAK / NIE


(b) Ten algorytm wykonuje O(n) mnożeń. . TAK / NIE
(c) Po wykonaniu algorytmu, e(n) jest największym elementem ciągu. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Formuła first(in(q,e)) = e jest prawdziwa w każdej strukturze kolejek. TAK / NIE

(b) Koszt operacji pop usuwania elementu ze stosu, zrealizowanego jako lista dynamiczna,


jest stały. TAK / NIE

(c) Formuła pop(push(e,s))=s jest prawdziwa w każdym stosie. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = O(lg n!) prawda / fałsz

32n = (3n) prawda / fałsz

n = (lg n) prawda / fałsz

Podpis studenta ........................................................................................

WERSJA B2

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!

Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............



1. Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany niemalejąco, ze względu na rząd występujących w nim funkcji (nN):
lg(n2) , |sin n | + n , 22lgn TAK / NIE
1000n + n1/2, lg n, 0.001*n3 +6 TAK / NIE
n2lgn, lgn!, lg3n TAK / NIE


2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją 2n, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 10 (na pewnym komputerze) wynosi 1024 sek.



  1. Ile czasu zajmie wykonanie zadania 2 razy mniejszego? Odp..............



  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 512 sek ? Odp..............



  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 7 na komputerze 2 razy szybszym? Odp.........

3. Niech A będzie optymalnym algorytmem wyszukiwania elementu największego i najmniejszego w danym n elementowym ciągu liczb rzeczywistych.



  1. Jaki jest koszt tego algorytmu zastosowanego do ciągu 10-elementowego? Odp.:..................



  2. Jaka jest złożoność tego algorytmu w przypadku gdy n= 2k? Odp. ..............................

  3. Czy istnieje algorytm o koszcie logarytmicznym rozwiązujący ten sam problem? TAK / NIE

4. Aby odnaleźć stronę z szukaną osobę w uporządkowanym spisie ludności pewnej miejscowości X trzeba sprawdzić co najwyżej 15 stron, stosując metodę „skoków co k”. Znalezienie strony o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek, a na stronie jest 25 nazwisk.





  1. Jeśli k=10, to ile co najwyżej mieszkańców ma miejscowość X. Odp.: ..................

  2. Ile co najwyżej stron trzeba obejrzeć aby wyszukać dowolną osobę, jeśli liczba mieszkańców
    wynosi 800, a do przeglądania zastosowaliśmy algorytm binary search. Odp.: ................................

  3. Ile czasu, w najgorszym przypadku, zajęłoby wyszukanie właściwej osoby, jeśli zastosujemy
    algorytm sekwencyjnego przeglądania stron, a w spisie figuruje 5000 nazwisk? Odp.: ..............

5. Niech A będzie algorytmem 'turniej' wyszukiwania elementu drugiego co do wielkości .



  1. W najgorszym razie algorytm wykona n2 porównań dla ciągu n elementowego. TAK / NIE

  2. Dla ciągu 32 elementowego algorytm A wykona 35 porównań TAK / NIE

(c) Wysokość drzewa turniejowego dla ciągu o 16 elementach wynosi 4. TAK / NIE

6. Niech A będzie algorytmem scalania ciągów uporządkowanych a i b.



  1. Ile co najwyżej razy wykonywany jest algorytm A w trakcie sortowania
    ciągu n elementowego metodą Merge Sort? Odp.: ........................

  2. A nie wykona on ani jednego porównania, jeśli elementy ciągu a są mniejsze niż elementy ciągu b.

TAK / NIE

  1. Koszt wykonania algorytmu A wynosi O(n+m), gdzie n i m są odpowiednio długościami ciągów a i b.

TAK / NIE

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem
Counting Sort (sortowania przez zlicznie) tablicy (2,3,3,2,1,2,1,1). Odp. :..............................................................

(b) Ile porównań elementów trzebay wykonać, gdyby do sortowania tego ciągu


użyto algorytmu sortowania pozycyjnego Radix_sort . Odp.:...............................

(c) W jakich algorytmach wykorzystuje się operację scalania dwóch ciągów uporządkowanych?

Odp. : ......................................................................

8. Niech A będzie algorytmem sortowania danego n elementowego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona ten algorytm podczas sortowania ciągu (2,5,3,4,10).
Jedno przestawienie polega na zamianie miejscami dwóch elementów? Odp.:.....................................................

(b) Jaki jest średni koszt czasowy tego algorytmu? Odp.:..............................

(c) W najgorszym razie algorytm A wykona O(n2) porównań. TAK / NIE

9. Rozważyć następujący algorytm w strukturze liczb rzeczywistych i ocenić każdą z wymienionych poniżej zależności

begin

i := 0;


while i ≤ n div 2 do

if e(i) > e(n-i) then pom := e(n-i); e(n-i) :=e(i); e(i) := pom; fi;

i := i+1;

od;


end

(a) Niezmiennikiem pętli w tym programie jest formuła (e(i) > e(n-i) dla i>0) TAK / NIE

(b) Jeśli e(1) jest najmniejszym elementem ciągu przed wykonaniem algorytmu, to po jego wykonaniu
też tak jest. TAK / NIE

(c) Ten algorytm zastosowany do ciągu 8-elementowego wykonuje 4 porównania. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Formuła first(push(s,e)) = e jest prawdziwa jedynie dla niepustego stosu s. TAK / NIE

(b) Koszt operacji in wstawiania elementu do kolejki zależy od długości listy. TAK / NIE

(c) Program „while not empty(s) do s := push(pop(s),e)) od” zawsze zatrzymuje się.. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = O(n) prawda / fałsz

4n = (2lg n!) prawda / fałsz

n = (lg n!) prawda / fałsz


Podpis studenta ........................................................................................

WERSJA C2

Kolokwium ALGORYTMY I STRUKTURY DANYCH
II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!


Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............

1. Które z wymienionych ciągów funkcji są, a które nie są uporządkowane niemalejąco ze względu na rząd wielkości:

n1/2+ lg(n), lg(n2), 2 lg n, TAK / NIE

n1/2 , lg (n!), n2 , TAK / NIE

(2 lg n), 300n2 + n, n2 + n3 TAK / NIE

2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją lg n, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 32 (na pewnym komputerze) wynosi 25 sek.



  1. Ile czasu zajmie wykonanie zadania 2 razy większego? Odp..........................

  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 20sek? Odp.................................

  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 44 na komputerze 5 razy szybszym?
    Odp..........................

3. Niech A będzie optymalnym algorytmem wyszukiwania elementu największego w danym n elementowym ciągu.


  1. Ile co najmniej operacji porównywania elementów trzeba wykonać, jeśli ciąg ma 10 elementów? Odp. .........

  2. Jaki jest koszt tego algorytmu w przypadku gdy n = 2k? Odp. ......................

  3. Czy istnieje algorytm o koszcie logarytmicznym rozwiązujący ten problem? TAK / NIE

4. W uporządkowanych alfabetycznie słowniku zawierającym x haseł, chcemy wyszukać stronę z hasłem "sprawdzian". Na każdej stronie słownika znajdują się 32 hasła. Otworzenie książki na stronie o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek.



  1. Ile co najwyżej stron musimy obejrzeć zanim znajdziemy stronę z naszym hasłem, jeśli x=2048, a do wyszukiwania zastosowaliśmy algorytm binarnych poszukiwań?
    Odp.: ...........................................................

  2. Jeśli wyszukanie strony z dowolnym hasłem metodą binarnych poszukiwań
    zajmuje nie więcej niż 5 sek., to ile haseł jest w tym słowniku? Odp.: ........................................

  3. Ile co najwyżej czasu zajęłoby wyszukiwanie nazwiska z ostatniej strony, jeśli słownik ma 299stron, a do wyszukiwania właściwej strony zastosowaliśmy algorytm „skoki co 5” ? Odp.: ............

5. Niech A będzie algorytmem 'turniej' wyszukiwania elementu drugiego co do wielkości.



  1. Czy koszt czasowy algorytmu A zależy od kolejności elementów w ciągu? TAK / NIE

  2. Czy element największy zawsze znajduje się w korzeniu drzewa turniejowego? TAK / NIE

  3. Czy element drugi co do wielkości musi się znajdować na przedostatnim poziomie w drzewie turnieju? TAK / NIE

6. Niech SPLIT będzie algorytmem rozdzielania ciągu względem pierwszego elementu stosowanym w algorytmie sortowania Quick Sort.



  1. Podaj zawartość tablicy [6,1,8,2,9,3,4, 7] po jednokrotnym wykonaniu SPLIT?.
    Odp. ................ .................

  2. W algorytmie Quick Sort wywołujemy SPLIT średnio O(lg n) razy. TAK / NIE

  3. Koszt algorytmu SPLIT jest proporcjonalny do długości ciągu . TAK / NIE

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem Counting Sort (sortowania przez zliczanie) tablicy (2,1,3,2,2,1,3,1).
Odp. :.................................................................................................................

(b) Czy algorytm Radix Sort jest stabilny? TAK / NIE

(c). Który algorytm Merge Sort, czy Quick Sort ma gorszą złożoność w przypadku pesymistycznym?
Odp.: .................................................................................................................

8. Niech A będzie algorytmem sortowania danego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona ten algorytm podczas sortowania ciągu (6,7,8,9,10,1).
Jedno przestawienie polega na zamianie miejscami dwóch elementów? Odp.:......................................................

(b) Ile porównań wykona algorytm Insertion Sort zastosowany do tego samego ciągu . Odp.:............................

(c) Koszt algorytmu A, mierzony liczbą porównań elementów, jest liniowy. TAK / NIE

9. Niech n będzie liczbą naturalną, a x oraz e(0),..., e(n) dowolnymi liczbami rzeczywistymi. Przy każdej z wymienionych zależności dotyczących następującego algorytmu, zaznacz, czy jest czy nie jest prawdziwa.


begin
s := e(0); pom := x; i := 1

while ( i < n+1 ) do

s := s + e(i)* pom;

pom := pom *x;

i := i + 1;

od ;


end;

(a) Formuła (i < n+1) jest niezmiennikiem pętli w tym algorytmie. TAK / NIE


(b) Ten algorytm wykonuje O(n) mnożeń. . TAK / NIE
(c) Po wykonaniu algorytmu, e(n) jest największym elementem ciągu. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Formuła first(in(q,e)) = e jest prawdziwa w każdej strukturze kolejek. TAK / NIE

(b) Koszt operacji pop usuwania elementu ze stosu, zrealizowanego jako lista dynamiczna,


jest stały. TAK / NIE

(c) Formuła pop(push(e,s))=s jest prawdziwa w każdym stosie. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = O(lg n!) prawda / fałsz

32n = (3n) prawda / fałsz

n = (lg n) prawda / fałsz

Podpis studenta ........................................................................................

WERSJA D2

Kolokwium ALGORYTMY I STRUKTURY DANYCH


II rok PJWSTK, 11 grudnia 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innych form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!

Imie i nazwisko ................................................................................................Nr grupy.............Nr indeksu.............



1. Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany niemalejąco, ze względu na rząd występujących w nim funkcji (nN):
lg(n2) , |sin n | + n , 22lgn TAK / NIE
1000n + n1/2, lg n, 0.001*n3 +6 TAK / NIE
n2lgn, lgn!, lg3n TAK / NIE


2. Niech A będzie algorytmem, którego złożoność wyraża się funkcją 2n, gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla danych o rozmiarze 10 (na pewnym komputerze) wynosi 1024 sek.



  1. Ile czasu zajmie wykonanie zadania 2 razy mniejszego? Odp..............



  2. Jaki jest maksymalny rozmiar zadania,  które można rozwiązać w ciągu 512 sek ? Odp..............



  3. Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze 7 na komputerze 2 razy szybszym? Odp.........

3. Niech A będzie optymalnym algorytmem wyszukiwania elementu największego i najmniejszego w danym n elementowym ciągu liczb rzeczywistych.



  1. Jaki jest koszt tego algorytmu zastosowanego do ciągu 10-elementowego? Odp.:..................



  2. Jaka jest złożoność tego algorytmu w przypadku gdy n= 2k? Odp. ..............................

  3. Czy istnieje algorytm o koszcie logarytmicznym rozwiązujący ten sam problem? TAK / NIE

4. Aby odnaleźć stronę z szukaną osobę w uporządkowanym spisie ludności pewnej miejscowości X trzeba sprawdzić co najwyżej 15 stron, stosując metodę „skoków co k”. Znalezienie strony o dowolnie usta­lonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek, a na stronie jest 25 nazwisk.





  1. Jeśli k=10, to ile co najwyżej mieszkańców ma miejscowość X. Odp.: ..................

  2. Ile co najwyżej stron trzeba obejrzeć aby wyszukać dowolną osobę, jeśli liczba mieszkańców
    wynosi 800, a do przeglądania zastosowaliśmy algorytm binary search. Odp.: ................................

  3. Ile czasu, w najgorszym przypadku, zajęłoby wyszukanie właściwej osoby, jeśli zastosujemy
    algorytm sekwencyjnego przeglądania stron, a w spisie figuruje 5000 nazwisk? Odp.: ..............

5. Niech A będzie algorytmem 'turniej' wyszukiwania elementu drugiego co do wielkości .



  1. W najgorszym razie algorytm wykona n2 porównań dla ciągu n elementowego. TAK / NIE

  2. Dla ciągu 32 elementowego algorytm A wykona 35 porównań TAK / NIE

(c) Wysokość drzewa turniejowego dla ciągu o 16 elementach wynosi 4. TAK / NIE

6. Niech A będzie algorytmem scalania ciągów uporządkowanych a i b.



  1. Ile co najwyżej razy wykonywany jest algorytm A w trakcie sortowania
    ciągu n elementowego metodą Merge Sort? Odp.: ........................

  2. A nie wykona on ani jednego porównania, jeśli elementy ciągu a są mniejsze niż elementy ciągu b.

TAK / NIE

  1. Koszt wykonania algorytmu A wynosi O(n+m), gdzie n i m są odpowiednio długościami ciągów a i b.

TAK / NIE

7.


(a) Wypisz kolejne stany tablicy pomocniczej podczas sortowania algorytmem
Counting Sort (sortowania przez zliczanie) tablicy (2,3,3,2,1,2,1,1).
Odp. :..............................................................

(b) Ile porównań elementów trzebaby wykonać, gdyby do sortowania tego ciągu


użyto algorytmu sortowania pozycyjnego Radix_sort . Odp.:...............................

(c) W jakich algorytmach wykorzystuje się operację scalania dwóch ciągów uporządkowanych?

Odp. : ......................................................................

8. Niech A będzie algorytmem sortowania danego n elementowego ciągu przez wybór (Selection Sort) w porządku niemalejącym.


(a) Ile przestawień elementów wykona ten algorytm podczas sortowania ciągu (2,5,3,4,10).
Jedno przestawienie polega na zamianie miejscami dwóch elementów? Odp.:.....................................................

(b) Jaki jest średni koszt czasowy tego algorytmu? Odp.:..............................

(c) W najgorszym razie algorytm A wykona O(n2) porównań. TAK / NIE

9. Rozważyć następujący algorytm w strukturze liczb rzeczywistych i ocenić każdą z wymienionych poniżej zależności

begin

i := 0;


while i ≤ n div 2 do

if e(i) > e(n-i) then pom := e(n-i); e(n-i) :=e(i); e(i) := pom; fi;

i := i+1;

od;


end

(a) Niezmiennikiem pętli w tym programie jest formuła (e(i) > e(n-i) dla i>0) TAK / NIE

(b) Jeśli e(1) jest najmniejszym elementem ciągu przed wykonaniem algorytmu, to po jego wykonaniu
też tak jest. TAK / NIE

(c) Ten algorytm zastosowany do ciągu 8-elementowego wykonuje 4 porównania. TAK / NIE

10. Ustal prawdziwość następujących zdań:

(a) Formuła first(push(s,e)) = e jest prawdziwa jedynie dla niepustego stosu s. TAK / NIE

(b) Koszt operacji in wstawiania elementu do kolejki zależy od długości listy. TAK / NIE

(c) Program „while not empty(s) do s := push(pop(s),e)) od” zawsze zatrzymuje się.. TAK / NIE

11 Niech n N. Oceń prawdziwość każdej z podanych zależności

2lgn = O(n) prawda / fałsz

4n = (2lg n!) prawda / fałsz

n = (lg n!) prawda / fałsz


Podpis studenta ........................................................................................



©operacji.org 2017
wyślij wiadomość

    Strona główna