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

...

1.

Zaªó»m

y

,

»e

ci¡

g

w

ej±cio

wy

dla

algorytm

u

MergeSort

skªada

si¦

z

n

= 2

k

elemen

tó

w,

gdzie

k

∈ N

+

,

wtedy:

(a)

[+]

T

(n) = Θ (n lg n)

,

(b)

[]

S

(n) = Ω (n)

,

(c)

[+]

drzew

o

p

o

dziaªu

ci¡

gu

w

ej±cio

w

ego

dla

rozw

a»anego

algorytm

u

jest

wysok

o±ci

k

± 1

.

2.

Co

jest

w

arunkiem

k

o«co

wym

p

oni»szego

algorytm

u

rekurencyjnego,

gdzie

n

∈ N

?

int

Cos(int

n)

{

if

(n==0)

return

0;

return

Cos(n-1)+n;

}

(a)

[]

Cos

(n) = n

2

.

(b)

[+]

Cos

(n) = 0 + 1 + 2 + . . . + (n − 1) + n

.

(c)

[]

n

· Cos (n) = O n

2

.

3.

Rozw

a»m

y

algorytm

rekurencyjn

y

z

zadania

2,

wtedy:

(a)

[+]

zªo»ono±¢

czaso

w

a

algorytm

u

jest

co

na

jwy»ej

rz¦du

n

2

,

(b)

[+]

zªo»ono±¢

czaso

w

a

algorytm

u

jest

co

na

jmniej

rz¦du

√

n

,

(c)

[]

zªo»ono±¢

pami¦cio

w

a

algorytm

u

jest

O

(1)

.

4.

Co

jest

w

arunkiem

k

o«co

wym

p

oni»szego

algorytm

u

rekurencyjnego,

je»eli

zaªo»ym

y

,

»e

root

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);

}

(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

root

.

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,

(b)

[]

zªo»ono±¢

czaso

w

a

algorytm

u

jest

O

(h)

,

gdzie

h

jest

wysok

o±ci¡

drzew

a

w

ej±cio

w

ego,

(c)

[]

zªo»ono±¢

pami¦cio

w

a

algorytm

u

jest

O

(lg n)

,

gdzie

n

jest

liczb¡

wierzc

hoªk

ó

w

drzew

a

w

ej±cio

w

ego.

6.

Dla

algorytm

u

SelectionSort

i

dan

yc

h

w

ej±cio

wyc

h

rozmiaru

n

pra

wd¡

jest,

»e:

(a)

[+]

W

(n) = Ω (n lg n)

,

je»eli

miar¡

jest

liczba

p

oró

wna«

elemen

tó

w,

(b)

[+]

W

(n) = O (n lg n)

,

je»eli

miar¡

jest

liczba

przesta

wie«

elemen

tó

w,

(c)

[+]

S

(n) = O (n lg n)

.

7.

Rozw

a»m

y

ci¡

g

w

ej±cio

wy

dla

algorytm

u

InsertionSort

p

ostaci

6, 5, 4, 3, 2, 1,

wtedy:

(a)

[+]

p

orz¡dek

elemen

tó

w

p

o

zak

o«czeniu

wsta

wiania

elemen

tu

4

jest

nast¦puj¡cy:

4, 5, 6, 3, 2, 1

,

(b)

[]

p

orz¡dek

elemen

tó

w

p

o

zak

o«czeniu

wsta

wiania

elemen

tu

3

jest

nast¦puj¡cy:

4, 5, 6, 3, 2, 1

,

(c)

[]

w

t

ym

przypadku

algorytm

wyk

ona

17

p

oró

wna«.

8.

Dla

algorytm

u

Quic

kSort

sorto

w

ania

n

-elemen

to

w

ego

ci¡

gu

w

ej±cio

w

ego

zapisanego

w

implemen

tacji

rekurencyjnej

pra

wd¡

jest,

»e:

(a)

[+]

A

(n) = O (n lg n)

,

(b)

[]

W

(n) = A (n)

,

(c)

[]

S

(n) = O (1)

.

9.

Rozw

a»m

y

algorytm

RadixSort,

który

zastoso

w

ano

do

p

osorto

w

ania

n

ci¡

gó

w

binarn

yc

h

dªugo±ci

k

,

wtedy:

(a)

[]

je»eli

n

= Θ



√

k



,

to

T

(n, k) = O (n)

,

(b)

[+]

je»eli

k

= Θ (

√

n

)

,

to

T

(n, k) = O (n

√

n

)

,

(c)

[]

je»eli

n

= Ω



√

k



,

to

S

(n, k) = O (n)

.

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:

(a)

[]

drugiej

cz¦±ci

algorytm

u

(zliczanie)

jest

nast¦puj¡ca:

1, 5, 2, 1, 2,

(b)

[+]

trzeciej

cz¦±ci

algorytm

u

(sumo

w

anie)

jest

nast¦puj¡ca:

1, 6, 8, 9, 10,

(c)

[+]

czw

artej

cz¦±ci

algorytm

u

(wypisanie)

jest

nast¦puj¡ca:

0, 1, 6, 8, 9.

11.

Które

z

p

oni»szyc

h

zda«

jest

za

wsze

pra

wdziw

e

w

dziedzinie

stosó

w:

(a)

[]

empty

(s) ⇒ ¬empty (pop (push (s, e)))

,

(b)

[]

¬empty (s) ⇒ top (s) 6= top (push (pop (s) , e))

,

(c)

[+]

¬empty (s) ⇒ top (pop (push (s, top (s)))) = top (s)

?

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:

(a)

[]

¬empty (q) ⇒ first (q) 6= first (in (out (q) , e))

,

(b)

[+]

out

(in (in (q, e) , e)) = in (out (in (q, e)) , e)

,

(c)

[+]

empty

(q) ⇒ empty (in (q, e)) = false

?

13.

Zaªó»m

y

,

»e

stos

s

za

wiera

n

elemen

tó

w

oraz,

»e

wyk

on

ujem

y

jedynie

op

eracje

stoso

w

e,

wtedy

o

dczytanie

elemen

tu

x

zna

jduj¡cego

si¦:

(a)

[]

na

wysok

o±ci

Θ (

√

n

)

wzgl¦dem

doªu

stosu,

wymaga

w

cze±niejszego

wyk

onania

Θ (

√

n

)

op

eracji

pop

na

stosie

s

,

(b)

[+]

na

wysok

o±ci

Θ (

√

n

)

wzgl¦dem



góry

stosu,

wymaga

w

cze±niejszego

wyk

onania

Θ (

√

n

)

op

eracji

pop

na

stosie

s

,

(c)

[]

na

wysok

o±ci

Θ (n)

wzgl¦dem



góry

stosu,

wymaga

w

cze±niejszego

wyk

onania

O

(1)

op

e-

racji

pop

na

stosie

s

.

14.

Struktur¦

dan

yc

h

hE ∪ L, add, supr, inf, cuti

,

gdzie:

• add



doª¡czy¢

elemen

t

na

p

o

cz¡tek

struktury

,

add

: L × E → L

,

• supr



usun¡¢

pierwszy

elemen

t

ze

struktury

,

supr

: L → L

,

• inf



p

o

da¢

na

jmniejszy

elemen

t

ze

struktury

,

inf

: L → E

,

• cut



usun¡¢

elemen

t

na

jmniejszy

i

wszystkie

elemen

t

y

doª¡czone

p

o

nim

do

struktury

,

cut

:

L

→ L

,

mo»na

zaimplemen

to

w

a¢

przy

staªej

zªo»ono±ci

wyk

onania

op

eracji,

je»eli:

(a)

[]

u»yjem

y

dw

ó

c

h

tablic

stat

yczn

yc

h

reprezen

tuj¡cyc

h

o

dp

o

wiednio

zb

ór

E

oraz

L

,

(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.

15.

Rozw

a»m

y

algorytm

obliczania

w

arto±ci

n

-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:

(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

n

,

(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