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

Czym jest graf ważony?

  1. AGrafem przechowywanym na dysku
  2. BGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
  3. CGrafem, który ma więcej krawędzi niż wierzchołków
  4. DGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
2.Łatwy

Czym jest liść w drzewie?

  1. AWęzłem z dokładnie jednym dzieckiem
  2. BWęzłem o największej wartości
  3. CWęzłem bez dzieci
  4. DWęzłem bez rodzica
3.Łatwy

Czym jest deque (kolejka dwustronna)?

  1. AKolejką posortowaną według priorytetu
  2. BStrukturą pozwalającą wstawiać i usuwać elementy na obu końcach
  3. CDwiema oddzielnymi kolejkami dzielącymi jedną tablicę
  4. DKolejką, która pozwala usuwać elementy tylko z końca
4.Średni

Dlaczego przechodzenie tablicy jest w praktyce często znacznie szybsze niż przechodzenie listy wiązanej o tej samej długości?

  1. AListy wiązane zawsze przechowują elementy na dysku
  2. BElementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora
  3. CPrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)
  4. DTablice wymagają mniej instrukcji do porównania wartości
5.Średni

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

  1. AStosu wywołań
  2. BBinarnego drzewa poszukiwań ramek
  3. CKolejki pamięci sterty
  4. DTablicy mieszającej funkcji
6.Średni

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

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

Jaki jest czas działania przeszukiwania wszerz (BFS) w grafie o V wierzchołkach przechowywanym jako macierz sąsiedztwa?

  1. AO(E log V)
  2. BO(V)
  3. CO(V + E)
  4. DO(V²)
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. ABy uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy
  2. BBo alokator pamięci może zwalniać pamięć tylko w ćwiartkach bloku
  3. CBy utrzymać tablicę posortowaną
  4. DBo zmniejszanie o połowę przy zapełnieniu w połowie spowodowałoby utratę elementów

Klucz odpowiedzi

  1. 1. D · Grafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  2. 2. C · Węzłem bez dzieci
  3. 3. B · Strukturą pozwalającą wstawiać i usuwać elementy na obu końcach
  4. 4. B · Elementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora
  5. 5. A · Stosu wywołań
  6. 6. A · O(log n)
  7. 7. D · O(V²)
  8. 8. A · 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.