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

Co zawiera każdy węzeł listy dwukierunkowej?

  1. ADane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim
  2. BDwie kopie danych i jeden wskaźnik
  3. CDane i tylko wskaźnik na następny węzeł
  4. DDane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
2.Łatwy

W liście jednokierunkowej każdy węzeł zawiera:

  1. ADane i referencje do wszystkich pozostałych węzłów
  2. BDane i referencję do następnego węzła
  3. CDane i indeks
  4. DTylko dane
3.Łatwy

Czym jest deque (kolejka dwustronna)?

  1. ADwiema oddzielnymi kolejkami dzielącymi jedną tablicę
  2. BKolejką posortowaną według priorytetu
  3. CKolejką, która pozwala usuwać elementy tylko z końca
  4. DStrukturą pozwalającą wstawiać i usuwać elementy na obu końcach
4.Ś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(1)
  3. CO(n²)
  4. DO(log n)
5.Średni

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

  1. AJest zawsze górnotrójkątna
  2. BJest symetryczna względem głównej przekątnej
  3. CKażdy wiersz ma dokładnie jedną jedynkę
  4. DNa jej głównej przekątnej zawsze są jedynki
6.Ś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. AStos
  2. BZrównoważone binarne drzewo poszukiwań
  3. CNieposortowana lista wiązana
  4. DTablica mieszająca
7.Trudny

Dlaczego serwer może losowo wybierać funkcję mieszającą z rodziny uniwersalnej?

  1. ABy było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
  2. BBy tablica mieszająca była posortowana
  3. CBy wyeliminować potrzebę zmiany rozmiaru tablicy
  4. DBy zagwarantować, że żadne dwa klucze nigdy nie będą kolidować, jakie klucze by nie wysłał atakujący
8.Trudny

Klucze 5, 3, 8, 1 wstawia się w tej kolejności do pustego binarnego kopca minimalnego opartego na tablicy. Jak wygląda końcowa tablica?

  1. A[1, 3, 5, 8]
  2. B[3, 1, 8, 5]
  3. C[1, 5, 8, 3]
  4. D[1, 3, 8, 5]

Klucz odpowiedzi

  1. 1. D · Dane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
  2. 2. B · Dane i referencję do następnego węzła
  3. 3. D · Strukturą pozwalającą wstawiać i usuwać elementy na obu końcach
  4. 4. B · O(1)
  5. 5. B · Jest symetryczna względem głównej przekątnej
  6. 6. B · Zrównoważone binarne drzewo poszukiwań
  7. 7. A · By było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
  8. 8. D · [1, 3, 8, 5]

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