Δυναμικές Δομές Δεδομένων Λίστες Δένδρα Γράφοι
Θεωρία Πληροφορική Γ Λυκείου
Κοινό γνώρισμα των στατικών δομών που υλοποιήθηκαν με χρήση μονοδιάστατου πίνακα είναι ότι οι διαδοχικοί κόμβοι αποθηκεύονται σε συνεχόμενες θέσεις της κύριας μνήμης. Στην ενότητα αυτή παρουσιάζεται η περίπτωση τριών σημαντικών δομών δεδομένων, στις οποίες οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης. Οι δομές αυτές ανήκουν στην κατηγορία των δυναμικών δομών δεδομένων και πρόκειται για τις λίστες, τα δένδρα και τους γράφους.
Λίστες Θεωρία Ορισμοί ΑΕΠΠ Γ Λυκείου
Το πεδίο Δεδομένα μπορεί να περιέχει μία ή περισσότερες αλφαριθμητικές ή αριθμητικές πληροφορίες. Ο δείκτης είναι ένας ιδιαίτερος τύπος δεδομένων που προσφέρεται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού. Ο δείκτης δεν λαμβάνει αριθμητικές τιμές όπως ακέραιες, πραγματικές κ.ά., αλλά οι τιμές του είναι διευθύνσεις στην κύρια μνήμη και χρησιμοποιείται ακριβώς για τη σύνδεση των διαφόρων στοιχείων μιας δομής, που είναι αποθηκευμένα σε μη συνεχόμενες θέσεις μνήμης.
Μία απλά συνδεδεμένη λίστα είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά. Κάθε κόμβος περιέχει, εκτός από τα δεδομένα του, και έναν δείκτη που δείχνει προς τον επόμενο κόμβο. Ο δείκτης του τελευταίου κόμβου δεν δείχνει σε κάποιον κόμβο. Για να το δηλώσουμε αυτό λέμε ότι το πεδίο δείκτη του τελευταίου κόμβου έχει την τιμή NULL. Για να προσπελάσουμε τους κόμβους της λίστας χρειάζεται να γνωρίζουμε τη διεύθυνση του πρώτου κόμβου της λίστας. Η διεύθυνση αυτή αποθηκεύεται σε μία ειδική μεταβλητή που την ονομάζουμε συνήθως Κεφαλή.
Απλά συνδεδεμένη λίστα με τέσσερις κόμβους. Ο δείκτης του τελευταίου κόμβου έχει την τιμή NULL.
Πως γίνεται η πρόσβαση στους κόμβους μιας απλά συνδεδεμένης λίστας
Οι κόμβοι μιας απλά συνδεδεμένης λίστας είναι διατεταγμένοι σε μια συγκεκριμένη σειρά, χωρίς αυτό να σημαίνει ότι αποθηκεύονται σε συνεχόμενες θέσεις στη μνήμη. Αντίθετα, είναι διασκορπισμένοι σε όλη τη μνήμη και η σύνδεση μεταξύ τους γίνεται μέσω των δεικτών. Έχουμε άμεση πρόσβαση μόνο στον πρώτο κόμβο της λίστας. Επομένως, για να εντοπίσουμε κάποιον από τους ενδιάμεσους κόμβους, πρέπει να ξεκινήσουμε από τον πρώτο κόμβο της λίστας και να ακολουθήσουμε τους δείκτες με τη σειρά, μέχρι να φτάσουμε στον επιθυμητό κόμβο.
Οι συνδεδεμένες λίστες αξιοποιούνται για την υλοποίηση της στοίβας και της ουράς, λόγω της δυνατότητας αυξομείωσης του μεγέθους τους.
Διπλά συνδεδεμένη λίστα Λειτουργία και Σχήμα
Στην απλά συνδεδεμένη λίστα μπορούμε να κινηθούμε προς μία μόνο κατεύθυνση, ξεκινώντας από τον αρχικό κόμβο και μετακινούμενοι προς τον τελευταίο.
Διπλά συνδεδεμένη λίστα: κάθε κόμβος έχει δείκτη προς τον προηγούμενο και προς τον επόμενο κόμβο.
Εισαγωγή και διαγραφή κόμβου σε απλά συνδεδεμένη λίστα τρόπος σχεδίασης και σχήμα
Με τη χρήση δεικτών διευκολύνονται οι λειτουργίες της εισαγωγής και της διαγραφής δεδομένων στις λίστες, γιατί δεν χρειάζεται να μετακινηθούν τα υπόλοιπα στοιχεία. Αρκεί να αλλάξουν οι δείκτες.
Εισαγωγή του κόμβου 28 μεταξύ του δεύτερου και του τρίτου κόμβου: ① ο δείκτης του νέου κόμβου δείχνει στον τρίτο κόμβο και ② ο δείκτης του δεύτερου κόμβου δείχνει στον νέο κόμβο.
Εισαγωγή κόμβου: αλλάζουν μόνο δύο δείκτες και οι υπόλοιποι κόμβοι δεν μετακινούνται.
Διαγραφή του τρίτου κόμβου (31): ο δείκτης του δεύτερου κόμβου αλλάζει και δείχνει πλέον στον τέταρτο κόμβο. Ο τρίτος κόμβος αποσυνδέεται από τη λίστα.
Διαγραφή κόμβου: ο δείκτης του προηγούμενου κόμβου «προσπερνά» τον κόμβο που διαγράφεται.
Διαφορές λίστας σε σχέση με τον πίνακα στη πληροφορική
| Πίνακας | Λίστα | |
|---|---|---|
| Προσπέλαση | Δομή τυχαίας προσπέλασης. | Δομή ακολουθιακής ή σειριακής προσπέλασης. Για να φθάσουμε σε έναν κόμβο πρέπει να περάσουμε από όλους τους προηγούμενους, ξεκινώντας από τον πρώτο. |
| Μέγεθος | Σταθερό μέγεθος, που δηλώνεται εξαρχής κατά την υλοποίηση, γιατί ο πίνακας είναι στατική δομή. | Δυναμική δομή: το μέγεθός της μεταβάλλεται καθώς εισέρχονται νέοι κόμβοι ή διαγράφονται κάποιοι άλλοι. |
| Αποθήκευση | Συνεχόμενες θέσεις μνήμης. | Μη συνεχόμενες θέσεις μνήμης. |
Πλεονεκτήματα και μειονεκτήματα χρήσης λιστών στη πληροφορική
| Πλεονεκτήματα | Μειονεκτήματα |
|---|---|
|
• Το δυναμικό τους μέγεθος. • Η ευκολία εισαγωγής και διαγραφής από οποιοδήποτε μέρος της λίστας. • Η μη αναγκαιότητα δήλωσης του μεγέθους τους. |
• Η τυχαία πρόσβαση στη λίστα δεν επιτρέπεται. Είναι αδύνατο να φτάσετε στον n-οστό κόμβο μιας απλά συνδεδεμένης λίστας χωρίς πρώτα να περάσετε από όλους τους κόμβους διαδοχικά, ξεκινώντας από τον πρώτο. Στην περίπτωση της διπλά συνδεδεμένης λίστας μπορείτε να ξεκινήσετε και από τον τελευταίο κόμβο. Επομένως, δεν μπορούμε να πραγματοποιήσουμε με αποτελεσματικό τρόπο δυαδική αναζήτηση σε συνδεδεμένες λίστες. • Οι συνδεδεμένες λίστες έχουν πολύ μεγαλύτερη επιβάρυνση από τους πίνακες, αφού οι συνδεδεμένοι κόμβοι είναι δυναμικά κατανεμημένοι και κάθε κόμβος πρέπει, επιπλέον, να αποθηκεύσει έναν πρόσθετο δείκτη που δείχνει στον επόμενο κόμβο. Στις διπλά συνδεδεμένες λίστες χρειαζόμαστε επιπλέον έναν δεύτερο δείκτη που δείχνει στον προηγούμενο κόμβο. |
Βασικές πράξεις των συνδεδεμένων λιστών στη πληροφορική
- Εισαγωγή κόμβου στη λίστα (στην αρχή, στο τέλος της λίστας ή ενδιάμεσα).
- Διαγραφή κόμβου από τη λίστα (από την αρχή, το τέλος της λίστας ή ενδιάμεσα).
- Έλεγχος για το αν η λίστα είναι κενή.
- Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου.
- Διάσχιση της λίστας και προσπέλαση των στοιχείων της.
Δένδρα Θεωρία Ορισμοί ΑΕΠΠ Γ Λυκείου
Ένα δένδρο αποτελείται από κόμβους, οι οποίοι συνδέονται μεταξύ τους με ακμές. Όταν δύο κόμβοι συνδέονται μεταξύ τους με μία ακμή, ονομάζουμε γονέα τον κόμβο από τον οποίο ξεκινάει η ακμή και παιδί τον κόμβο στον οποίο καταλήγει η ακμή. Ένας κόμβος μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά. Όλοι οι κόμβοι, εκτός από έναν, έχουν ακριβώς έναν γονέα. Ο κόμβος χωρίς γονέα ονομάζεται ρίζα και βρίσκεται στην κορυφή του δένδρου. Κόμβοι με τον ίδιο γονέα ονομάζονται αδέλφια. Οι κόμβοι χωρίς παιδιά ονομάζονται φύλλα.
Δένδρο με 7 κόμβους: ρίζα ο Α, φύλλα οι Γ, Ε, Ζ, Η.
Μπορούμε να έχουμε ένα απλό δένδρο, το οποίο να απαρτίζεται από έναν μόνο κόμβο. Αυτός ο κόμβος είναι και ρίζα του δένδρου, διότι δεν έχει γονέα, και φύλλο, διότι δεν έχει παιδιά.
- Υπάρχει ένας ξεχωριστός κόμβος που ονομάζεται ρίζα. Αυτός είναι ένας κόμβος χωρίς γονέα.
- Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c παιδί του p.
- Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο.
Δένδρο απόφασης στη πληροφορική
Τα δένδρα απόφασης είναι δένδρα στα οποία κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό, κάθε ακμή αντιπροσωπεύει μια απόφαση και κάθε φύλλο αντιπροσωπεύει ένα αποτέλεσμα. Στους αλγορίθμους μηχανικής μάθησης τα δένδρα απόφασης έχουν πρωτεύοντα ρόλο.
Ο κόμβος αντιπροσωπεύει ένα χαρακτηριστικό (ερώτηση), οι ακμές τις αποφάσεις και τα φύλλα το αποτέλεσμα. Το παράδειγμα είναι ενδεικτικό.
Δυαδικά δένδρα στη πληροφορική
Μπορούμε, συνεπώς, να μιλάμε για αριστερό και δεξιό υποδένδρο ενός κόμβου. Προφανώς, αν ανταλλάξουμε το αριστερό με το δεξιό υποδένδρο ενός κόμβου, παίρνουμε ένα διαφορετικό δένδρο.
Δυαδικά δένδρα αναζήτησης στη πληροφορική και διαφορές με τα απλά δυαδικά δένδρα
Δυαδικό δένδρο αναζήτησης: στο αριστερό υποδένδρο κάθε κόμβου βρίσκονται μικρότερες τιμές και στο δεξιό μεγαλύτερες.
Λόγω αυτής της διάταξης, η αναζήτηση μιας τιμής ξεκινά από τη ρίζα: αν η τιμή είναι μικρότερη από την τιμή του κόμβου, συνεχίζουμε στο αριστερό υποδένδρο, ενώ αν είναι μεγαλύτερη, συνεχίζουμε στο δεξιό. Σε κάθε βήμα αποκλείεται ένα ολόκληρο υποδένδρο.
Γράφοι Θεωρία Ορισμός ΑΕΠΠ Γ Λυκείου
Το πιο θεμελιώδες χαρακτηριστικό των μη γραμμικών δομών είναι ότι τα δεδομένα τους δεν ακολουθούν μια σειρά, όπως στους πίνακες ή τις συνδεδεμένες λίστες. Τα δένδρα, όπως είδαμε, ξεκινούν με έναν κόμβο ρίζας και μπορεί να συνδεθούν με άλλους κόμβους, κάτι που σημαίνει ότι θα μπορούσαν να περιέχουν δευτερεύοντα δένδρα στο εσωτερικό τους. Τα δένδρα, γενικά, διέπονται από συγκεκριμένους κανόνες, ενώ σε ορισμένους τύπους δένδρων ισχύουν ιδιαίτεροι κανόνες, όπως στα δυαδικά δένδρα αναζήτησης, στα οποία κάθε κόμβος έχει το πολύ δύο παιδιά.
Αλλά τι θα γίνει αν αγνοήσουμε αυτούς τους κανόνες; Τότε δεν αναφερόμαστε σε δένδρα αλλά σε μία νέα δυναμική δομή δεδομένων, που ονομάζεται γράφος. Τα δένδρα δεν είναι παρά περιορισμένοι τύποι γράφων. Ένα δένδρο θα είναι πάντα ένας γράφος, αλλά δεν είναι όλοι οι γράφοι δένδρα.
Διαφορές γράφου και δένδρου στη πληροφορική
| Δένδρο | Γράφος | |
|---|---|---|
| Ρίζα | Έχει κόμβο ρίζας. | Δεν έχει την έννοια ενός κόμβου «ρίζας». Οι κόμβοι μπορούν να συνδεθούν με οποιονδήποτε τρόπο. |
| Κατεύθυνση | Μπορεί μόνο να ρέει προς μία κατεύθυνση, από τον κόμβο ρίζας προς τους κόμβους φύλλων ή παιδιών. | Δεν έχει «μονοκατευθυντική» ροή. Μπορεί να έχει κατεύθυνση ή να μην έχει καμία κατεύθυνση. |
| Συνδέσεις | Μόνο μονόδρομες συνδέσεις. Ένας κόμβος παιδί μπορεί να έχει μόνο έναν γονέα και δεν μπορεί να υπάρχουν βρόχοι ή κυκλικοί δεσμοί. | Δεν υπάρχουν τέτοιοι περιορισμοί. |
Τύποι γράφων στην πληροφορική
Σε έναν γράφο δεν υπάρχουν πραγματικοί κανόνες για τον τρόπο που ένας κόμβος συνδέεται με έναν άλλο κόμβο. Οι ακμές μπορούν να συνδέσουν τους κόμβους με οποιονδήποτε τρόπο. Οι διαφορετικοί τύποι ακμών είναι πολύ σημαντικοί όταν πρόκειται για την αναγνώριση και τον καθορισμό του τύπου των γράφων. Δύο τύποι γράφων είναι αρκετά εύκολο να εντοπιστούν και είναι συνηθισμένοι στα προβλήματα θεωρίας γράφων:
- Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος.
- Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος.
Ο γράφος έχει κύκλους (π.χ. Α-Β-Γ-Δ) και δεν έχει ρίζα, γι' αυτό δεν είναι δένδρο.
Ασκήσεις θεωρίας στις Δυναμικές δομές δεδομένων ΑΕΠΠ Γ Λυκείου
Σωστό / Λάθος Λιστες Δένδρα Γράφοι στη Πληροφορική
Απαντήστε πρώτα μόνοι σας και μετά ελέγξτε τις απαντήσεις στον πίνακα.
- Μια διπλά συνδεδεμένη λίστα μπορούμε να τη διατρέξουμε μόνο προς μία κατεύθυνση.
- Σε μια απλά συνδεδεμένη λίστα, τα στοιχεία μπορούν να αφαιρεθούν από παντού εκτός από το τέλος της.
- Κάθε λίστα είναι γράφος.
- Κάθε δένδρο είναι γράφος.
- Σε ένα δυαδικό δένδρο αναζήτησης, κάθε κόμβος-γονέας μπορεί να έχει τουλάχιστον δύο παιδιά.
- Το φύλλο ενός δένδρου είναι ο μόνος κόμβος ενός δένδρου που δεν έχει γονέα.
- Σε ένα δένδρο, κάθε κόμβος-γονέας μπορεί να έχει οποιονδήποτε αριθμό παιδιών.
- Οι γράφοι υποχρεωτικά έχουν ακμές με κατεύθυνση.
- Οι λίστες και οι πίνακες είναι στατικές δομές δεδομένων.
- Οι στοίβες και οι ουρές υλοποιούνται με λίστες.
| Α/Α | Απάντηση | Γιατί |
|---|---|---|
| 1 | Λάθος | Η διπλά συνδεδεμένη λίστα διατρέχεται και προς τις δύο κατευθύνσεις. |
| 2 | Λάθος | Η διαγραφή επιτρέπεται από την αρχή, το τέλος ή ενδιάμεσα. |
| 3 | Σωστό | Ο γράφος είναι η πιο γενική δομή, και όλες οι άλλες δομές μπορούν να θεωρηθούν περιπτώσεις γράφων. |
| 4 | Σωστό | Τα δένδρα είναι περιορισμένοι τύποι γράφων. |
| 5 | Λάθος | Σε ένα δυαδικό δένδρο κάθε κόμβος έχει το πολύ δύο παιδιά. |
| 6 | Λάθος | Ο μόνος κόμβος χωρίς γονέα είναι η ρίζα. Τα φύλλα είναι οι κόμβοι χωρίς παιδιά. |
| 7 | Σωστό | Ένας κόμβος σε ένα (γενικό) δένδρο μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά. |
| 8 | Λάθος | Οι ακμές ενός γράφου μπορεί να έχουν κατεύθυνση ή να μην έχουν καμία κατεύθυνση. |
| 9 | Λάθος | Ο πίνακας είναι στατική δομή, ενώ η λίστα είναι δυναμική δομή. |
| 10 | Σωστό | Οι συνδεδεμένες λίστες αξιοποιούνται για την υλοποίηση της στοίβας και της ουράς, λόγω της δυνατότητας αυξομείωσης του μεγέθους τους. |
Ερωτήσεις ανάπτυξης Λιστες Δένδρα Γράφοι στη Πληροφορική
Οι λύσεις είναι γραμμένες όπως θα ζητηθούν στις πανελλήνιες εξετάσεις. Κεφάλαιο γεμάτο ορισμούς και θεωρία, μπορούν να πέσουν και σαν ανάπτυξης και σαν πολλαπλής επιλογής ακόμη και σαν αντιστοίχισης. Ξεκάθαρο σημείο των εξετάσεων ΑΕΠΠ Γ λυκείου είναι ότι συνδιάζουν τη θεωρία και την πράξη με μορφή σχημάτων.
1. Τι ονομάζουμε «απλά συνδεδεμένη λίστα» και τι «διπλά συνδεδεμένη»;
Μία λίστα ονομάζεται «διπλά συνδεδεμένη» όταν μπορούμε να τη διατρέξουμε και προς τις δύο κατευθύνσεις. Για την υλοποίησή της χρειαζόμαστε δύο δείκτες:
α) τον δείκτη «κεφαλή» που δείχνει τον πρώτο κόμβο της λίστας,
β) τον δείκτη «ουρά» που δείχνει τον τελευταίο κόμβο της λίστας.
2. Τι είναι το δυαδικό δένδρο αναζήτησης;
3. Τι είναι δένδρο, φύλλο, γονέας - παιδί, ρίζα, αδέλφια;
2) Γονέας και παιδί: όταν δύο κόμβοι ενώνονται μεταξύ τους με μία ακμή, γονέας είναι ο κόμβος από τον οποίο ξεκινάει η ακμή και παιδί είναι ο κόμβος στον οποίο καταλήγει η ακμή. Ένας κόμβος μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά.
3) Ρίζα: είναι ο κόμβος που δεν έχει γονέα και βρίσκεται στην κορυφή του δένδρου.
4) Αδέλφια: είναι κόμβοι που έχουν τον ίδιο γονέα.
5) Φύλλα: είναι κόμβοι που δεν έχουν παιδιά.
4. Ποιες είναι οι διαφορές λίστας και πίνακα;
• Ο πίνακας έχει σταθερό μέγεθος που δηλώνεται εξαρχής (στατική δομή), ενώ το μέγεθος της λίστας μεταβάλλεται (δυναμική δομή).
• Οι κόμβοι της λίστας αποθηκεύονται σε μη συνεχόμενες θέσεις μνήμης, ενώ τα στοιχεία του πίνακα σε συνεχόμενες.
5. Ποια είναι τα πλεονεκτήματα και τα μειονεκτήματα των λιστών σε σχέση με τους πίνακες;
Μειονεκτήματα: δεν επιτρέπεται τυχαία πρόσβαση (δεν γίνεται αποτελεσματικά δυαδική αναζήτηση) και υπάρχει μεγαλύτερη επιβάρυνση μνήμης, αφού κάθε κόμβος αποθηκεύει επιπλέον δείκτη (δύο στη διπλά συνδεδεμένη λίστα).
6. Ποιες είναι οι βασικές πράξεις των συνδεδεμένων λιστών;
7. Τι είναι ο γράφος και ποιες είναι οι διαφορές του από το δένδρο;
8. Ποιοι είναι οι τύποι γράφων με βάση τις ακμές;
Πολλαπλής επιλογής Λιστες Δένδρα Γράφοι στη Πληροφορική
Σε κάθε ερώτηση να επιλέξετε τη σωστή απάντηση. Υπάρχει μόνο μία σωστή επιλογή.
1. Ποια τιμή έχει το πεδίο δείκτη του τελευταίου κόμβου μιας απλά συνδεδεμένης λίστας;
- 0
- NULL
- -1
- Τη διεύθυνση του πρώτου κόμβου
2. Σε μια απλά συνδεδεμένη λίστα έχουμε άμεση πρόσβαση:
- μόνο στον πρώτο κόμβο
- μόνο στον τελευταίο κόμβο
- σε οποιονδήποτε κόμβο
- σε κανέναν κόμβο
3. Ποιο από τα παρακάτω ΔΕΝ είναι πλεονέκτημα των λιστών σε σχέση με τους πίνακες;
- Το δυναμικό μέγεθος
- Η ευκολία εισαγωγής και διαγραφής κόμβων
- Η μη αναγκαιότητα δήλωσης του μεγέθους
- Η τυχαία πρόσβαση στα στοιχεία
4. Πώς ονομάζεται ο κόμβος ενός δένδρου που δεν έχει γονέα;
- Φύλλο
- Αδέλφι
- Ρίζα
- Παιδί
5. Σε ένα δυαδικό δένδρο αναζήτησης, για κάθε κόμβο u ισχύει ότι:
- οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες από την τιμή του u
- οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μεγαλύτερες από την τιμή του u
- ο u έχει τουλάχιστον δύο παιδιά
- ο u δεν έχει γονέα
6. Ένας γράφος του οποίου καμία ακμή δεν έχει κατεύθυνση ονομάζεται:
- κατευθυνόμενος γράφος
- μη κατευθυνόμενος γράφος
- δυαδικό δένδρο
- συνδεδεμένη λίστα
| Ερώτηση | Σωστή απάντηση | Γιατί |
|---|---|---|
| 1 | β | Ο δείκτης του τελευταίου κόμβου δεν δείχνει σε κάποιον κόμβο, και το πεδίο του έχει την τιμή NULL. |
| 2 | α | Έχουμε άμεση πρόσβαση μόνο στον πρώτο κόμβο, μέσω της μεταβλητής Κεφαλή. Για τους υπόλοιπους ακολουθούμε τους δείκτες με τη σειρά. |
| 3 | δ | Η τυχαία πρόσβαση είναι χαρακτηριστικό του πίνακα. Στη λίστα η προσπέλαση είναι σειριακή, και αυτό είναι μειονέκτημα. |
| 4 | γ | Ο κόμβος χωρίς γονέα ονομάζεται ρίζα και βρίσκεται στην κορυφή του δένδρου. |
| 5 | α | Στο αριστερό υποδένδρο βρίσκονται μικρότερες τιμές και στο δεξιό μεγαλύτερες. Κάθε κόμβος έχει το πολύ δύο παιδιά. |
| 6 | β | Αν όλες οι ακμές δεν έχουν κατεύθυνση, ο γράφος είναι μη κατευθυνόμενος. |
Αντιστοίχιση Λιστες Δένδρα Γράφοι στη Πληροφορική
Να αντιστοιχίσετε κάθε έννοια της στήλης Α με την περιγραφή της στη στήλη Β. Στη στήλη Β υπάρχουν δύο περιγραφές που περισσεύουν.
| Στήλη Α | Στήλη Β |
|---|---|
| 1. Κεφαλή | α. Τύπος δεδομένων που οι τιμές του είναι διευθύνσεις στην κύρια μνήμη. |
| 2. Δείκτης | β. Κόμβοι που έχουν τον ίδιο γονέα. |
| 3. Ρίζα | γ. Κόμβοι που δεν έχουν παιδιά. |
| 4. Φύλλα | δ. Μεταβλητή που περιέχει τη διεύθυνση του πρώτου κόμβου της λίστας. |
| 5. Κατευθυνόμενος γράφος | ε. Ο κόμβος χωρίς γονέα, στην κορυφή του δένδρου. |
| – | στ. Γράφος του οποίου καμία ακμή δεν έχει κατεύθυνση. |
| – | ζ. Γράφος του οποίου όλες οι ακμές έχουν κατεύθυνση. |
| Στήλη Α | Αντιστοιχία | Γιατί |
|---|---|---|
| 1. Κεφαλή | δ | Η Κεφαλή είναι η ειδική μεταβλητή που αποθηκεύει τη διεύθυνση του πρώτου κόμβου. |
| 2. Δείκτης | α | Ο δείκτης δεν παίρνει αριθμητικές τιμές αλλά διευθύνσεις στην κύρια μνήμη. |
| 3. Ρίζα | ε | Είναι ο μόνος κόμβος χωρίς γονέα. |
| 4. Φύλλα | γ | Φύλλα είναι οι κόμβοι χωρίς παιδιά. Η περιγραφή β αφορά τα αδέλφια και περισσεύει. |
| 5. Κατευθυνόμενος γράφος | ζ | Όλες οι ακμές του έχουν κατεύθυνση. Η περιγραφή στ αφορά τον μη κατευθυνόμενο γράφο και περισσεύει. |
Αν θέλετε περισσότερες ερωτήσεις τύπου ανάπτυξης ή γενικότερα ερωτήσεις θεωρίας στην ύλη της Πληροφορικής Γ Λυκείου στο κεφάλαιο Δυναμικές Δομές (Λίστες, Δένδρα, Γράφοι), δείτε τα τεστ, τα διαγωνίσματα και τις θεωρίες που έχουμε δημιουργήσει, για να καταφέρετε τον καλύτερο δυνατό βαθμό στις πανελλήνιες εξετάσεις.
Συχνές ερωτήσεις για τις Δυναμικές Δομές Δεδομένων
(Λιστες Δένδρα και Γράφους) ΑΕΠΠ Γ Λυκείου
Τι είναι οι δυναμικές δομές δεδομένων;
Είναι δομές δεδομένων στις οποίες οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις της κύριας μνήμης. Στο σχολικό βιβλίο παρουσιάζονται τρεις τέτοιες δομές: οι λίστες, τα δένδρα και οι γράφοι.
Τι είναι η συνδεδεμένη λίστα;
Είναι μια σειρά από κόμβους που συνήθως βρίσκονται σε απομακρυσμένες θέσεις μνήμης. Κάθε κόμβος έχει ένα τμήμα με τα δεδομένα και ένα τμήμα με δείκτη που δείχνει στον επόμενο κόμβο. Ο δείκτης του τελευταίου κόμβου έχει την τιμή NULL.
Τι είναι ο δείκτης και τι η Κεφαλή;
Ο δείκτης είναι ένας τύπος δεδομένων που οι τιμές του είναι διευθύνσεις στην κύρια μνήμη και χρησιμοποιείται για τη σύνδεση των στοιχείων μιας δομής. Η Κεφαλή είναι η ειδική μεταβλητή που αποθηκεύει τη διεύθυνση του πρώτου κόμβου της λίστας.
Ποια είναι η διαφορά απλά και διπλά συνδεδεμένης λίστας;
Στην απλά συνδεδεμένη λίστα κινούμαστε προς μία μόνο κατεύθυνση, από τον πρώτο προς τον τελευταίο κόμβο. Η διπλά συνδεδεμένη λίστα διατρέχεται και προς τις δύο κατευθύνσεις: κάθε κόμβος έχει δείκτη προς τον επόμενο και προς τον προηγούμενο, και χρειάζονται οι δείκτες «κεφαλή» και «ουρά» για τον πρώτο και τον τελευταίο κόμβο.
Ποιες είναι οι διαφορές λίστας και πίνακα;
Ο πίνακας είναι στατική δομή με τυχαία προσπέλαση, σταθερό μέγεθος και στοιχεία σε συνεχόμενες θέσεις μνήμης. Η λίστα είναι δυναμική δομή με σειριακή προσπέλαση, μεταβλητό μέγεθος και κόμβους σε μη συνεχόμενες θέσεις μνήμης.
Ποια είναι τα πλεονεκτήματα και τα μειονεκτήματα των λιστών;
Πλεονεκτήματα: δυναμικό μέγεθος, ευκολία εισαγωγής και διαγραφής από οποιοδήποτε σημείο και δεν χρειάζεται δήλωση μεγέθους. Μειονεκτήματα: δεν επιτρέπεται τυχαία πρόσβαση (άρα δεν γίνεται αποτελεσματικά δυαδική αναζήτηση) και υπάρχει μεγαλύτερη επιβάρυνση μνήμης λόγω των δεικτών.
Τι είναι το δένδρο και ποιοι είναι οι βασικοί όροι του;
Το δένδρο αποτελείται από κόμβους που συνδέονται με ακμές. Ρίζα είναι ο κόμβος χωρίς γονέα. Γονέας είναι ο κόμβος από τον οποίο ξεκινά μια ακμή και παιδί ο κόμβος στον οποίο καταλήγει. Αδέλφια είναι οι κόμβοι με τον ίδιο γονέα και φύλλα οι κόμβοι χωρίς παιδιά.
Τι είναι το δυαδικό δένδρο και τι το δυαδικό δένδρο αναζήτησης;
Στο δυαδικό δένδρο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί. Στο δυαδικό δένδρο αναζήτησης, για κάθε κόμβο u, οι κόμβοι του αριστερού υποδένδρου έχουν μικρότερες τιμές και οι κόμβοι του δεξιού υποδένδρου μεγαλύτερες τιμές από την τιμή του u.
Τι είναι ο γράφος και σε τι διαφέρει από το δένδρο;
Ο γράφος είναι μια δομή με κόμβους και γραμμές που ενώνουν μερικούς ή όλους τους κόμβους, και είναι η πιο γενική δομή δεδομένων. Σε αντίθεση με το δένδρο, δεν έχει ρίζα, επιτρέπει κύκλους και οι ακμές του μπορεί να έχουν ή να μην έχουν κατεύθυνση (κατευθυνόμενος και μη κατευθυνόμενος γράφος). Κάθε δένδρο είναι γράφος, αλλά όχι κάθε γράφος είναι δένδρο.

