t001

1.    CO ROZUMIEMY POD POJĘCIEM ALGORYTMU POPRAWNEGO WG FLOYDA’ - D

TO TAKI ALGORYTM, KTÓRY DLA KAŻDEGO EGZEMPLARZA PROBLEMU ZATRZYMUJE SIĘ I DAJE DOBRY WYNIK._

2.    PESYMISTYCZNY CZAS DZIAŁANIA ALGORYTMU JEST JEGO: A

GÓRNĄ GRANICĄ MOŻLIWEGO CZASU DZIAŁANIA ALGORYTMU._

3.    ZŁ02ON0ŚĆ CZASOWA ALGORYTMU JEST TO: A

CZAS WYKONANIA ALGORYTMU WYRAŻONY FUNKCJĄ ROZMIARU PROBLEMU. _

4.    ZŁOŻONOŚĆ PAMIĘCIOWA ALGORYTMU WYRAŻONA JEST FUNKCJĄ: B

HM-

5.    ALGORYTM PRZEZ PROSTE WSTAWIANIE MOŻNA POPRAWIĆ POPRZEZ ZASTOSOWANIE:

C-WSTAWIANIE KLUCZA Z WARTOŚCIĄ 6.

6.    SORTOWANIE WYMYŚLONE PRZEZ C.A.R.

HOARE'A TO: D-SORTOWANIE PRZEZ PODZIAŁ (QUICK-SORT)_

7.    OBIEKT NIE WIĘKSZY (MNIEJSZY LUB

RÓWNY) POŁOWIE n OBIEKTÓW ORAZ NIE MNIEJSZY (WIĘKSZY LUB RÓWNY) 00 DRUGIEJ POŁOWY n OBIEKTÓW TO OBIEKT: C-MEPIANA_

8.    KOPIEC DEFINIUJEMY JAKO CIĄG KLUCZY h,, Iy»i,.. .h. TAKICH ZE: A- h,<«h_a I hi<»h_M«i

|    9. W TABLICY ROZPOROSZONEJ ROZWIĄZANIE

I PROBLEMU KOLIZJI POLEGAJĄCE NA PRZEGLĄDANIU PAMIĘCI CYKLICZNIE, ZE . STAŁĄ DŁUGOŚCIĄ KROKU: d,«(do+a‘i) moO p ! NAZYWANE JEST SZUKANIEM: A - LINIOWYM j 10. ŚCIEŻKA W i RAFIE JEST NAZYWANA PROSTĄ JEŚLI WSZYSTKIE JEJ WIERZCHOŁKI

_są n__________

_*.l DISnAł o-^aF: D-SKIEROWANY

12.    minimalne crzewo rozpinające w

i GRAFIE NIESKIEROWANYM ŁĄCZY WSZYSTKIE WIERZCHOŁKI GRAFU TAK ABY ŁĄCZNA WAGA DRZEWA BYŁA: C-MINIMALNA. _

13.    BINARNE DRZEWO ZRÓWNOWAŻONE TO DRZEWO, W KTÓRYM DLA KAŻDEGO WĘZŁA LICZBY WĘZŁÓW W JEGO LEWYM I PRAWYM PODDRZEWIE RÓŻNIĄ SIĘ CO NAJWYŻEJ O: D-0

14.    JEŻELI OBIEKT SKŁADA SIĘ Z SIEBIE

■ SAMEGO LUB JEGO DEFINICJA ODWOŁUJE SIĘ DO NIEGO SAMEGO, TO TAKI OBIEKT NAZYWAMY: D-REKURENCYJNYM._

15.    ZŁOŻONOŚĆ OBLICZENIOWA

WYSZUKIWANIA W TABLICY ROZPROSZONEJ JEST RZĘDU: A- 0(n)_

16.    SORTOWANIE DRZEWIASTE

WYKORZYSTUJE: A- BINARNE DRZEWO SORTUJĄCE_

17.    GRAF, W KTÓRYM KAŻDY WIERZCHOŁEK

MA TEN SAM STOPIEŃ NAZYWAMY: C-REGULARNYM._

18.    DŁUGOŚĆ ŚCIEŻKI HIERARCHICZNEJ DO

WĘZŁA NA POZIOMIE K W DRZEWIE JEST RÓWNA: C- k-1_

19.    W DRZEWIE ZAPISANYM ZA POMOCĄ STRUKTURY LEWOUSTOWEJ: A(B(D(1),E(J,KL)),C(F(0).G(M.N).H(P)))

LICZBA WĘZŁÓW NA POZIOMIE 2 WYNOSI: D-

20. W BINARNYM DRZEWIE POSZUKIWAŃ, DLA KAŻDEGO WĘZŁA WSZYSTKIE KLUCZE Z LEWEGO PODGRZEWA SĄ W STOSUNKU DO KLUCZA W TYM WĘŹLE: A-MN1EJSZE._

1.    CO ROZUMIEMY POD POJĘCIEM ALGORYTMU

POPRAWNEGO WG FLOYDA’ - D-TO TAKI ALGORYTM, KTÓRY DLA KAŻDEGO EGZEMPLARZA ZATRZYMUJE SIĘ I DAJE DOBRY WYNIK. _

2.    KLASA PROBLEMÓW P (POLONOMIAL)

ZAWIERA WSZYSTKIE PROBLEMY ROZWIĄZYWALNE W CZASIE WIELOMIANOWYM, A WIĘC TAKIE, KTÓRE ROZWIĄZUJE W CO NAJMWYŻEJ CZASIE WIELOMIANOWYM: D-DETERMINISTYCZNA MASZYNA TURINGA.__

3.    ZŁOŻONOŚĆ PESYMISTYCZNA WYRAŻONA JEST WZOREM: A- T*.(n)«m«Cr(d), d-

^; dane rozmiaru w> _

i 4. NOTACJA O POCHODZI OD SŁOWA: (W J.

! ANG.) B-RZĄD._

I 5. ALGORYTM PRZEZ PROSTE WSTAWIANIE ' MOŻNA POPRAWIĆ POPRZEZ ZASTOSOWANIE:

¹ C-WSTAWIENIE KLUCZA Z WARTOŚCIĄ Ó.

. 6. JEDNA Z NAJGORSZYCH METOD I SORTOWANIA JEST: D-SORT. BĄBELKOWE

7.    KOPIEC DEFINIUJEMY JAKO CIĄG KLUCZY h„ h,,,. ,h. TAKICH ŻE: A- h,<-h„ I hi<«h_M„

8.    NAJLEPSZE METODY SORTOWANIA

(STOGOWE, SZYBKIE) MAJĄ ZŁOŻONOŚĆ OBLICZENIOWĄ RZĘOU: A- nloflżn_

9.    SZUKANIE KWADRATOWE TO NATURALNA

METODA UWOLNIENIA SIĘ OD GRUPOWANIA KLUCZY W TABLICY ROZPROSZONEJ I    i

WYGLĄDA NASTĘPUJĄCO: A-

hi«(yi4L^li^ł)mVi __ I

10.    JEŚLI W GRAFIE NIESKIEROWANYM KAŻDA

PARA WIERZCHOŁKÓW JEST POŁĄCZONA ŚCIEŻKĄ TO TAKI GRAF NAZYWAMY: C-SPÓJNYM_

11.    JEŻELI OBIEKT SKŁADA SIĘ Z SIEBIE

SAMEGO LUB JEGO DEFINICJA ODWOŁUJE SIĘ DO NIEGO SAMEGO, TO TAKI OBIEKT NAZYWAMY. D-REKURENCYJNYM._

12.    ZŁOŻONOŚĆ OBLICZENIOWA

WYSZUKIWANIA W TABLICY ROZPROSZONEJ JEST RZĘOU: A- O(n)_

13.    SORTOWANIE DRZEWIASTE

WYKORZYSTUJE: A-BINARNE DRZEWO SORTUJĄCE_

; 14. EULER W SWYM TWIERDZENIU 0 | ŚCIEŻKACH W GRAFACH WYMAGA: C-I PARZYSTEJ LICZBY KRAWĘDZI WYCHODZĄCYCH Z KAŻDEGO WIERZCHOŁKA.__

15.    KTÓRY Z PODANYCH ALGORYTMÓW NIE JEST ALGORYTMEM TWORZENIA MINIMALNEGO DRZEWA ROZPINAJĄCEGO: D-DIJKSTRY.

16.    W TEORII GRAFÓW NIE ISTNIEJE NASTĘPUJĄCE POJECIE: D-GRAF EUKLIDESA.

17.    LICZBĘ BEZPOŚREDNICH POTOMKÓW

WĘZŁA W DRZEWIE NAZYWAMY JEGO: B-STOPNIEM._

18.    PRZEGLĄ3AJĄC DRZEWO

REPREZENTUJĄCE WYRAŻENIA ALGEBRAICZNE UZYSKANO NASTĘPUJĄCY REZULTAT: abc/+d«f*-v JEST TO PORZĄDEK TYPU: B-POSTORDER(POSTFIKS,WSTECZNY). _

19.    W BINARNYM DRZEWIE POSZUKIWAŃ, DLA

KAŻDEGO WĘZŁA WSZYSTKIE KLUCZE Z PRAWEGO POO DRZEWA SĄ W STOSUNKU DO KLUCZA W TYM WĘŹLE : B-WIĘKSZE_

20.    BINARNE DRZEWO ZRÓWNOWAŻONE TO

DRZEWO, W KTÓRYM DLA KAŻDEGO WĘZŁA LICZBY WĘZŁÓW W JEGO LEWYM I PRAWYM PODDRZEWIE RÓŻNIĄ SIĘ CO NAJWYŻEJ O: D-0. ___