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

Co robi operacja peek (lub top) na stosie?

  1. AZwraca element z wierzchołka bez usuwania go
  2. BUsuwa element z wierzchołka i go zwraca
  3. CUsuwa wszystkie elementy ze stosu
  4. DZwraca element z dna stosu
2.Łatwy

Czym jest graf ważony?

  1. AGrafem, który ma więcej krawędzi niż wierzchołków
  2. BGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  3. CGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
  4. DGrafem przechowywanym na dysku
3.Ł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. COdczyt pierwszego elementu
  4. DUsuwanie pierwszego elementu
4.Średni

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

  1. AO(log n), gdzie n to liczba słów
  2. BO(L × n)
  3. CO(L), niezależnie od liczby przechowywanych słów
  4. DO(n), gdzie n to liczba słów
5.Średni

Kolejkę zaimplementowano za pomocą dwóch stosów: push na stos „in”, a pop ze stosu „out”, który, gdy jest pusty, uzupełnia się ze stosu „in”. Jaki jest zamortyzowany koszt jednej operacji?

  1. AO(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(1)
6.Średni

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

  1. ATablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne
  2. BJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy
  3. CKopce nigdy nie zawierają więcej niż 100 elementów
  4. DWszystkie klucze w kopcu są równe
7.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. BBy utrzymać tablicę posortowaną
  3. CBo zmniejszanie o połowę przy zapełnieniu w połowie spowodowałoby utratę elementów
  4. DBo alokator pamięci może zwalniać pamięć tylko w ćwiartkach bloku
8.Trudny

Filtr Blooma potrafi odpowiedzieć na pytanie „czy ten element należy do zbioru?”:

  1. AZ możliwymi fałszywie ujemnymi wynikami, ale bez fałszywie dodatnich
  2. BZawsze dokładnie
  3. CZ możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych
  4. DTylko dla liczb

Klucz odpowiedzi

  1. 1. A · Zwraca element z wierzchołka bez usuwania go
  2. 2. B · Grafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  3. 3. A · Dostęp do elementu o indeksie i
  4. 4. C · O(L), niezależnie od liczby przechowywanych słów
  5. 5. D · O(1)
  6. 6. B · Jest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy
  7. 7. A · By uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy
  8. 8. C · Z możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych

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