test_100121_rozw.pdf
(
94 KB
)
Pobierz
Imie i nazwisko:
Nr indek
su:
email:
Miejsce: od okna:
, od tablicy:
Pytania
Odpowiedzi
r
111111
r
1000000
r
3
1000001
1.
Jak a postac binarn a ma liczba dziesietna 65?
r
3
1100100
r
1100010
r
10000000
2.
Jak a postac binarn a ma liczba dziesietna 100?
r
48
r
3
54
r
60
3.
Jak a liczb a dziesietn a jest liczba binarna 110110?
4.
Jak a liczb a dziesietn a jest liczba szesnastkowa 100?
r
100
r
160
r
3
256
5.
1 MB (megabajt) to . . .
r
1000000 B
r
1024000 B
r
3
1048576 B
r?000000000?
r?000111000?
r
3
?000111111?
r?111000111?
6.
Maszyna Turinga MT
Æh
{
q
0
}, {0, 1, ?},
±
i
, gdzie
±
Æ
{
h
q
0
, 0
i7!h
q
0
, 1, L
i
}, została
uruchomiona na tasmie z zapisem
?000111000?
z głowic a ustawion a na
pierwszym zerze od prawej strony. Jaki bedzie zapis na tasmie po wykonaniu
programu?
r?000000000?
r?000111000?
r?111000000?
r
3
?111000111?
7.
Maszyna Turinga z poprzedniego zadania 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
n pocz atkowych naturalnych
r
n pocz atkowych parzystych
r
3
parzystych mniejszych od n
8.
Sume jakich liczb wyznacza schemat blokowy z ilustracji 1?
r
tak samo jak z tym blokiem
r
3
zwróci zero
r
nie zako nczy działania
9.
Jak zadzi
ała dla n=5 algorytm schematu z ilustracji 1 po usunieciu bloku
s:=s+i
?
10.
Jak zadz
iała dla n=5 algorytm schematu z ilustracji 1 po usunieciu bloku
i:=i+2
?
r
tak samo jak z tym blokiem
r
zwróci zero
r
3
nie zako nczy działania
r
3
3
r
5
r
6
11.
Ile mnoze n trzeba wykonac by wyznaczyc wartosc wielomianu
2
x
3
Å
3
x
2
¡
5
x
Å
1 schematem Hornera?
12.
Ile wywoła n rekurencyjnych nast api po wywołaniu funkcji
FuRek(12)
jesli
FuRek
jest zdefiniowana jak w ilustracji 2?
r
1
r
2
r
3
3
13.
Jaka jest wartosc
FuRek(6)
jesli
FuRek
jest zdefiniowana jak w ilustracji 2?
r
2
r
3
3
r
4
r
3
r
3
5
r
7
Ci ag dalszy na odwrocie. . .
14.
Ile zamian wartosci zostanie wykonanych w pojedynczym przebiegu (od
lewej strony do prawej) algorytmu sortowania b abelkowego dla tablicy [12, 3, 4,
17, 5, 21, 2, 1], skoro sortujemy niemalej aco?
1
Pytania
Odpowiedzi
r
O(1)
r
3
O(
n
)
r
O(
n
2
)
15.
Jaka jest złozonosc algorytmu sortowania b abelkowego, gdy dane wejsciowe
s a posortowane? (
n
– liczba elementów w sortowanej tablicy)
r
3
2
r
4
r
17
16.
Jaki bedzie czwarty element tablicy [12, 3, 4, 17, 5, 21, 2, 1] po pierwszym
przebiegu (tj. przed pierwszym podziałem) algorytmu sortowania szybkiego, jesli
jako wartosc podziału wybrano 12?
r
3
tak
r
nie
17.
Czy sortowanie szybkie działa „w miejscu” (in situ)?
18.
Jaka jest złozonosc czasowa algorytmu sortowania szybkiego, gdy dane
wejsciowe s a posortowane, a element podziału jest wybierany jako pierwszy
element z tablicy? (
n
– liczba elementów w sortowanej tablicy)
r
O(
n
)
r
O(
n
log
n
)
r
3
O(
n
2
)
19.
Jaka jest złozonosc czasowa algorytmu sortowania przez zliczanie
r
3
O(
n
)
r
O(
n
log
n
)
r
O(
n
2
)
r
3
O(log
n
)
r
O(
n
)
r
O(
n
log
n
)
20.
Jaka jest złozonosc czasowa operacji wyszukiwania w wywazonym drzewie
uporz adkowanym? (
n
– liczba wezłów drzewa)
r
3
tak
r
nie
21.
Czy kazde drzewo rozpinaj ace graf jest spójne?
r
tak
r3
nie
22.
Czy drzewo moze zawierac cykl?
r
1
r
2
r
3
4
23.
Ile znaków
1
(niesko nczonosc) wyst api w tablicowej reprezentacji grafu
przedstawionego ilustracj a 3?
r
(
v
1
v
2
)
r
3
(
v
2
v
3
)
r
(
v
4
v
5
)
25.
Jaka jest złozonosc czasowa algorytmu Prima? (n - liczba wierzchołków)
r
O(
n
)
r
3
O(
n
2
)
r
O(
n
3
)
24.
Algorytm Prima dla grafu z ilustracji 4 startuje od wierzchołka
v
1
. Która
krawedz zostanie dodana do wynikowego drzewa jako ostatnia?
r3
v
2
r
v
3
r
v
5
26.
Który wierzchołek zostanie algorytmem Kruskala dla grafu z ilustracji 4
dodany do wynikowego drzewa jako ostatni?
27.
Graf nieskierowany ma
n
wierzchołków. Kazdy wierzchołek jest ko ncem
trzech krawedzi. Jaka jest złozonosc czasowa algorytmu Kruskala dla takiego
grafu?
r
O(
n
)
r
3
O(
n
log
n
)
r
O(
n
2
log
n
)
r
v
1
r
v
2
r
3
v
3
28.
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
7
r
3
8
r
10
29.
Jaka bedzie suma długosci wszystkich krawedzi wybranych algorytmem
Dijkstry dla grafu z ilustracji 3 i wierzchołka startowego
v
1
?
r
3
0
r
1
r
2
30.
Ile wartosci zmieni sie w tablicy reprezentuj acej graf z ilustracji 3 po
pierwszej iteracji algorytmu Floyda?
2
Ilustracje
dane:n:integer
s:=0
FunkcjaFuRek(n)
Dane:n-liczbaca“kowita
Wynik:liczbaca“kowita
De
nicja:
Je»elin
·
1to
FuRek(n)
Ã
0.
Je»elinmod3=0to
FuRek(n)
Ã
2+FuRek(ndiv3).
Je»elinmod2=0to
FuRek(n)
Ã
1+FuRek(ndiv2).
FuRek(n)
Ã
-1.
i:=2
nie
i>n s:=s+i i:=i+2
tak
wyniki:s
Ilustracja1:Schematblokowy
Ilustracja2:Funkcjarekurencyjna
v
1
v
1
4
4
4
2
3
5
3
v
5
v
2
v
4
v
2
1
7
5
4
7
3
2
2
v
4
v
3
v
3
1
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