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

Czym jest współczynnik zapełnienia (load factor) tablicy mieszającej?

  1. ACzasem potrzebnym do wczytania tablicy z dysku
  2. BDotychczasową liczbą kolizji
  3. CLiczbą przechowywanych elementów podzieloną przez liczbę kubełków
  4. DLiczbą kubełków podzieloną przez średnią długość przechowywanych kluczy
2.Łatwy

Która struktura danych działa według zasady „pierwszy na wejściu, pierwszy na wyjściu” (FIFO)?

  1. ADrzewo binarne
  2. BKolejka
  3. CKopiec
  4. DStos
3.Łatwy

Co definiuje drzewo binarne?

  1. AKażdy węzeł ma dokładnie dwoje dzieci
  2. BKażdy węzeł ma co najwyżej dwoje dzieci
  3. CKażdy węzeł przechowuje liczbę binarną
  4. DDrzewo ma dokładnie dwa poziomy
4.Średni

Jaka jest pesymistyczna wysokość binarnego drzewa poszukiwań z n węzłami, jeśli klucze są wstawiane w kolejności posortowanej?

  1. Alog₂ n
  2. B1
  3. Cn (drzewo staje się listą wiązaną)
  4. D√n
5.Ś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
6.Średni

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

  1. AO(L × n)
  2. BO(L), niezależnie od liczby przechowywanych słów
  3. CO(n), gdzie n to liczba słów
  4. DO(log n), gdzie n to liczba słów
7.Trudny

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

  1. ALiczyć węzły, aż liczba przekroczy pole z długością listy
  2. BZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
  3. CPrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  4. DPosortować listę i szukać duplikatów
8.Trudny

Która para przejść zawsze jednoznacznie wyznacza drzewo binarne o różnych kluczach?

  1. APreorder i postorder
  2. BPreorder i inorder
  3. CSamo przejście poziomami
  4. DSam preorder

Klucz odpowiedzi

  1. 1. C · Liczbą przechowywanych elementów podzieloną przez liczbę kubełków
  2. 2. B · Kolejka
  3. 3. B · Każdy węzeł ma co najwyżej dwoje dzieci
  4. 4. C · n (drzewo staje się listą wiązaną)
  5. 5. B · Przenosi się ostatni element do korzenia i przesuwa go w dół
  6. 6. B · O(L), niezależnie od liczby przechowywanych słów
  7. 7. C · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  8. 8. B · Preorder i inorder

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