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

...

1.

Niec

h

f (n) = (lg n!)

2

,

wtedy

pra

wd¡

jest,

»e:

(a)

[+]

f (n) = O n

3

,

(b)

[+]

f (n) = Ω



lg (n!)

2



,

(c)

[+]

f (n) = Θ



2

lg n

2

lg

2

n



.

2.

Rozw

a»m

y

funk

cj¦

f : N → R

+

∪ {0}

p

ostaci

f (n) =

√

n

,

wtedy:

(a)

[+]

f (n) = Θ

1
c

· f (n) + c

,

gdzie

c

jest

p

ewn¡

do

datni¡

staª¡,

(b)

[+]

f (n) = O (n · f (n))

,

(c)

[+]

f (n) = Ω



f (n)

−2



.

3.

Które

z

p

oni»szyc

h

zda«

jest

pra

wdziw

e:

(a)

[]

je»eli

f (n) = O (n)

i

g (n) = O (n)

,

to

f (n) + g (n) = Ω n

2

,

(b)

[+]

je»eli

f (n) = O n

2

i

g (n) = O n

2

,

to

f (n) + g (n) = O n

2

,

(c)

[+]

je»eli

f (n) = Ω (n)

i

g (n) = Ω (n)

,

to

f (n) · g (n) = Ω n

2

.

4.

Zaªó»m

y

,

»e

zªo»ono±¢

czaso

w

¡

p

ewnego

algorytm

u

A

okre±la

funk

cja

T (A, n) = n

2

,

gdzie

n

jest

rozmiarem

dan

yc

h

w

ej±cio

wyc

h.

K

omputer

K

wyk

on

uje

rozw

a»an

y

algorytm

dla

dan

yc

h

rozmiaru

8

w

ci¡

gu

32

sekund,

tj.

T

K

(A, 8) = 32

.

St¡d:

(a)

[]

T

K

(A, 9) = 40

,

(b)

[+]

T

K

(A, 10) = 50

,

(c)

[+]

w

ci¡

gu

200

sekund

k

omputer

K

wyk

ona

rozw

a»an

y

algorytm

dla

dan

yc

h

w

ej±cio

wyc

h

rozmiaru

co

na

jmniej

20

.

5.

Rozw

a»m

y

nast¦puj¡cy

algorytm

void

Algorytm(int

n)

{

Alg1(n);

for

(i=0;i<n*n;i++)

{

Alg2(n);

}

}

gdzie

Alg

1

oraz

Alg

2

s¡

algorytmami

o

zªo»ono±ci

czaso

w

ej

o

dp

o

wiednio

T (Alg

1

n) = O (

√

n lg n!)

oraz

A (Alg

2

, n) = Θ n

2

,

W (Alg

2

, n) = Ω n

2

,

st¡d:

(a)

[]

T (Algorytm, n) = Θ n

2

lg n!

,

1

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

(b)

[]

A (Algorytm, n) = O n

2

lg n!

,

(c)

[+]

W (Algorytm, n) = Ω n

2

lg n!

.

6.

Rozw

a»m

y

nast¦puj¡cy

algorytm

int

Cos(int

n)

{

//

wp:

n

∈ N

int

i=1;

while

(i*i

≥

0)

i=i+1;

return

n;

//

wk:

n

∈ 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

op

erator

do

da

w

ania

zdeniujem

y

jak

dzielenie,

tj.

+ =

def

/

.

7.

Rozw

a»m

y

nast¦puj¡cy

algorytm

int

Cos(int

n,

int

k)

{

int

i=n,

wynik=0;

while

(i

≥

k)

{

i=i

div

k;

wynik=wynik+1;

}

return

wynik;

//

wk:

wynik=

blog

k

n

c

}

wtedy:

(a)

[]

program

Cos

jest

cz¦±cio

w

o

p

opra

wn

y

dla

w

arunku

p

o

cz¡tk

o

w

ego

k, n ∈ N

,

(b)

[+]

program

Cos

jest

cz¦±cio

w

o

p

opra

wn

y

dla

w

arunku

p

o

cz¡tk

o

w

ego

dla

n ∈ N

i

k ∈ N\{0, 1}

,

(c)

[+]

program

Cos

jest

caªk

o

wicie

p

opra

wn

y

dla

w

arunku

p

o

cz¡tk

o

w

ego

n = k

c

,

dla

c ∈ N

+

i

k ∈ N \ {0, 1}

,

8.

Rozw

a»m

y

nast¦puj¡cy

algorytm

int

Cos(int

n)

{

//

wp:

n

∈ N

int

i=0,

s=0;

while

(i

≤

n)

{

i=i+1;

s=s+i;

}

return

s;

}

wtedy:

(a)

[+]

niezmiennikiem

p

¦tli

w

programie

Cos

jest

form

uªa

s =

i

(i+1)

2

,

(b)

[]

niezmiennikiem

p

¦tli

w

programie

Cos

jest

form

uªa

s =

(i+1)(i+2)

2

,

(c)

[]

niezmiennikiem

p

¦tli

w

programie

Cos

jest

form

uªa

i ≥ 0

,

a

w

arunkiem

k

o«co

wym

s =

n−1

X

i

=0

i

.

9.

Które

ze

zda«

jest

pra

wdziw

e:

(a)

[+]

spra

wdzenie,

czy

dan

y

elemen

t

nale»y

do

nieup

orz¡dk

o

w

anego

uniw

ersum

rozmiaru

n

wymaga

Ω (

√

n)

p

oró

wna«,

(b)

[]

spra

wdzenie,

czy

dan

y

elemen

t

nale»y

do

nieup

orz¡dk

o

w

anego

uniw

ersum

rozmiaru

√

n

wymaga

O (lg n)

p

oró

wna«,

(c)

[+]

k

oszt

czaso

wy

opt

ymalnego

algorytm

u

wyszuk

ania

elemen

tu

minimalnego

w

nieup

orz¡d-

k

o

w

an

ym

uniw

ersum

rozmiaru

10

6

wynosi

10

6

− 1

.

2

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

10.

Rozw

a»m

y

algorytm

turniej

dla

dan

yc

h

rozmiaru

n = 2

k

,

gdzie

k ∈ N

+

.

Które

z

p

oni»szyc

h

st

wierdze«

jest

za

wsze

sp

eªnione:

(a)

[]

k

oszt

budo

wy

drzew

a

turnieju

wynosi

dokªadnie

n

p

oró

wna«,

(b)

[+]

elemen

t

3-ci

co

do

wielk

o±ci

p

o

jedynk

o

w

aª

si¦

z

co

na

jwy»ej

z

lg n

elemen

tami,

(c)

[+]

elemen

t

1-szy

co

do

wielk

o±ci

p

o

jedynk

o

w

aª

si¦

z

co

na

jmniej

lg n

elemen

tami.

11.

Rozw

a»m

y

iteracyjn

y

algorytm

dla

problem

u

min-max

i

dan

yc

h

rozmiaru

n = 2

k

,

gdzie

k ∈ N

+

,

wtedy:

(a)

[+]

algorytm

ten

jest

opt

ymaln

ym

rozwi¡zaniem

dla

rozw

a»anego

problem

u,

(b)

[+]

zªo»ono±¢

czaso

w

¡

algorytm

u

mo»na

oszaco

w

a¢

przez

O (n)

,

(c)

[]

zªo»ono±¢

pami¦cio

w

a

algorytm

u

jest

rz¦du

Ω (lg n)

.

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-

w

ersum

rozmiaru

n

wymaga

O (n)

p

oró

wna«,

(b)

[+]

spra

wdzenie

algorytmem

BinSearc

h,

czy

dan

y

elemen

t

nale»y

do

up

orz¡dk

o

w

anego

uni-

w

ersum

rozmiaru

n

wymaga

O (n)

p

oró

wna«,

(c)

[]

k

oszt

czaso

wy

algorytm

u

BinSearc

h

dla

p

opra

wn

yc

h

dan

yc

h

rozmiaru

2 · 10

3

wynosi

co

na

jwy»ej

8

p

oró

wna«.

13.

Zaªó»m

y

,

»e

p

ewien

algorytm

Alg

dla

dan

yc

h

w

ej±cio

wyc

h

rozmiaru

n

skªada

si¦

z

trzec

h

cz¦±ci:

• n

√

n

-krotne

wyszuk

anie

elemen

tu

maksymalnego

meto

d¡

sekw

encyjn¡,

• n

-krotne

wyszuk

anie

elemen

tu

minimalnego

algorytmem

Hoare'a,

•

√

n

-krotne

wyszuk

anie,

algorytmem

opt

ymaln

ym,

median

y

w

ci¡

gu

up

orz¡dk

o

w

an

ym.

Które

z

oszaco

w

a«

jest

p

opra

wne:

(a)

[+]

A (Alg, n) = Ω n

2

,

(b)

[]

W (Alg, n) = O n

2

,

(c)

[]

S (Alg, n) = Θ (n)

.

14.

Który

z

p

oni»szyc

h

ci¡

gó

w

jest

p

opra

wn

ym

rezultatem

wyk

onania

pro

cedury

P

artition

dla

dan

yc

h

w

ej±cio

wyc

h

4, 7, 9, 11, 3, 5, 2,

(a)

[]

4,7,3,2,11,9,5,

(b)

[+]

2,7,9,11,3,5,4,

(c)

[]

2,3,4,5,7,9,11.

15.

Rozw

a»m

y

wyszukiw

anie

elemen

tu

n

-tego

co

do

wielk

o±ci,

w

n

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

Split,

wtedy:

(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

Ω (n)

,

(c)

[]

zªo»ono±¢

czaso

w

¡

rozwi¡zania

w

t

ym

przypadku

szacujem

y

przez

Θ n

2

.

16.

Pro

w

adz¡cy

za

j¦cia

¢wiczenio

w

e

z

ASD

jest:

(a)

blondynem,

(b)

brunetem,

(c)

alb

o

nie

znam

czªo

wiek

a

...

alb

o

m

y±l¦,

»e

liczba

wªosó

w

na

jego

gªo

wie

da

je

si¦

szaco

w

a¢

przez

Ω (1)

.

3

P

a

w

eª

Remb

elski