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

Wysokość drzewa definiuje się zwykle jako:

  1. AŁączną liczbę węzłów w drzewie, wliczając korzeń i każdy liść
  2. BLiczbę liści w drzewie
  3. CLiczbę dzieci korzenia
  4. DLiczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
2.Łatwy

Ile krawędzi ma drzewo o n węzłach?

  1. An
  2. Bn − 1
  3. Cn + 1
  4. D2n
3.Łatwy

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

  1. ALiczbą kubełków podzieloną przez średnią długość przechowywanych kluczy
  2. BCzasem potrzebnym do wczytania tablicy z dysku
  3. CDotychczasową liczbą kolizji
  4. DLiczbą przechowywanych elementów podzieloną przez liczbę kubełków
4.Średni

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

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

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

  1. AIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  2. BIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
  3. CSprawdzić tylko korzeń
  4. DOdwiedzić każdy liść i porównać je
6.Średni

Jak wstawia się nowy element do kopca binarnego?

  1. ABuduje się cały kopiec od nowa
  2. BUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
  3. CUmieszcza się go w korzeniu i przesuwa w dół
  4. DWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy
7.Trudny

Dlaczego bazy danych do indeksów często używają B+ drzew zamiast zwykłych B-drzew?

  1. AB+ drzewa przechowują dane tylko w korzeniu
  2. BB+ drzewa nie muszą być zrównoważone
  3. CB+ drzewa używają binarnych węzłów wewnętrznych, co zmniejsza liczbę odczytów z dysku
  4. DWszystkie rekordy są w połączonych liściach, co czyni skanowanie zakresów wydajnym
8.Trudny

Jaka jest główna zaleta listy z przeskokami (skip list) nad posortowaną listą wiązaną?

  1. AGwarantowane wyszukiwanie w O(1), bo każdy węzeł przechowuje wskaźnik do każdego innego węzła
  2. BOczekiwane wyszukiwanie w O(log n) dzięki kilku poziomom wskaźników do przodu
  3. CPrzechowuje klucze bez uporządkowania
  4. DNie zużywa dodatkowej pamięci

Klucz odpowiedzi

  1. 1. D · Liczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
  2. 2. B · n − 1
  3. 3. D · Liczbą przechowywanych elementów podzieloną przez liczbę kubełków
  4. 4. A · O(L), niezależnie od liczby przechowywanych słów
  5. 5. A · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  6. 6. B · Umieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
  7. 7. D · Wszystkie rekordy są w połączonych liściach, co czyni skanowanie zakresów wydajnym
  8. 8. B · Oczekiwane wyszukiwanie w O(log n) dzięki kilku poziomom wskaźników do przodu

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