Nederlands
Menu

Datastructuren en algoritmen

De expressie „3 4 + 2 * 5 −” in omgekeerde Poolse notatie (postfixnotatie) wordt geëvalueerd door elk getal op een stack te leggen en bij elke operator twee waarden eraf te halen, het resultaat te berekenen en dat weer op de stack te leggen. Wat is het resultaat? De linkeroperand van een operator is de waarde die het eerst op de stack is gelegd.

  1. A−9
  2. B6
  3. C9
Antwoord en toelichting tonen

Antwoord: C. 9

Eerst gaan 3 en 4 erop; + haalt ze eraf en legt 3 + 4 = 7 terug. Leg 2 erop; * legt 7 × 2 = 14 terug. Leg 5 erop; − trekt de latere waarde 5 af van de eerdere waarde 14, wat 14 − 5 = 9 oplevert. In postfixnotatie ligt de volgorde van de bewerkingen vast in de volgorde van de symbolen, dus haakjes zijn niet nodig; in de gewone notatie komt deze expressie overeen met (3 + 4) × 2 − 5. −9 ontstaat als de operanden van de aftrekking worden verwisseld, en 6 als de expressie zonder haakjes als 3 + 4 × 2 − 5 wordt gelezen.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Welke beschrijving van een botsing (collision) in een hashtabel is juist?
  2. De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?
  3. Welke vergelijking van chaining (de elementen op dezelfde positie aan elkaar koppelen in een gelinkte lijst) en open adressering (een andere vrije positie in de tabel zoeken) als methoden om botsingen in een hashtabel af te handelen is juist? De bezettingsgraad (load factor) is het aantal opgeslagen elementen gedeeld door de grootte van de tabel.
  4. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  5. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?