BPC-ALD_Zpracované_otazky_ke_zkousce
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Průběžný krok:
•Vezmeme prvek uložený v akt. uzlu 𝑢, označme ho 𝑐, a provedeme jeho srovnání s hledanou hodnotou 𝑥.
•Je-li 𝑥<𝑐, hledání musí pokračovat v levém podstromu.
•Jako nový aktuální uzel 𝑢 použijeme levého následníka současného aktuálního uzlu a znovu
provedeme průběžný krok.
•Pokud současný uzel levého následníka nemá, vyhledávání končí, hledaný prvek ve stromu není.
•Pokud není 𝑥<𝑐, srovnáme zda 𝑥>𝑐. Pokud ano, je nutno v hledání pokračovat v pravém podstromu.
•Jako nový aktuální uzel 𝑢 použijeme pravého následníka současného aktuálního uzlu a znovu
provedeme průběžný krok.
•Pokud současný uzel pravého následníka nemá, vyhledávání končí, hledaný prvek ve stromu není.
• Pokud není 𝑥<𝑐 a zároveň ani 𝑥>𝑐, musí být 𝑥=𝑐. Hledání končí, neboť prvek obsažený v aktuálním uzlu 𝑢 je
hledaným prvkem.
https://www.youtube.com/watch?v=LCdrThJcRQY
4. Co je to hašovací funkce, k čemu se používá a popište význam obou částí této funkce. (++) Účelem hašovací funkce je vytvořit obraz (celé číslo - číslo řádku v tabulce) vzoru (hodnota prvku (v případě struktury
hodnota klíče, podle kterého vyhledáváme)) - jedná se tedy o jakousi transformaci.;
Hašovací funkce se skládá ze dvou částí: funkce c(x) a funkce (operace) "modulo m”.
Funkce c(x) je závislá
na datovém typu prvku (resp. klíče) a vytváříme si ji sami. Tato funkce musí hodnotu prvku
převést na celé číslo.
Funkce "modulo m
” není závislá na datovém typu prvku (resp. klíče) a jejím úkolem je převést celé číslo (získáné
funkcí c(x)) na číslo řádku v hašovací tabulce (m je počet řádků hašovací tabulky).
Výsledná hašovací funkce má tvar: h(x) = c(x) mod m.
(Stejsky)
https://www.youtube.com/watch?v=MfhjkfocRR0&t=358s
Legenda:
(+) – Jednoduchá otázka
(++) – Středně obtížná otázka
(+++) – Obtížnější otázka