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