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 najlepiej nadaje się do funkcji „cofnij” (undo) w edytorze tekstu?

  1. AGraf
  2. BZbiór mieszający
  3. CStos
  4. DKolejka
2.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

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

Co robi operacja peek (lub top) na stosie?

  1. AUsuwa wszystkie elementy ze stosu
  2. BZwraca element z wierzchołka bez usuwania go
  3. CUsuwa element z wierzchołka i go zwraca
  4. DZwraca element z dna stosu
4.Średni

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

  1. AStosu
  2. BKolejki
  3. CWyłącznie tablicy mieszającej
  4. DKopca
5.Ś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. ATablica mieszająca
  2. BZrównoważone binarne drzewo poszukiwań
  3. CStos
  4. DNieposortowana lista wiązana
6.Średni

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

  1. AKolejki o stałym rozmiarze
  2. BBinarnego drzewa poszukiwań
  3. CPrzechodzenia grafu
  4. DFunkcji mieszającej
7.Trudny

Którą własność musi spełniać drzewo czerwono-czarne?

  1. AKorzeń musi być czerwony
  2. BKażdy czerwony węzeł musi mieć czerwone dzieci, więc czerwone węzły zawsze tworzą nieprzerwane łańcuchy aż do liści
  3. CKażda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
  4. DKażdy węzeł musi być czerwony
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. C · Stos
  2. 2. A · Liczbą krawędzi z nim połączonych
  3. 3. B · Zwraca element z wierzchołka bez usuwania go
  4. 4. A · Stosu
  5. 5. B · Zrównoważone binarne drzewo poszukiwań
  6. 6. A · Kolejki o stałym rozmiarze
  7. 7. C · Każda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
  8. 8. B · 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.