Test - Algorytmy i struktury danych

Odpowiedz Nowy wątek
2016-01-19 00:44
0

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) i
2-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

Pozostało 580 znaków

2016-01-19 00:52
0
  1. Niejednoznaczne bo nie wiadomo co to za kodowanie (znak-liczba, u1, u2) i nie wiadomo czy little czy big endian
  2. b) jedyne algorytmy sortowania o złożoności O(n) to takie które nie są oparte o porównywanie elementów (jak zliczanie). Jeśli porównujesz elementy to dolne asymptotyczne ograniczenie na czas działania algorytmu to O(nlogn)

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
a reszta dobrze ? - Ronaldo7 2016-01-19 00:55
a tak dokładniej ? - Ronaldo7 2016-01-19 00:57
No tak na oko reszta jest ok ale jest godzina 1:00 więc istnieje szansa że mógłbym sie pomylić :P - Shalom 2016-01-19 01:02
ok dzieki jak mozesz to jeszcze za dnia rzuc okiem - Ronaldo7 2016-01-19 01:04

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0