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

Jak elementy tablicy są przechowywane w pamięci?

  1. AW losowych miejscach wybranych przez funkcję mieszającą
  2. BW drzewie stron pamięci
  3. CW rozproszeniu, połączone wskaźnikami
  4. DW jednym ciągłym bloku, jeden po drugim
2.Łatwy

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

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

W binarnym drzewie poszukiwań wartości w lewym poddrzewie węzła są:

  1. ARówne wartości węzła
  2. BW losowej kolejności
  3. CMniejsze od wartości węzła
  4. DWiększe od wartości węzła
4.Średni

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

  1. ANa jej głównej przekątnej zawsze są jedynki
  2. BJest zawsze górnotrójkątna
  3. CKażdy wiersz ma dokładnie jedną jedynkę
  4. DJest symetryczna względem głównej przekątnej
5.Średni

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

  1. AStosu wywołań
  2. BBinarnego drzewa poszukiwań ramek
  3. CKolejki pamięci sterty
  4. DTablicy mieszającej funkcji
6.Średni

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

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

Algorytm Kahna sortowania topologicznego wielokrotnie usuwa wierzchołki o stopniu wejściowym 0. Która struktura przechowuje te wierzchołki?

  1. AStos wszystkich odwiedzonych krawędzi
  2. BKolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0
  3. CKopiec maksymalny uporządkowany według stopnia wyjściowego
  4. DMacierz sąsiedztwa zapisującą, które wierzchołki zostały już usunięte
8.Trudny

Jaki jest oczekiwany czas wyszukiwania przy prostym równomiernym haszowaniu w tablicy mieszającej z metodą łańcuchową, n kluczami i m kubełkami?

  1. AO(n)
  2. BO(log n)
  3. CO(m)
  4. DO(1 + α), gdzie α = n / m

Klucz odpowiedzi

  1. 1. D · W jednym ciągłym bloku, jeden po drugim
  2. 2. B · W korzeniu
  3. 3. C · Mniejsze od wartości węzła
  4. 4. D · Jest symetryczna względem głównej przekątnej
  5. 5. A · Stosu wywołań
  6. 6. B · O(log n)
  7. 7. B · Kolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0
  8. 8. D · O(1 + α), gdzie α = n / m

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