AISD term1

Red-black Trees are approximately balanced

TRUE

B-trees are perfectly balanced

TRUE

MergeSort cannot be-performed in-place?

TRUE

The knapsack problem (discrete version) is a polynomial time problem?

FALSE

The continuous knapsack problem is a polynomial time problem?

TRUE

The knapsack problem (discrete version) requires K*N operations

TRUE

Pessimistic time complexity of MergeSort sorting algorithm is

O(nlog(n))

Pessimistic time complexity of ShellSort sorting algorithm (simpler version) is

O(n^1.2)

Amortized analysis provides an understanding of the algorithm’s behavior for worst-case scenarios

FALSE

Can QuickSort be performed in place?

FALSE

MergeSort cannot be used for purpose of sorting data in a file (not in an array)

FALSE

The discrete knapsack problem is not polynomial

TRUE

The optimistic time complexity of search in a BST is O(1)

TRUE

Red-black trees are not perfectly balanced and B-trees are perfectly balanced?

TRUE

The search time in a TRIE structure DOES NOT depend on the number of elements in that tree?

TRUE

The memory complexity of Partition in a typical implementation is

O(N) ; it can be improved to O(log n).

The optimistic time complexity of searching in a BST is O(log h(T))

FALSE

Does QuickSort have the best possible worst-case time complexity?

FALSE

Does Quicksort lend itself to sorting data in a file?

FALSE

There isn’t a sorting algorithm with pessimistic complexity better than O(nlog(n))

FALSE

Are there any sorting algorithms faster than n^2 that can be in place?

TRUE

Co w notacji asymptotycznej oznacza o(x)?

wolniej niż

Co w notacji asymptotycznej oznacza O(x)?

nie szybciej niż

Co w notacji asymptotycznej oznacza ω(x)?

szybciej niż

Co w notacji asymptotycznej oznacza Ω(x)?

nie wolniej niż

Co w notacji asymptotycznej oznacza θ(x)?

dokładnie tak samo

Jaką złożoność czasową ma zapisywanie danych w tablicy?

θ(1)

Jaką złożoność czasową ma odczytywanie danych w tablicy?

θ(1)

Jaka jest złożoność czasowa wyszukiwania elementów w tablicy?

O(n) dla tablicy nieposortowanej, O(log n) dla tablicy posortowanej

Jaka jest złożoność czasowa przeszukiwania listy?

O(n)

Jaka jest złożoność czasowa dopisywania danych na początek listy?

θ(1)

Jaka jest złożoność czasowa wpisywania danych w środku listy?

θ(i) i to pozycja na której chcemy wpisać

Jaka jest złożoność czasowa czytania dowolnego elementu listy?

O(n)

Jaka jest złożoność czasowa bubble sorta?

O(n^2)

Jaka jest złożoność czasowa insertion sorta?

O(n^2)

Jaka jest złożoność czasowa shell sorta?

Zależy od wyboru współczynnika podziału k:

k = 1 : O(n^2)
k = (2^i) - 1 : O(n^1.2)
k = (2^r) * (2^q) , q,r są naturalne : O(n log^2 n)

Jaka jest średnia złożoność czasowa quicksorta?

O(n log n)

Jaka jest najgorsza złożoność czasowa quicksorta?

O(n^2)

Czy quicksort jest stabilny?

To zależy od algorytmu partition

Jaka jest najgorsza złożoność pamięciowa quicksorta?

O(n)

Jaka jest najlepsza złożoność pamięciowa quicksorta?

O(log n)

Jaka jest złożoność czasowa mergesorta?

O(n log n)

Jaka jest złożoność czasowa przeszukiwania BST?

O(h(T))

Jaka jest złożoność czasowa znajdowania min/max w BST?

O(h(T))

Jaka jest złożoność czasowa dodawania elementów na stos?

θ(1)

Jaka jest złożoność czasowa usuwania elementów ze stosu?

θ(1)

Jaka jest złożoność czasowa usuwania elementów z kolejki?

θ(1)

Jaka jest złożoność czasowa dodawania elementów do kolejki?

θ(1)

Czy BST jest perfekcyjnie zbalansowane?

Nie

Jaką wysokość mają RB drzewa?

h

Jaka jest złożoność czasowa przeszukiwania RB drzewa?

O(log n)

Czy B drzewa są idealnie zbalansowane?

TAK

Jaką złożoność czasową ma dodawanie elementów do kopca binarnego?

θ(log n)

Jaką złożoność czasową ma usuwanie elementów z kopca binarnego?

O(log n)

Jaką złożoność czasową ma usuwanie min/max z kopca binarnego?

θ(log n)

Jaką złożoność czasową ma znajdowanie min/max w kopcu binarnym?

θ(1)

Jaką złożoność czasową ma łączenie kopców binarnych?

O(n log n)

Jaką złożoność czasową ma łączenie kopców dwumianowych?

O(log n)

Jaką złożoność czasową ma łączenie kopców Fibonacciego?

θ(1) [analiza zamortyzowana]

Jaką złożoność czasową ma zmiana wartości elementu w kopcu binarnym?

O(log n)

Jaką złożoność czasową ma zmiana wartości elementu w kopcu dwumianowym?

O(log n)

Jaką złożoność czasową ma zmiana wartości elementu w kopcu Fibonacciego?

θ(1) [analiza zamortyzowana]

Jaką złożoność czasową ma usuwanie min/max z kopca dwumianowego?

θ(log n)

Jaką złożoność czasową ma usuwanie min/max z kopca Fibonacciego?

O(log n) [analiza zamortyzowana]

Jaką złożoność czasową ma znajdowanie min/max w kopcu Fibonacciego?

θ(1) [analiza zamortyzowana]

Jaką złożoność czasową ma dodawanie elementów do kopca dwumianowego?

O(log n)

Jaką złożoność czasową ma dodawanie elementów do kopca Fibonacciego?

θ(1) [analiza zamortyzowana]

Jaką złożoność czasową ma usuwanie elementów z kopca Fibonacciego?

O(log n) [analiza zamortyzowana]

Czym jest analiza zamortyzowana?

Analiza zamortyzowana zajmuje się oszacowaniem czasu niezbędnego do wykonania ciągu operacji, a nie pojedynczej operacji. Na przykład: powiększenie pełnego wektora ma złożoność O(n), ale dzieje się to rzadko, więc koszt tego jest rozłożony w czasie.

Złożoność czasowa przeszukiwania drzewa Trie nie zależy od ilości elementów w nim

Prawda, jest to O(h(T))

Czy quicksort ma najlepszą możliwą pesymistyczną złożoność czasową spośród algorytmów sortujących?

Nie, wynosi ona O(n^2) i jest okropna

Czy quicksort jest zalecany do sortowania danych w pliku?

Nie, ponieważ pliki nie mają random access jak tablice

Nie ma algorytmu sortującego z pesymistyczną złożonością czasową lepszą niż O(n log n)

Fałsz

Czy dyskretny problem plecakowy jest wielomianowy?

Nie, jest on pseudowielomianowy

Czy ciągły problem plecakowy jest wielomianowy?

Tak

Czy algorytmy zachłanne nigdy nie dają gwarancji optymalnego rozwiązania?

Fałsz

Czy ciągły problem plecakowy wymaga K * N operacji?

Nie

Wzór na minimalną liczbę węzłów w B-Tree

(2t^h+1)/(t-1)

Wzór na maksymalną liczbę węzłów w B-Tree

((2t)^h+1-1)/(2t-1)

Wzór na minimalną liczbę kluczy w B-Tree

2t^h-1

Wzór na maksymalną liczbę węzłów w B-Tree

(2t)^h+1-1