221 / 306
Εκδόσεις ΜΠΑΧΑΡΑΚΗ – ΑΕΠΠ
220
Α5.
Να περιγράψετε τις κύριες λειτουργίες σε μια στοίβα και να αναφέρετε
τι πρέπει να ελέγχει κάθε λειτουργία, προκειμένου να μην παρουσιάζεται
πρόβλημα στη λειτουργία της στοίβας. (Μονάδες 7)
Απάντηση:
Α5.
Δύο είναι οι κύριες λειτουργίες σε μία στοίβα:
→
Η ώθηση (push) στοιχείου στην κορυφή της στοίβας, και
→
Η απώθηση (pop) στοιχείου από τη στοίβα.
Η διαδικασία της ώθησης πρέπει οπωσδήποτε να ελέγχει, αν η στοίβα είναι
γεμάτη, οπότε λέγεται ότι συμβαίνει υπερχείλιση (overflow) της στοίβας.
Αντίστοιχα, η διαδικασία απώθησης ελέγχει, αν υπάρχει ένα τουλάχιστον
στοιχείο στη στοίβα, δηλαδή ελέγχει αν γίνεται υποχείλιση (underflow) της
στοίβας. Μια στοίβα μπορεί να υλοποιηθεί πολύ εύκολα με τη βοήθεια ενός
μονοδιάστατου πίνακα. Μια βοηθητική μεταβλητή (με όνομα συνήθως top)
χρησιμοποιείται για να δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην
κορυφή της στοίβας. Για την εισαγωγή ενός νέου στοιχείου στη στοίβα (ώθηση)
αρκεί να αυξηθεί η μεταβλητή top κατά ένα και στη θέση αυτή να εισέλθει το
στοιχείο. Αντίθετα για την εξαγωγή ενός στοιχείου από τη στοίβα (απώθηση)
εξέρχεται πρώτα το στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η top
μειώνεται κατά ένα για να δείχνει τη νέα κορυφή.
Δίνεται το παρακάτω τμήμα αλγορίθμου, στο οποίο έχουν αριθμηθεί οι
γραμμές. Θεωρήστε ότι οι τιμές που εισάγονται είναι ακέραιες και
μεγαλύτερες του μηδενός.
1.
ΔΙΑΒΑΣΕ
x, y
2.
ΑΝ
x < y
ΤΟΤΕ
3.
z ← x
4.
ΑΛΛΙΩΣ
5.
z ← y
6.
ΤΕΛΟΣ_ΑΝ
7.
ΟΣΟ
z <> 0
ΕΠΑΝΑΛΑΒΕ
8.
z ← x
MOD
y
9.
x ← y
10.
y ← z
11.
ΤΕΛΟΣ_ ΕΠΑΝΑΛΗΨΗΣ
Β1.
Να αναπαραστήσετε με διάγραμμα ροής το παραπάνω τμήμα
αλγορίθμου. (Μονάδες 6)
Β2.
Δίνεται το ακόλουθο υπόδειγμα πίνακα τιμών:
ΘΕΜΑ Β
ΕΠΑΝΑΛΗΠΤΙΚΕΣ ΕΞΕΤΑΣΕΙΣ 2010