Test z Stos (stack)

Pytanie 1: Materiały zawierają szczegółowy przykład implementacji operacji `peek` dla stosu opartego na tablicy.

A. Tak

B. Nie

Wyjaśnienie: Materiały opisują, czym jest operacja `peek` i jakie ma zastosowanie, ale w sekcji 'Implementacja Stosu za Pomocą Tablicy' zawierają szczegółowe przykłady implementacji jedynie dla operacji `push` i `pop`, a nie dla `peek`.

Pytanie 2: W implementacji stosu za pomocą tablicy, zmienna `wierzchołek` (lub `top`) pełni kluczową rolę w zarządzaniu elementami. Które stwierdzenia prawidłowo opisują jej zachowanie podczas operacji `push` i `pop`?

A. Podczas operacji `push` zmienna `wierzchołek` jest najpierw zwiększana o 1, a następnie nowy element jest umieszczany w `tablicaStosu[wierzchołek]`.

B. Podczas operacji `pop` element jest najpierw pobierany z `tablicaStosu[wierzchołek]`, a następnie zmienna `wierzchołek` jest zmniejszana o 1.

C. Początkowa wartość zmiennej `wierzchołek` dla pustego stosu to 0.

D. Przed operacją `push` sprawdza się, czy `wierzchołek` jest większy lub równy maksymalnemu rozmiarowi tablicy, aby wykryć przepełnienie.

Wyjaśnienie: Zgodnie z opisem implementacji stosu za pomocą tablicy: - Dla operacji `push`: "Zwiększ `wierzchołek` o 1 (`wierzchołek = wierzchołek + 1`). Umieść `element` w `tablicaStosu[wierzchołek]`." Zatem opcja 0 jest prawidłowa. - Dla operacji `pop`: "Pobierz `element` z `tablicaStosu[wierzchołek]`. Zmniejsz `wierzchołek` o 1 (`wierzchołek = wierzchołek - 1`)." Zatem opcja 1 jest prawidłowa. - Początkowa wartość `wierzchołek` dla pustego stosu to -1, a nie 0, co sprawia, że opcja 2 jest nieprawidłowa. - Przed operacją `push` sprawdza się, czy `wierzchołek` jest mniejszy niż `N-1`, a nie czy jest większy lub równy maksymalnemu rozmiarowi, co sprawia, że opcja 3 jest nieprawidłowa (warunek na pełny stos to `wierzchołek < N-1`, co oznacza, że stos jest pełny, gdy `wierzchołek` osiągnie `N-1`).

Pytanie 3: Stos może być użyty do sprawdzenia, czy nawiasy w wyrażeniach matematycznych są poprawnie zagnieżdżone i sparowane.

A. Tak

B. Nie

Wyjaśnienie: Stos jest wykorzystywany do sprawdzania poprawności nawiasów. Gdy napotykany jest nawias otwierający, jest on wpychany na stos. Kiedy pojawia się nawias zamykający, element jest ściągany ze stosu i sprawdzane jest, czy odpowiada on nawiasowi otwierającemu. Jeśli stos jest pusty na końcu lub nawiasy nie pasują, wyrażenie jest niepoprawne.

Pytanie 4: W przeglądarkach internetowych, kiedy użytkownik klika przycisk „Wstecz”, przeglądarka dodaje poprzednio odwiedzoną stronę na stos.

A. Tak

B. Nie

Wyjaśnienie: Materiały wskazują, że każda odwiedzona strona jest dodawana na stos. Natomiast kiedy użytkownik klika „Wstecz”, przeglądarka pobiera (ściąga) ostatnio odwiedzoną stronę ze stosu i wyświetla ją, a nie dodaje.

Pytanie 5: Które z poniższych stwierdzeń najlepiej wyjaśnia, dlaczego podstawowe operacje stosu (takie jak `push`, `pop` i `peek`) charakteryzują się stałą złożonością czasową O(1)?

A. Operacje te zawsze dotyczą tylko jednego, konkretnego miejsca w pamięci (wierzchołka stosu), bez konieczności przeszukiwania czy przesuwania innych elementów.

B. Złożoność czasowa jest stała, ponieważ stos jest zawsze implementowany za pomocą tablic statycznych.

C. Czas potrzebny na wykonanie tych operacji jest niezależny od liczby elementów znajdujących się na stosie.

D. Stos zawsze przechowuje elementy posortowane, co ułatwia szybki dostęp do wierzchołka.

Wyjaśnienie: Podstawowe operacje stosu (`push`, `pop`, `peek`) mają stałą złożoność czasową O(1), ponieważ czas potrzebny na ich wykonanie jest niezależny od liczby elementów znajdujących się na stosie. Jest to możliwe, ponieważ operacje te zawsze dotyczą tylko jednego, konkretnego miejsca w pamięci (wierzchołka stosu), bez konieczności przeszukiwania czy przesuwania innych elementów. Opcja dotycząca implementacji za pomocą tablic statycznych jest nieprawdziwa, ponieważ stos może być również implementowany za pomocą listy łączonej. Stos nie wymaga sortowania elementów, a jedynie dostępu do wierzchołka.