Algorytmy i struktury danych: zadania i pytania egzaminacyjne

Notacja dużego O, czas działania typowych algorytmów i kompromisy między tablicami, listami wiązanymi, drzewami, tablicami mieszającymi i grafami.

Ćwicz ten przedmiot za darmoĆwicz ten przedmiotNapisz egzamin próbny5 darmowych zadań dziennie. Bez karty.

Zestaw na powtórkę (PDF)Wzory, kroki metod i zadania z pełnymi rozwiązaniami, gotowe do wydruku.

Tematy w tym przedmiocie

  1. Algorytmy i złożonośćkluczowe pojęcia i fakty · stosowanie pojęć · przypadki i analizatest wyboru
  2. Struktury danychkluczowe pojęcia i fakty · stosowanie pojęć · przypadki i analizatest wyboru
  3. Teoria grafówstopnie i krawędzie · ścieżki Eulera i drzewa · najkrótsze ścieżki i drzewa rozpinająceobliczenia

Wskazówki egzaminacyjne: Algorytmy i struktury danych

  • Przy zagnieżdżonych pętlach mnóż liczby iteracji; przy pętlach po kolei zostaw większy składnik.
  • Znaj koszt wyszukiwania, wstawiania i usuwania dla każdej struktury danych.
  • Dzielenie danych wejściowych na pół w każdym kroku daje czas logarytmiczny.

Przykłady z rozwiązaniami

Algorytmy i złożonośćŁatwy

Która notacja opisuje górne ograniczenie tempa wzrostu?

  1. ANotacja duże Omega
  2. BNotacja małe omega
  3. CNotacja duże O
  4. DNotacja duże Theta
Pokaż podpowiedzi
  1. „Co najwyżej”.
  2. Dwie błędne odpowiedzi są teraz skreślone. Jedna z dwóch pozostałych jest poprawna.
Pokaż odpowiedź i wyjaśnienie

Dlaczego to jest odpowiedź

O daje ograniczenie górne, Ω ograniczenie dolne, a Θ ograniczenie dokładne (asymptotycznie ścisłe).

Odpowiedź

C · Notacja duże O
Struktury danychŚredni

Jak działa extract-min w binarnym kopcu minimalnym?

  1. AUsuwa się ostatni element tablicy
  2. BPrzenosi się ostatni element do korzenia i przesuwa go w dół
  3. CUsuwa się korzeń i przesuwa wszystkie elementy o jedno miejsce w lewo
  4. DPrzeszukuje się wszystkie liście w poszukiwaniu nowego minimum
Pokaż podpowiedzi
  1. Zachowaj zupełność drzewa, a potem napraw porządek.
  2. Dwie błędne odpowiedzi są teraz skreślone. Jedna z dwóch pozostałych jest poprawna.
Pokaż odpowiedź i wyjaśnienie

Dlaczego to jest odpowiedź

Ostatni element wypełnia lukę w korzeniu i jest zamieniany z mniejszym dzieckiem, dopóki nie zostanie spełniona własność kopca, co zajmuje O(log n).

Odpowiedź

B · Przenosi się ostatni element do korzenia i przesuwa go w dół

Jak wygląda ćwiczenie

  • „Ćwicz ten przedmiot” miesza zadania ze wszystkich jego tematów, jak na prawdziwym egzaminie.
  • Każde zadanie ma nowe wartości, więc uczysz się metody, a nie odpowiedzi.
  • Utknąłeś? Najpierw otwórz małą podpowiedź, a pełne wyjaśnienie dopiero wtedy, gdy go potrzebujesz.
  • Egzaminy próbne są mierzone czasem i nie mają podpowiedzi, a na końcu dostajesz wynik i pełne omówienie.

Powiązane przedmioty

Podstawy informatykiMatematyka dyskretnaSieci komputerowe
Ćwicz ten przedmiot za darmoĆwicz ten przedmiotNapisz egzamin próbny5 darmowych zadań dziennie. Bez karty.