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 operacja jest wolna w tablicy, ale szybka na początku listy wiązanej?

  1. AOdczyt ostatniego elementu po indeksie
  2. BWstawianie na początku
  3. CDostęp do 5. elementu
  4. DUstalenie długości tablicy o stałym rozmiarze
2.Łatwy

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

  1. AStosu
  2. BKolejki priorytetowej
  3. CKolejki
  4. DTablicy mieszającej
3.Łatwy

Co robi funkcja mieszająca w tablicy mieszającej?

  1. ALiczy, ile kluczy jest przechowywanych
  2. BOdwzorowuje klucz na indeks w tablicy
  3. CSzyfruje wartości w tablicy
  4. DSortuje klucze w tablicy
4.Średni

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

  1. A1
  2. B2
  3. CNie ma maksimum
  4. D0,5
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

Kolejkę zaimplementowano za pomocą dwóch stosów: push na stos „in”, a pop ze stosu „out”, który, gdy jest pusty, uzupełnia się ze stosu „in”. Jaki jest zamortyzowany koszt jednej operacji?

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

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

  1. APreorder i postorder
  2. BSam preorder
  3. CSamo przejście poziomami
  4. DPreorder i inorder
8.Trudny

Jaki jest koszt czasowy i dodatkowy pamięciowy odwrócenia listy jednokierunkowej w miejscu?

  1. ACzas O(n) i dodatkowa pamięć O(n)
  2. BCzas O(n) i dodatkowa pamięć O(1)
  3. CCzas O(1) i dodatkowa pamięć O(1)
  4. DCzas O(n log n) i dodatkowa pamięć O(1)

Klucz odpowiedzi

  1. 1. B · Wstawianie na początku
  2. 2. C · Kolejki
  3. 3. B · Odwzorowuje klucz na indeks w tablicy
  4. 4. A · 1
  5. 5. A · 4 5 2 3 1
  6. 6. C · O(1)
  7. 7. D · Preorder i inorder
  8. 8. B · Czas O(n) i dodatkowa pamięć O(1)

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