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 kolizja w tablicy mieszającej?

  1. AOdwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. BDwukrotnym zapisaniem dwóch równych kluczy
  3. CWyczerpaniem pamięci przez tablicę
  4. DSytuacją, w której klucza w ogóle nie da się zahaszować
2.Łatwy

Czym jest graf ważony?

  1. AGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
  2. BGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  3. CGrafem przechowywanym na dysku
  4. DGrafem, który ma więcej krawędzi niż wierzchołków
3.Łatwy

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

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

Aplikacja potrzebuje szybkiego wyszukiwania, a także wypisywania kluczy w kolejności posortowanej i odpowiadania na zapytania o zakres. Która struktura pasuje najlepiej?

  1. AZrównoważone binarne drzewo poszukiwań
  2. BNieposortowana lista wiązana
  3. CTablica mieszająca
  4. DStos
5.Średni

Jaki warunek zrównoważenia utrzymuje drzewo AVL w każdym węźle?

  1. AKażdy węzeł jest pokolorowany na czerwono lub czarno
  2. BWysokości lewego i prawego poddrzewa różnią się co najwyżej o 1
  3. CWszystkie liście są na dokładnie tej samej głębokości
  4. DOba poddrzewa każdego węzła zawierają dokładnie tyle samo węzłów
6.Średni

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

  1. ASprawdzić tylko korzeń
  2. BIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
  3. CIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  4. DOdwiedzić każdy liść i porównać je
7.Trudny

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

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

Drzewo przedziałowe (segment tree) służy zwykle do:

  1. APrzechowywania krawędzi grafu
  2. BImplementacji stosu
  3. CAlfabetycznego sortowania napisów przez przechowywanie każdego prefiksu w osobnym węźle drzewa
  4. DOdpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)

Klucz odpowiedzi

  1. 1. A · Odwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. 2. B · Grafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  3. 3. B · Klucz każdego rodzica jest większy lub równy kluczom jego dzieci
  4. 4. A · Zrównoważone binarne drzewo poszukiwań
  5. 5. B · Wysokości lewego i prawego poddrzewa różnią się co najwyżej o 1
  6. 6. C · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  7. 7. D · Wszystkie rekordy są w połączonych liściach, co czyni skanowanie zakresów wydajnym
  8. 8. D · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)

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