1. Zmienna L wskazuje na pierwszy wierzchołek niepustej, jednokierunkowej listy. Która z poniższych operacji ma stałą (O(1)) złożoność obliczeniową?
A. Dodanie wierzchołka na początek listy.
B. Dodanie wierzchołka na koniec listy.
C. Dodanie wierzchołka w środku listy.
D. Określenie ilości elementów na liście.
E. Zwolnienie wszystkich wierzchołków listy do zapasu pamięci.
2. Dla którego z poniższych drzew zarówno droga w sensie preorder jak i inorder da ten sam ciąg liter?
A. a B. a C. a D. a E. a
lm lm l lm lm
b c b b b b a a c
l
c
3. Które wyrażenie jest równoważne poniższemu fragmentowi kodu?
if (n > 0) n = -n;
if (n < 0) n = 0;
A. n = 0;
B. if (n > 0) n = 0;
C. if (n < 0) n = 0;
D. if (n > 0) n = -n;
else n = 0;
E. if (n < 0) n = 0;
else n = -n;
4. Co jest głównym powodem używania listy dwukierunkowej zamiast jednokierunkowej?
A. Na listę dwukierunkową potrzeba mniej pamięci niż na listę jednokierunkową.
B. Lista dwukierunkowa może być użyta do zaimplementowania stosu, podczas gdy lista jednokierunkowa – nie.
C. Liczba elementów może być określona łatwiej z użyciem listy dwukierunkowej niż jednokierunkowej.
D. Łatwiejsze usuwanie elementu z listy dwukierunkowej niż z jednokierunkowej.
E. Łatwiejsze dodawanie nowego elementu do listy dwukierunkowej niż jednokierunkowej.
5. Które z poniższych zdań jest prawdziwe dla wszystkich drzew poszukiwań binarnych?
A. Dla każdego wierzchołka liczba wierzchołków w lewym poddrzewie jest taka sama jak liczba wierzchołków w prawym poddrzewie.
B. Liczba liści jest taka sama jak liczba wierzchołków niebędących liśćmi.
C. W najgorszym przypadku czas potrzebny na znalezienie w drzewie danej wartości jest proporcjonalny do wysokości drzewa (najdłuższa ścieżka z korzenia do liścia).
D. Każdy wierzchołek ma albo 0 albo 2 następniki.
E. W najgorszym przypadku czas potrzebny na dodanie nowej wartości do drzewa o N wierzchołkach wynosi O(N2)
6. Następująca funkcja zwraca wartość true wtedy i tylko wtedy, gdy dana wartość key znajduje się w tablicy. Funkcja jednak nie jest napisana prawidłowo. (Numery linii kodu zostały dodatkowo oznaczone).
1. bool Search(const spvector <int> & A, int key)
2. {
3. int k=0;
4. while ((k < A.length())&&(A(k) != key)) k++;
5. if (A(k) == key) return true;
6. return false;
7. }
Które z poniższych zdań jest prawdziwe?
A. Nastąpi błąd kompilacji, ponieważ operator && użyty w linii 4 odnosi się do wyrażeń nie-boolowskich.
B. Wyrażenie "A(k) != key" w linii 4 spowoduje błąd wykonania funkcji, kiedy tablica A zawiera wartość key.
C. Wyrażenie "A(k) != key" w linii 4 spowoduje błąd wykonania funkcji, kiedy tablica A nie zawiera wartości key.
D. Wyrażenie "A(k) == key" w linii 5 spowoduje błąd wykonania funkcji, kiedy tablica A zawiera wartość key.
E. Wyrażenie "A(k) == key" w linii 5 spowoduje błąd wykonania funkcji, kiedy tablica A nie zawiera wartości key.
Pytania 7 i 8 dotyczą projektu struktury danych do przechowywania informacji na temat, które siedzenia w samolocie są zajęte. Samolot ma N rzędów; w każdym rzędzie są cztery siedzenia. Pod uwagę bierze się dwie struktury danych:
Struktura 1: Dwuwymiarowa tablica zmiennych boolowskich. Rzędy tablicy odpowiadają rzędom w samolocie. Kolumny tablicy odpowiadają siedzeniom w każdym z rzędów w samolocie. Element tablicy ma wartość true wtedy i tylko wtedy, gdy odpowiadające mu miejsce jest zajęte.
Struktura 2: Jednowymiarowa tablica obiektów utworzonych na podstawie struktury. Każdy z tych obiektów zawiera dwie zmienne całkowite: numer rzędu i numer siedzenia w rzędzie. Tablica początkowo ma rozmiar 0. Za każdym razem, gdy jakieś miejsce jest rezerwowane, tablica jest rozszerzana o jeden element, w którym zapisywane są numery nowo zajmowanego rzędu i siedzenia. Zapis odbywa się w ostatnim elemencie tablicy.
7. Pod jakim warunkiem Struktura 1 potrzebuje mniej zapasu pamięci niż Struktura 2?
A. Brak siedzeń zajętych.
B. Wszystkie siedzenia są zajęte.
C. Tylko siedzenia w pierwszym rzędzie są zajęte.
D. Tylko siedzenia w ostatnim rzędzie są zajęte.
E. Struktura 1 nigdy nie zużyje mniej pamięci niż Struktura 2.
8. Załóżmy, że czas potrzebny do powiększenia rozmiaru tablicy z N do N+1 jest proporcjonalny do N. Która z poniższych operacji może zostać zaimplementowana efektywniej z użyciem Struktury 1 niż Struktury 2?
I. Określenie ile miejsc jest zajętych.
II. Określenie czy dane miejsce (znane numery rzędu i siedzenia) jest zajęte.
III. Zarezerwowanie miejsca w na pół wypełnionym samolocie.
A. Tylko I.
B. Tylko II.
C. Tylko III.
D. I i II.
E. II i III.
9. Które z poniższych zdań dotyczących warunków wywołania funkcji jest prawdziwe?
A. Muszą być dostarczone przez autora funkcji, inaczej funkcja się nie skompiluje.
B. Są tłumaczone przez kompilator jako sumy kontrolne.
C. Dostarczają użytkownikom funkcji informacji określających, jakie warunki są spełnione, kiedy funkcja jest wywoływana.
D. Dostarczają autorowi funkcji informacji określających, jak wygląda implementacja.
E. Dostarczają informacji, które moduły przekazujące parametry są używane prze funkcję.
10. Które z poniższych zdań najlepiej opisuje, co powinien zrobić destruktor klasy?
A. Odinicjować wszystkie składniki klasy.
B. Uczynić wszystkie funkcje klasy niezdolnymi do dalszej pracy.
C. Wydrukować wiadomość o błędzie i zatrzymać wykonywanie programu.
D. Zwrócić do zapasu pamięci wszystkie dynamicznie zaalokowane składniki klasy.
E. Wszystkie wskaźniki należące do klasy ustawić na NULL.
Pytania 11 i 12 dotyczą następującej definicji klasy IntList, używanej do reprezentacji uporządkowanej listy liczb całkowitych:
class IntList {
public:
IntList(); //konstruktor
void AddToEnd(int k); //dodaje k na koniec listy
private:
struct ListNode {
int data;
ListNode *next;
};
ListNode *myFirst;
ListNode *MyLast;
Pusta lista jest reprezentowana przez IntList, gdzie myFirst i myLast wskazują na NULL. Niepusta lista jest reprezentowana przez IntList, gdzie:
§ Obiekty są przechowywane w liście połączonej;
§ myFirst wskazuje na pierwszy wierzchołek listy połączonej;
§ myLast wskazuje na ostatni wierzchołek listy połączonej.
Następująca definicja jest błędną implementacją funkcji AddToEnd z klasy IntList:
void IntList::AddToEnd(int k)
//warunki początkowe: lista zawiera wartości v1 v2 … vn, n ≥ 0
// myFirst wskazuje na v1
// myLast wskazuje na vn
//warunki końcowe: lista zawiera wartości v1 v2 … vn k
// myLast wskazuje na k
{
ListNode *tmp = new ListNode;
tmp->data = k;
tmp->next = NULL;
if (myLast != NULL) myLast->next = tmp;
myLast = tmp;
}
11. Kiedy powyższa wersja funkcji AddToEnd nie będzie działać poprawnie?
A. Zawsze.
B. Kiedy lista jest inicjowana jako pusta.
C. Kiedy lista jest inicjowana jako niepusta.
D. Kiedy lista po inicjacji zawiera jeden element.
E. Kiedy dana wartość k jest już na liście.
12. Która ze złożoności obliczeniowych najlepiej opisuje działanie powyższej funkcji AddToEnd (dla listy zawierającej początkowo n elementów)?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
E. O(n2)
13. Drzewa binarne są implementowane przez poniższą deklarację:
struct TreeNode {
TreeNode *left;
TreeNode *right;
Dana jest następująca funkcja:
int Mystery(TreeNode *T)
if (T == NULL) return 0;
return (1 + Mystery(T->left) + Mystery(T->right));
Które z poniższych zdań najlepiej określa, co funkcja Mystery robi?
A. Zawsze zwraca wartość 0.
B. Zwraca liczbę wierzchołków w drzewie T.
C. Zwraca liczbę liści w drzewie T.
D. Zwraca liczbę nie-liści w drzewie T.
E. Zwraca wysokość drzewa ...
amigo47