Κεφάλαιο 03.2 – Σελίδα 56 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 3 (σελ. 74)

Να δοθεί ο ορισμός της δομής δεδομένων.

Σκέψη / Μεθοδολογία: Ερώτηση με σαφή, κλειστή απάντηση — ο ορισμός δίνεται ρητά στο §3.2.

Λύση:

Ανατρέχουμε στον ορισμό του §3.2 και τον αποδίδουμε πλήρως.

Απάντηση: Δομή δεδομένων (data structure) είναι ένα σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών. Κάθε δομή δεδομένων αποτελείται από ένα σύνολο κόμβων (nodes).

Πρόσεξε:

• Να αναφερθεί τόσο το σύνολο δεδομένων όσο και το σύνολο λειτουργιών πάνω τους — ο ορισμός δεν αφορά μόνο τα δεδομένα, αλλά και τις επιτρεπτές πράξεις.

Ερώτηση 4 (σελ. 74)

Ποιες είναι οι βασικές πράξεις επί των δομών δεδομένων;

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση απαρίθμησης — οι οκτώ λειτουργίες δίνονται ρητά στο §3.2.

Λύση:

Απαριθμούμε τις οκτώ λειτουργίες με τη σειρά, δίνοντας για την καθεμία μία σύντομη επεξήγηση.

Απάντηση: Οι βασικές λειτουργίες πάνω σε μία δομή δεδομένων είναι: (1) Προσπέλαση — πρόσβαση σε κόμβο για εξέταση/τροποποίηση. (2) Εισαγωγή — προσθήκη νέου κόμβου. (3) Διαγραφή — αφαίρεση κόμβου. (4) Αναζήτηση — εντοπισμός κόμβου/κόμβων με συγκεκριμένη ιδιότητα. (5) Ταξινόμηση — διάταξη κόμβων κατά αύξουσα/φθίνουσα σειρά. (6) Αντιγραφή — αντιγραφή όλων ή μέρους των κόμβων σε άλλη δομή. (7) Συγχώνευση — ένωση δύο ή περισσότερων δομών σε μία. (8) Διαχωρισμός — αντίστροφο της συγχώνευσης.

Πρόσεξε:

• Να αναφερθούν και οι οκτώ πράξεις· να σημειωθεί ότι σπάνια χρησιμοποιούνται όλες πάνω στην ίδια δομή.

Ερώτηση 5 (σελ. 74)

Ποια είναι η εξάρτηση μεταξύ της δομής δεδομένων και του αλγορίθμου που επεξεργάζεται τη δομή;

Σκέψη / Μεθοδολογία: Ερώτηση κατανόησης — απαντάται με την εξίσωση του Wirth και το παράδειγμα του τηλεφωνικού καταλόγου από το §3.2.

Λύση:

Παραθέτουμε την εξίσωση του Wirth και εξηγούμε τι σημαίνει στην πράξη, χρησιμοποιώντας το παράδειγμα του τηλεφωνικού καταλόγου για να δείξουμε πώς η ίδια λειτουργία γίνεται πιο αποδοτική αλλάζοντας τη δομή δεδομένων.

Απάντηση: Ο Niklaus Wirth διατύπωσε την εξίσωση «Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα», που εκφράζει τη στενή, αδιάσπαστη σχέση ανάμεσα στη δομή δεδομένων και τον αλγόριθμο που την επεξεργάζεται. Η επιλογή της κατάλληλης δομής δεδομένων μπορεί να κάνει μια λειτουργία (π.χ. αναζήτηση ονόματος σε τηλεφωνικό κατάλογο) πολύ πιο αποδοτική, χωρίς να αλλάξει το «τι» ζητάμε — απλή σάρωση μιας ακολουθίας ζευγών είναι αργή για μεγάλη πόλη, ενώ μια ταξινομημένη ακολουθία με βοηθητική δομή ευρετηρίου ανά γράμμα περιορίζει την αναζήτηση σε μικρό τμήμα.

Πρόσεξε:

• Να μην αναφερθεί μόνο η εξίσωση, αλλά να εξηγηθεί με παράδειγμα γιατί η δομή δεδομένων επηρεάζει την απόδοση του αλγορίθμου.

Ερώτηση 6 (σελ. 74)

Να περιγραφούν οι δύο κυριότερες κατηγορίες των δομών δεδομένων.

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση σύγκρισης — η διάκριση στατικών/δυναμικών δίνεται ρητά στο §3.2.

Λύση:

Περιγράφουμε τις στατικές δομές και μετά τις δυναμικές, τονίζοντας τη διαφορά ως προς τη θέση στη μνήμη και το μεταβλητό μέγεθος.

Απάντηση: Οι στατικές (static) δομές αποθηκεύονται σε συνεχόμενες θέσεις μνήμης, με μέγεθος που καθορίζεται εκ των προτέρων και δεν αλλάζει κατά την εκτέλεση (π.χ. πίνακας, στοίβα, ουρά). Οι δυναμικές (dynamic) δομές δεν αποθηκεύονται απαραίτητα σε συνεχόμενες θέσεις — στηρίζονται στη δυναμική παραχώρηση μνήμης, οπότε ο αριθμός των κόμβων τους μπορεί να μεγαλώνει ή να μικραίνει κατά την εκτέλεση (π.χ. λίστα, δένδρο, γράφος).

Πρόσεξε:

• Να δοθεί έμφαση στα δύο κριτήρια διάκρισης: (α) συνεχόμενη ή μη θέση μνήμης, (β) σταθερό ή μεταβλητό μέγεθος.