Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
SPRA
WDZIAN
I
Imi¦
i
nazwisk
o:
Nr
indeksu:
Nr
grup
y:
Uw
aga!
Spra
wdzian
jest
testem
wielokrotnego
wyb
oru,
gdzie
wszystkie
mo»liw
e
k
om
binacje
o
dp
o
wiedzi
s¡
dopuszczalne
(tj.
zaró
wno
wszystkie
o
dp
o
wiedzi
p
opra
wne,
cz¦±¢
o
dp
o
wiedzi
p
opra
wna
jak
i
brak
o
dp
o
wiedzi
p
opra
wn
yc
h).
P
opra
wne
o
dp
o
wiedzi
nale»y
zaznaczy¢,
z
lew
ej
stron
y
k
artki,
sym
b
olem
+.
Natomiast
sym
b
ol
-
jak
i
brak
sym
b
olu
przy
o
dp
o
wiedzi
oznacza
o
dp
o
wied¹
niep
opra
wn¡.
Pytanie
jest
uznane
za
p
opra
wnie
rozwi¡zane
(tj.
+1pkt)
wtedy
i
t
ylk
o
wtedy
gdy
wszystkie
jego
o
dp
o
wiedzi
zaznaczone
s¡
p
opra
wnie.
yczym
y
p
o
w
o
dzenia
...
√
f (n) =
n lg n!
1.
Niec
h
,
wtedy
pra
wd¡
jest,
»e:
f (n) = O n2
(a)
[+]
,
√
f (n) = Ω (n n) (b)
[+]
,
f (n) = Θ 2lg √nn lg n (c)
[+]
.
f : N → R+ ∪ {0}
f (n) = 2n
2.
Rozw
a»m
y
funk
cj¦
p
ostaci
,
wtedy:
f (n) = Θ (c · f (n) + 1) c
(a)
[+]
,
gdzie
jest
p
ewn¡
do
datni¡
staª¡,
f (n) = O 1
(b)
[]
n! · f (n),
f (n) = Ω f (n)2
(c)
[]
.
3.
Które
z
p
oni»szyc
h
zda«
jest
pra
wdziw
e:
f (n) = O (n) g (n) = O (n) f (n) + g (n) = O n2
(a)
[+]
je»eli
i
,
to
,
f (n) = O n2 g (n) = O n2
f (n) + g (n) = O n2
(b)
[+]
je»eli
i
,
to
,
f (n) = Ω (n) g (n) = Ω (n) f (n) + g (n) = Ω n2
(c)
[]
je»eli
i
,
to
.
√
A
T (A, n) =
n
n
4.
Zaªó»m
y
,
»e
zªo»ono±¢
czaso
w
¡
p
ewnego
algorytm
u
okre±la
funk
cja
,
gdzie
jest
K
rozmiarem
dan
yc
h
w
ej±cio
wyc
h.
K
omputer
wyk
on
uje
rozw
a»an
y
algorytm
dla
dan
yc
h
rozmiaru
36
12
TK (A, 36) = 12
w
ci¡
gu
sekund,
tj.
.
St¡d:
TK (A, 49) = 16
(a)
[]
,
TK (A, 49) = 18
(b)
[]
,
100
K
(c)
[+]
w
ci¡
gu
sekund
k
omputer
wyk
ona
rozw
a»an
y
algorytm
dla
dan
yc
h
w
ej±cio
wyc
h
2500
rozmiaru
co
na
jwy»ej
.
5.
Rozw
a»m
y
nast¦puj¡cy
algorytm
void
Algorytm(int
n)
{
Alg1(n);
for
(i=0;i<n*n;i++)
{
Alg2(n);
}
}
Alg1
Alg2
T (Alg1n) = O (n lg n!) gdzie
oraz
s¡
algorytmami
o
zªo»ono±ci
czaso
w
ej
o
dp
o
wiednio
A (Alg2, n) = Θ (n) W (Alg2, n) = Θ n2
oraz
,
,
st¡d:
T (Algorytm, n) = Θ n2 lg n!
(a)
[]
,
1
P
a
w
eª
Remb
elski
Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
A (Algorytm, n) = O n2 lg n!
(b)
[+]
,
W (Algorytm, n) = Ω n2 lg n!
(c)
[+]
.
6.
Rozw
a»m
y
nast¦puj¡cy
algorytm
∈ N
int
Cos(int
n)
{
//
wp:
n
int
i=10;
≥
while
(i
0)
i=i+1;
∈ N
return
n;
//
wk:
n
}
wtedy:
(a)
[]
program
Cos
jest
caªk
o
wicie
p
opra
wn
y
w
strukturze
liczb
naturaln
yc
h,
(b)
[+]
program
Cos
jest
cz¦±cio
w
o
p
opra
wn
y
w
strukturze
liczb
naturaln
yc
h,
(c)
[+]
program
Cos
jest
caªk
o
wicie
p
opra
wn
y
w
strukturze
liczb
naturaln
yc
h
przy
zaªo»eniu,
»e
+ =def −
op
erator
do
da
w
ania
zdeniujem
y
jak
o
dejmo
w
anie,
tj.
.
7.
Rozw
a»m
y
nast¦puj¡cy
algorytm
int
Cos(int
n,
int
k)
{
int
i=k,
wynik=1;
≤
while
(i
n)
{
i=i*k;
wynik=wynik+1;
}
log
return
wynik;
//
wk:
wynik=
k n+1
}
wtedy:
k, n ∈ N
(a)
[]
program
Cos
jest
cz¦±cio
w
o
p
opra
wn
y
dla
w
arunku
p
o
cz¡tk
o
w
ego
,
n = kc
c ∈ N+
(b)
[+]
program
Cos
jest
cz¦±cio
w
o
p
opra
wn
y
dla
w
arunku
p
o
cz¡tk
o
w
ego
,
dla
i
k ∈ N \ {0, 1}, n = kc
c ∈ N \
(c)
[+]
program
Cos
jest
caªk
o
wicie
p
opra
wn
y
dla
w
arunku
p
o
cz¡tk
o
w
ego
,
dla
{0, 1, 2, . . . , k} k ∈ N \ {0, 1}
i
.
8.
Rozw
a»m
y
nast¦puj¡cy
algorytm
∈ N
int
Cos(int
n)
{
//
wp:
n
int
i=0,
s=0;
while
(i<n)
{
i=i+1;
s=s+i;
}
return
s;
}
wtedy:
s = i(i+1)
(a)
[+]
niezmiennikiem
p
¦tli
w
programie
Cos
jest
form
uªa
2
,
s = i(i−1)
(b)
[]
niezmiennikiem
p
¦tli
w
programie
Cos
jest
form
uªa
2
,
i ∈ N
s =
(c)
[+]
niezmiennikiem
p
¦tli
w
programie
Cos
jest
form
uªa
,
a
w
arunkiem
k
o«co
wym
n
X i.
i=0
9.
Które
ze
zda«
jest
pra
wdziw
e:
n
(a)
[]
spra
wdzenie,
czy
dan
y
elemen
t
nale»y
do
nieup
orz¡dk
o
w
anego
uniw
ersum
rozmiaru
wy-
√
O ( n)
maga
p
oró
wna«,
√n
(b)
[+]
spra
wdzenie,
czy
dan
y
elemen
t
nale»y
do
nieup
orz¡dk
o
w
anego
uniw
ersum
rozmiaru
O (n)
wymaga
p
oró
wna«,
2
P
a
w
eª
Remb
elski
Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
(c)
[+]
k
oszt
czaso
wy
sekw
encyjnego
algorytm
u
wyszuk
ania
elemen
tu
minimalnego
w
nieup
orz¡d-
106
106 − 1
k
o
w
an
ym
uniw
ersum
rozmiaru
wynosi
.
n = 2k
k ∈ N+
10.
Rozw
a»m
y
algorytm
turniej
dla
dan
yc
h
rozmiaru
,
gdzie
.
Które
z
p
oni»szyc
h
st
wierdze«
jest
za
wsze
sp
eªnione:
n + 1
(a)
[]
k
oszt
budo
wy
drzew
a
turnieju
wynosi
dokªadnie
p
oró
wna«,
lg n − 1
(b)
[]
elemen
t
2-gi
co
do
wielk
o±ci
p
o
jedynk
o
w
aª
si¦
dokªadnie
z
elemen
tami,
lg n
(c)
[+]
elemen
t
1-szy
co
do
wielk
o±ci
p
o
jedynk
o
w
aª
si¦
dokªadnie
z
elemen
tami.
n = 2k
k ∈ N+
11.
Rozw
a»m
y
iteracyjn
y
algorytm
dla
problem
u
min-max
i
dan
yc
h
rozmiaru
,
gdzie
,
wtedy:
(a)
[+]
algorytm
ten
jest
opt
ymaln
ym
rozwi¡zaniem
dla
rozw
a»anego
problem
u,
3 n ± c
c ≤ 3
(b)
[+]
zªo»ono±¢
czaso
w
¡
algorytm
u
mo»na
oszaco
w
a¢
przez
2
,
gdzie
,
O (lg n)
(c)
[+]
zªo»ono±¢
pami¦cio
w
a
algorytm
u
jest
rz¦du
.
12.
Które
ze
zda«
jest
pra
wdziw
e:
(a)
[]
spra
wdzenie
algorytmem
BinSearc
h,
czy
dan
y
elemen
t
nale»y
do
nieup
orz¡dk
o
w
anego
uni-
n
O (1)
w
ersum
rozmiaru
wymaga
p
oró
wna«,
(b)
[+]
spra
wdzenie
algorytmem
BinSearc
h,
czy
dan
y
elemen
t
nale»y
do
up
orz¡dk
o
w
anego
uni-
n
O (lg n)
w
ersum
rozmiaru
wymaga
p
oró
wna«,
1111
(c)
[+]
k
oszt
czaso
wy
algorytm
u
BinSearc
h
dla
p
opra
wn
yc
h
dan
yc
h
rozmiaru
wynosi
co
na
jwy»ej
12
p
oró
wna«.
Alg
n
13.
Zaªó»m
y
,
»e
p
ewien
algorytm
dla
dan
yc
h
w
ej±cio
wyc
h
rozmiaru
skªada
si¦
z
dw
ó
c
h
cz¦±ci:
√
•
n-krotne wyszukanie elementu minimalnego metod¡ sekwencyjn¡,
• lg n-krotne wyszukanie elementu minimalnego algorytmem Hoare'a.
Które
z
oszaco
w
a«
jest
p
opra
wne:
√
A (Alg, n) = Ω (n n) (a)
[+]
,
√
W (Alg, n) = O (n n lg n) (b)
[]
,
S (Alg, n) = Θ (1) (c)
[+]
.
14.
Który
z
p
oni»szyc
h
ci¡
gó
w
jest
p
opra
wn
ym
rezultatem
wyk
onania
pro
cedury
Split
dla
dan
yc
h
w
ej-
±cio
wyc
h
4, 7, 9, 11, 3, 5, 2, (a)
[]
4,2,3,11,9,5,7, (b)
[]
2,3,4,5,7,9,11, (c)
[+]
3,2,4,11,9,5,7.
n
n
15.
Rozw
a»m
y
wyszukiw
anie
elemen
tu
-tego
co
do
wielk
o±ci,
w
-elemen
to
w
ej
up
orz¡dk
o
w
anej
rosn¡co
tablicy
w
ej±cio
w
ej,
przy
zastoso
w
aniu
algorytm
u
Hoare'a
z
pro
cedur¡
p
o
dziaªu
zgo
dn¡
z
meto
d¡
P
artition,
wtedy:
O (1)
(a)
[]
zªo»ono±¢
czaso
w
¡
rozwi¡zania
w
t
ym
przypadku
szacujem
y
przez
,
O (n)
(b)
[]
zªo»ono±¢
czaso
w
¡
rozwi¡zania
w
t
ym
przypadku
szacujem
y
przez
,
O n2
(c)
[+]
zªo»ono±¢
czaso
w
¡
rozwi¡zania
w
t
ym
przypadku
szacujem
y
przez
.
16.
Pro
w
adz¡cy
za
j¦cia
¢wiczenio
w
e
z
ASD
jest:
(a)
lew
or¦czn
y
,
(b)
pra
w
or¦czn
y
,
Θ (1)
(c)
nie
wiem,
ale
z
dokªadno±ci¡
do
notacji
u»yw
a
jednej
r¦ki.
3
P
a
w
eª
Remb
elski