GRUDAT, ÖVNING 7 Hashning, prioritetskö (heap, trappa) 1 TRAPPA MED TAL Om man stoppar in talen 3,1,4,2 i den konkreta datastrukturen heap och sedan plockar ut talen, vad händer i heapens inre? Vi tänker oss en min-heap (minsta talet överst). Var kan man finna största talet i en min-heap? 2 PROGRAMDATABAS (gammal tentauppgift) Titti Ruta vill varje vecka lägga in alla tevekanalers programtablåer i en databas för att inte missa något. Hon vill på datorns skärm hela tiden se vilka program som börjar den närmaste timmen. Vilken datastruktur vill du rekommendera? Välj en av följande och motivera! Vektor med binärsökning, lista med linjärsökning, binärträd, hashtabell, heap, stack. 3 WEBBTOPPEN (eller Tildatenta 21 mars 1998, uppgift 7) Vissa webbsidor räknar hur många besökare dom har eftersom välbesökta webbsidor ger prestige. Du får i uppdrag att skapa webbtoppen, ett program som för varje dag läser av räknarna för tiotusen webbsidor och sedan publicerar dagens tio i topp. Din första tanke är att spara talen i en vektor med längd tiotusen, leta fram och skriva ut segraren, nollställa segraren och göra detta tio gånger. Hur många jämförelser skulle krävas för denna algoritm? Din andra tanke är att spara talen i en trappa (heap) och sedan ta ut och skriva ut tio tal ur trappan. Hur många jämförelser kan det då bli frågan om? Din tredje tanke är att det borde räcka med en trappa med plats för tio tal. Hur skulle man då göra och hur många jämförelser skulle krävas? 4 SL TRAFIKSVAR (Tildatenta 12 april 1997, uppgift 4) 5 HASHAD HISTORIA (Tildatenta 13 mars 1999, uppgift 4) 6 FISKDAMMSDATATRUKTURER (Tildatenta 16 jan 2001, uppgift 7) 7 STADSSILHUETTEN Om man på håll betraktar en stad i skymningen ser man inte dom enskilda byggnaderna utan bara silhuetten, den yttersta konturen, avteckna sig mot himlen. Du ska ge en algoritm som givet varje byggnads kontur ska beräkna stadssilhuetten. Anta att alla byggnader står på x-axeln, är rektangulära och beskrivs av trippler x1, y, x2 där x1 är x-koordinaten för byggnadens vänstra vägg, x2 är x-koordinaten för dess högra vägg och y är dess höjd. Hustripplerna finns på filen hus.txt programmet ritar konturen med anrop av typen drawto(x,y).