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. BOdczyt ostatniego elementu po indeksie
  3. CDostęp do 5. elementu
  4. DUstalenie długości tablicy o stałym rozmiarze
2.Łatwy

Co przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

  1. AŁączną liczbę krawędzi w grafie
  2. BListę jego sąsiednich wierzchołków
  3. CWiersz V wartości logicznych
  4. DNajkrótszą ścieżkę do każdego innego wierzchołka
3.Łatwy

W binarnym drzewie poszukiwań wartości w lewym poddrzewie węzła są:

  1. AW losowej kolejności
  2. BWiększe od wartości węzła
  3. CMniejsze od wartości węzła
  4. DRówne wartości węzła
4.Ś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. ANieposortowana lista wiązana
  2. BZrównoważone binarne drzewo poszukiwań
  3. CTablica mieszająca
  4. DStos
5.Średni

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

  1. AJest symetryczna względem głównej przekątnej
  2. BJest zawsze górnotrójkątna
  3. CKażdy wiersz ma dokładnie jedną jedynkę
  4. DNa jej głównej przekątnej zawsze są jedynki
6.Ś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. BPrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)
  3. CTablice wymagają mniej instrukcji do porównania wartości
  4. DElementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora
7.Trudny

Która struktura pozwala obliczyć maksimum każdego okna o rozmiarze k w tablicy w łącznym czasie O(n)?

  1. ALista jednokierunkowa elementów okna
  2. BPosortowana tablica aktualizowana przez przesuwanie
  3. CKopiec minimalny budowany od nowa dla każdego okna
  4. DDeque przechowująca indeksy w kolejności malejących wartości
8.Trudny

W BST z korzeniem 50, lewym poddrzewem 30 (dzieci 20, 40) i prawym poddrzewem 70 (dzieci 60, 80) usuwa się korzeń przy użyciu następnika w porządku inorder. Który klucz zostaje nowym korzeniem?

  1. A60
  2. B40
  3. C70
  4. D80

Klucz odpowiedzi

  1. 1. A · Wstawianie na początku
  2. 2. B · Listę jego sąsiednich wierzchołków
  3. 3. C · Mniejsze od wartości węzła
  4. 4. B · Zrównoważone binarne drzewo poszukiwań
  5. 5. A · Jest symetryczna względem głównej przekątnej
  6. 6. D · Elementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora
  7. 7. D · Deque przechowująca indeksy w kolejności malejących wartości
  8. 8. A · 60

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