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

Jak nazywa się operacja na kolejce, która usuwa element z jej początku?

  1. APush
  2. BDequeue
  3. CEnqueue
  4. DInsert
2.Łatwy

Czym jest korzeń drzewa?

  1. AWęzeł o największej wartości
  2. BNajwyższy węzeł, który nie ma rodzica
  3. CDowolny węzeł w środku
  4. DWęzeł bez dzieci
3.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

  1. ALiczbą wierzchołków w grafie
  2. BLiczbą krawędzi z nim połączonych
  3. CDługością najdłuższej ścieżki z niego wychodzącej
  4. DJego pozycją na liście sąsiedztwa
4.Średni

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

  1. ANajstarsze klucze są usuwane, by zrobić miejsce
  2. BTylko kolidujące klucze są przenoszone na nową listę nadmiarową na końcu tablicy
  3. CAlokuje się większą tablicę i ponownie wstawia każdy klucz
  4. DIstniejące klucze są sortowane w miejscu
5.Średni

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia postorder?

  1. A4 5 2 3 1
  2. B5 4 3 2 1
  3. C1 2 4 5 3
  4. D4 2 5 1 3
6.Średni

Jaka jest wartość wyrażenia w notacji postfiksowej 3 4 + 2 * ?

  1. A10
  2. B24
  3. C14
  4. D11
7.Trudny

Struktura union-find (zbiory rozłączne) z łączeniem według rangi i kompresją ścieżki ma zamortyzowany koszt operacji równy:

  1. ADokładnie O(log n)
  2. BO(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  3. CO(n)
  4. DO(n²)
8.Trudny

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

  1. ASamo przejście poziomami
  2. BSam preorder
  3. CPreorder i inorder
  4. DPreorder i postorder

Klucz odpowiedzi

  1. 1. B · Dequeue
  2. 2. B · Najwyższy węzeł, który nie ma rodzica
  3. 3. B · Liczbą krawędzi z nim połączonych
  4. 4. C · Alokuje się większą tablicę i ponownie wstawia każdy klucz
  5. 5. A · 4 5 2 3 1
  6. 6. C · 14
  7. 7. B · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  8. 8. C · Preorder i inorder

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