Test z Lista połączona

Pytanie 1: Wstawianie lub usuwanie elementu w środku listy połączonej, wliczając w to znalezienie miejsca, ma zawsze stałą złożoność czasową O(1).

A. Tak

B. Nie

Wyjaśnienie: Zgodnie z materiałami, wstawianie/usuwanie w środku listy po znalezieniu poprzednika jest operacją O(1). Jednakże, samo znalezienie tego poprzednika wymaga złożoności czasowej O(n). Zatem, cała operacja wstawiania lub usuwania w środku listy, wliczając w to znalezienie miejsca, nie ma zawsze stałej złożoności O(1), lecz liniową O(n).

Pytanie 2: Próba odwołania się do danych lub wskaźnika 'następny' z węzła, którego wskaźnik ma wartość 'NULL', zamiast błędu wykonania programu, skutkuje jedynie ostrzeżeniem kompilatora.

A. Tak

B. Nie

Wyjaśnienie: Zgodnie z materiałami, próba odwołania się do danych lub wskaźnika 'następny' z węzła, którego wskaźnik ma wartość 'NULL', spowoduje błąd wykonania programu, a nie jedynie ostrzeżenie kompilatora.

Pytanie 3: Które stwierdzenia prawidłowo opisują operację wstawiania nowego elementu na początek jednokierunkowej listy połączonej, zgodnie z przedstawionymi materiałami?

A. Złożoność czasowa tej operacji wynosi O(1).

B. Wskaźnik 'następny' nowego węzła ustawia się na aktualną głowę listy, a następnie głowa listy zostaje zaktualizowana, aby wskazywała na nowy węzeł.

C. Operacja ta jest mniej efektywna niż wstawianie elementu na koniec listy bez wskaźnika ogona.

D. Wymaga przeszukania całej listy w celu znalezienia odpowiedniego miejsca dla nowego elementu.

Wyjaśnienie: Zgodnie z materiałami, wstawianie na początek listy jest operacją bardzo efektywną o złożoności czasowej O(1). Proces polega na tym, że nowy węzeł tworzy się, jego wskaźnik 'następny' ustawia się na aktualną głowę listy, a następnie głowa listy zostaje zaktualizowana, aby wskazywała na nowy węzeł. Operacja ta nie wymaga przeszukiwania całej listy. Wstawianie na koniec listy bez wskaźnika ogona ma złożoność O(n), co czyni je mniej efektywnym niż wstawianie na początek (O(1)).

Pytanie 4: Które zdanie najlepiej opisuje operację usunięcia elementu z końca jednokierunkowej listy połączonej, jeśli lista nie posiada wskaźnika na ogon?

A. Wskaźnik `głowa` jest przesuwany na następny węzeł, a usuwany węzeł jest zwalniany, co zajmuje O(1).

B. Należy przejść listę od głowy, aby znaleźć węzeł poprzedzający ostatni element. Następnie wskaźnik `następny` przedostatniego węzła ustawia się na `NULL`, a usuwany element jest zwalniany. Złożoność tej operacji wynosi O(n).

C. Tworzy się nowy węzeł, jego wskaźnik `następny` ustawia się na aktualną głowę listy, a następnie głowa listy zostaje zaktualizowana, aby wskazywała na nowy węzeł. Złożoność tej operacji wynosi O(1).

D. Wskaźnik `następny` ostatniego węzła ustawia się na nowy węzeł. Złożoność tej operacji wynosi O(1), ponieważ mamy bezpośredni dostęp do ogona.

Wyjaśnienie: Aby usunąć element z końca jednokierunkowej listy połączonej bez wskaźnika na ogon, należy przejść całą listę, aby znaleźć węzeł poprzedzający ostatni element. Dopiero wtedy można zaktualizować jego wskaźnik `następny` na `NULL` i usunąć ostatni element. To przeszukanie listy od początku do przedostatniego elementu sprawia, że złożoność czasowa tej operacji wynosi O(n). Opcja 0 opisuje usunięcie z początku listy. Opcja 2 opisuje wstawianie na początek listy. Opcja 3 opisuje wstawianie na koniec, ale zakłada posiadanie wskaźnika ogona, co zmienia złożoność na O(1).

Pytanie 5: Zgodnie z materiałami, sprawdzenie, czy wskaźnik nie jest `NULL` przed próbą dostępu do jego zawartości, jest opcjonalne i nie wpływa na stabilność programu.

A. Tak

B. Nie

Wyjaśnienie: Materiały wyraźnie stwierdzają: "Należy zawsze sprawdzać, czy wskaźnik nie jest `NULL` przed próbą dostępu do jego zawartości", aby uniknąć błędów wskaźnikowych i błędu wykonania programu.