Test z podstaw algorytmów

Odpowiedz Nowy wątek
2015-01-21 22:37
0

Mógłby ktoś sprawdzić czy dobrze rozwiązałem test .

Pytanie 1
W schemacie Von Neumana maszyny cyfrowej rozkaz jest umieszczany w:
a/ rejestrze rozkazów
B/ liczniku rozkazów
c/ rejestrze arytmometru

Pytanie 2
Operacje push oraz pop stosowane są w pracy ze strukturami :
a/ kolejki
b/ stosu
c/ pliku

Pytanie 3
Algorytm liniowego przeszukiwania listy uporządkowanej ma złożoność obliczeniową:
a/O(log2N)
b/O(Nlog2N)
c/O(N)

Pytanie 4
W strukturze kopca binarnego operacja wstawiania elementu ma miejsce w:
a/ liściu
b/ korzeniu
c/ to zależy czy kopiec jest typu MIN czy MAX

Pytanie 5
W kopcu binarnym pozycja węzła nadrzędnego w stosunku do węzła i-tego wyraża się wzorem:
a/└i/2┘
b/ i 2
c/ i
2 + 1

Pytanie 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];
}

Pytanie 7
Problem komiwojażera dla rozmiaru N miast ma złożoność obliczeniowa:
a/ 2N
b/ N!
c/ N2

Pytanie 8
Obliczanie mediany N liczb ma złożoność obliczeniową, w porównaniu do sortowania N liczb:
a/ mniejszą
b/ taką samą
c/ większą

Pytanie 9
Przedstawione obok drzewo jest przykładem:
A/ kopca
B/ drzewa BST
C/ drzewa B+

Pytanie 10
W drzewie BST o N elementach, czas wyszukiwania elementu o zadanej wartości klucza jest rzędu:
a/ O(N)
b/ O(log N)
c/ O(N * logN)

Moje odpowiedzi
1 a
2 a
3 c
4 a
5 a
6 b
7 b
8 c
9 b
10 b

W załączniku rysunek do pytania 9

Pozostało 580 znaków

2015-01-21 22:48

2 b
8 a albo b zależy o jakie sortowanie chodzi -> algorytm magicznych piątek jest liniowy więc mediana jest niewątpliwie liniowa, ale countingsort też, ale znów counting sort ma pewne ograniczenia. Nie wiem o jakich algorytmach mówiliście na zajeciach.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 2x, ostatnio: Shalom, 2015-01-21 22:50
A reszta jest dobrze - realmadryt 2015-01-22 00:35

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