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. AWstawianie na początku
  2. BUstalenie długości tablicy o stałym rozmiarze
  3. COdczyt ostatniego elementu po indeksie
  4. DDostęp do 5. elementu
2.Łatwy

W jakiej kolejności przejście preorder (wzdłużne) drzewa binarnego odwiedza węzły?

  1. ALewe poddrzewo, potem węzeł, potem prawe poddrzewo
  2. BPoziomami, od góry
  3. CWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
  4. DLewe poddrzewo, potem prawe poddrzewo, potem węzeł
3.Łatwy

Na czym polega własność kopca maksymalnego (max-heap)?

  1. AKlucz każdego lewego dziecka jest większy lub równy kluczowi jego prawego rodzeństwa
  2. BWszystkie liście zawierają klucz maksymalny
  3. CKlucz każdego rodzica jest większy lub równy kluczom jego dzieci
  4. DKlucze są posortowane od lewej do prawej
4.Średni

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

  1. AFunkcji mieszającej
  2. BKolejki o stałym rozmiarze
  3. CPrzechodzenia grafu
  4. DBinarnego drzewa poszukiwań
5.Średni

Ile czasu zajmuje sprawdzenie, czy istnieje krawędź (u, v), przy użyciu macierzy sąsiedztwa?

  1. AO(E)
  2. BO(1)
  3. CO(log V)
  4. DO(V)
6.Średni

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

  1. AStosu
  2. BTablicy mieszającej
  3. CBinarnego drzewa poszukiwań
  4. DKolejki
7.Trudny

Dla każdego elementu tablicy chcesz znaleźć najbliższy większy element po jego prawej stronie, w łącznym czasie O(n). Która struktura pomaga?

  1. AKolejka przechowująca każdą parę elementów
  2. BBinarne drzewo poszukiwań budowane od nowa dla każdego elementu
  3. CTablica mieszająca wszystkich elementów
  4. DStos przechowujący elementy czekające na swoją odpowiedź
8.Trudny

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

  1. APosortować listę i szukać duplikatów
  2. BZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
  3. CPrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  4. DLiczyć węzły, aż liczba przekroczy pole z długością listy

Klucz odpowiedzi

  1. 1. A · Wstawianie na początku
  2. 2. C · Węzeł, potem lewe poddrzewo, potem prawe poddrzewo
  3. 3. C · Klucz każdego rodzica jest większy lub równy kluczom jego dzieci
  4. 4. B · Kolejki o stałym rozmiarze
  5. 5. B · O(1)
  6. 6. A · Stosu
  7. 7. D · Stos przechowujący elementy czekające na swoją odpowiedź
  8. 8. C · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają

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