Test
1 W zapisie heksadecymalnym liczba FFFE odpowiada liczbie całkowitej ze znakiem
a) -1
b) -2
c) 2^16- 1
2 Wyszukiwanie zadanej wartości klucza w liście N elementów ma złożoność obliczeniową
a) O(log2N)
b) O(N)
c) O(N*log2N)
3 Algorytm sortowania metodą scalania ma złożoność obliczeniową
a) O(log2N)
b) O(N*log2N)
c) O(N)
4 Alicja wysłała wiadomość do Bartka stosując algorytm szyfrowania RSA. Bartek do odczytania tej wiadomości stosuje
a) klucz publiczny Bartka
b) klucz publiczny Alicji
c) klucz prywatny Bartka
5 W kopcu binarnym typu MIN pozycja węzła potomnego w stosunku do węzła i-tego wyraża się wzorem
a) i/2
b) i2
c) i2-1
6 W strukturze stosu (realizowanego jako tablica o
rozmiarze N ) operację pobierania elementu ze
stosu niepustego można opisać w C++
(gdzie top oznacz szczyt stosu):
a/ int pop()
{
return Stos[--top];
}
b) int pop()
{
return Stos[top--];
}
c) int pop()
{
return Stos[top];
}
7 Problem sortowania N losowych elementów metodą QuickSort ma złożoność obliczeniową
a) O(N^2)
b) O(log N)
c) O(N*log N)
8 Obliczanie mediany ciągu N liczb ma złożoność obliczeniową, w porównaniu do sortowania (metodą scalenia) ciągu N liczb:
a/ mniejszą
b/ taką samą
c/ większą
9 Przedstawione obok drzewo jest przykładem:
A/ kopca
B/ drzewa BST
C/ zrównoważonego drzewa binarnego
10 W zrównoważonym drzewie BST o N elementach czas wyszukiwania elementu o zadanej wartości klucza jest rzędu
a) O(N)
b) O(logN)
c) O(N*logN)
do pytania 9 zdj w załączniku
Odpowiedzi
1 b
2 b
3 c
4 c
5 b
6 b
7a
8 a
9 c
10 b