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. ASytuacją, w której klucza w ogóle nie da się zahaszować
  2. BWyczerpaniem pamięci przez tablicę
  3. CDwukrotnym zapisaniem dwóch równych kluczy
  4. DOdwzorowaniem dwóch różnych kluczy na ten sam indeks
2.Łatwy

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

  1. ALista wiązana
  2. BStos
  3. CKolejka
  4. DTablica mieszająca
3.Łatwy

Co robi operacja peek (lub top) na stosie?

  1. AUsuwa wszystkie elementy ze stosu
  2. BZwraca element z dna stosu
  3. CZwraca element z wierzchołka bez usuwania go
  4. DUsuwa element z wierzchołka i go zwraca
4.Średni

Jak w kolejce cyklicznej przechowywanej w tablicy o pojemności n oblicza się następną pozycję po indeksie i?

  1. Ai + 1
  2. B(i − 1) mod n
  3. C2i + 1
  4. D(i + 1) mod n
5.Średni

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

  1. A0,5
  2. B1
  3. C2
  4. DNie ma maksimum
6.Średni

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

  1. AWstawiania
  2. BRosnącej (posortowanej)
  3. CZawsze malejącej
  4. DPoziomami
7.Trudny

Ile trwa wyszukanie dowolnego klucza w binarnym kopcu minimalnym o n elementach?

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

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

  1. ASortowanie tablicy i wyszukiwanie binarne
  2. BZnajdowanie mediany w O(1)
  3. CZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
  4. DWstawianie elementów na dowolnej pozycji

Klucz odpowiedzi

  1. 1. D · Odwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. 2. B · Stos
  3. 3. C · Zwraca element z wierzchołka bez usuwania go
  4. 4. D · (i + 1) mod n
  5. 5. B · 1
  6. 6. B · Rosnącej (posortowanej)
  7. 7. B · O(n)
  8. 8. C · Zapytania o sumy prefiksowe i aktualizacje pojedynczych elementów

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