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.
//Back slash
je tam proto, že uvozovky jsou speciální znak (tzn.: Chceš-li v řetězci napsat uvozovky, musíš před ně
napsat ‘\’, tedy ‘\”’...podobně když chceš napsat ‘\’, musíš napsat ‘\\’, atd...). (Stejsky) +1
//pokud jsem dobře pochopil Petyho tak ten backslash tam má být pokud chceš v řetězci vytisknout úvozovky tzn => pokud chceš
vytisknout např tohle“ “ahoj”, řekl…” //Ano, protože to, co myslíš v printf, je tzv. formátovací řetězec (Stejsky)
//takže jo měl by tam být jenom znak “ -> dostáváš se do stavu úvozovky (Wójcik)
//Nene, do stavu UVOZOVKY se dostaneš po tom, co přijmeš znak
‘\”’ (viz. část mého programu). (Stejsky)
Přednáška 7: Vyhledávání a třídění (Ing. Ondřej Boštík)
Podrobněji vysvětleno v otázce 13-1 a 13-2 (Stejsky)
1. Popište algoritmus sekvenčního vyhledávání v nesetříděném poli hodnot. (+) Jedná se o postupné procházení a současné porovnávání prvků nesetříděného pole (od začátku do konce) s
hledaným prvkem X, dokud hledaný prvek nenajdeme. Pakliže je hledaný prvek hned na prvním místě, dojde
pouze k jednomu porovnání, složitost je tedy konstantní (O(1)). Může se ale stát, že bude hledaný prvek
posledním prvkem pole
– pak musíme provést n porovnání (pro pole o n prvcích), složitost v tomto případě je
lineární (O(n)
). Tedy průměrná časová složitost je O(n/2).
2. Popište algoritmus sekvenčního vyhledávání v setříděném poli hodnot. (+)
I když je pole setříděné, průběh i složitost budou stejné. (Fučela, Stejsky)
3. Popište algoritmus binárního vyhledávání v setříděném poli hodnot. (+)
• Nutností je setříděné pole
• Binární proto, že pole dělíme neustále na dvě poloviny
• O(log2(n)) • Vezmeme prvek, který je v poli uprostřed (jsou-li uprostřed 2, můžeme si zvolit levý nebo pravý) a označíme