Algo

rytmy

i

struktury

danych

materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

SPRA

WDZIAN

I

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.

Które

z

p

oni»szyc

h

zda«

jest

za

wsze

pra

wdziw

e

w

dziedzinie

sªo

wnik

ó

w:

(a)

[]

empty

(d) ⇔ empty (delete (insert (insert (d, e) , e) , e))

,

(b)

[]

¬member (insert (delete (d, e) , e) , e)

,

(c)

[+]

member

(d, e) ⇒ ¬member (delete (d, e) , e)

.

2.

Niec

h

T

b

¦dzie

drzew

em

BST

p

o

wstaªym

przez

k

olejne

wsta

wianie

wierzc

hoªk

ó

w

o

et

ykietac

h

1, 7, 3, 2, 5, 8

do

p

o

cz¡tk

o

w

o

pustej

struktury

,

wtedy:

(a)

[]

k

orzeniem

drzew

a

T

jest

wierzc

hoªek

o

et

ykiecie

3

,

(b)

[+]

rezultatem

dziaªania

algorytm

u

PreOrder

dla

drzew

a

T

jest

ci¡

g

et

ykiet

1, 7, 3, 2, 5, 8

,

(c)

[]

usuni¦cie

wierzc

hoªk

a

o

et

ykiecie

1

z

drzew

a

T

wymaga

okre±lenia

jego

b

ezp

o±redniego

nast¦pnik

a

w

rozw

a»an

ym

drzewie.

3.

Niec

h

T

b

¦dzie

drzew

em

A

VL

p

o

wstaªym

przez

k

olejne

wsta

wianie

wierzc

hoªk

ó

w

o

et

ykietac

h

1, 7, 3, 2, 5, 8

do

p

o

cz¡tk

o

w

o

pustej

struktury

,

wtedy:

(a)

[]

k

orzeniem

drzew

a

T

jest

wierzc

hoªek

o

et

ykiecie

5

,

(b)

[]

rezultatem

dziaªania

algorytm

u

P

ostOrder

dla

drzew

a

T

jest

ci¡

g

et

ykiet

2, 1, 3, 5, 8, 7

,

(c)

[+]

usuni¦cie

wierzc

hoªk

a

o

et

ykiecie

3

z

drzew

a

T

wymaga

okre±lenia

jego

b

ezp

o±redniego

p

oprzednik

a/nast¦pnik

a

w

rozw

a»an

ym

drzewie.

4.

Niec

h

T

b

¦dzie

drzew

em

A

VL

skªada

j¡cym

si¦

z

n

wierzc

hoªk

ó

w,

gdzie

n >

10

6

,

wtedy:

(a)

[+]

k

oszt

op

eracji

member

na

drzewie

T

jest

nie

wi¦kszy

ni»

√

n

p

oró

wna«

et

ykiet

wierzc

hoª-

k

ó

w

drzew

a,

(b)

[]

realizacja

op

eracji

insert

w

drzewie

T

mo»e

sp

o

w

o

do

w

a¢

wyk

onanie

wi¦cej

ni»

6

-ciu

co

na

jwy»ej

p

o

dw

ó

jn

yc

h

rotacji,

(c)

[]

realizacja

op

eracji

delete

dla

p

ewnego

wierzc

hoªk

a

drzew

a

T

nie

mo»e

sp

o

w

o

do

w

a¢

wyk

o-

nania

wi¦cej

ni»

6

-ciu

co

na

jwy»ej

p

o

dw

ó

jn

yc

h

rotacji.

5.

Niec

h

drzew

o

binarne

T

b

¦dzie

implemen

tacj¡

n

-elemen

to

w

ego

sªo

wnik

a

d

,

wtedy

zªo»ono±¢

czaso

w

a

op

eracji:

(a)

[+]

member

dla

sªo

wnik

a

d

jest

O

(lg n)

,

je»eli

T

jest

drzew

em

A

VL,

(b)

[]

insert

dla

sªo

wnik

a

d

jest

Θ (lg n)

,

je»eli

T

jest

drzew

em

BST,

(c)

[+]

delete

dla

sªo

wnik

a

d

jest

Ω (1)

,

je»eli

T

jest

drzew

em

A

VL.

1

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych

materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

6.

Które

z

p

oni»szyc

h

zda«

jest

za

wsze

pra

wdziw

e

w

dziedzinie

k

olejek

prioryteto

wyc

h:

(a)

[+]

min

(pq) = min (insert (pq, min (pq)))

,

(b)

[]

min

(pq) 6= min (insert (delmin (pq) , min (pq)))

,

(c)

[+]

empty

(pq) ⇒ empty (delmin (insert (pq, e)))

.

7.

Niec

h

H

b

¦dzie

10

6

-elemen

to

wym

k

op

cem

binarn

ym

zaimplemen

to

w

an

ym

w

drzewie

binarn

ym

T

,

wtedy:

(a)

[+]

wysok

o±¢

drzew

a

T

jest

rz¦du

lg 10

6

,

(b)

[]

drzew

o

T

ma

co

na

jwy»ej

√

10

6

wierzc

hoªk

ó

w

w

ewn¦trzn

yc

h,

(c)

[+]

liczba

wierzc

hoªk

ó

w

li±ci

na

ostatnim

p

oziomie

drzew

a

T

jest

ró

wna

co

na

jmniej

1

.

8.

Rozw

a»m

y

ci¡

g

liczb

α

= 0, 4, 1, 2, 5

,

wtedy:

(a)

[]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

α

przez

k

olejne

wysta-

wianie

elemen

tó

w

do

p

o

cz¡tk

o

w

o

pustego

k

op

ca

ma

p

osta¢

[0, 1, 2, 4, 5]

,

(b)

[]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

α

przez

zastoso

w

anie

szybkiej

pro

cedury

budo

wy

k

op

ca

(tj.

HeapConstruct)

ma

p

osta¢

[0, 1, 2, 4, 5]

,

(c)

[+]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

α

przez

zastoso

w

anie

szybkiej

pro

cedury

budo

wy

k

op

ca

(tj.

HeapConstruct)

ma

p

osta¢

[0, 2, 1, 4, 5]

.

9.

Rozw

a»m

y

ci¡

g

n

liczb

naturaln

yc

h,

do

którego

zastoso

w

ano

algorytm

HeapSort,

wtedy:

(a)

[+]

k

oszt

budo

wy

k

op

ca

binarnego

wynosi

Ω (n)

,

(b)

[+]

k

oszt

rozebrania

k

op

ca

binarnego

wynosi

O

(n lg n)

,

(c)

[+]

algorytm

HeapSort

jest

opt

ymaln

ym

algorytmem

sortuj¡cym

przez

p

oró

wnania.

10.

Rozw

a»m

y

k

opiec

binarn

y-drzew

o

H

p

o

wstaªy

przez

k

olejne

wsta

wianie

liczb

2, 3, 4, 5, 6

do

p

o

cz¡t-

k

o

w

o

pustej

struktury

,

wtedy:

(a)

[]

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

P

ostOrder

t

w

orz¡

ci¡

g

6, 5, 4, 3, 2

,

(b)

[+]

je»eli

wyk

onam

y

ci¡

g

op

eracji

insert

(H, 1)

,

min

(H)

,

to

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

InOrder

t

w

orz¡

ci¡

g

5, 3, 6, 1, 4, 2

,

(c)

[+/]

k

oszt

op

eracji

insert

na

strukturze

H

jest

rz¦du

linio

w

ego

wzgl¦dem

liczb

y

wierzc

hoªk

ó

w

drzew

a.

11.

Rozw

a»m

y

k

opiec

binarn

y-drzew

o

H

p

o

wstaªy

przez

k

olejne

wsta

wianie

liczb

6, 5, 4, 3, 2

do

p

o

cz¡t-

k

o

w

o

pustej

struktury

,

wtedy:

(a)

[+]

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

PreOrder

t

w

orz¡

ci¡

g

2, 3, 6, 4, 5

,

(b)

[+]

je»eli

wyk

onam

y

ci¡

g

op

eracji

delmin

(H)

,

delmin

(H)

,

to

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

InOrder

t

w

orz¡

ci¡

g

6, 4, 5

,

(c)

[+]

k

oszt

op

eracji

delmin

na

strukturze

H

jest

rz¦du

linio

w

ego

wzgl¦dem

wysok

o±ci

drzew

a.

12.

Rozw

a»m

y

graf

p

eªn

y

z

w

agami

G

skªada

j¡cy

si¦

z

n

wierzc

hoªk

ó

w,

wtedy:

(a)

[]

k

oszt

pami¦cio

wy

macierzy

s¡siedzt

w

a

grafu

G

jest

rz¦du

O

(n)

,

(b)

[]

k

oszt

pami¦cio

wy

tablicy

list

incydencji

grafu

G

jest

rz¦du

Θ (n)

,

(c)

[+]

k

oszt

pami¦cio

wy

macierzy

s¡siedzt

w

a

grafu

G

jest

rz¦du

k

osztu

pami¦cio

w

ego

tablicy

list

incydencji

grafu

G

.

2

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych

materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

13.

Rozw

a»m

y

graf

G

= (V, E)

przedsta

wion

y

na

p

oni»szym

rysunku,

wtedy:

(a)

[+]

k

olejno±¢

o

dwiedzania

wierzc

hoªk

ó

w

grafu

algorytmem

DFS

jest

zgo

dna

z

p

orz¡dkiem

a, z, f, d, x, k, c, s

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

a

,

(b)

[]

k

olejno±¢

o

dwiedzania

wierzc

hoªk

ó

w

grafu

algorytmem

DFS

jest

zgo

dna

z

p

orz¡dkiem

z, s, d, f, x, k, s, c

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

c

,

(c)

[+]

maksymalna

wysok

o±¢

stosu

p

omo

cniczego

w

algorytmie

DFS

zastoso

w

an

ym

do

wierz-

c

hoªk

a

starto

w

ego

s

jest

ró

wna

3

.

14.

Rozw

a»m

y

graf

G

= (V, E)

z

zadania

13-tego,

wtedy:

(a)

[+]

k

olejno±¢

o

dwiedzania

wierzc

hoªk

ó

w

grafu

algorytmem

BFS

jest

zgo

dna

z

p

orz¡dkiem

f, d, z, c, k, x, a, s

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

f

,

(b)

[+]

k

olejno±¢

o

dwiedzania

wierzc

hoªk

ó

w

grafu

algorytmem

BFS

jest

zgo

dna

z

p

orz¡dkiem

x, d, c, f, k, s, z, a

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

x

,

(c)

[+]

zªo»ono±¢

czaso

w

a

algorytm

u

BFS

dla

rozw

a»anego

grafu

jest

rz¦du

O

(|V | + |E|)

.

15.

Niec

h

G

b

¦dzie

p

ewn

ym

grafem

skiero

w

an

ym,

wtedy

algorytm

sorto

w

ania

top

ologicznego

grafu

G

:

(a)

[]

dziaªa

p

opra

wnie

wtt

w,

gdy

graf

ten

jest

grafem

sp

ó

jn

ym,

(b)

[]

dziaªa

p

opra

wnie

wtt

w,

gdy

graf

ten

jest

grafem

z

w

agami,

(c)

[]

ma

zªo»ono±¢

rz¦du

O

(|V |)

,

gdzie

V

jest

zbiorem

wierzc

hoªk

ó

w

rozw

a»anego

grafu.

3

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych

materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

16.

Zapis

auten

t

ycznej

rozmo

wy

radio

w

ej

przepro

w

adzonej

mi¦dzy

ameryk

a«skim

okr¦tami

a

Kanadyj-

czyk

ami.

Miaªa

ona

miejsce

w

pa¹dzierniku

1995r.

u

wybrze»y

No

w

ej

F

unlandii.

•

Kanadyjczycy:

Prosz¦

o

zmian¦

kursu

o

15

stopni

na

p

oªudnie

w

celu

unikni¦cia

k

olizji.

•

A

merykanie:

Radzim

y

w

am

zmieni¢

kurs

o

15

stopni

na

p

óªno

c,

ab

y

unikn¡¢

k

olizji.

•

Kanadyjczycy:

T

o

niemo»liw

e.

T

o

wy

b

¦dziecie

m

usieli

zmieni¢

kurs

o

15

stopni

na

p

oªudnie,

ab

y

unikn¡¢

k

olizji.

•

A

merykanie:

Mó

wi

k

apitan

okr¦tu

w

o

jennego

Stanó

w

Zjedno

czon

yc

h.

P

o

wtarzam

p

ono

wnie:

wy

zmie«cie

kurs.

•

Kanadyjczycy:

Nie.

P

o

wtarzam:

zmie«cie

kurs,

ab

y

unikn¡¢

k

olizji.

•

A

merykanie:

Mó

wi

k

apitan

lotnisk

o

w

ca

USS

"Lincoln"

-

drugiego

p

o

d

wzgl¦dem

wielk

o±ci

okr¦tu

b

o

jo

w

ego

ameryk

a«skiej

marynarki

w

o

jennej

ot

y

atlan

t

yc

kiej.

T

o

w

arzysz¡

nam

trzy

niszczyciele,

trzy

kr¡»o

wniki

i

wiele

inn

yc

h

okr¦tó

w

wsp

omagania.

Domagam

si¦,

ab

y±cie

to

wy

zmienili

kurs

o

15

stopni

na

p

óªno

c.

W

inn

ym

przypadku

p

o

dejmiem

y

k

on

trdziaªania

w

celu

obron

y

grup

y!

•

Kanadyjczycy:

Mó

wi

latarnia

morsk

a:

w

asz

wyb

ór!

Jak

sk

o«czyªa

si¦

o

w

a

historia:

(a)

dobrze,

(b)

¹le,

(c)

tego

nie

wiedz¡

na

w

et

na

jstarsi

górale.

4

P

a

w

eª

Remb

elski