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 stosie, która dodaje element na wierzchołek?

  1. AEnqueue
  2. BPush
  3. CPop
  4. DPeek
2.Łatwy

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

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

Jak elementy tablicy są przechowywane w pamięci?

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

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

  1. AZawsze malejącej
  2. BPoziomami
  3. CWstawiania
  4. DRosnącej (posortowanej)
5.Ś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ń
6.Średni

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

  1. APod indeksem 2i + 1
  2. BPod indeksem ⌊(i − 1) / 2⌋
  3. CPod indeksem ⌊i / 2⌋ + 1
  4. DPod indeksem i − 1
7.Trudny

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

  1. AZamianę go z korzeniem
  2. BUsunięcie całego poddrzewa
  3. CZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy
  4. DZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
8.Trudny

Złożoność czasowa operacji decrease-key w kopcu binarnym (przy znanej pozycji elementu) wynosi:

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n log n)

Klucz odpowiedzi

  1. 1. B · Push
  2. 2. A · Dane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
  3. 3. C · W jednym ciągłym bloku, jeden po drugim
  4. 4. D · Rosnącej (posortowanej)
  5. 5. D · Stosu wywołań
  6. 6. B · Pod indeksem ⌊(i − 1) / 2⌋
  7. 7. D · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
  8. 8. B · O(log n)

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