Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
SPRA
WDZIAN
I
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
...
n = 2k
k ∈ N+
1.
Zaªó»m
y
,
»e
ci¡
g
w
ej±cio
wy
dla
algorytm
u
MergeSort
skªada
si¦
z
elemen
tó
w,
gdzie
,
wtedy:
T (n) = Θ (n lg n) (a)
[+]
,
S (n) = Ω (n)
(b)
[]
,
k ± 1
(c)
[+]
drzew
o
p
o
dziaªu
ci¡
gu
w
ej±cio
w
ego
dla
rozw
a»anego
algorytm
u
jest
wysok
o±ci
.
n ∈ N
2.
Co
jest
w
arunkiem
k
o«co
wym
p
oni»szego
algorytm
u
rekurencyjnego, gdzie
?
int
Cos(int
n)
{
if
(n==0)
return
0;
return
Cos(n-1)+n;
}
Cos (n) = n2
(a)
[]
.
Cos (n) = 0 + 1 + 2 + . . . + (n − 1) + n (b)
[+]
.
n · Cos (n) = O n2
(c)
[]
.
3.
Rozw
a»m
y
algorytm
rekurencyjn
y
z
zadania
2,
wtedy:
n2
(a)
[+]
zªo»ono±¢
czaso
w
a
algorytm
u
jest
co
na
jwy»ej
rz¦du
,
√n
(b)
[+]
zªo»ono±¢
czaso
w
a
algorytm
u
jest
co
na
jmniej
rz¦du
,
O (1)
(c)
[]
zªo»ono±¢
pami¦cio
w
a
algorytm
u
jest
.
root
4.
Co
jest
w
arunkiem
k
o«co
wym
p
oni»szego
algorytm
u
rekurencyjnego, je»eli
zaªo»ym
y
,
»e
jest
do
wi¡zaniem
do
k
orzenia
p
ewnego
drzew
a
binarnego?
int
Cos(TreeNode
root)
{
if
(root==NULL)
return
0;
else
if
((root.left==NULL)&&(ro ot.r igh t==N ULL) ) return
2;
else
return
Cos(root.left)+Cos(root .rig ht);
}
root
(a)
[]
Suma
wierzc
hoªk
ó
w
drzew
a
binarnego
o
k
orzeniu
.
root
(b)
[+]
P
o
dw
o
jona
liczba
wierzc
hoªk
ó
w
zewn¦trzn
yc
h
drzew
a
binarnego
o
k
orzeniu
.
root
(c)
[]
W
ysok
o±¢
drzew
a
binarnego
o
k
orzeniu
.
1
P
a
w
eª
Remb
elski
Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
5.
Rozw
a»m
y
algorytm
rekurencyjn
y
z
zadania
4,
wtedy:
(a)
[+]
zªo»ono±¢
czaso
w
a
algorytm
u
jest
ró
wna
z
dokªadno±ci¡
do
rz¦du
funk
cji
liczbie
wierzc
hoª-
k
ó
w
drzew
a
w
ej±cio
w
ego,
O (h)
h
(b)
[]
zªo»ono±¢
czaso
w
a
algorytm
u
jest
,
gdzie
jest
wysok
o±ci¡
drzew
a
w
ej±cio
w
ego,
O (lg n)
n
(c)
[]
zªo»ono±¢
pami¦cio
w
a
algorytm
u
jest
,
gdzie
jest
liczb¡
wierzc
hoªk
ó
w
drzew
a
w
ej±cio
w
ego.
n
6.
Dla
algorytm
u
SelectionSort
i
dan
yc
h
w
ej±cio
wyc
h
rozmiaru
pra
wd¡
jest,
»e:
W (n) = Ω (n lg n) (a)
[+]
,
je»eli
miar¡
jest
liczba
p
oró
wna«
elemen
tó
w,
W (n) = O (n lg n) (b)
[+]
,
je»eli
miar¡
jest
liczba
przesta
wie«
elemen
tó
w,
S (n) = O (n lg n) (c)
[+]
.
7.
Rozw
a»m
y
ci¡
g
w
ej±cio
wy
dla
algorytm
u
InsertionSort
p
ostaci
6, 5, 4, 3, 2, 1, wtedy:
4
4, 5, 6, 3, 2, 1
(a)
[+]
p
orz¡dek
elemen
tó
w
p
o
zak
o«czeniu
wsta
wiania
elemen
tu
jest
nast¦puj¡cy:
,
3
4, 5, 6, 3, 2, 1
(b)
[]
p
orz¡dek
elemen
tó
w
p
o
zak
o«czeniu
wsta
wiania
elemen
tu
jest
nast¦puj¡cy:
,
17
(c)
[]
w
t
ym
przypadku
algorytm
wyk
ona
p
oró
wna«.
n
8.
Dla
algorytm
u
Quic
kSort
sorto
w
ania
-elemen
to
w
ego
ci¡
gu
w
ej±cio
w
ego
zapisanego
w
implemen
tacji
rekurencyjnej
pra
wd¡
jest,
»e:
A (n) = O (n lg n) (a)
[+]
,
W (n) = A (n)
(b)
[]
,
S (n) = O (1)
(c)
[]
.
n
9.
Rozw
a»m
y
algorytm
RadixSort,
który
zastoso
w
ano
do
p
osorto
w
ania
ci¡
gó
w
binarn
yc
h
dªugo±ci
k, wtedy:
√
n = Θ
k
T (n, k) = O (n) (a)
[]
je»eli
,
to
,
√
√
k = Θ ( n)
T (n, k) = O (n n) (b)
[+]
je»eli
,
to
,
√
n = Ω
k
S (n, k) = O (n) (c)
[]
je»eli
,
to
.
10.
Rozw
a»m
y
algorytm
Coun
tingSort
dla
dan
yc
h
w
ej±cio
wyc
h
1, 1, 4, 3, 2, 1, 1, 0, 2, 1, wtedy
p
osta¢
tablicy
p
omo
cniczej
(tablica
TMP)
p
o:
1, 5, 2, 1, 2,
(a)
[]
drugiej
cz¦±ci
algorytm
u
(zliczanie)
jest
nast¦puj¡ca:
1, 6, 8, 9, 10, (b)
[+]
trzeciej
cz¦±ci
algorytm
u
(sumo
w
anie)
jest
nast¦puj¡ca:
0, 1, 6, 8, 9.
(c)
[+]
czw
artej
cz¦±ci
algorytm
u
(wypisanie)
jest
nast¦puj¡ca:
11.
Które
z
p
oni»szyc
h
zda«
jest
za
wsze
pra
wdziw
e
w
dziedzinie
stosó
w:
empty (s) ⇒ ¬empty (pop (push (s, e))) (a)
[]
,
¬empty (s) ⇒ top (s) 6= top (push (pop (s) , e)) (b)
[]
,
¬empty (s) ⇒ top (pop (push (s, top (s)))) = top (s) (c)
[+]
?
2
P
a
w
eª
Remb
elski
Algo
rytmy
i
struktury
danych
materiaªy
¢wiczenio
w
e
Studia
dzienne
PJWSTK
12.
Które
z
p
oni»szyc
h
zda«
jest
za
wsze
pra
wdziw
e
w
dziedzinie
k
olejek:
¬empty (q) ⇒ first (q) 6= first (in (out (q) , e)) (a)
[]
,
out (in (in (q, e) , e)) = in (out (in (q, e)) , e) (b)
[+]
,
empty (q) ⇒ empty (in (q, e)) = f alse (c)
[+]
?
s
n
13.
Zaªó»m
y
,
»e
stos
za
wiera
elemen
tó
w
oraz,
»e
wyk
on
ujem
y
jedynie
op
eracje
stoso
w
e,
wtedy
x
o
dczytanie
elemen
tu
zna
jduj¡cego
si¦:
√
√
Θ ( n)
Θ ( n)
(a)
[]
na
wysok
o±ci
wzgl¦dem
doªu
stosu,
wymaga
w
cze±niejszego
wyk
onania
pop
s
op
eracji
na
stosie
,
√
√
Θ ( n)
Θ ( n)
(b)
[+]
na
wysok
o±ci
wzgl¦dem
góry
stosu,
wymaga
w
cze±niejszego
wyk
onania
pop
s
op
eracji
na
stosie
,
Θ (n)
O (1)
(c)
[]
na
wysok
o±ci
wzgl¦dem
góry
stosu,
wymaga
w
cze±niejszego
wyk
onania
op
e-
pop
s
racji
na
stosie
.
hE ∪ L, add, supr, inf, cuti 14.
Struktur¦
dan
yc
h
,
gdzie:
• add
add : L × E → L
doª¡czy¢
elemen
t
na
p
o
cz¡tek
struktury
,
,
• supr
supr : L → L
usun¡¢
pierwszy
elemen
t
ze
struktury
,
,
• inf
inf : L → E
p
o
da¢
na
jmniejszy
elemen
t
ze
struktury
,
,
• cut
cut :
usun¡¢
elemen
t
na
jmniejszy
i
wszystkie
elemen
t
y
doª¡czone
p
o
nim
do
struktury
,
L → L,
mo»na
zaimplemen
to
w
a¢
przy
staªej
zªo»ono±ci
wyk
onania
op
eracji,
je»eli:
E
L
(a)
[]
u»yjem
y
dw
ó
c
h
tablic
stat
yczn
yc
h
reprezen
tuj¡cyc
h
o
dp
o
wiednio
zb
ór
oraz
,
(b)
[]
u»yjem
y
dw
ó
c
h
list
jednokierunk
o
wyc
h
dziaªa
j¡cyc
h
w
trybie
k
olejek,
k
olejno
k
olejki
elemen
tó
w
oraz
k
olejki
elemen
tó
w
na
jmniejszyc
h,
(c)
[+/]
u»yjem
y
dw
ó
c
h
list
jednokierunk
o
wyc
h
dziaªa
j¡cyc
h
w
trybie
stosó
w,
k
olejno
stosu
elemen
tó
w
oraz
stosu
elemen
tó
w
na
jmniejszyc
h.
n
15.
Rozw
a»m
y
algorytm
obliczania
w
arto±ci
-op
eratoro
w
ego
wyra»enia
arytmet
ycznego
przy
u»yciu
dw
ó
c
h
stosó
w
(stos
op
eratoró
w
oraz
stos
argumen
tó
w),
wtedy:
√n
(a)
[]
zªo»ono±¢
czaso
w
a
algorytm
u
jest
rz¦du
,
n
(b)
[]
zªo»ono±¢
pami¦cio
w
a
algorytm
u
jest
rz¦du
,
(c)
[+]
zªo»ono±¢
pami¦cio
w
a
algorytm
u
jest
zale»na
o
d
sp
osobu
na
wiaso
w
ania
wyra»enia
i
w
przypadku
opt
ymist
yczn
ym
jest
staªa.
16.
Go¹dzik
o
w
a
t
wierdzi,
»e
Etopiryna:
(a)
jest
do
nab
ycia
w
na
jbli»szej
aptece
b
ez
k
olejki,
(b)
dziaªa
w
miejscu,
(c)
jest
stabilna
w
przypadku
o
czekiw
an
ym.
3
P
a
w
eª
Remb
elski