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 elementy tablicy są przechowywane w pamięci?

  1. AW jednym ciągłym bloku, jeden po drugim
  2. BW losowych miejscach wybranych przez funkcję mieszającą
  3. CW drzewie stron pamięci
  4. DW rozproszeniu, połączone wskaźnikami
2.Łatwy

Która operacja ma złożoność O(1) dla tablicy, ale O(n) dla listy jednokierunkowej?

  1. ADostęp do elementu o indeksie i
  2. BWstawianie na początku
  3. CUsuwanie pierwszego elementu
  4. DOdczyt pierwszego elementu
3.Łatwy

Co definiuje drzewo binarne?

  1. AKażdy węzeł ma co najwyżej dwoje dzieci
  2. BKażdy węzeł ma dokładnie dwoje dzieci
  3. CDrzewo ma dokładnie dwa poziomy
  4. DKażdy węzeł przechowuje liczbę binarną
4.Średni

Której struktury danych używa działający program do śledzenia aktywnych wywołań funkcji i ich zmiennych lokalnych?

  1. ATablicy mieszającej funkcji
  2. BKolejki pamięci sterty
  3. CBinarnego drzewa poszukiwań ramek
  4. DStosu wywołań
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 preorder?

  1. A1 2 3 4 5
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 4 5 3
6.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

  1. AWyszukiwanie w czasie stałym w każdym przypadku
  2. BŻe żaden węzeł nie ma dwojga dzieci
  3. CPrzechowywanie kluczy w kolejności wstawiania
  4. DWysokość O(log n) dzięki równoważeniu
7.Trudny

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

  1. AZnajdowanie mediany w O(1)
  2. BZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
  3. CSortowanie tablicy i wyszukiwanie binarne
  4. DWstawianie elementów na dowolnej pozycji
8.Trudny

Tablica dynamiczna podwaja rozmiar, gdy jest pełna. Dlaczego wiele implementacji zmniejsza ją dopiero przy zapełnieniu w jednej czwartej, a nie w połowie?

  1. ABo zmniejszanie o połowę przy zapełnieniu w połowie spowodowałoby utratę elementów
  2. BBy utrzymać tablicę posortowaną
  3. CBy uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy
  4. DBo alokator pamięci może zwalniać pamięć tylko w ćwiartkach bloku

Klucz odpowiedzi

  1. 1. A · W jednym ciągłym bloku, jeden po drugim
  2. 2. A · Dostęp do elementu o indeksie i
  3. 3. A · Każdy węzeł ma co najwyżej dwoje dzieci
  4. 4. D · Stosu wywołań
  5. 5. D · 1 2 4 5 3
  6. 6. D · Wysokość O(log n) dzięki równoważeniu
  7. 7. B · Zapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
  8. 8. C · By uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy

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