test_110203_form.pdf
(
93 KB
)
Pobierz
448430234 UNPDF
Imie i nazwisko:
Nr indeksu:
Pytania Odpowiedzi
1.
Jak a postac binarn a ma liczba dziesietna 40?
r
100000
r
101110
r
101000
2.
Jak a postac binarn a ma liczba dziesietna 99?
r
1101101
r
1100011
r
1111111
3.
Jak a liczb a dziesietn a jest liczba binarna 101010?
r
36
r
42
r
54
4.
Jak a liczb a dziesietn a jest liczba szesnastkowa 2F?
r
29
r
35
r
47
5.
Ile bitów zawiera 1 kilobajt?
r
1000
r
1024
r
8192
6.
Maszyna Turinga MT
Æh
{
q
0
}, {0, 1, ?},
±
i
, gdzie
±
Æ
{
h
q
0
, 1
i7!h
q
0
, 0, L
i
}, została
uruchomiona na tasmie z zapisem
?111000111?
z głowic a ustawion a na
pierwszej jedynce od prawej strony. Jaki bedzie zapis na tasmie po wykonaniu
programu?
r
?000000000?
r
?111000000?
r
?111111000?
r
?111000111?
r
?000000000?
r
?000111000?
r
?111000000?
r
?111000111?
8.
Jak a wartosc wyznacza schemat blokowy z ilustracji 1?
r
n
2
r
1
Å
. . .
Å
n
r
n
!
9.
Jak zadzia
ła dla n=3 algorytm schematu z ilustracji 1 po usunieciu bloku
x:=x+n
?
r
tak samo jak z tym blokiem
r
nie zako nczy działania
r
zwróci zero
r
tak samo jak z tym blokiem
r
nie zako nczy działania
r
zwróci zero
11.
Jak a złozonosc ma algorytm schematu z ilustracji 1?
r
O(1)
r
O(
n
)
r
O(
n
2
)
r
2
r
3
r
4
13.
Jaka jest wartosc
FuRek(14)
jesli
FuRek
jest zdefiniowana jak w ilustracji 2?
r
7
r
14
r
28
14.
Ile zamian wartosci zostanie wykonanych w pojedynczym przebiegu (od
prawej strony do lewej) algorytmu sortowania b abelkowego dla tablicy [9, 12, 2,
7, 15, 3, 11, 8], skoro sortujemy niemalej aco?
r
5
r
6
r
7
Ci ag dalszy na odwrocie. . .
1
7.
Maszyna Turinga z poprzedniego zadania została uruchomiona z głowic a
ustawion a na pierwszym zerze od prawej strony. Jaki bedzie zapis na tasmie po
wykonaniu programu?
10.
Jak zadz
iała dla n=3 algorytm schematu z ilustracji 1 po usunieciu bloku
i:=i+1
?
12.
Ile wywoła n rekurencyjnych nast api po wywołaniu funkcji
FuRek(20)
jesli
FuRek
jest zdefiniowana jak w ilustracji 2?
Pytania Odpowiedzi
15.
Kiedy sortowanie b abelkowe działa „w miejscu” (in situ)?
r
zawsze
r
w wyj atkowych przypadkach
r
nigdy
16.
Jaka jest srednia złozonosc algorytmu sortowania b abelkowego?
r
O(
n
)
r
O(
n
log
n
)
r
O(
n
2
)
17.
Jaki bedzie drugi element tablicy [3, 9, 11, 8, 15, 7, 2, 12] po pierwszym
przebiegu (tj. przed pierwszym podziałem) algorytmu sortowania szybkiego, jesli
jako wartosc podziału wybrano 8?
r
2
r
9
r
12
r
O(
n
)
r
O(
n
log
n
)
r
O(
n
2
)
19.
Czy sortowanie przez zliczanie w wersji
in situ
jest sortowaniem stabilnym?
r
nie
r
tak
20.
Czy kazde drzewo jest grafem?
r
nie
r
tak
21.
Czy kazdy graf jest drzewem?
r
nie
r
tak
22.
Jakiego rzedu jest maksymalna liczba krawedzi w grafie o
n
wezłach?
r
n
r
n
2
r
n
n
23.
Ile znaków
1
(niesko nczonosc) wyst api w tablicowej reprezentacji grafu
przedstawionego ilustracj a 3?
r
2
r
3
r
4
24.
Algorytmem Dijkstry szukamy dróg z wierzchołka
v
4
w grafie z ilustracji 3.
Droga do którego z wierzchołków zostanie wyznaczona jako ostatnia?
r
v
1
r
v
2
r
v
3
25.
Jaka bedzie suma długosci wszystkich krawedzi wybranych algorytmem
Dijkstry dla grafu z ilustracji 3 i wierzchołka startowego
v
2
?
r
5
r
7
r
8
26.
Ile wartosci zmieni sie w tablicy reprezentuj acej graf z ilustracji 3 po
pierwszej iteracji algorytmu Floyda?
r
0
r
1
r
2
r
(
v
2
v
3
)
r
(
v
2
v
5
)
r
(
v
4
v
5
)
28.
Jaka jest złozonosc czasowa algorytmu Prima? (n - liczba wierzchołków)
r
O(
n
)
r
O(
n
2
)
r
O(
n
3
)
29.
Która krawedz zostanie algorytmem Kruskala dla grafu z ilustracji 4 dodana
do wynikowego drzewa jako ostatnia?
r
(
v
2
v
3
)
r
(
v
2
v
5
)
r
(
v
4
v
5
)
30.
Jaka jest złozonosc czasowa w najgorszym przypadku dla algorytmu
Kruskala?
r
O(
n
log
n
)
r
O(
n
2
)
r
O(
n
2
log
n
)
2
18.
Jaka jest złozonosc czasowa algorytmu sortowania przez prosty wybór, gdy
dane wejsciowe s a posortowane? (
n
– liczba elementów w sortowanej tablicy)
27.
Algorytm Prima dla grafu z ilustracji 4 startuje od wierzchołka
v
1
. Która
krawedz zostanie dodana do wynikowego drzewa jako ostatnia?
Ilustracje
dane:n:integer
x:=0
i:=0
FunkcjaFuRek(n)
Dane:n-liczbaca“kowita
Wynik:liczbaca“kowita
De
nicja:
Je»elinmod2=0to
FuRek(n)
Ã
FuRek(ndiv2),
wprzeciwnymprzypadku:
FuRek(n)
Ã
n.
i
¸
n
x:=x+n
i:=i+1
nie
tak
wyniki:x
Ilustracja1:Schematblokowy
Ilustracja2:Funkcjarekurencyjna
v
1
v
1
4
6
4
1
3
v
5
2
v
2
v
4
v
2
1
1
6
5
7
4
2
2
v
3
v
4
1
v
3
Ilustracja3:Grafskierowany
Ilustracja4:Grafnieskierowany
3
Plik z chomika:
umkc
Inne pliki z tego folderu:
Podstawy algorytmów z przykładami w C.pdf
(3030 KB)
Wstep_do_Informatyki_-_Fulmanski__Sobieski.pdf
(3665 KB)
test_100121_rozw.pdf
(94 KB)
test_110203_form.pdf
(93 KB)
Inne foldery tego chomika:
> nie przypisane
Biologiczne podstawy zachowania
Filozofia
Komunikacja człowiek - komputer
Lingiwstyka kognitywna
Zgłoś jeśli
naruszono regulamin