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:

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

[]

,

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

[]

,

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

[+]

.

T

2.

Niec

h

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 pocz¡tkowo pustej struktury, wtedy: T

3

(a)

[]

k

orzeniem

drzew

a

jest

wierzc

hoªek

o

et

ykiecie

,

T

1, 7, 3, 2, 5, 8

(b)

[+]

rezultatem

dziaªania

algorytm

u

PreOrder

dla

drzew

a

jest

ci¡

g

et

ykiet

,

1

T

(c)

[]

usuni¦cie

wierzc

hoªk

a

o

et

ykiecie

z

drzew

a

wymaga

okre±lenia

jego

b

ezp

o±redniego

nast¦pnik

a

w

rozw

a»an

ym

drzewie.

T

3.

Niec

h

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 pocz¡tkowo pustej struktury, wtedy: T

5

(a)

[]

k

orzeniem

drzew

a

jest

wierzc

hoªek

o

et

ykiecie

,

T

2, 1, 3, 5, 8, 7

(b)

[]

rezultatem

dziaªania

algorytm

u

P

ostOrder

dla

drzew

a

jest

ci¡

g

et

ykiet

,

3

T

(c)

[+]

usuni¦cie

wierzc

hoªk

a

o

et

ykiecie

z

drzew

a

wymaga

okre±lenia

jego

b

ezp

o±redniego

p

oprzednik

a/nast¦pnik

a

w

rozw

a»an

ym

drzewie.

T

n

n > 106

4.

Niec

h

b

¦dzie

drzew

em

A

VL

skªada

j¡cym

si¦

z

wierzc

hoªk

ó

w,

gdzie

,

wtedy:

√

member

T

n

(a)

[+]

k

oszt

op

eracji

na

drzewie

jest

nie

wi¦kszy

ni»

p

oró

wna«

et

ykiet

wierzc

hoª-

k

ó

w

drzew

a,

insert

T

6

(b)

[]

realizacja

op

eracji

w

drzewie

mo»e

sp

o

w

o

do

w

a¢

wyk

onanie

wi¦cej

ni»

-ciu

co

na

jwy»ej

p

o

dw

ó

jn

yc

h

rotacji,

delete

T

(c)

[]

realizacja

op

eracji

dla

p

ewnego

wierzc

hoªk

a

drzew

a

nie

mo»e

sp

o

w

o

do

w

a¢

wyk

o-

6

nania

wi¦cej

ni»

-ciu

co

na

jwy»ej

p

o

dw

ó

jn

yc

h

rotacji.

T

n

d

5.

Niec

h

drzew

o

binarne

b

¦dzie

implemen

tacj¡

-elemen

to

w

ego

sªo

wnik

a

,

wtedy

zªo»ono±¢

czaso

w

a

op

eracji:

member

d

O (lg n)

T

(a)

[+]

dla

sªo

wnik

a

jest

,

je»eli

jest

drzew

em

A

VL,

insert

d

Θ (lg n)

T

(b)

[]

dla

sªo

wnik

a

jest

,

je»eli

jest

drzew

em

BST,

delete

d

Ω (1)

T

(c)

[+]

dla

sªo

wnik

a

jest

,

je»eli

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:

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

[+]

,

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

[]

,

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

[+]

.

H

106

T

7.

Niec

h

b

¦dzie

-elemen

to

wym

k

op

cem

binarn

ym

zaimplemen

to

w

an

ym

w

drzewie

binarn

ym

,

wtedy:

T

lg 106

(a)

[+]

wysok

o±¢

drzew

a

jest

rz¦du

,

√

T

106

(b)

[]

drzew

o

ma

co

na

jwy»ej

wierzc

hoªk

ó

w

w

ewn¦trzn

yc

h,

T

1

(c)

[+]

liczba

wierzc

hoªk

ó

w

li±ci

na

ostatnim

p

oziomie

drzew

a

jest

ró

wna

co

na

jmniej

.

α = 0, 4, 1, 2, 5

8.

Rozw

a»m

y

ci¡

g

liczb

,

wtedy:

α

(a)

[]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

przez

k

olejne

wysta-

[0, 1, 2, 4, 5]

wianie

elemen

tó

w

do

p

o

cz¡tk

o

w

o

pustego

k

op

ca

ma

p

osta¢

,

α

(b)

[]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

przez

zastoso

w

anie

[0, 1, 2, 4, 5]

szybkiej

pro

cedury

budo

wy

k

op

ca

(tj.

HeapConstruct) ma

p

osta¢

,

α

(c)

[+]

tablica

reprezen

tuj¡ca

k

opiec

binarn

y

ut

w

orzon

y

z

elemen

tó

w

ci¡

gu

przez

zastoso

w

anie

[0, 2, 1, 4, 5]

szybkiej

pro

cedury

budo

wy

k

op

ca

(tj.

HeapConstruct) ma

p

osta¢

.

n

9.

Rozw

a»m

y

ci¡

g

liczb

naturaln

yc

h,

do

którego

zastoso

w

ano

algorytm

HeapSort,

wtedy:

Ω (n)

(a)

[+]

k

oszt

budo

wy

k

op

ca

binarnego

wynosi

,

O (n lg n)

(b)

[+]

k

oszt

rozebrania

k

op

ca

binarnego

wynosi

,

(c)

[+]

algorytm

HeapSort

jest

opt

ymaln

ym

algorytmem

sortuj¡cym

przez

p

oró

wnania.

H

2, 3, 4, 5, 6

10.

Rozw

a»m

y

k

opiec

binarn

y-drzew

o

p

o

wstaªy

przez

k

olejne

wsta

wianie

liczb

do

p

o

cz¡t-

k

o

w

o

pustej

struktury

,

wtedy:

6, 5, 4, 3, 2

(a)

[]

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

P

ostOrder

t

w

orz¡

ci¡

g

,

insert (H, 1) min (H) (b)

[+]

je»eli

wyk

onam

y

ci¡

g

op

eracji

,

,

to

et

ykiet

y

drzew

a

o

dczytane

w

5, 3, 6, 1, 4, 2

p

orz¡dku

InOrder

t

w

orz¡

ci¡

g

,

insert

H

(c)

[+/]

k

oszt

op

eracji

na

strukturze

jest

rz¦du

linio

w

ego

wzgl¦dem

liczb

y

wierzc

hoªk

ó

w

drzew

a.

H

6, 5, 4, 3, 2

11.

Rozw

a»m

y

k

opiec

binarn

y-drzew

o

p

o

wstaªy

przez

k

olejne

wsta

wianie

liczb

do

p

o

cz¡t-

k

o

w

o

pustej

struktury

,

wtedy:

2, 3, 6, 4, 5

(a)

[+]

et

ykiet

y

drzew

a

o

dczytane

w

p

orz¡dku

PreOrder

t

w

orz¡

ci¡

g

,

delmin (H) delmin (H) (b)

[+]

je»eli

wyk

onam

y

ci¡

g

op

eracji

,

,

to

et

ykiet

y

drzew

a

o

dczytane

w

6, 4, 5

p

orz¡dku

InOrder

t

w

orz¡

ci¡

g

,

delmin

H

(c)

[+]

k

oszt

op

eracji

na

strukturze

jest

rz¦du

linio

w

ego

wzgl¦dem

wysok

o±ci

drzew

a.

G

n

12.

Rozw

a»m

y

graf

p

eªn

y

z

w

agami

skªada

j¡cy

si¦

z

wierzc

hoªk

ó

w,

wtedy:

G

O (n)

(a)

[]

k

oszt

pami¦cio

wy

macierzy

s¡siedzt

w

a

grafu

jest

rz¦du

,

G

Θ (n)

(b)

[]

k

oszt

pami¦cio

wy

tablicy

list

incydencji

grafu

jest

rz¦du

,

G

(c)

[+]

k

oszt

pami¦cio

wy

macierzy

s¡siedzt

w

a

grafu

jest

rz¦du

k

osztu

pami¦cio

w

ego

tablicy

list

G

incydencji

grafu

.

2

P

a

w

eª

Remb

elski

Algo

rytmy

i

struktury

danych

materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

G = (V, E)

13.

Rozw

a»m

y

graf

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 a

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

,

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

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

,

(c)

[+]

maksymalna

wysok

o±¢

stosu

p

omo

cniczego

w

algorytmie

DFS

zastoso

w

an

ym

do

wierz-

s

3

c

hoªk

a

starto

w

ego

jest

ró

wna

.

G = (V, E)

14.

Rozw

a»m

y

graf

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 f

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

,

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

je»eli

wierzc

hoªkiem

starto

wym

jest

wierzc

hoªek

,

O (|V | + |E|) (c)

[+]

zªo»ono±¢

czaso

w

a

algorytm

u

BFS

dla

rozw

a»anego

grafu

jest

rz¦du

.

G

G

15.

Niec

h

b

¦dzie

p

ewn

ym

grafem

skiero

w

an

ym,

wtedy

algorytm

sorto

w

ania

top

ologicznego

grafu

:

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

O (|V |)

V

(c)

[]

ma

zªo»ono±¢

rz¦du

,

gdzie

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 poªudnie w celu unikni¦cia kolizji.

• Amerykanie: Radzimy wam zmieni¢ kurs o 15 stopni na póªnoc, aby unikn¡¢ kolizji.

• Kanadyjczycy: To niemo»liwe. To wy b¦dziecie musieli zmieni¢ kurs o 15 stopni na poªudnie, ab

y

unikn¡¢

k

olizji.

• Amerykanie: Mówi kapitan okr¦tu wojennego Stanów Zjednoczonych. Powtarzam ponownie: wy

zmie«cie

kurs.

• Kanadyjczycy: Nie. Powtarzam: zmie«cie kurs, aby unikn¡¢ kolizji.

• Amerykanie: Mówi kapitan lotniskowca USS "Lincoln" - drugiego pod wzgl¦dem wielko±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 morska: wasz 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