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

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

  1. AKopiec
  2. BKolejka
  3. CStos
  4. DDrzewo binarne
2.Łatwy

Jaka jest cecha definiująca zbiór jako abstrakcyjny typ danych?

  1. APrzechowuje elementy bez duplikatów
  2. BPrzechowuje pary klucz–wartość
  3. CPrzechowuje elementy w kolejności posortowanej
  4. DPozwala na dostęp tylko z jednego końca
3.Łatwy

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

  1. AStos
  2. BNieuporządkowana lista jednokierunkowa
  3. CKopiec
  4. DCiąg znaków
4.Średni

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

  1. AO(n²), bo każdy element przesuwa się n razy
  2. BO(n), bo dalsze elementy trzeba przesunąć
  3. CO(1), bo indeks jest znany
  4. DO(log n), z powodu wyszukiwania binarnego
5.Średni

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

  1. A2
  2. B0,5
  3. CNie ma maksimum
  4. D1
6.Średni

Co się dzieje, gdy tablica mieszająca wykonuje rehashing po przekroczeniu progu współczynnika zapełnienia?

  1. ATylko kolidujące klucze są przenoszone na nową listę nadmiarową na końcu tablicy
  2. BIstniejące klucze są sortowane w miejscu
  3. CAlokuje się większą tablicę i ponownie wstawia każdy klucz
  4. DNajstarsze klucze są usuwane, by zrobić miejsce
7.Trudny

Dla każdego elementu tablicy chcesz znaleźć najbliższy większy element po jego prawej stronie, w łącznym czasie O(n). Która struktura pomaga?

  1. ABinarne drzewo poszukiwań budowane od nowa dla każdego elementu
  2. BTablica mieszająca wszystkich elementów
  3. CStos przechowujący elementy czekające na swoją odpowiedź
  4. DKolejka przechowująca każdą parę elementów
8.Trudny

Które stwierdzenie o sortowaniu przez kopcowanie (heapsort) jest poprawne?

  1. ADziała w czasie O(n) dla każdych danych wejściowych
  2. BJest stabilne i wymaga O(n) dodatkowej pamięci
  3. CWymaga binarnego drzewa poszukiwań jako dodatkowej pamięci, więc zużywa O(n) pamięci dodatkowej
  4. DSortuje w miejscu w pesymistycznym czasie O(n log n), ale nie jest stabilne

Klucz odpowiedzi

  1. 1. B · Kolejka
  2. 2. A · Przechowuje elementy bez duplikatów
  3. 3. C · Kopiec
  4. 4. B · O(n), bo dalsze elementy trzeba przesunąć
  5. 5. D · 1
  6. 6. C · Alokuje się większą tablicę i ponownie wstawia każdy klucz
  7. 7. C · Stos przechowujący elementy czekające na swoją odpowiedź
  8. 8. D · Sortuje w miejscu w pesymistycznym czasie O(n log n), ale nie jest stabilne

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