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

Jaka jest cecha definiująca zbiór jako abstrakcyjny typ danych?

  1. APozwala na dostęp tylko z jednego końca
  2. BPrzechowuje elementy w kolejności posortowanej
  3. CPrzechowuje pary klucz–wartość
  4. DPrzechowuje elementy bez duplikatów
2.Łatwy

Co robi funkcja mieszająca w tablicy mieszającej?

  1. ASzyfruje wartości w tablicy
  2. BOdwzorowuje klucz na indeks w tablicy
  3. CLiczy, ile kluczy jest przechowywanych
  4. DSortuje klucze w tablicy
3.Łatwy

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

  1. ANieuporządkowana lista jednokierunkowa
  2. BKopiec
  3. CCiąg znaków
  4. DStos
4.Średni

Do czego służy węzeł wartownika (sentinel, węzeł pozorny) w liście wiązanej?

  1. APrzechowuje liczbę elementów
  2. BUpraszcza kod, usuwając przypadki szczególne na początku lub końcu listy
  3. CZapobiega wydłużaniu się listy ponad ustaloną maksymalną liczbę węzłów
  4. DSprawia, że lista jest posortowana
5.Średni

Jaka jest pesymistyczna wysokość binarnego drzewa poszukiwań z n węzłami, jeśli klucze są wstawiane w kolejności posortowanej?

  1. Alog₂ n
  2. Bn (drzewo staje się listą wiązaną)
  3. C1
  4. D√n
6.Ś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(1)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
7.Trudny

Jaką regułę muszą spełniać skrót i równość, by tablica mieszająca działała poprawnie?

  1. AWartości skrótu muszą być liczbami pierwszymi
  2. BRóżne klucze muszą mieć różne wartości skrótu
  3. CRówne klucze muszą mieć równe wartości skrótu
  4. DRówne wartości skrótu oznaczają równe klucze
8.Trudny

W buforze cyklicznym front == rear może oznaczać bufor pusty albo pełny. Jaki jest popularny sposób ich rozróżnienia?

  1. APrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
  2. BPrzechowywanie front i rear w tej samej zmiennej
  3. CCzyszczenie bufora za każdym razem, gdy front równa się rear, więc stan jest pusty
  4. DUstawienie rozmiaru bufora na potęgę dwójki

Klucz odpowiedzi

  1. 1. D · Przechowuje elementy bez duplikatów
  2. 2. B · Odwzorowuje klucz na indeks w tablicy
  3. 3. B · Kopiec
  4. 4. B · Upraszcza kod, usuwając przypadki szczególne na początku lub końcu listy
  5. 5. B · n (drzewo staje się listą wiązaną)
  6. 6. A · O(1)
  7. 7. C · Równe klucze muszą mieć równe wartości skrótu
  8. 8. A · Przechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji

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