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. BInsert
  3. CDequeue
  4. DEnqueue
2.Łatwy

Co robi operacja peek (lub top) na stosie?

  1. AZwraca element z dna stosu
  2. BUsuwa wszystkie elementy ze stosu
  3. CZwraca element z wierzchołka bez usuwania go
  4. DUsuwa element z wierzchołka i go zwraca
3.Ł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
4.Średni

Jaka jest pesymistyczna wysokość binarnego drzewa poszukiwań z n węzłami, jeśli klucze są wstawiane w kolejności posortowanej?

  1. A√n
  2. Blog₂ n
  3. Cn (drzewo staje się listą wiązaną)
  4. D1
5.Średni

Której struktury danych używa się, by sprawdzić, czy nawiasy w „{[()]}” są zrównoważone?

  1. AStosu
  2. BTablicy mieszającej
  3. CKolejki
  4. DBinarnego drzewa poszukiwań
6.Średni

Bufor cykliczny (ring buffer) jest powszechnie używany do implementacji:

  1. ABinarnego drzewa poszukiwań
  2. BPrzechodzenia grafu
  3. CKolejki o stałym rozmiarze
  4. DFunkcji mieszającej
7.Trudny

Która struktura danych umożliwia pamięć podręczną LRU (least recently used) z operacjami get i put w O(1)?

  1. AMapa mieszająca połączona z listą dwukierunkową
  2. BWyłącznie stos
  3. CWyłącznie binarne drzewo poszukiwań
  4. DPojedyncza posortowana tablica
8.Trudny

Wstawienie klucza do drzewa AVL sprawia, że lewe poddrzewo pewnego węzła staje się zbyt wysokie, a nowy klucz trafił do lewego poddrzewa jego lewego dziecka (przypadek lewo-lewo). Jaką naprawę się stosuje?

  1. APojedynczą rotację w lewo w niezrównoważonym węźle
  2. BRotację w lewo w dziecku, a potem rotację w prawo w węźle
  3. CPojedynczą rotację w prawo w niezrównoważonym węźle
  4. DPrzekolorowanie węzła i jego dziecka

Klucz odpowiedzi

  1. 1. C · Dequeue
  2. 2. C · Zwraca element z wierzchołka bez usuwania go
  3. 3. B · Dane i referencję do następnego węzła
  4. 4. C · n (drzewo staje się listą wiązaną)
  5. 5. A · Stosu
  6. 6. C · Kolejki o stałym rozmiarze
  7. 7. A · Mapa mieszająca połączona z listą dwukierunkową
  8. 8. C · Pojedynczą rotację w prawo w niezrównoważonym węźle

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