Struktury danych: karta pracy z odpowiedziami

Darmowa karta pracy do druku – Struktury danych: 8 zadań od łatwych do poziomu egzaminu, z kluczem odpowiedzi. Wydrukuj ją lub zapisz jako PDF.

Nowa karta pracyĆwicz online z podpowiedziami

Dla nauczycieli: można bezpłatnie drukować, kopiować i używać na zajęciach. Każdy nowy arkusz ma nowe wartości i własny klucz odpowiedzi. Będziemy wdzięczni za link do ExamProblems na stronie kursu.

Imię: ____________________   Data: ____________

1.Łatwy

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

  1. AW skrajnie lewym liściu
  2. BNa ostatniej pozycji tablicy
  3. CW korzeniu
  4. DW którymś liściu, którego trzeba szukać
2.Łatwy

Na czym polega własność kopca maksymalnego (max-heap)?

  1. AKlucz każdego rodzica jest większy lub równy kluczom jego dzieci
  2. BKlucze są posortowane od lewej do prawej
  3. CKlucz każdego lewego dziecka jest większy lub równy kluczowi jego prawego rodzeństwa
  4. DWszystkie liście zawierają klucz maksymalny
3.Łatwy

Co zawiera każdy węzeł listy dwukierunkowej?

  1. ADane i tylko wskaźnik na następny węzeł
  2. BDwie kopie danych i jeden wskaźnik
  3. CDane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim
  4. DDane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
4.Średni

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

  1. ASprawdzić tylko korzeń
  2. BOdwiedzić każdy liść i porównać je
  3. CIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  4. DIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
5.Średni

Której struktury danych używa działający program do śledzenia aktywnych wywołań funkcji i ich zmiennych lokalnych?

  1. ABinarnego drzewa poszukiwań ramek
  2. BTablicy mieszającej funkcji
  3. CStosu wywołań
  4. DKolejki pamięci sterty
6.Średni

Sieć drogowa ma 100 000 skrzyżowań, z których każde łączy się z około 4 innymi. Która reprezentacja jest najodpowiedniejsza?

  1. AListy sąsiedztwa
  2. BMacierz sąsiedztwa
  3. CKopiec binarny krawędzi
  4. DJedna posortowana tablica wierzchołków
7.Trudny

Która struktura pozwala obliczyć maksimum każdego okna o rozmiarze k w tablicy w łącznym czasie O(n)?

  1. ADeque przechowująca indeksy w kolejności malejących wartości
  2. BKopiec minimalny budowany od nowa dla każdego okna
  3. CPosortowana tablica aktualizowana przez przesuwanie
  4. DLista jednokierunkowa elementów okna
8.Trudny

Co robi drzewo splay po każdym dostępie?

  1. APrzenosi odwiedzony węzeł do liścia
  2. BPrzekolorowuje węzły na ścieżce wyszukiwania
  3. CBuduje całe drzewo od nowa w formie zrównoważonej
  4. DRotacjami przenosi odwiedzony węzeł do korzenia

Klucz odpowiedzi

  1. 1. C · W korzeniu
  2. 2. A · Klucz każdego rodzica jest większy lub równy kluczom jego dzieci
  3. 3. D · Dane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
  4. 4. C · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  5. 5. C · Stosu wywołań
  6. 6. A · Listy sąsiedztwa
  7. 7. A · Deque przechowująca indeksy w kolejności malejących wartości
  8. 8. D · Rotacjami przenosi odwiedzony węzeł do korzenia

Pełne rozwiązania krok po kroku: ćwicz ten temat na examproblems.com.