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