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 struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

  1. AStos
  2. BKolejka
  3. CLista wiązana
  4. DTablica mieszająca
2.Łatwy

W jakiej kolejności przejście preorder (wzdłużne) drzewa binarnego odwiedza węzły?

  1. ALewe poddrzewo, potem prawe poddrzewo, potem węzeł
  2. BPoziomami, od góry
  3. CWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
  4. DLewe poddrzewo, potem węzeł, potem prawe poddrzewo
3.Łatwy

Czym jest korzeń drzewa?

  1. AWęzeł o największej wartości
  2. BDowolny węzeł w środku
  3. CWęzeł bez dzieci
  4. DNajwyższy węzeł, który nie ma rodzica
4.Średni

Którego abstrakcyjnego typu danych używa algorytm Dijkstry do wyboru następnego wierzchołka do przetworzenia?

  1. AStosu
  2. BZbioru bez uporządkowania
  3. CKolejki priorytetowej typu min
  4. DKolejki FIFO
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

Sieć drogowa ma 100 000 skrzyżowań, z których każde łączy się z około 4 innymi. Która reprezentacja jest najodpowiedniejsza?

  1. AKopiec binarny krawędzi
  2. BMacierz sąsiedztwa
  3. CJedna posortowana tablica wierzchołków
  4. DListy sąsiedztwa
7.Trudny

Ile trwa wyszukanie dowolnego klucza w binarnym kopcu minimalnym o n elementach?

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

Co robi drzewo splay po każdym dostępie?

  1. APrzenosi odwiedzony węzeł do liścia
  2. BBuduje całe drzewo od nowa w formie zrównoważonej
  3. CPrzekolorowuje węzły na ścieżce wyszukiwania
  4. DRotacjami przenosi odwiedzony węzeł do korzenia

Klucz odpowiedzi

  1. 1. A · Stos
  2. 2. C · Węzeł, potem lewe poddrzewo, potem prawe poddrzewo
  3. 3. D · Najwyższy węzeł, który nie ma rodzica
  4. 4. C · Kolejki priorytetowej typu min
  5. 5. D · Stosu wywołań
  6. 6. D · Listy sąsiedztwa
  7. 7. A · O(n)
  8. 8. D · Rotacjami przenosi odwiedzony węzeł do korzenia

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