B-drzewo: jest drzewem zrównoważonym jest drzewem binarnym pełnym jest drzewem avl ma operację sumowania elementów w czasie Drzewo avl



Pobieranie 104.59 Kb.
Data18.06.2016
Rozmiar104.59 Kb.

  1. B-drzewo:

jest drzewem zrównoważonym

jest drzewem binarnym

jest drzewem binarnym pełnym

jest drzewem AVL

ma operację sumowania elementów w czasie




  1. Drzewo AVL:

koszt pesymistyczny wyszukiwania elementu wynosi O(logn)

jest drzewem BST

jest drzewem binarnym




  1. Wstawiamy do pustego drzewa BST kolejno: 1 0 3 4 6 2 5. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

0 2 5 6 4 3 1

0 2 5 6 4 3 1

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 6 4 3 5 2 0 1. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

1 0 2 3 5 4 6

1 0 2 3 5 4 6

0 1 2 3 4 5 6





  1. Wstawiamy do pustego drzewa BST kolejno: 0 4 1 2 3 6 5. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

0 1 2 3 4 5 6

3 2 1 5 6 4 0

3 2 1 5 6 4 0




  1. Wstawiamy do pustego drzewa BST kolejno: 4 0 6 1 3 5 2. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

2 3 1 0 5 6 4

2 3 1 0 5 6 4

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 2 0 6 4 3 1 5.Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

1 0 3 5 4 6 2

1 0 3 5 4 6 2

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 2 5 3 6 1 0 4 .Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

0 1 2 3 4 5 6

0 1 4 3 6 5 2

0 1 4 3 6 5 2




  1. Wstawiamy do pustego drzewa BST kolejno: 3 2 5 4 0 6 1 .Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

1 0 2 4 6 5 3

0 1 2 3 4 5 6

1 0 2 4 6 5 3




  1. Wstawiamy do pustego drzewa BST kolejno: 3 0 6 2 4 1 5. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

1 2 0 5 4 6 3

1 2 0 5 4 6 3

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 6 4 5 1 0 2 3. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

0 1 2 3 4 5 6

0 3 2 1 5 4 6

0 3 2 1 5 4 6




  1. Wstawiamy do pustego drzewa BST kolejno: 5 1 0 3 6 2 4. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:

0 1 2 3 4 5 6

0 2 4 3 1 6 5

0 2 4 3 1 6 5




  1. Wstawiamy do pustego drzewa BST kolejno: 6 0 5 3 1 4 2. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder, otrzymamy:

2 1 4 3 5 0 6

2 1 4 3 5 0 6

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 2 6 0 3 5 4 1. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder, otrzymamy:

1 0 4 5 3 6 2

1 0 4 5 3 6 2

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 1 5 3 2 0 6 4. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder, otrzymamy:

0 2 4 3 6 5 1

0 2 4 3 6 5 1

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 3 0 6 2 4 1 5. Wypisując wartości węzłów przy przejściu tego drzewa w porządku postorder, otrzymamy:

0 1 2 3 4 5 6

1 2 0 5 4 6 3

1 2 0 5 4 6 3




  1. Wstawiamy do pustego drzewa BST kolejno: 2 6 0 3 5 4 1. Wypisując wartości węzłów przy przejściu tego drzewa w porządku postorder, otrzymamy:

1 0 4 5 3 6 2

1 0 4 5 3 6 2

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 1 4 3 2 5 0 6. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder, otrzymamy:

0 2 3 6 5 4 1

0 2 3 6 5 4 1

0 1 2 3 4 5 6




  1. Wstawiamy do pustego drzewa BST kolejno: 1 5 3 2 0 6 4. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder, otrzymamy:

0 2 4 3 6 5 1

0 2 4 3 6 5 1

0 1 2 3 4 5 6





  1. Mamy graf niekierowany: a--b, b--c, c --a. Wykonujemy na nim DFS z punktu ”a” i oznaczamy czasy rozpoczęcia i zakończenia. Notując x (p/f), gdzie x-wierzchołek, p-czas rozpoczęcia, f-czas zakończenia przetwarzania, możemy otrzymać:

a(0/5), b(1/3), c(2/4)

a(0/3), b(1/4), c(2/5)

a(0/5), b(1/2), c(3/4)




  1. Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->c, c->d, d->a. Jest on:

drzewem


pełny

acykliczny




  1. Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, a->c, b->a, b->c, c->a, c->b. Jest on:

spójny


drzewem

pełny


acykliczny


  1. Mamy graf skierowany złożony z wierzchołków {a,b} i krawędzi a->b, b->a. Jest on:

pełny


acykliczny

spójny



  1. Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b. Jest on:

acykliczny

spójny

pełny



  1. Mamy graf skierowany złożony z wierzchołków {a} i krawędzi a->a. Jest on:

pełny


acykliczny

drzewem


spójny


  1. Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, c->d. Jest on:

acykliczny

spójny

pełny



  1. Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->a, c->d, d->c. Jest on:

spójny


drzewem

pełny


acykliczny


  1. Listę, ze zmodyfikowaną operacją get, który przesuwa żądany element na początek listy:

warto używać, kiedy większość operacji get tyczy się małego podzbioru elementów tej listy

warto używać, kiedy większość operacji get tyczy się różnych elementów tej listy

warto używać, kiedy większość operacji tyczy się jednego elementu

zawsze warto używać, kiedy większość operacji, to operacje get

warto używać dla losowych danych




  1. Listę, ze zmodyfikowaną operacją get, który przesuwa żądany element na koniec listy:

warto używać, kiedy większość operacji tyczy się jednego elementu

zawsze warto używać, kiedy większość operacji, to operacje get

warto używać, kiedy większość operacji get tyczy się różnych elementów tej listy

warto używać, kiedy większość operacji get tyczy się małego podzbioru elementów tej listy

warto używać, dla losowych danych




  1. Które z niżej wymienionych wymagają co najmniej O(n) dodatkowej pamięci:

CountSort

Sortowanie bąbelkowe

SelectionSort




  1. Porównując (dla danego algorytmu) złożoność pesymistyczną pamięciową z oczekiwaną obliczeniową:

mogą być sobie równe

pierwsza jest (zawsze) nie lepsza od drugiej

pierwsza jest (zawsze) gorsza od drugiej




  1. Porównując (dla danego algorytmu) złożoność pesymistyczną pamięciową z oczekiwaną pamięciową:

pierwsza jest (zawsze) gorsza od drugiej

pierwsza jest (zawsze) nie lepsza od drugiej

pierwsza może być lepsza od drugiej




  1. Porównując (dla danego algorytmu) złożoność pesymistyczną obliczeniową z oczekiwaną pamięciową:

pierwsza jest (zawsze) gorsza od drugiej

pierwsza jest (zawsze) nie lepsza od drugiej

mogą być sobie równe




  1. Porównując (dla danego algorytmu) złożoność pesymistyczną obliczeniową z optymistyczną obliczeniową:

pierwsza może być lepsza od drugiej

pierwsza jest (zawsze)gorsza od drugiej

mogą być sobie równe

pierwsza jest (zawsze) nie lepsza od drugiej


  1. Porównując (dla danego algorytmu) złożoność pesymistyczną obliczeniową z oczekiwaną obliczeniową:

pierwsza jest (zawsze)gorsza od drugiej

mogą być sobie równe

pierwsza może być lepsza od drugiej




  1. Porównując (dla danego algorytmu) złożoność oczekiwaną obliczeniową z oczekiwaną pamięciową:

pierwsza jest (zawsze) gorsza od drugiej

pierwsza jest (zawsze) nie lepsza od drugiej

mogą być sobie równe




  1. Porównując (dla danego algorytmu) złożoność oczekiwaną obliczeniową z optymistyczną pamięciową:

mogą być sobie równe

pierwsza jest (zawsze) nie lepsza od drugiej

pierwsza jest (zawsze) gorsza od drugiej




  1. Szybkiej transformaty Fouriera używamy do:

analizy i obróbki sygnałów dźwiękowych

znajdowania najkrótszej ścieżki w grafie

mnożenia wielomianów

mnożenia liczb

sortowania




  1. Jakie jest najlepsze oszacowanie na złożoność problemu znajdowania największego elementu w posortowanej tablicy rozmiaru n:

O(n)


O(lgn)

O(1)



  1. Jakie jest najlepsze oszacowanie na złożoność problemu znajdowania największego elementu w danej tablicy rozmiaru n:

O(n)


O(lgn)

O(1)



  1. Mnożenie dwóch n-cyfrowych liczb da się wykonać w czasie:

O(nlogn)


O(n2)

O(nlog23))

O(n)


  1. Dla posortowanej niemalejąco tablicy A następujący algorytm: I=0; p=n-1; while(I

oblicza indeks ostatniego wystąpienia największej liczby nieprzekraczającej x

oblicza indeks ostatniego wystąpienia najmniejszej liczby nieprzekraczającej x

oblicza indeks pierwszego wystąpienia najmniejszej liczby co najmniej równej x

oblicza indeks ostatniego wystąpienia x w A

oblicza indeks pierwszego wystąpienia x w A

oblicza indeks pierwszego wystąpienia największej liczby nieprzekraczającej x

zawsze działa w czasie O(logn)

może się zapętlić


  1. Algorytm Karacuby służy do:

analizy i obróbki sygnałów dźwiękowych

przechodzenia grafu

znajdowania najkrótszej ścieżki w grafie

sortowania

mnożenia wielomianów

mnożenia liczb


  1. Stabilne są algorytmy sortowania:

Insertionsort

Selectionsort

MergeSort

HeapSort

QuickSort




  1. Spośród następujących rzędów złożoności minimalne są:

O(2log n)

O(n log n)

O(ln 2n)




  1. Spośród następujących rzędów złożoności minimalne są:

O(ln 2n)

O(log102n)

O(nlogn)



  1. Algorytm Bluma-Floyda-Pratta-Rivesta-Tarjana znajdowania k-tego co do wielkości elementu w n-elementowym zbiorze zaczyna się od podziału na m-elementowe podzbiory dla m=5. Gdyby analogicznie pomysł wykorzystać dla innej, ale ustalonej z góry liczności m, to liniową złożoność pesymistyczną uzyskalibyśmy dla:

m=3


m=n/5

m=7


m=√(n)


  1. Jeżeli pewien algorytm działa w pesymistycznym czasie O(n) dla danych wielkości n, to będzie działał w pesymistycznym czasie O(n) również dla danych wielkości:

n+1


2n

2n + 2ln n

logn

nlogn


2n + 2ln n

n2




  1. Jeżeli pewien algorytm działa w pesymistycznym czasie O(nlogn) dla danych wielkości n, to będzie działał w pesymistycznym czasie O(nlogn) również dla danych wielkości:

n+1


2n + 2ln n

nlogn


2n

n2

logn


  1. Jeżeli pewien algorytm działa w pesymistycznym czasie O(logn) dla danych wielkości n, to będzie działał w pesymistycznym czasie O(logn) również dla danych wielkości:

2n

logn



n2


  1. Rozważmy graf pełny z wagami G=(V,E), gdzie |V| =n, wtedy:

rozmiar tablicy list incydencji grafu G jest rzędu Θ(n2)

rozmiar macierzy sąsiedztwa grafu G jest rzędu Θ(n2)

rozmiar macierzy sąsiedztwa grafu G jest rzędu Θ(n)

rozmiar tablicy list incydencji grafu G jest rzędu Ω(n)

rozmiar tablicy list incydencji grafu G jest rzędu Ω(n)




  1. Rozważmy algorytm sortowania przez zliczenie CS zastosowany do sortowania n-elementowego ciągu binarnego X, wtedy:

w tym przypadku rezultatem działania algorytmu CS będzie ciąg binarny uporządkowany nierosnąco

S(CS(X),n)= Θ(n2)

T(CS(X),n,m)=Œ(n+m), gdzie m jest stałą nie większą niż 4

A(CS(X),n)≠W(CS(X),n)

S(CS(X),n)= Θ(n)


  1. Rozważmy algorytm sortowania przez wstawianie IS, z binarnym wyszukiwaniem pozycji dla wstawianego elementu, zastosowany do danych wejściowych rozmiaru n, wtedy:

W(IS,n)=O(n×lg(n)), jeżeli operacją dominującą jest przestawianie danych

W(IS,n)=Ω(A(IS,n)), jeżeli operacją dominującą jest porównywanie danych

W(IS,n)= Θ (A(IS,n)), jeżeli operacją dominującą jest przestawianie danych

W(IS,n)= Θ(n2), jeżeli operacją dominującą jest przestawianie danych

W(IS,n)=O(n×lg(n)), jeżeli operacją dominującą jest porównywanie danych




  1. Rozważmy zastosowanie algorytmu sortowania przez scalanie MS do uporządkowanych nierosnąco danych wejściowych X rozmiaru n, wtedy:

T(MS(X),n)= Θ(lg(n!))

w tym przypadku wysokość drzewa wywołań rekurencyjnych algorytmu MS będzie nie mniejsza niż n

T(MS(X),n)= O(n)




  1. Rozważmy algorytm HeapSort zastosowany do sortowania n-elementowego ciągu wejściowego zapisanego w tablicy X, wtedy:

W(HeapSort(X),n)=O(n), jeżeli operacją dominującą jest czynność przedstawiania elementów tablicy

algorytm HeapSort sortuje dane wejściowe w miejscu

w drzewie decyzyjnego algorytmu HeapSort zastosowanego do rozważanych danych może istnieć ścieżka korzeń-liść, której długość jest rzędu O(n)

S(HeapSort(X),n)=O(1)


  1. Niech Alg będzie optymalnym algorytmem dla problemu wyszukania pewnego elementu(zakładamy, że takowy istnieje) w n-elementowym nieuporządkowanym uniwersum, wtedy:

A(Alg, n)= Ω(nxlg(n))

W(Alg, n)=O(n1/2)

A(Alg, n)=O(W(Alg,n))




  1. Rozważmy graf pełny G=(V,E), gdzie V=a,b,c,d,e,f,g wtedy:

koszt algorytmu BFS dla rozważanego grafu G jest rzędu O(|V|+|E|)

kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS jest następująca: d,c,e,b,f,a,g, jeżeli wierzchołki wybieramy w porządku odwrotnym do alfabetycznego

kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS jest następująca: d,g,f,e,c,b,a, jeżeli wierzchołki wybieramy w porządku odwrotnym do alfabetycznego

kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS jest następująca: d,a,b,c,e,f,g,

jeżeli wierzchołki wybieramy w porządku alfabetycznym

koszt algorytmu BFS dla rozważanego grafu G jest rzędu Θ(|V|)

koszt algorytmu DFS dla rozważanego grafu G jest rzędu O(|V|)

kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm DFS jest następująca: d,a,g,b,f,c,e jeżeli wierzchołki wybieramy w porządku alfabetycznym

kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm DFS jest następująca: d,a,b,c,e,f,g jeżeli wierzchołki wybieramy w porządku alfabetycznym




  1. Rozważmy graf G=(V,E), gdzie |V|=n i n>10, w którym algorytmy DFS oraz BFS generują ten sam ciąg etykiet odwiedzanych wierzchołków z pewnego wierzchołka źródłowego, wtedy graf G może być:

grafem-drzewem binarnym wysokości Θ(lg(n))

grafem pustym

grafem-gwiazdą, tj. grafem spójnym takim, że każdy wierzchołek tego grafu ma rząd równy 1 za wyjątkiem wierzchołka centralnego, którego rząd jest równy n-1

grafem-drzewem binarnym wysokości n-1



  1. Niech H będzie kopcem-drzewem typu min powstałym przez kolejne wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:

wierzchołki kopca-drzewa H wypisane w kolejności PreOrder tworzą ciąg: 0,1,5,8,6,7,2,4,3

wierzchołki kopca-drzewa H wypisane w kolejności InOrder tworzą ciąg: 8,5,6,1,7,0,4,2,3

wysokość kopca-drzewa H jest rzędu lg(n), gdzie n jest liczbą wierzchołków rozważanego drzewa

wysokość kopca-drzewa H jest równa 3

jeżeli w kopcu-drzewie H wykonamy operację delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji sczytane w kolejności InOrder tworzą ciąg 1,2,3,4,5,6,7,8

jeżeli w kopcu-drzewie H wykonamy operację delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji sczytane w kolejności PostOrder tworzą ciąg 8,6,7,5,4,3,2,1

liczba liści na ostatnim poziomie kopca-drzewa H jest równa 2

jeżeli w kopcu-drzewie H wykonamy operację delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji sczytane w kolejności PreOrder tworzą 1,2,5,6,7,4,3,8

wysokość kopca-drzewa H jest niezależna od kolejności wstawiania rozważanych wierzchołków




  1. Niech D będzie drzewem decyzyjnym dla pewnego algorytmu sortowania przez porównania zastosowanego do danych wejściowych rozmiaru n, wtedy:

liczba liści w drzewie D jest co najwyżej rzędu n2

liczba liści w drzewie D jest co najwyżej rzędu nn

wysokość drzewa D jest rzędu co najwyżej lg(n!)




  1. Niech T będzie drzewem BST powstałym przez losowe wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:

wierzchołki drzewa T wypisane w kolejności InOrder tworzą ciąg nierosnący

wierzchołki drzewa T wypisane w kolejności InOrder mogą odpowiadać ciągowi wierzchołków w kolejności PostOrder

wysokość drzewa T jest równa co najwyżej 5

wysokość drzewa T jest zależna od kolejności wstawiania rozważanych wierzchołków i w przypadku pesymistycznym może być równa 8

wysokość drzewa T jest równa co najmniej lg(n), gdzie n jest liczbą wierzchołków rozważanego drzewa




  1. Niech T będzie drzewem BST powstałym przez kolejne wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:

wysokość drzewa T jest równa co najwyżej lg(n), gdzie n jest liczbą wierzchołków rozważanego drzewa

wierzchołki drzewa T wypisane w kolejności InOrder tworzą ciąg 8,0,1,2,3,4,7,5,6

usunięcie wierzchołka z etykietą 8 w drzewie T prowadzi do drzewa, którego korzeniem będzie wierzchołek z etykietą 2 usunięcie wierzchołka z etykietą 2 w drzewie T prowadzi do drzewa, w którym w miejscu wierzchołka z etykietą 2 znajdzie się wierzchołek z etykietą 1 lub 3

usunięcie wierzchołka z etykietą 2 w drzewie T prowadzi do drzewa, w którym w miejscu wierzchołka z etykietą 2 znajdzie się wierzchołek z etykietą 4


  1. Załóżmy, że kolejka Q zawiera n elementów i że wykonujemy jedynie operacje zdefiniowane w strukturze kolejek, wtedy:

wycięcie z kolejki Q elementu znajdującego się w odległości n/4 względem początku kolejki wymaga wcześniejszego wyjęcia z kolejki 3n/4±1 elementów

wycięcie z kolejki Q elementu znajdującego się w odległości n względem końca kolejki wymaga wcześniejszego wyjęcia z kolejki n±1 elementów

wycięcie z kolejki Q elementu znajdującego się w odległości n/4 względem początku kolejki wymaga wcześniejszego wyjęcia z kolejki n/4±1 elementów

wycięcie z kolejki Q elementu znajdującego się w odległości 1 względem początku kolejki wymaga wcześniejszego wyjęcia z kolejki n±1 elementów

używając tylko co najwyżej dwóch kolejek pomocniczych Q1 oraz Q2 i operacji kolejkowych można odwrócić kolejność elementów w kolejce Q




  1. Załóżmy, że stos S zawiera n elementów i że wykonujemy jedynie operacje zdefiniowane w strukturze stosów, wtedy:

zdjęcie ze stosu S elementu znajdującego się na wysokości n/4 względem góry stosu wymaga wcześniejszego zdjęcia ze stosu n/4±1 elementów

zdjęcie ze stosu S elementu znajdującego się na wysokości n względem góry stosu wymaga wcześniejszego zdjęcia ze stosu n±1 elementów

używając tylko co najwyżej dwóch stosów pomocniczych S1 i S2 i operacji stosowanych można odwrócić kolejność elementów na stosie S

zdjęcie ze stosu S elementu znajdującego się na wysokości 1 względem góry stosu wymaga wcześniejszego zdjęcia ze stosu n±1 elementów


  1. Nazwa struktury danych AVL i związany z nią algorytm pochodzi od:

pierwszych liter nazwisk trzech twórców tej metody

pierwszych liter angielskiego skrótu opisującego najważniejszą cechę tej struktury

nazwy uniwersyteckiej ligi siatkówki, której pasjonatami byli jej twórcy




  1. Niech T będzie drzewem AVL powstałym przez kolejne wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:

wysokość drzewa jest równa 4

w trakcie budowy drzewa wykonamy co najmniej dwie podwójne rotacje

w trakcie budowy drzewa T wykonamy dwie podwójne i jedną pojedynczą rotację

wysokość drzewa jest niezależna od kolejności wstawiania rozważanych wierzchołków

wierzchołki drzewa wypisane w kolejności PreOrder tworzą ciąg 3,4,2,1,0,7,6,5,8

wierzchołki drzewa wypisane w kolejności PostOrder tworzą ciąg 0,1,3,2,5,6,8,7,4

wierzchołki drzewa wypisane w kolejności InOrder tworzą ciąg 0,1,2,3,4,5,6,7,8





  1. Kopiec n-elementowy można:

przekształcić w kopiec odwrotny(z najmniejszym, a nie największym elementem w każdym korzeniu) w czasie O(n)

rozebrać w czasie O(n)

utworzyć w czasie O(n)

scalić z innym kopcem n-elementowym (czyli utworzyć nowy kopiec z tych dwóch) w czasie O(n)


  1. Które z poniższych zdań jest zawsze prawdziwe w strukturze kolejek priorytetowych typu min:

empty(pq)→empty(delmin(insert(insert(pq,e),e)))

min(pq)=min(insert(delmin(pq),min(pq)))

min(pq)=min(insert(pq,e))

empty(pq)→empty(delmin(insert(pq,e),e))


  1. Które z poniższych zdań jest zawsze prawdziwe w strukturze kolejek:

¬empty(q) → empty(out(q))=true

¬empty(q) →first(q)≠first(in(out(q),e))

out(in(in(q,e),e))=in(out(in(q,e)),e)




  1. Niech X=[0,3,2,4,3,3,2,0,0] będzie tablicą danych wejściowych dla algorytmu sortowania przez zliczenie CS, wtedy:

stan tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu sumowania(tj. tuż po 3-ciej pętli iteracyjnej algorytmu CS) jest następujący [3,3,5,7,9]

stan tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu sumowania(tj. tuż po 3-ciej pętli iteracyjnej algorytmu CS) jest następujący [2,3,5,8,9]

rozmiar tablicy pomocniczej niezbędnej do realizacji czynności zliczania w algorytmie CS jest nie mniejszy niż 5

stan tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu sumowania(tj. tuż po 2-giej pętli iteracyjnej algorytmu CS) jest następujący [3,0,2,3,1]

stan tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu zliczania(tj. tuż po 2-giej pętli iteracyjnej algorytmu CS) jest następujący [3,3,2,3,1]




  1. Które z poniższych zdań jest prawdziwe:

istnieje algorytm, który z zadanego n-wierzchołkowego kopca-drzewa konstruuje drzewo BST w czasie O(n)

istnieje algorytm, który konstruuje kopiec-drzewo z losowego ciągu n elementów wejściowych w czasie O(n)

istnieje algorytm, który z zadanego n-wierzchołkowego drzewa AVL konstruuje kopiec-drzewo w czasie O(n1/2)

istnieje algorytm, który konstruuje kopiec-drzewo z losowego ciągu n elementów wejściowych w czasie O(lg(n))

istnieje algorytm, który z zadanego n-wierzchołkowego kopca-drzewa konstruuje drzewo AVL w czasie O(n× lg(n))




  1. Rozważmy algorytm Alg i korzeń drzewa binarnego root, gdzie Alg(root)=(if(root==NULL)return 0 else if(root.left==NULL AND root.right==NULL) return 1 else return Alg(root.left) + Alg(root.right) +1}, wtedy:

rezultatem wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest liczba wierzchołków zewnętrznych tego drzewa

rezultatem wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest liczba wierzchołków tego drzewa

rezultatem wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest liczba wierzchołków wewnętrzn. tego drzewa

S(Alg, root)=Θ(n), gdzie n jest liczbą wierzchołków drzewa o korzeniu root i uwzględniamy stos wywołań rekurencyjnych

rezultatem wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest wysokość tego drzewa




  1. Rozważmy algorytm Alg(n)={int k=1, x=1; while(k

x=1+2+3+…+(k-1)+k

x=x*k i k ≤x

x=k!


x=k! i x≥k

x=k! i s≥k

k ≤n


  1. Rozważmy algorytm Alg(n)={int s=0, k=1; while(k<=n) do s=k*k; k=k+1 od}. Które z poniższych zdań jest prawdziwe:

algorytm Alg zatrzymuje się dla dowolnej parzystej liczby naturalnej

algorytm Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1 (i+k2))

algorytm Alg nie zatrzymuje się dla dowolnej liczby naturalnej n≥210




  1. Rozważmy algorytm Alg(n)={int s=0, k=1; while(k<=n) do s=s+k*k; k=k+1 od}. Które z poniższych zdań jest prawdziwe:

Algorytm Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1(i-1)2)

Algorytm Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1(i+k)2)

Algorytm Alg jest częściowo poprawny dla warunku początkowego i końcowego odpowiednio WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1 i2)




  1. Rozważmy algorytm Alg(n)={if(n= =0) return 3 else return Alg(n-1) + Alg(n-1) + Alg(n-1))}, wtedy dla n naturalnego:

S(Alg, n)=Θ(n), jeżeli uwzględnimy stos wywołań rekurencyjnych

S(Alg, n)=O(n), jeżeli nie uwzględnimy stos wywołań rekurencyjnych

W(Alg, n)≠ Θ(A(Alg,n))

Alg(n)=3n

T(Alg, n)=Ω(3n)





  1. Rozpatrujemy całkowitą poprawność algorytmu, poprzez metodę niezmienników pętli. Jesteśmy w miejscu, tuż po zakończeniu pętli. Wiemy, że:

zachodzi zaprzeczenie dozoru pętli

zachodzi zaprzeczenie dozoru pętli oraz niezmiennik pętli z ostatniej iteracji

zachodzi dozór pętli oraz niezmiennik pętli z ostatniej iteracji




  1. Przy haszowaniu otwartym z uporządkowanymi listami wykonanie k operacji insert do pustej n-elementowej tablicy:

pesymistycznie kosztuje O(k2)

pesymistycznie kosztuje O(n2)

średnio kosztuje O(k2/n)




  1. Przy założeniu, że n>0, a przy tym n jest liczbą parzystą, zaś k jest liczbą całkowitą nieparzystą, dla pętli j=n; x=k; while(j!=0){x+=j; j--;} poprawnym niezmiennikiem jest:

parzystość zmiennych j oraz x są zawsze różne

jeśli pętla wykonała co najmniej 4 obroty, to parzystość x oraz j są takie same, jak cztery obroty pętli wcześniej

x≥0


j ≥0


  1. Sortowanie radixsort pozwala posortować n elementów szybciej niż w czasie O(nlogn) m.in. dzięki temu, że:

reprezentacje elementów z sortowanego zbioru mają określoną i stałą ze względu na n długość liczoną w bitach

algorytm countsort jest stabilny

to nie jest prawda, że radixsort może sortować za pomocą mniej niż ??? operacji

nie wykonujemy bezpośrednich operacji na elementach, tylko odwołujemy się do ich reprezentacji bitowej



  1. Aby otrzymać B-drzewo o wysokości 2 dla t=5

wstawić co najwyżej 1000 elementów

doprowadzić do sytuacji, w której łącznie będzie co najmniej 9 węzłów

ustalić jego stopień na co najmniej 5

należy po zainicjalizowaniu pustego drzewa wstawić co najmniej 25 elementów



  1. Rozważmy drzewo T typu AVL powstałe przez losowe wstawianie wierzchołków o etykietach 1,2,3,…., n-1,n do początkowo pustej struktury, wtedy:

w drzewie #%T%# może istnieć ścieżka korzeń-liść, której długość jest rzędu #%on^(1/2)%#


wysokość drzewa T jest nie większa niż c×n, gdzie c jest pewną stałą

w drzewie T może istnieć ścieżka korzeń-liść, której długość jest rzędu lg(lg(n))

usunięcie pewnego wierzchołka z drzewa T może wymagać wykonania co najwyżej jednej podwójnej rotacji

usunięcie pewnego wierzchołka z drzewa T może wymagać wykonania Θ(lg(n)) rotacji

wstawienie wierzchołka z etykietą n+1 do drzewa T wymaga wykonania co najwyżej jednej podwójnej rotacji

wstawienie wierzchołka z etykietą n+1 do drzewa T wymaga Θ(n) rotacji

wysokość drzewa T jest nie większa niż c×lg(n), gdzie c jest pewną stałą


  1. Które z poniższych zdań jest zawsze prawdziwe w strukturze słowników:

┐member(insert(delete(d,e),e),e)

empty(d)↔empty(delete(insert(insert(d,e),e),e))

member(insert(delete(d,e),e),e)

┐empty(d) ↔ empty(delete(insert(insert(d,e),e),e))


  1. Które z poniższych zdań jest zawsze prawdziwe w strukturze stosów:

┐empty(s)→top(s)≠top(push(pop(s),e))

┐empty(s)→top(s)(pop(push(s,top(s))))=top(s)

┐empty(s)→top(s)(pop(push(s,top(s))))=top(s)




  1. Mamy pewien algorytm o złożoności obliczeniowej O(n2), zmierzyliśmy czas działania dla pewnych danych o dużej liczbie elementów, równej n i czas wyniósł t.

Szacunkowo, algorytm w ciągu 4t, jest w stanie przetworzyć dane o wielkości 2n

Szacunkowo, algorytm w ciągu 16t, jest w stanie przetworzyć dane o wielkości 8n

Szacunkowo, algorytm w ciągu 8t, jest w stanie przetworzyć dane o wielkości 2n

Szacunkowo, algorytm dla danych wielkości 4n, będzie działać 4t.

Szacunkowo, algorytm w ciągu 64t, jest w stanie przetworzyć dane o wielkości 8n




  1. Dana jest funkcja laszująca h(i)=i mod17 oraz rehaszująca r(i)=(i+3)mod17. Korzystając z tych funkcji wprowadzamy do początkowo pustej tablicy intA[16] kolejno wartości: 6,0,20,13,3,17. Po wprowadzeniu tych liczb:

trzy liczby znajdują się pod indeksami im równymi

0 poprzedza wszystkie inne wprowadzone wartości

3 występuje przed 6

17 znajdzie się po wszystkich wprowadzonych wartościach


  1. Wyznaczenie operacji(i) dominującej/ych jest potrzebne do określenia:

złożoności optymistycznej pamięciowej

złożoności oczekiwanej pamięciowej

złożoności oczekiwanej obliczeniowej




  1. Analizujemy częściową poprawność algorytmu. Powinniśmy więc sprawdzić:

własność stopu

krok indukcyjny

czy niezmiennik pętli jest prawdziwy po wejściu do pętli dla danych spełniających warunek początkowy

czy niezmiennik pętli jest prawdziwy po wejściu do pętli dla każdych danych wejściowych


  1. Niech f(n)=n 2 lg(n), wtedy prawdą jest, że:

f(n) × f(n)=Ω(n3)

f(n) × f(n)= Θ(n3)

f(n) =O(n3)

f(n) = Ω (2n)

f(n)=Θ (n2)

f(n)+f(n)=Θ(n3)

f(n)+f(n)=O(n3)




  1. Pesymistycznie operacja wyszukiwania elementu w n-elementowym drzewie AVL: Niech f(n)=n 2 lg(n), wtedy prawdą jest, że:

wymaga Θ(logn) pamięci

ma złożoność obliczeniową O(lg n)

wymaga Θ(1) pamięci




  1. Rozważmy algorytm Hoare’a wyszukania elementu k-tego co do wielkości w nieuporządkowanym uniwersum rozmiaru n, wtedy:

złożoność pesymistyczna algorytmu jest rzędu co najmniej n

złożoność średnia algorytmu jest rzędu co najwyżej lg(n)

liczba wywołań procedury podziału (np. Split, Partition) jest rzędu co najwyżej k

złożoność pesymistyczna algorytmu jest rzędu co najwyżej n2


  1. Niech Alg1 oraz Alg2 będą algorytmami takimi, że T(Alg1,n)=O(nlg(n)) oraz A(Alg2,n)=O(lg(n!)) i W(Alg2,n)=Θ(n3). Rozważmy teraz algorytm Alg3 taki, że Alg3(n)=(int i=0; while(i

A(Alg3,n)=Θ(n3)

A(Alg3,n)=O(n2)

W(Alg3,n)=Ω(n3lg(n))




  1. Niech X będzie tablicą n losowych liczb naturalnych oraz SS, IS, QS będą odpowiednio algorytmami sortowania przez selekcję, sortowania przez wybór i sortowania szybkiego, wtedy:

W(QS(SS(IS(X))),n)= Ω(n)

A(IS(QS(X)),n)=O(lg(n!))

A(QS(IS(SS(X))),n)=O(n3)

W(SS(IS(X)),n)=Θ(n×lg(n))

A(SS(QS(X)),n)=O(n×lg(n))




  1. Lepiej użyć algorytmu InsertionSort, zamiast MergeSort, kiedy…

dane są prawie posortowane

mamy do czynienia z bardzo małymi danymi

mamy bardzo mało dodatkowej pamięci




  1. Czym można posortować dane używając:

sortowania kubełkowego, a w kubełkach posortować dane używając algorytmu Dijkstry

sortowania kubełkowego, a w kubełkach posortować dane używając Sita Eratostenesa

RadixSort,a do sortowaia po poszczególnych kolumnach sortowania kubełkowego, a w kubełkach stabilnej wersji QuickSort

sortowania kubełkowego, a w kubełkach posortować dane używając QuickSort

drzewa AVL




  1. Który z podanych poniżej ciągów jest asymptotycznie rosnącym ciągiem funkcji zmiennej n w dziedzinie liczb naturalnych dodatnich:

2n, (3!)n/2, (32)n/2, (n/2)!, n!-7n, nn/3



2n-1, lg(lg(n!)), lg(n)-3, n1/3, n3, 2n, 3n-2

lg(n), lg(n!), n2, n2-n, n3+100, lg(n)×n!, n!





©snauka.pl 2019
wyślij wiadomość

    Strona główna
Komunikat prasowy
przedmiotu zamówienia
najkorzystniejszej oferty
Informacja prasowa
wyborze najkorzystniejszej
warunków zamówienia
istotnych warunków
sprawie powołania
Regulamin konkursu
udzielenie zamówienia
przetargu nieograniczonego
zamówienia publicznego
Nazwa przedmiotu
Specyfikacja istotnych
modułu kształcenia
Rozporządzenie komisji
studia stacjonarne
wyborze oferty
Zapytanie ofertowe
Szkolny zestaw
Ochrony rodowiska
ramach projektu
prasowy posiedzenie
trybie przetargu
obwodowych komisji
zagospodarowania przestrzennego
komisji wyborczych
komisji wyborczej
Program konferencji
Wymagania edukacyjne
Lista kandydatów
szkoły podstawowej
która odbyła
Województwa ląskiego
Decyzja komisji
przedmiotu modułu
poszczególne oceny
Sylabus przedmiotu
szkół podstawowych
semestr letni
Postanowienia ogólne
przedsi biorców
produktu leczniczego
Karta przedmiotu
Scenariusz lekcji
Lista uczestników
Program nauczania
Projekt współfinansowany
Informacje ogólne
biblioteka wojewódzka
semestr zimowy