Algorytmy i złożoność: karta pracy z odpowiedziami

Problem zwykle nazywa się praktycznie rozwiązywalnym (tractable), jeśli:

1. ADa się go rozwiązać tylko przez sprawdzenie wszystkich możliwości
2. BDa się go rozwiązać w czasie wielomianowym
3. CNie ma rozwiązania
4. DDa się go rozwiązać w czasie stałym

Jaką strategię projektowania stosuje sortowanie przez scalanie?

1. ADziel i zwyciężaj
2. BWybór zachłanny
3. CSiłę brutalną (przegląd zupełny)
4. DProgramowanie dynamiczne

Jaką złożoność ma zwykle algorytm z dwiema zagnieżdżonymi pętlami, z których każda wykonuje się n razy?

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(2n)

Programowanie dynamiczne jest przydatne, gdy problem ma:

1. ANakładające się podproblemy i optymalną podstrukturę
2. BWyłącznie losowe dane wejściowe
3. CŻadnych podproblemów, więc można go rozwiązać w jednym kroku
4. DPojedynczą pętlę

Co mierzy analiza zamortyzowana?

1. AKoszt algorytmu dla najlepszych danych
2. BKoszt pojedynczej najdroższej operacji w dowolnym miejscu ciągu
3. COczekiwany koszt dla losowych danych wejściowych
4. DŚredni koszt na operację w pesymistycznym ciągu operacji

Jaki jest czas działania sortowania pozycyjnego LSD (radix sort) dla n liczb całkowitych o d cyfrach w systemie o podstawie k?

1. AO(d(n + k))
2. BO(n²)
3. CO(n log n)
4. DO(dn log k)

Dla którego wariantu problemu plecakowego reguła zachłanna „bierz przedmioty według wartości na jednostkę wagi" zawsze daje optymalną odpowiedź?

1. ACiągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić
2. BDyskretnego problemu plecakowego 0/1, w którym przedmioty zawsze trzeba brać w całości
3. CObu wariantów
4. DŻadnego z wariantów

Która technika zapewnia oczekiwany czas działania O(n log n) dla quicksorta na dowolnych danych wejściowych?

1. AWybieranie zawsze pierwszego elementu
2. BStosowanie rekurencji tylko po lewej stronie
3. CLosowanie pivota z rozkładem jednostajnym
4. DPosortowanie danych przed uruchomieniem quicksorta