A Jméno:……………………….….. St. Sk.:……. Cvičící:………..………Bodů ze cv.:……
1.
( úspěšnost: 39 z 49 = 80%) Insert sort řadí do neklesajícího pořadí pole o n prvcích, v němž jsou stejné všechny hodnoty kromě první a poslední, které jsou větší a navzájem stejné. Jediné nepravdivé označení asymptotické složitosti výpočtu je a) b) c) d) e)
Ο(n) Θ(n) Ω(n2) Ο(n2) Ω(n)
1.
2.
Situace v poli před zahájením řazení je naznačena na prvním obrázku. V obecném kroku algoritmu se nad daným polem provede akce znázorněná na druhém obrázku. Jeden velký prvek se posune o pozici doprava a aktuální (šedý) prvek se posune o pozici doleva. To představuje konstantní počet operací. Rovněž poslední krok algoritmu, kdy se pouze porovnají poslední dva prvky, potřebuje konstantní počet operací. Celkem tedy složitost výpočtu je úměrná výrazu konst ⋅ n. Platí ovšem konst ⋅ n ∈ Ο(n) (konst ⋅ n neroste asymptoticky rychleji než n) konst ⋅ n ∈ Θ(n) (to jsme právě zdůvodnili) konst ⋅ n ∈ Ο(n2) (a libovolné vyšší mocniny n) konst ⋅ n ∈ Ω(n) (konst ⋅ n neroste asymptoticky pomaleji než n) Jediné nepravdivé tvrzení je tudíž obsaženo ve variantě c).
2. ( úspěšnost: 43 z 49 = 88%) Jednoduchá pravá rotace v uzlu u má operační složitost
a) b) c) d)
Θ(1) závislou na hloubce uzlu u mezi O(1) a Ω (log n) Ω(n)
Zde je nutno vědět, jak přibližně rotace vypadá. Mění jen několik ukazatelů na uzly stromu. Intuitivně by mělo pak být jasné, že má složitost konstantní. Varianty b) a d) v takovém případě neplatí. Varianta c) tvrdí, že dotyčná složitost je mezi O(1) a Ω (log n), což znamená, že sice roste pomaleji než log(n), ale zároveň rychleji než konstanta (která „neroste vůbec“). Platí ovšem a).
A 3. ( úspěšnost: 40 z 49 = 82%) void fff(int x) { if (x < 0) return; abc(x); fff(x–1); fff(x–2); } Daná funkce fff je volána s parametrem 2: fff(2);. Funkce abc(x) je tedy celkem volána a) 1 krát b) 3 krát c) 4 krát d) 7 krát e) 8 krát
Strom rekurzivního volání funkce fff vidíme na obrázku (jenž není součástí zadání úlohy), v každém uzlu je vepsána hodnota parametru x při odpovídajícím volání funkce fff. Při volání, kdy je hodnota x je menší než 0 (x = –1 nebo x = –2) , nastává okamžitý návrat z funkce fff a funkce abc v takovém případě již volána není. To znamená že funkce fff bude volána jen v bílých uzlech stromu na obrázku, jež jsou dohromady 4. Platí varianta c).
4. ( úspěšnost: 26 z 49 = 54%) Mapovací funkce pro pole uložené po sloupcích s číslem řádku i v rozsahu i = <3,7> a sloupcovým indexem j = <2,5> a počáteční adresou pole v paměti adr vypadá následovně: a) b) c) d)
map(i,j) = adr + (i–3) + (j–2) * 5 map(i,j) = adr + (i–3) + (j–2) * 4 map(i,j) = adr + (i–3) * 4 + (j–2) map(i,j) = adr + (i–3) * 5 + (j–2) * 5
Nejjednodušeji varianty ověříme, když do každé z nich dosadíme. Vybereme si proto v poli prvek, který má co nejmenší index a přitom jeho poloha je „co nejobecnější“, tj. neleží ani v prvním řádku ani v prvním sloupci ani na diagonále a také jeho indexy se navzájem liší. To může být například zvýrazněný prvek s indexy [5] a [3] (obrázek není součástí zadání) . Jeho poloha od začátku pole při ukládání po sloupcích(!) je adr + 7. Dosaďme nyní jeho indexy do každé varianty: adr + (5 – 3) + (3 – 2) * 5 = adr + 2 + 1 * 5 = adr + 7 adr + (5 – 3) + (3 – 2) * 4 = adr + 2 + 1 * 4 = adr + 6 adr + (5 – 3) * 4 + (3 – 2) = adr + 2 * 4 + 1 = adr + 9 adr + (5 – 3) * 5 + (3 – 2) * 5 = adr + 2 * 5 + 1 * 5 = adr + 15 Souhlasí pouze varianta a).
5. ( úspěšnost: 45 z 49 = 92%) Červenočerný strom a) b) c) d)
má černé listy udržuje ve všech větvích stejnou červenou výšku následníci černého uzlu jsou vždy červení má maximální výšku rovnou 2/3 své červené výšky
Červenočerný strom má řadu vlastností, které je nutno si pamatovat, odvozují se špatně. Citujme z přednášky: 1. Every node is either red or black
A 2. Every leaf (nil) is black 3. If a node is red, then both its children are black 4. Every simple path from a node to a descendant leaf contains the same number of black nodes (5. Root is black) Podmínka 3. říká, že v žádné cestě z kořene do listu nemůže být více červených uzlů než černých, výška stromu tedy nepřekročí dvojnásobek jeho černé výšky. Prostřídáme-li ve vyváženém stromu červené a černé vrstvy, vidíme, že lze tohoto maxima téměř dosáhnout. Varianta d) je v rozporu s tímto zjištěním. Varianta c) je také v rozporu s podmínkou 3, podmínka 4 popírá variantu b). Platí a).
6. ( úspěšnost: 39 z 49 = 80%) Na obrázku je skupina úseček. Při výpočtu jejich vzájemných průsečíků se udržuje postupový plán (x-struktura) a struktura svázaná s přímkou uchovávající mezivýsledky (ystruktura). Jaký je stav obou struktur po dokončení 4. kroku podle postupového plánu, tj.po aktualizaci obou struktur? a) X-str: P2,A, B, F, D Y-str: z,y,x b) X-str: P1,B, F, D Y-str: x,z,y c) X-str: P1, P2,B, F, D Y-str: z,y d) X-str:,A, B, F, D Y-str: z,x,y
A x E
D
z P1
P2
B y
F
C Úloha je kopií úlohy z předtermínu, zde jen opakujeme řešení.
Řešení této úlohy navazuje na řešení úlohy 6 ze sousedního oddělení B. Je tam stejný obrázek, jen je prohozeno označení P2 a P1 a zkoumá se stav po třetím kroku. Podle toho tedy stav obou struktur v této úloze po třetím kroku je x-str: A, B, F, D, ystr: z,y. Ve čtvrtém kroku je zaregistrována úsečka x a přidána do y-struktury nahoru a také je díky ní objeven průsečík P1 a přidán do x-struktury. Poté je A z x-struktury vyřazeno. V obou strukturách se tak ocitne právě to, co je popsáno ve variantě b). Lze také uvažovat jednodušeji. Bod A je čtvrtý zleva, takže po čtvrtém kroku, již nemůže být v x-struktuře, tím odpadají varianty a) a d). Bod P2 je dokonce jen třetí zleva, takže z podobného důvodu odpadá varianta c).
7. ( úspěšnost: 46 z 49 = 94%) Double hashing a) je metoda ukládání klíčů na dvě různá místa současně b) je metoda minimalizace kolizí u metody otevřeného rozptylování c) má vyšší pravděpodobnost vzniku kolizí než linear probing d) je metoda minimalizace kolizí u metody rozptylování s vnějším zřetězením Tady nepomůže asi nic jiného než dobrá paměť.
A 8. ( úspěšnost: 42 z 49 = 86%) Funkce f(x) a g(x) nerostou asymptoticky stejně rychle. Funkce f(x) roste asymptoticky stejně rychle jako funkce log(x). Platí tedy nutně a) b) c) d) e)
g(x) ∉ Ο(log(x)) g(x) ∈ Θ(log(x)) g(x) ∉ Θ(log(x)) g(x) ∈ Ω(log(x)) g(x) ∉ Ω(log(x))
Funkce g(x) roste asymptoticky buď pomaleji nebo rychleji než f(x), roste tedy asymptoticky rychleji nebo pomaleji než funkce log(x). Který z těchto dvou případů nastává, ovšem není řečeno, takže jediné, co víme, je, že g(x) neroste stejně rychle jako log(x). Může růst pomaleji, čímž je vyloučena varianta a) a také d). Může však růst i rychleji, čímž je vyloučena varianta e). Variantu b) jsme před chvilkou vyloučili, takže zbývá jen správná varianta c).
9. ( úspěšnost: 42 z 49 = 86%) Merge sort, který dělí řazený úsek vždy na poloviny, řadí pole šesti čísel: { 3, 6, 1, 7, 2, 5 }. Situace v aktuálně řazeném poli (ať už to bude původní pole nebo pomocné) bude těsně před provedením posledního slévání (merging) následující: a) b) c) d) e)
123567 361725 765321 136257 176532
Merge sort je charakteristický tím, že nejprve pole rozdělí na poloviny aniž jakkoli „hýbe“ s daty, pak obě poloviny zvlášť seřadí a jako poslední krok provede operaci nazvanou slévání (meeting), jež obě seřazené poloviny sloučí v jedinou seřazenou posloupnost. To znamená, že po posledním slévání bude již pole definitivně seřazené a těsně před posledním sléváním budou seřazeny obě poloviny pole. První polovina pole obsahuje čísla 3, 6, 1, po jejím seřazení to bude 1, 3, 6. Podobně v druhé polovině po jejím seřazení najdeme hodnoty 2, 5, 7. Celkem tak před posledním sléváním bude pole obsahovat posloupnost 1, 3, 6, 2, 5, 7. To je právě varianta d).
10. ( úspěšnost: 41 z 49 = 84%) Automat A nad abecedou {a,b,c} má jediný koncový stav X. Automat A přijímá slovo ab. Po přečtení slova aba se octne ve startovním stavu. Automat A určitě přijme slovo (při tom začne vždy ve svém startovním stavu): a) b) c) d)
abc aaaaa ababa abaab
e) ababc Podstatné je, že automat A se po přečtení tří znaků tvořících slovo aba octne ve startovním stavu. To znamená, že pokud přijímá nějaké slovo α, přijímá dozajista také slovo abaα. (Proč? Protože jak při čtení slova α tak při čtení slova abaα se v okamžiku, kdy se chystá číst první znak v posloupnosti znaků tvořících slovo α, se nalézá ve startovním stavu.) Pro slovo α jednu možnost známe: α = ab. Tudíž je jisto, že automat A přijme také slovo abaab. To odpovídá variantě d). (Také by A přijal např. slovo abaabaabaabaab, apod.)
B Jméno:……………………….….. St. Sk.:……. Cvičící:………..………Bodů ze cv.:…… 1. ( úspěšnost: 44 z 48 = 92%) void gg(int x) { if (x < 0) return; abc(x); gg(x–1); gg(x–1); } Daná funkce gg je volána s parametrem 2: gg(2);. Funkce abc(x) je tedy celkem volána a) 1 krát b) 3 krát c) 4 krát d) 7 krát e) 8 krát Strom rekurzivního volání funkce gg vidíme na obrázku (jenž není součástí zadání úlohy), v každém uzlu je vepsána hodnota parametru x při odpovídajícím volání funkce gg. Při volání, kdy je hodnota x = –1, nastává okamžitý návrat z funkce gg a funkce abc v takovém případě již volána není. To znamená že funkce gg bude volána jen v bílých uzlech stromu na obrázku, jichž je dohromady 7. Platí varianta d).
2. ( úspěšnost: 41 z 48 = 85%) Jednoduchá levá rotace v uzlu u má operační složitost a) závislou na výšce levého podstromu uzlu u b) konstantní c) mezi O(1) a Ω(n) d) závislou na hloubce uzlu u Zde je nutno vědět, jak přibližně rotace vypadá. Mění jen několik ukazatelů na uzly stromu. Varianty a) a d) neplatí, varianta c) je nesmyslná sama o sobě, průnik množin O(1) a Ω(n) je prázdný. Platí samozřejmě b). ( úspěšnost: 36 z 48 = 75%) 3. Mapovací funkce pro pole uložené po řádcích s číslem řádku i v rozsahu i = <3,7> a sloupcovým indexem j = <2,5> a počáteční adresou pole v paměti adr vypadá následovně: a) b) c) d)
map(i,j) = adr + (i–3) + (j–2) * 5 map(i,j) = adr + (i–3) + (j–2) * 4 map(i,j) = adr + (i–3) * 4 + (j–2) map(i,j) = adr + (i–3) * 5 + (j–2) * 5
Nejjednodušeji varianty ověříme, když do každé z nich dosadíme. Vybereme si proto v poli prvek, který má co nejmenší index a přitom jeho poloha je „co nejobecnější“, tj. neleží ani v prvním řádku ani v prvním sloupci ani na diagonále a také jeho indexy se navzájem liší. To může být například zvýrazněný prvek s indexy [4] a [5] (obrázek není součástí zadání) . Jeho poloha od začátku pole při ukládání po řádcích je adr + 7. Dosaďme nyní jeho indexy do každé varianty: a) adr + (4 – 3) + (5 – 2) * 5 = adr + 1 + 3 * 5 = adr + 16 b) adr + (4 – 3) + (5 – 2) * 4 = adr + 1 + 3 * 4 = adr + 13 c) adr + (4 – 3) * 4 + (5 – 2) = adr + 1 * 4 + 3 = adr + 7 d) adr + (4 – 3) * 5 + (5 – 2) * 5 = adr + 1 * 5 + 3 * 5 = adr + 20 Souhlasí pouze varianta c). ¨
B 4. ( úspěšnost: 35 z 48 = 73%) Insert sort řadí do neklesajícího pořadí pole o n prvcích kde hodnoty od třetího do posledního prvku rostou a hodnoty prvních dvou prvků jsou stejné a v poli největší. Jediné nepravdivé označení asymptotické složitosti výpočtu je a) b) c) d) e)
Ο(n) Θ(n) Ο(n2) Ω(n2) Ω(n)
1.
2. Situace v poli před zahájením řazení je naznačena na prvním obrázku. V obecném kroku algoritmu se nad daným polem provede akce znázorněná na druhém obrázku. Dva velké prvky se posunou o pozici doprava a aktuální (šedý) prvek se posune o dvě pozice doleva. To představuje konstantní počet operací. Rovněž první krok algoritmu, kdy se pouze porovnají první dva prvky, potřebuje konstantní počet operací. Celkem tedy složitost výpočtu je úměrná výrazu konst ⋅ n. Platí ovšem konst ⋅ n ∈ Ο(n) (konst ⋅ n neroste asymptoticky rychleji než n) konst ⋅ n ∈ Θ(n) (to jsme právě zdůvodnili) konst ⋅ n ∈ Ο(n2) (a libovolné vyšší mocniny n) konst ⋅ n ∈ Ω(n) (konst ⋅ n neroste asymptoticky pomaleji než n) Jediné nepravdivé tvrzení je tudíž obsaženo ve variantě d).
5. ( úspěšnost: 33 z 48 = 69%) Zřetězený seznam synonym a) minimalizuje délku clusterů u metody otevřeného rozptylování b) u otevřeného rozptylování nevzniká c) je posloupnost synonym uložená v souvislém úseku adres d) řeší kolize uložením klíče na první volné místo v poli Otázka opět spíše definitorická. Zřetězený seznam dává jméno zřetězenému rozptylování, takže se v otevřeném rozptylování neobjevuje. Tím je vyloučena varianta a). Je nutná určitá představa o otevřeném rozptylování, neboť formulace variant c) a d) naznačuje, že se týkají právě jeho. Zbývá tak jen zřejmá správná varianta b) 6. ( úspěšnost: 35 z 48 = 73%) Na obrázku je skupina úseček. Při výpočtu jejich vzájemných průsečíků se udržuje postupový plán (x-struktura) a struktura svázaná s přímkou uchovávající mezivýsledky (ystruktura). Jaký je stav obou struktur po dokončení 3. kroku podle postupového plánu, tj.po aktualizaci obou struktur? a) X-str: P1,A, B, F, D Y-str: x,z b) X-str: A, P2,B, F, D Y-str: x,z,y c) X-str: A, B, F, D Y-str: z,y d) X-str: P1, P2,E, F, D Y-str: z,y
A x E
P1
B y
C
D
z P2 F
B Úloha je kopií úlohy z předtermínu, zde jen opakujeme řešení.
Jednotlivé kroky se činí zleva doprava, přičemž se postupuje po bodech, jenž jsou buďto krajními body úseček, nebo průsečíky, které již algoritmus při svém postupu zleva doprava nalezl. Protože ze začátku nejsou žádné průsečíky známy, obsahuje postupový plán (x-struktura) pouze krajní body úseček – C,E,A,B,F,D. V prvním kroku vstoupí algoritmus do bodu C a zaregistruje v y-struktuře jemu příslušející úsečku z. Ve druhém kroku vstoupí do bodu E a zaregistruje úsečku y nad(!) úsečkou z. V tu chvíli také určí průsečík úseček z a y – bod P1. Bod P1 se tak stává dalším zastavením postupového plánu zleva doprava a je vložen na jemu příslušné místo: P1, A, B, F, D (nesmíme přitom zapomínat, že body již jednou navštívené se z postupového plánu vylučují). Při zpracování bodu P1, což je třetí krok, se jednak obrátí pořadí úseček v y-struktuře, tj. z se ocitne nad y a dále P je vyloučeno z xstruktury. Žádný nový průsečík nebude objeven. Poté tedy máme: y-struktura v pořadí shora: z,y; x-struktura A,B,F,D. To odpovídá variantě b). Lze uvažovat i ještě mnohem jednodušeji: Ve třetím kroku algoritmus vstoupí do bodu P1, a tam ještě nemůže objevit bod P2, neboť dosud nedorazil do bodu A, tudíž dosud nemohl zaregistrovat úsečku x i s jejími průsečíky. Bod P2 tedy nemůže bát ještě prvkem postupového plánu (x-struktury). Ve variantách a), c) a d) však uveden je, což je nesprávně, takže zbývá jen varianta b).
7. ( úspěšnost: 41 z 48 = 85%) Funkce f(x) a g(x) nerostou asymptoticky stejně rychle. Funkce f(x) roste asymptoticky stejně rychle jako funkce x2 . Platí tedy nutně a) b) c) d) e)
x2∉ Ο(g(x)) x2∈ Θ(g(x)) x2∉ Ω (g(x)) x2∈ Ω(g(x)) nic z předchozího
g(x) roste asymptoticky buď pomaleji nebo rychleji než f(x), tedy roste asymptoticky rychleji nebo pomaleji než funkce x2. Který z těchto dvou případů nastává, ovšem není řečeno, takže jediné, co víme, je, že g(x) neroste stejně rychle jako x2. Může růst pomaleji, čímž je vyloučena varianta a) a také d). Může však růst i rychleji, čímž je vyloučena varianta c). Variantu b) jsme před chvilkou vyloučili, takže zbývá jen správná varianta e). 8. ( úspěšnost: 47 z 48 = 98%) Červenočerný strom a) b) c) d)
má maximální výšku rovnou dvojnásobku své černé výšky má tři typy uzlů: vnitřní černé, vnitřní červené a listy červené následníci červeného uzlu jsou vždy černí a jsou tři má červené listy
Červenočerný strom má řadu vlastností, které je nutno si pamatovat, odvozují se špatně. Citujme z přednášky: 1. Every node is either red or black 2. Every leaf (nil) is black 3. If a node is red, then both its children are black 4. Every simple path from a node to a descendant leaf contains the same number of black nodes (5. Root is black)
B Podmínka 3. říká, že v žádné cestě z kořene do listu nemůže být více červených uzlů než černých, výška stromu tedy nepřekročí dvojnásobek jeho černé výšky. Prostřídáme-li ve vyváženém stromu červené a černé vrstvy, vidíme, že lze tohoto maxima téměř dosáhnout. Varianta b) i d) je vyloučena podmínkou 2. Varianta c) nepravdivě sugeruje, že strom je ternární (Naopak následník ve smyslu uspořádání zleva doprava může být jen jeden).
9. ( úspěšnost: 45 z 48 = 94%) Automat A nad abecedou {d,e,f} má jediný koncový stav Y. Automat A přijímá slovo dd. Po přečtení slova ddf se octne ve startovním stavu. Automat A určitě přijme slovo(při tom začne vždy ve svém startovním stavu): a) b) c) d) e)
defdef ddfdd ddffd dfddd fdedf
Podstatné je, že automat A se po přečtení tří znaků tvořících slovo ddf octne ve startovním stavu. To znamená, že pokud přijímá nějaké slovo α, přijímá dozajista také slovo ddfα. (Proč? Protože jak při čtení slova α tak při čtení slova ddfα se v okamžiku, kdy se chystá číst první znak v posloupnosti znaků tvořících slovo α, nalézá se ve startovním stavu.) Pro slovo α jednu možnost známe: α = dd. Tudíž je jisto, že automat A přijme také slovo ddfdd. To odpovídá variantě b). (Také by A přijal např. slovo ddfddfddfddfddfddfddfdd, apod.)
10. ( úspěšnost: 42 z 48 = 88%) Merge sort, který dělí řazený úsek vždy na poloviny, řadí pole šesti čísel: { 2, 9, 4, 8, 1, 6 }. Situace v aktuálně zpracovaném poli (ať už to bude původní pole nebo pomocné) bude těsně před provedením posledního slévání (merging) následující: a) b) c) d) e)
249168 124689 294816 986421 198642
Merge sort je charakteristický tím, že nejprve pole rozdělí na poloviny aniž jakkoli „hýbe“ s daty, pak obě poloviny zvlášť seřadí a jako poslední krok provede operaci nazvanou slévání (meeting), jež obě seřazené poloviny sloučí v jedinou seřazenou posloupnost. To znamená, že po posledním slévání bude již pole definitivně seřazené a těsně před posledním sléváním budou seřazeny obě poloviny pole. První polovina pole obsahuje čísla 2, 9, 4, po jejím seřazení to bude 2, 4, 9. Podobně v druhé polovině po jejím seřazení najdeme hodnoty 1, 6, 8. Celkem tak před posledním sléváním bude pole obsahovat posloupnost 2, 9, 4, 1, 6, 8. To je právě varianta a).
B Úlohy druhé části jsou vesměs vybrány z loňska. Spanilomyslnou čtenářku odkazujeme tamtéž na řešení. A: 1. (4 b.) Implementujte operace Init, Search, Insert pro rozptylovací tabulku s otevřeným rozptylováním, do níž se ukládají celočíselné klíče. Předpokládejte, že rozptylovací funkce je již implementována a Vám stačí ji jen volat. Použijte strategii „Linear probing“. 2. (6 b.) Napište rekurzívně a nerekurzívně funkci, která projde n-ární strom (každý uzel může mít až n podstromů. Odkazy na podstromy jsou uloženy v každém uzlu v poli délky n). Datová struktura uzlu (1 bod). Rekurzívní verze (2b), nerekurzívní (3b.) 3. (5 b.) Na vstupu je neseřazené pole prvků pole[počet]. Bez toho, abyste toto pole seřadili, napište funkci, která v něm nalezne nalezne k-tý nejmenší prvek (= k-tý v seřazeném poli). Použijte metodu rozděl a panuj jako při řazení Quick-sortem, ale celé pole neřaďte. Hodnota k bude vstupním parametrem Vašeho algoritmu. B: 1. (4 b.) Implementujte operace Init, Search, Insert a Delete pro rozptylovací tabulku se zřetězeným rozptylováním, do níž se ukládají celočíselné klíče. Předpokládejte, že rozptylovací funkce je již implementována a Vám stačí ji jen volat. 2. (5 b.) Je dána struktura popisující uzel binárního vyhledávacího stromu takto Struct node { valType val; node * left, right; int count; } Navrhněte nerekurzívní proceduru, která do proměnné count v každém uzlu zapíše počet listů v podstromu, jehož kořenem je tento uzel (včetně tohoto uzlu, je-li sám listem). 3. (6 b.) Implementujte Selection sort pro jednosměrně zřetězený spojový seznam. ==================================================================== Celková konečná klasifikace při této zkoušce Známka 1 2 3 4 Počet v oddělení A 12 10 14 13 Počet v oddělení B 8 16 12 12 Závislost konečné známky v této zkoušce na počtu bodů ze semestru. (Např. známku 2 získalo 17 účastníků, jejichž bodový zisk ze semestru je 30-34 body. Body ze sem. 20-24 25-29 30-34 35-39 40-44 45-49 50-55 Počet známek 1 3 2 5 8 2 Počet známek 2 2 17 5 1 1 Počet známek 3 4 16 6 Počet známek 4 4 11 4 3 1 2
