ΤΕΣΤ (ΑΣΚΗΣΕΙΣ) ONLINE
98 Tests / Διαγωνίσματα

Κεφάλαιο 15.1 – (σελ. 16-22) – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

§15.1 Στοίβα — Ασκήσεις

Άσκηση 1 (σελ. 21)

Δίνεται η επόμενη ακολουθία αριθμών: 4, 8, 2, 5, 9, 13. α) Ποια λειτουργία θα χρησιμοποιήσετε για την τοποθέτηση των αριθμών σε στοίβα; β) Σχεδιάστε τη στοίβα μετά την τοποθέτηση των αριθμών. γ) Ποια λειτουργία θα χρησιμοποιηθεί για την έξοδο των αριθμών από τη στοίβα; δ) Πόσες φορές θα πρέπει να εκτελεστεί η προηγούμενη λειτουργία στη στοίβα για να εξαχθεί ο αριθμός 5;

Σκέψη / Μεθοδολογία: Οι αριθμοί εισάγονται με διαδοχικές ωθήσεις, οπότε η στοίβα έχει στην κορυφή τον τελευταίο που μπήκε (13). Για να εξαχθεί ο 5 πρέπει πρώτα να εξαχθούν όλα τα στοιχεία πάνω από αυτόν.

Λύση:

α) Η λειτουργία τοποθέτησης σε στοίβα είναι η Ώθηση (push). β) Ωθώντας διαδοχικά 4, 8, 2, 5, 9, 13, η στοίβα από τη βάση προς την κορυφή γίνεται: 4, 8, 2, 5, 9, 13 (κορυφή=13, top=6). γ) Η λειτουργία εξόδου είναι η Απώθηση (pop). δ) Πάνω από το 5 βρίσκονται τα 9 και 13 (2 στοιχεία). Άρα χρειάζονται 2 απωθήσεις (εξάγονται τα 13, 9) ώστε το 5 να φτάσει στην κορυφή, και μία ακόμη (3η συνολικά) απώθηση για να εξαχθεί και το ίδιο το 5.

Απάντηση: α) Ώθηση (push). β) Στοίβα από τη βάση: 4, 8, 2, 5, 9, 13 — κορυφή το 13 (top=6). γ) Απώθηση (pop). δ) Χρειάζονται 3 διαδοχικές απωθήσεις (εξάγονται με τη σειρά 13, 9 και τέλος 5) για να εξαχθεί ο αριθμός 5.

Πρόσεξε:

  • Η ερώτηση (δ) ζητά πόσες απωθήσεις χρειάζονται ΜΕΧΡΙ ΚΑΙ την εξαγωγή του 5 (δηλαδή 3), όχι μόνο πόσα στοιχεία βρίσκονται πάνω από αυτόν (2).

Άσκηση 2 (σελ. 21)

Σε μια στοίβα έχουν τοποθετηθεί κατά σειρά οι αριθμοί: 24, 7, 11, 13, 65, 39, 5. α) Να σχεδιάσετε την παραπάνω δομή. β) Ποια θα είναι η τιμή του δείκτη της παραπάνω στοίβας; γ) Αν θέλετε να τοποθετήσετε τον αριθμό 25 στην στοίβα, ποια λειτουργία θα χρησιμοποιήσετε; δ) Ποια θα είναι η τιμή του δείκτη μετά την λειτουργία αυτή; ε) Αν θέλετε να εξάγετε τον αριθμό 65 από τη στοίβα, ποια λειτουργία θα χρησιμοποιήσετε; στ) Ποια θα είναι η τιμή του δείκτη μετά τη λειτουργία αυτή;

Σκέψη / Μεθοδολογία: Η στοίβα έχει 7 στοιχεία, άρα top=7 αρχικά. Κάθε ώθηση αυξάνει το top κατά 1, κάθε απώθηση το μειώνει κατά 1 — ανεξάρτητα από ΠΟΙΟ στοιχείο εξάγεται (πάντα εξάγεται μόνο η κορυφή, όχι το 65 απευθείας).

Λύση:

α)-β) Η στοίβα από τη βάση προς την κορυφή είναι: 24, 7, 11, 13, 65, 39, 5, με top=7. γ)-δ) Η τοποθέτηση νέου στοιχείου γίνεται με Ώθηση· μετά την ώθηση του 25, top=8. ε)-στ) Η εξαγωγή γίνεται πάντα από την κορυφή, με Απώθηση· καθώς το 65 δεν βρίσκεται στην κορυφή, πρέπει πρώτα να απωθηθούν τα στοιχεία πάνω από αυτό.

Απάντηση: α)-β) Στοίβα (βάση→κορυφή): 24, 7, 11, 13, 65, 39, 5 · top=7. γ) Ώθηση (push). δ) top=8 (24, 7, 11, 13, 65, 39, 5, 25). ε) Απώθηση (pop) — αλλά επειδή η στοίβα επιτρέπει πρόσβαση μόνο στην κορυφή, το 65 δεν εξάγεται απευθείας· πρέπει πρώτα να απωθηθούν τα στοιχεία 25, 5, 39 που βρίσκονται πάνω από αυτό. στ) Μετά από μία μόνο απώθηση (του 25), το top γίνεται 7· για να εξαχθεί τελικά το 65 χρειάζονται συνολικά 4 διαδοχικές απωθήσεις, οπότε το top καταλήγει σε 4.

Πρόσεξε:

  • Παγίδα: το ερώτημα (ε) φαίνεται να ζητά απευθείας εξαγωγή του 65, αλλά η στοίβα δεν επιτρέπει τυχαία πρόσβαση — μόνο η κορυφή είναι προσβάσιμη κάθε φορά.

Άσκηση 3 (σελ. 22)

Χαρακτηρίστε τις παρακάτω προτάσεις ως Σωστές ή Λάθος. Στην περίπτωση που πιστεύετε ότι είναι λανθασμένες δικαιολογήστε την επιλογή σας.

  1. Για την υλοποίηση μιας στοίβας μπορεί να χρησιμοποιηθεί ένας πίνακας.
  2. Στη στοίβα το στοιχείο που μπαίνει πρώτο βγαίνει πρώτο.
  3. Στην υλοποίηση της στοίβας χρειάζονται δύο μεταβλητές-δείκτες.
  4. Η λειτουργία της ώθησης μπορεί να εκτελεστεί και σε μια άδεια στοίβα.
  5. Η λειτουργία της ώθησης μπορεί να εκτελεστεί και σε μια γεμάτη στοίβα.
  6. Η ώθηση στοιχείου γίνεται στην κορυφή της στοίβας.
  7. Στη δομή της στοίβας απαιτούνται δύο δείκτες, ο εμπρός και ο πίσω.
  8. Υπερχείλιση έχουμε όταν εισάγουμε ένα στοιχείο σε μία ήδη γεμάτη στοίβα.
  9. Η μέθοδος LIFO περιγράφει τη διαδικασία εκείνη κατά την οποία το στοιχείο που τοποθετείται τελευταίο εξάγεται πρώτο.
  10. Κάθε στοιχείο που εισάγεται πρώτο σε μια στοίβα είναι αυτό που εξάγεται πρώτο.

Σκέψη / Μεθοδολογία: Ελέγχουμε κάθε πρόταση ξεχωριστά έναντι του ορισμού LIFO και της υλοποίησης με έναν μόνο δείκτη top (οι προτάσεις 3 και 7 περιγράφουν στην πραγματικότητα την ουρά).

Απάντηση:

  1. Σωστό — η υλοποίηση με μονοδιάστατο πίνακα είναι η συνηθέστερη.
  2. Λάθος — ισχύει LIFO: το στοιχείο που μπαίνει ΤΕΛΕΥΤΑΙΟ βγαίνει πρώτο.
  3. Λάθος — χρειάζεται μόνο ΕΝΑΣ δείκτης (top)· αυτό ισχύει για την ουρά.
  4. Σωστό — η ώθηση σε άδεια στοίβα (top=0) είναι έγκυρη λειτουργία.
  5. Λάθος — η ώθηση σε γεμάτη στοίβα προκαλεί υπερχείλιση.
  6. Σωστό — η ώθηση προσθέτει πάντα στοιχείο στην κορυφή.
  7. Λάθος — οι δείκτες «εμπρός/πίσω» (front/rear) χαρακτηρίζουν την ουρά.
  8. Σωστό — αυτός είναι ο ορισμός της υπερχείλισης.
  9. Σωστό — αυτός είναι ο ορισμός του LIFO.
  10. Λάθος — το πρώτο στοιχείο που εισάγεται είναι το ΤΕΛΕΥΤΑΙΟ που εξάγεται.

Πρόσεξε:

  • Οι προτάσεις 3 και 7 είναι η πιο συνηθισμένη παγίδα — περιγράφουν τη δομή της ΟΥΡΑΣ, όχι της στοίβας.

Άσκηση 4 (σελ. 16)

Να αναπτύξετε τμήμα προγράμματος σε ΓΛΩΣΣΑ, που πραγματοποιεί ώθηση στοιχείου στην κορυφή της στοίβας με χρήση μονοδιάστατου πίνακα Α, 10 θέσεων.

Σκέψη / Μεθοδολογία: Θεωρούμε ότι η στοίβα δεν είναι κενή και η μεταβλητή top έχει έγκυρη τιμή· ελέγχουμε top<10 πριν την ώθηση.

Απάντηση:

ΓΡΑΨΕ 'Δώσε στοιχείο για να εισαχθεί στη στοίβα Α:'
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ top<10 ΤΟΤΕ
    top ← top+1
    A[top] ← στοιχείο
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υπερχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ

Πρόσεξε:

  • Ο έλεγχος υπερχείλισης (top<10) γίνεται ΠΡΙΝ την αύξηση του top.

Άσκηση 5 (σελ. 16)

Να αναπτύξετε τμήμα προγράμματος σε ΓΛΩΣΣΑ που πραγματοποιεί την απώθηση στοιχείου από στοίβα με χρήση ενός μονοδιάστατου πίνακα Α, 10 θέσεων.

Σκέψη / Μεθοδολογία: Θεωρούμε ότι η στοίβα δεν είναι κενή· ελέγχουμε top≥1 πριν την απώθηση.

Απάντηση:

ΑΝ top>=1 ΤΟΤΕ
    ΓΡΑΨΕ Α[top]
    top ← top-1
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υποχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ

Πρόσεξε:

  • Η εκτύπωση του στοιχείου γίνεται ΠΡΙΝ τη μείωση του top.