Λίστες, Δένδρα & Γράφοι ΑΕΠΠ Γ΄ Λυκείου.

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

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

Τι είναι οι δυναμικές δομές δεδομένων στο ΑΕΠΠ

Σε αντίθεση με τους πίνακες, οι δυναμικές δομές δεν έχουν απαραίτητα σταθερό μέγεθος, και οι κόμβοι τους μπορούν να προστίθενται ή να διαγράφονται κατά την εκτέλεση του προγράμματος και συνδέονται μεταξύ τους με δείκτες. Γι' αυτό στις εξετάσεις εμφανίζονται μόνο σε επίπεδο θεωρίας (Θέμα Α) και πρακτικής θεωρίας (Θέμα Β) και όχι σε μορφή προγραμμάτων.

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

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

Στατικές και δυναμικές δομές: οι 3 βασικές διαφορές

Σύγκριση στατικών και δυναμικών δομών δεδομένων
Στατικές δομές δεδομένωνΔυναμικές δομές δεδομένων
Έχουν καθορισμένο μέγεθος από την αρχή.Το μέγεθός τους μεταβάλλεται κατά την εκτέλεση.
Τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.Οι κόμβοι δεν είναι απαραίτητο να βρίσκονται σε συνεχόμενες θέσεις μνήμης.
Χαρακτηριστικό παράδειγμα: πίνακας.Παραδείγματα: λίστα, δένδρο, γράφος.

Λίστες στο ΑΕΠΠ: απλά και διπλά συνδεδεμένες λίστες

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

Ξεκινάμε από τον πρώτο κόμβο, που ονομάζεται κεφαλή, και ακολουθούμε διαδοχικά τους δείκτες μέχρι τον τελευταίο κόμβο. Ο δείκτης του τελευταίου κόμβου έχει την τιμή NULL, που δηλώνει ότι δεν υπάρχει επόμενος κόμβος.

Σχηματική αναπαράσταση απλά συνδεδεμένης λίστας

ΚΕΦΑΛΗ
→
12
→
25
→
8NULL

Κάθε κόμβος περιέχει δεδομένο και δείκτη προς τον επόμενο κόμβο.

Οι βασικές λειτουργίες στις λίστες

Βασικές λειτουργίες λίστας και τρόπος εκτέλεσης
ΛειτουργίαΠώς εκτελείται στην πράξη
ΠροσπέλασηΞεκινάμε από τον πρώτο κόμβο και ακολουθούμε τους δείκτες μέχρι να βρούμε τον ζητούμενο κόμβο ή το NULL.
ΕισαγωγήΔημιουργούμε νέο κόμβο και αλλάζουμε κατάλληλα τους δείκτες, ώστε να ενταχθεί στη λίστα.
ΔιαγραφήΠαρακάμπτουμε τον κόμβο που θέλουμε να αφαιρέσουμε, συνδέοντας τον προηγούμενο με τον επόμενο κόμβο.
ΑναζήτησηΕλέγχουμε διαδοχικά τα δεδομένα των κόμβων μέχρι να βρούμε το ζητούμενο στοιχείο.

Παράδειγμα άσκηση ΑΕΠΠ: εισαγωγή κόμβου σε απλά συνδεδεμένη λίστα

Θέλουμε να εισαγάγουμε τον αριθμό 18 ανάμεσα στους κόμβους 12 και 25. Ο νέος κόμβος πρέπει πρώτα να συνδεθεί με τον κόμβο 25 και μετά ο κόμβος 12 να δείχνει προς τον νέο κόμβο. Στις Πανελλαδικές κάνουμε πάντα δύο σχήματα: ένα για την αρχική μορφή της λίστας και ένα για την τελική μορφή μετά την εισαγωγή.

Πριν από την εισαγωγή

12
→
25
→
8NULL

↓

Μετά την εισαγωγή του 18

12
→
18
→
25
→
8NULL

Παράδειγμα άσκηση ΑΕΠΠ: διαγραφή κόμβου από απλά συνδεδεμένη λίστα

Θέλουμε να διαγράψουμε τον κόμβο 18. Ο δείκτης του προηγούμενου κόμβου (12) πρέπει να δείχνει απευθείας στον επόμενο (25). Δεν αλλάζουμε τις τιμές των υπόλοιπων κόμβων, αλλάζουμε μόνο τις συνδέσεις, ώστε ο κόμβος 18 να παρακαμφθεί.

Πριν από τη διαγραφή του 18

ΚΕΦΑΛΗ
→
12
→
18
→
25
→
8NULL

↓

Μετά τη διαγραφή του 18

ΚΕΦΑΛΗ
→
12
→
25
→
8NULL

Ο κόμβος 12 δείχνει πλέον απευθείας στον 25. Ο κόμβος 18 έχει παρακαμφθεί και δεν ανήκει στη λίστα.

Διπλά συνδεδεμένη λίστα παράδειγμα ΑΕΠΠ

Σε μια διπλά συνδεδεμένη λίστα κάθε κόμβος έχει δύο δείκτες, έναν προς τον επόμενο και έναν προς τον προηγούμενο κόμβο. Η αρχή της λίστας είναι η κεφαλή και το τέλος της η ουρά.

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

Ο πρώτος κόμβος δεν έχει προηγούμενο, άρα ο προηγούμενος δείκτης του είναι NULL. Ο τελευταίος κόμβος δεν έχει επόμενο, άρα ο επόμενος δείκτης του είναι επίσης NULL.

Κάθε κόμβος: δείκτης προς προηγούμενο, δεδομένο, δείκτης προς επόμενο

ΚΕΦΑΛΗ
→
NULL12
↔
25
↔
8NULL
←
ΟΥΡΑ

Αριστερό πεδίο: προηγούμενος κόμβος  |  Μεσαίο πεδίο: δεδομένο  |  Δεξί πεδίο: επόμενος κόμβος

Διαφορές απλά και διπλά συνδεδεμένης λίστας ΑΕΠΠ

Σύγκριση απλά και διπλά συνδεδεμένης λίστας
Απλά συνδεδεμένη λίσταΔιπλά συνδεδεμένη λίστα
Κάθε κόμβος έχει έναν δείκτη, προς τον επόμενο κόμβο.Κάθε κόμβος έχει δύο δείκτες: προς τον προηγούμενο και προς τον επόμενο κόμβο.
Η προσπέλαση γίνεται προς μία κατεύθυνση.Η προσπέλαση γίνεται και προς τις δύο κατευθύνσεις.
Απαιτεί λιγότερη μνήμη ανά κόμβο.Απαιτεί περισσότερη μνήμη, λόγω του επιπλέον δείκτη.

Δένδρα στο ΑΕΠΠ: μεθοδολογίες.

Ένα δένδρο είναι μια δυναμική δομή δεδομένων στην οποία ένας κόμβος μπορεί να συνδέεται με περισσότερους από έναν επόμενους κόμβους. Υπάρχει ένας μοναδικός αρχικός κόμβος, η ρίζα, από τον οποίο ξεκινούν όλοι οι υπόλοιποι.

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

Σχηματική αναπαράσταση δυαδικού δένδρου

15
Ρίζα
8
22
4
11
30
Οι κόμβοι 4, 11 και 30 είναι φύλλα. Τα βέλη δείχνουν τη σχέση γονέα προς παιδί.

Πώς αναγνωρίζω και αναφέρω τα βασικά χαρακτηριστικά ενός δένδρου

Στο σχήμα η ρίζα είναι ο κόμβος 15. Τα παιδιά της ρίζας είναι οι κόμβοι 8 και 22, ενώ οι 4, 11 και 30 είναι φύλλα, επειδή δεν έχουν παιδιά. Αδέρφια είναι οι κόμβοι 8 και 22, καθώς και οι 4 και 11.

Το δένδρο έχει τρία επίπεδα: στο πρώτο η ρίζα, στο δεύτερο οι 8 και 22 και στο τρίτο τα φύλλα. Όταν μετράμε επίπεδα, το ύψος του είναι τρία.

Πολύ μεγάλη προσοχή: στις Πανελλαδικές, στο Θέμα Α ή Β, μπορεί να σου ζητήσουν για ένα δένδρο που δίνεται να αναφέρεις: α) τη ρίζα, β) τους γονείς και τα παιδιά τους, γ) τα φύλλα, δ) τα αδέρφια.

Τι είναι δυαδικό δένδρο και τι δυαδικό δένδρο αναζήτησης στο ΑΕΠΠ

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

Πολύ μεγάλη προσοχή: άλλο το δυαδικό δένδρο και άλλο το δυαδικό δένδρο αναζήτησης. Στην ύλη των Πανελλαδικών, δένδρο αναζήτησης είναι αυτό στο οποίο κάθε δεξί παιδί είναι μεγαλύτερο από τον γονέα του και κάθε αριστερό παιδί είναι μικρότερο από τον γονέα του. Το σχήμα με ρίζα το 15 είναι και δυαδικό δένδρο αναζήτησης, αφού τα 8 και 4 είναι αριστερά και μικρότερα και τα 22 και 30 δεξιά και μεγαλύτερα.

Γράφοι στο ΑΕΠΠ: μεθοδολογίες

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

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

Σχηματική αναπαράσταση μη κατευθυνόμενου γράφου στο ΑΕΠΠ

Α
Β
Γ
Δ
Ε
Ζ
Οι κύκλοι είναι κορυφές και οι γραμμές ακμές. Η κορυφή Β και η ακμή Β–Ε έχουν επισημανθεί με πορτοκαλί.

Κατευθυνόμενος και μη κατευθυνόμενος γράφος διαφορά με σχήμα

Η βασική διαφορά βρίσκεται στη φορά των ακμών: στον μη κατευθυνόμενο γράφο η ακμή Α–Β επιτρέπει μετάβαση και από την Α στη Β και από τη Β στην Α, ενώ στον κατευθυνόμενο η ακμή Α→Β επιτρέπει μετάβαση μόνο από την Α στη Β.

Μη κατευθυνόμενος γράφος

Α
Β
Γ
Δ

Η ακμή Α–Β επιτρέπει μετάβαση και προς τις δύο κατευθύνσεις.

Κατευθυνόμενος γράφος

Α
Β
Γ
Δ

Η ακμή Α→Β επιτρέπει μετάβαση μόνο από την Α προς τη Β.

Συμπέρασμα: χωρίς βέλη έχουμε μη κατευθυνόμενο γράφο, με βέλη κατευθυνόμενο γράφο.

Λίστες, δένδρα και γράφοι: διαφορές για πανελλαδικές εξετάσεις ΑΕΠΠ

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

Σύγκριση λίστας, δένδρου και γράφου
ΧαρακτηριστικόΛίσταΔένδροΓράφος
ΟργάνωσηΓραμμικήΜη γραμμικήΜη γραμμική
Ειδικός αρχικός κόμβοςΚεφαλήΡίζαΔεν απαιτείται
Επόμενες συνδέσειςΣυνήθως μία προς τον επόμενο κόμβοΈνας ή περισσότεροι απόγονοιΠολλές πιθανές συνδέσεις
Παράδειγμα εφαρμογήςΛίστα αναμονήςΔομή φακέλωνΟδικό δίκτυο πόλεων

Λυμένα παραδείγματα λιστών στο ΑΕΠΠ

Λυμένο Παράδειγμα 1: εισαγωγή και διαγραφή κόμβων σε απλά συνδεδεμένη λίστα στο ΑΕΠΠ

Σε μια απλά συνδεδεμένη λίστα έχουν τοποθετηθεί διαδοχικά οι αριθμοί 5, 20, -3 και 8. Να σχεδιαστεί η λίστα, να προστεθεί ο αριθμός 7 μετά τον -3 και να διαγραφεί ο δεύτερος κόμβος.

1. Σχεδίαση της λίστας

Η λίστα αποτελείται από τέσσερις κόμβους. Κάθε κόμβος έχει ένα δεδομένο και έναν δείκτη προς τον επόμενο, και ο τελευταίος δείκτης είναι NULL.

ΚΕΦΑΛΗ
→
5
→
20
→
-3
→
8NULL

Αρχική λίστα: 5 → 20 → -3 → 8 → NULL

2. Προσθήκη νέου κόμβου

Για να εισαγάγουμε το 7 μετά τον κόμβο με δεδομένο -3, δημιουργούμε νέο κόμβο με τιμή 7. Ο δείκτης του νέου κόμβου πρέπει να δείχνει στον κόμβο 8, και ο δείκτης του κόμβου -3 πρέπει να αλλάξει ώστε να δείχνει στον νέο κόμβο 7. Η σειρά μετά την εισαγωγή είναι: 5 → 20 → -3 → 7 → 8 → NULL.

Νέα λίστα μετά την εισαγωγή του 7

ΚΕΦΑΛΗ
→
5
→
20
→
-3
→
7
→
8NULL

Ο κόμβος -3 δείχνει πλέον στον νέο κόμβο 7 και ο κόμβος 7 στον κόμβο 8.

3. Διαγραφή κόμβου

Μετά την εισαγωγή του 7 η λίστα είναι 5 → 20 → -3 → 7 → 8. Ο δεύτερος κόμβος είναι ο 20. Για να τον διαγράψουμε, αλλάζουμε τον δείκτη του πρώτου κόμβου, ώστε ο 5 να δείχνει απευθείας στον -3 και ο 20 να παρακαμφθεί. Η τελική σειρά είναι: 5 → -3 → 7 → 8 → NULL.

Τελική λίστα μετά τη διαγραφή του δεύτερου κόμβου

ΚΕΦΑΛΗ
→
5
→
-3
→
7
→
8NULL

Ο κόμβος 20 δεν ανήκει πλέον στη λίστα, επειδή ο κόμβος 5 δείχνει απευθείας στον κόμβο -3.

Λυμένο Παράδειγμα 2: δημιουργία διπλά συνδεδεμένης λίστας ΑΕΠΠ

Εκφώνηση: Να δημιουργηθεί μια διπλά συνδεδεμένη λίστα που αναπαριστά τις διαδρομές μεταξύ των πόλεων Houston, Dallas, San Antonio και Austin.

Σε μια διπλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται με τον προηγούμενο και τον επόμενο. Η διαδρομή διασχίζεται και από την κεφαλή προς την ουρά και από την ουρά προς την κεφαλή.

Διαδρομή προς τα δεξιά και επιστροφή προς τα αριστερά

ΚΕΦΑΛΗ
→
NULLHouston
↔
Dallas
↔
San Antonio
↔
AustinNULL
←
ΟΥΡΑ

Αριστερό πεδίο: προηγούμενη πόλη  |  Μεσαίο πεδίο: πόλη  |  Δεξί πεδίο: επόμενη πόλη

Πώς διαβάζουμε τη διπλά συνδεδεμένη λίστα

Από την αρχή προς το τέλος: Houston → Dallas → San Antonio → Austin. Από το τέλος προς την αρχή, με τους προηγούμενους δείκτες: Austin → San Antonio → Dallas → Houston.

Ο κόμβος Houston έχει προηγούμενο NULL, επειδή είναι ο πρώτος, και ο Austin έχει επόμενο NULL, επειδή είναι ο τελευταίος.

Πόσες προσπελάσεις χρειάζονται για να φτάσουμε στον San Antonio; Η απάντηση είναι διπλή: 3 προσπελάσεις αν ξεκινήσουμε από την κεφαλή (Houston, Dallas, San Antonio) και 2 αν ξεκινήσουμε από την ουρά (Austin, San Antonio).

Λυμένες ασκήσεις δένδρων γράφων για τις Πανελλήνιες Εξετάσεις ΑΕΠΠ

Άσκηση ΑΕΠΠ με σχεδίαση δένδρου και γονέα–παιδιού, ρίζα, φύλλα και αδέρφια

Εκφώνηση: Να σχεδιάσετε το δένδρο που προκύπτει από τις ακόλουθες πληροφορίες:

  1. Ο κόμβος Α έχει παιδιά τους κόμβους Β, Γ και Δ.
  2. Οι κόμβοι Ε και Ζ έχουν πατέρα τον κόμβο Δ.
  3. Ο κόμβος Κ έχει αδέλφια τους κόμβους Λ και Μ και πατέρα τον κόμβο Γ.
  4. Ο κόμβος Π έχει παιδί τον κόμβο Ρ και πατέρα τον κόμβο Β.

Λύση

Ο Α είναι η ρίζα και έχει τρία παιδιά: τους Β, Γ και Δ. Οι Ε και Ζ είναι παιδιά του Δ, οι Κ, Λ και Μ είναι αδέλφια με πατέρα τον Γ, ο Π είναι παιδί του Β και ο Ρ είναι παιδί του Π. Άρα αδέρφια είναι οι Β, Γ και Δ, οι Κ, Λ και Μ, και οι Ε και Ζ. Φύλλα είναι οι κόμβοι Ρ, Κ, Λ, Μ, Ε και Ζ.

Α → Β, Γ, Δ  |  Δ → Ε, Ζ  |  Γ → Κ, Λ, Μ  |  Β → Π → Ρ

Α
Β
Γ
Δ
Π
Ρ
Κ
Λ
Μ
Ε
Ζ
Οι ακμές δείχνουν τη σχέση γονέα προς παιδί.

Άσκηση ΑΕΠΠ δένδρο απόφασης

Εκφώνηση (πιθανό και για Θέμα Α): Να δημιουργήσετε ένα δένδρο απόφασης που να κατηγοριοποιεί τους προορισμούς Ηράκλειο, Αθήνα, Παρίσι και Νέα Υόρκη σύμφωνα με τα χαρακτηριστικά:

  1. Αν ο προορισμός είναι εσωτερικού ή εξωτερικού.
  2. Στην περίπτωση του εσωτερικού, αν βρίσκεται σε νησί ή όχι.
  3. Στην περίπτωση του εξωτερικού, αν βρίσκεται στην Ευρώπη ή όχι.

Λύση

Η πρώτη απόφαση χωρίζει τους προορισμούς σε εσωτερικού και εξωτερικού. Στη συνέχεια κάθε κλάδος εξετάζει διαφορετικό χαρακτηριστικό: για το εσωτερικού ελέγχουμε αν είναι σε νησί και για το εξωτερικού αν είναι στην Ευρώπη.

Προορισμός
Εσωτερικού
Εξωτερικού
Νησί
Όχι νησί
Ευρώπη
Εκτός Ευρώπης
Ηράκλειο
Αθήνα
Παρίσι
Νέα Υόρκη
Τα βέλη δείχνουν τη διαδοχή των αποφάσεων.
Κατηγοριοποίηση προορισμών στο δένδρο απόφασης
ΠροορισμόςΚατηγορίαΔιαδρομή στο δένδρο
ΗράκλειοΕσωτερικού, σε νησίΠροορισμός → Εσωτερικού → Νησί → Ηράκλειο
ΑθήναΕσωτερικού, όχι σε νησίΠροορισμός → Εσωτερικού → Όχι νησί → Αθήνα
ΠαρίσιΕξωτερικού, ΕυρώπηΠροορισμός → Εξωτερικού → Ευρώπη → Παρίσι
Νέα ΥόρκηΕξωτερικού, εκτός ΕυρώπηςΠροορισμός → Εξωτερικού → Εκτός Ευρώπης → Νέα Υόρκη

Άσκηση ΑΕΠΠ με συνδεδεμένο γράφο

Εκφώνηση: Να σχεδιάσετε έναν γράφο για την αναπαράσταση σύνδεσης ιστοσελίδων, με βάση τις παρακάτω πληροφορίες:

  • Η ιστοσελίδα Α συνδέεται με τις ιστοσελίδες Β και Γ με αμφίδρομη σχέση.
  • Η ιστοσελίδα Β συνδέεται με τις ιστοσελίδες Δ και Ε με αμφίδρομη σχέση.
  • Η ιστοσελίδα Ε μπορεί να συνδεθεί με την ιστοσελίδα Ζ, αλλά όχι το αντίθετο.
  • Η ιστοσελίδα Γ μπορεί να συνδεθεί με την ιστοσελίδα Π, αλλά όχι το αντίθετο.

Λύση

Οι σχέσεις Α–Β, Α–Γ, Β–Δ και Β–Ε είναι αμφίδρομες, άρα παριστάνονται με γραμμές χωρίς βέλη. Οι σχέσεις Ε→Ζ και Γ→Π είναι μονόδρομες, άρα παριστάνονται με γραμμές με βέλος που δείχνει τη φορά της σύνδεσης.

Είδος ακμής για κάθε σχέση της Άσκησης Γ
ΣχέσηΕίδος ακμήςΑναπαράσταση
Α – ΒΑμφίδρομηΓραμμή χωρίς βέλος
Α – ΓΑμφίδρομηΓραμμή χωρίς βέλος
Β – ΔΑμφίδρομηΓραμμή χωρίς βέλος
Β – ΕΑμφίδρομηΓραμμή χωρίς βέλος
Ε → ΖΜονόδρομηΓραμμή με βέλος προς Ζ
Γ → ΠΜονόδρομηΓραμμή με βέλος προς Π
Α
Β
Γ
Δ
Ε
Ζ
Π
Οι μπλε γραμμές δηλώνουν αμφίδρομες σχέσεις. Τα πορτοκαλί βέλη δηλώνουν μονόδρομες συνδέσεις.

Ερμηνεία του σχήματος

  • Η ιστοσελίδα Α συνδέεται αμφίδρομα με τις Β και Γ.
  • Η ιστοσελίδα Β συνδέεται αμφίδρομα με τις Δ και Ε.
  • Η ιστοσελίδα Ε συνδέεται μονόδρομα με τη Ζ. Δεν υπάρχει σύνδεση από τη Ζ προς την Ε.
  • Η ιστοσελίδα Γ συνδέεται μονόδρομα με την Π. Δεν υπάρχει σύνδεση από την Π προς τη Γ.

Συμπέρασμα: στον ίδιο γράφο μπορούν να συνυπάρχουν ακμές χωρίς φορά και ακμές με φορά. Η μορφή κάθε ακμής εξαρτάται από το αν η σύνδεση λειτουργεί και προς τις δύο κατευθύνσεις ή μόνο προς μία.

Ερωτήσεις θεωρίας ΑΕΠΠ για λίστες, δένδρα και γράφους

Ερωτήσεις Σωστού/Λάθους ΑΕΠΠ δυναμικές δομές δεδομένων

Χαρακτήρισε κάθε πρόταση με Σωστό (Σ) ή Λάθος (Λ).

  1. Οι δυναμικές δομές δεδομένων έχουν πάντα σταθερό μέγεθος.
  2. Οι κόμβοι μιας δυναμικής δομής δεν είναι απαραίτητο να αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
  3. Σε μια απλά συνδεδεμένη λίστα κάθε κόμβος περιέχει δεδομένο και δείκτη προς τον επόμενο κόμβο.
  4. Ο δείκτης του τελευταίου κόμβου μιας απλά συνδεδεμένης λίστας δείχνει στον πρώτο κόμβο.
  5. Σε μια διπλά συνδεδεμένη λίστα η προσπέλαση μπορεί να γίνει και από την ουρά προς την κεφαλή.
  6. Κάθε δένδρο έχει έναν μοναδικό κόμβο που ονομάζεται ρίζα.
  7. Οι κόμβοι ενός δένδρου που δεν έχουν παιδιά ονομάζονται φύλλα.
  8. Σε ένα δυαδικό δένδρο κάθε κόμβος έχει υποχρεωτικά δύο παιδιά.
  9. Σε δένδρο αναζήτησης κάθε αριστερό παιδί είναι μικρότερο από τον γονέα του.
  10. Ένας γράφος αποτελείται από κορυφές και ακμές.
  11. Σε μη κατευθυνόμενο γράφο η ακμή Α–Β επιτρέπει κίνηση και από τη Β προς την Α.
  12. Σε κάθε γράφο απαγορεύεται να υπάρχουν κύκλοι.
Δες τις απαντήσεις
  1. Λ – Το μέγεθος των δυναμικών δομών μπορεί να μεταβάλλεται κατά την εκτέλεση.
  2. Σ – Οι κόμβοι μπορούν να βρίσκονται σε διαφορετικές θέσεις μνήμης και να συνδέονται με δείκτες.
  3. Σ – Αυτή είναι η βασική μορφή της απλά συνδεδεμένης λίστας.
  4. Λ – Ο δείκτης του τελευταίου κόμβου έχει τιμή NULL.
  5. Σ – Οι δύο δείκτες κάθε κόμβου επιτρέπουν διάσχιση προς τις δύο κατευθύνσεις.
  6. Σ – Η ρίζα είναι ο μοναδικός αρχικός κόμβος του δένδρου.
  7. Σ – Φύλλα είναι οι κόμβοι χωρίς παιδιά.
  8. Λ – Έχει το πολύ δύο παιδιά, άρα μπορεί να έχει κανένα, ένα ή δύο.
  9. Σ – Αυτός είναι ο ορισμός του δένδρου αναζήτησης στην ύλη των Πανελλαδικών.
  10. Σ – Οι κόμβοι ονομάζονται κορυφές και οι συνδέσεις ακμές.
  11. Σ – Η ακμή δεν έχει φορά σε μη κατευθυνόμενο γράφο.
  12. Λ – Στους γράφους μπορούν να υπάρχουν κύκλοι.

Πολλαπλής επιλογής ΑΕΠΠ δυναμικές δομές δεδομένων

1. Ποιο είναι βασικό χαρακτηριστικό μιας δυναμικής δομής δεδομένων;

  1. Έχει υποχρεωτικά σταθερό μέγεθος.
  2. Τα στοιχεία της βρίσκονται πάντα σε συνεχόμενες θέσεις μνήμης.
  3. Το πλήθος των κόμβων της μπορεί να μεταβάλλεται κατά την εκτέλεση.
  4. Δεν επιτρέπεται η εισαγωγή νέων στοιχείων.

2. Σε μια απλά συνδεδεμένη λίστα, η τιμή NULL στον τελευταίο κόμβο δηλώνει:

  1. Ότι ο κόμβος είναι ο πρώτος της λίστας.
  2. Ότι δεν υπάρχει επόμενος κόμβος.
  3. Ότι ο κόμβος δεν περιέχει δεδομένο.
  4. Ότι η λίστα είναι ταξινομημένη.

3. Πόσους δείκτες έχει κάθε κόμβος μιας διπλά συνδεδεμένης λίστας;

  1. Έναν
  2. Δύο
  3. Τρεις
  4. Κανέναν

4. Πώς ονομάζεται ο μοναδικός αρχικός κόμβος ενός δένδρου;

  1. Φύλλο
  2. Ακμή
  3. Ρίζα
  4. Δείκτης

5. Ποια πρόταση ισχύει για ένα δυαδικό δένδρο;

  1. Κάθε κόμβος έχει ακριβώς δύο παιδιά.
  2. Κάθε κόμβος μπορεί να έχει το πολύ δύο παιδιά.
  3. Δεν έχει ρίζα.
  4. Περιέχει πάντα κύκλους.

6. Πώς ονομάζονται οι κόμβοι ενός γράφου;

  1. Κορυφές
  2. Φύλλα
  3. Δείκτες
  4. Εγγραφές

7. Ο βαθμός μιας κορυφής σε μη κατευθυνόμενο γράφο είναι:

  1. Το πλήθος των κόμβων του γράφου.
  2. Το πλήθος των ακμών που συνδέονται με την κορυφή.
  3. Το πλήθος των φύλλων του γράφου.
  4. Το ύψος του γράφου.
Δες τις απαντήσεις
  1. γ) Το πλήθος των κόμβων της μπορεί να μεταβάλλεται κατά την εκτέλεση.
  2. β) Ότι δεν υπάρχει επόμενος κόμβος.
  3. β) Δύο, έναν προς τον προηγούμενο και έναν προς τον επόμενο κόμβο.
  4. γ) Ρίζα.
  5. β) Κάθε κόμβος μπορεί να έχει το πολύ δύο παιδιά.
  6. α) Κορυφές.
  7. β) Το πλήθος των ακμών που συνδέονται με την κορυφή.

Ασκήσεις αντιστοίχισης ΑΕΠΠ δυναμικές δομές δεδομένων

Άσκηση 1. Αντιστοίχισε τις έννοιες της στήλης Α με τις περιγραφές της στήλης Β.

Αντιστοίχιση 1: βασικές έννοιες δυναμικών δομών
Στήλη ΑΣτήλη Β
1. NULLα) Κόμβος δένδρου χωρίς παιδιά
2. Ρίζαβ) Σύνδεση δύο κορυφών γράφου
3. Φύλλογ) Δηλώνει ότι δεν υπάρχει επόμενος κόμβος
4. Ακμήδ) Μοναδικός αρχικός κόμβος δένδρου
5. Κορυφήε) Κόμβος γράφου
Δες την απάντηση

1 → γ, 2 → δ, 3 → α, 4 → β, 5 → ε.

Άσκηση 2. Αντιστοίχισε τις δομές της στήλης Α με τα χαρακτηριστικά της στήλης Β.

Αντιστοίχιση 2: δομές και χαρακτηριστικά
Στήλη ΑΣτήλη Β
1. Λίσταα) Ιεραρχική οργάνωση δεδομένων
2. Δένδροβ) Δικτυακή αναπαράσταση σχέσεων
3. Γράφοςγ) Γραμμική ακολουθία κόμβων
4. Δυναμική δομήδ) Δομή με μεταβαλλόμενο πλήθος κόμβων
Δες την απάντηση

1 → γ, 2 → α, 3 → β, 4 → δ.

Συχνές ερωτήσεις για λίστες, δένδρα και γράφους στο ΑΕΠΠ

Τι είναι οι δυναμικές δομές δεδομένων;

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

Τι είναι η απλά συνδεδεμένη λίστα και τι σημαίνει NULL;

Η απλά συνδεδεμένη λίστα είναι μια γραμμική δομή από κόμβους, όπου κάθε κόμβος έχει ένα δεδομένο και έναν δείκτη προς τον επόμενο κόμβο. Το NULL στον δείκτη του τελευταίου κόμβου δηλώνει ότι δεν υπάρχει επόμενος κόμβος.

Ποια είναι η διαφορά απλά και διπλά συνδεδεμένης λίστας;

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

Πώς γίνεται η εισαγωγή και η διαγραφή κόμβου σε λίστα;

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

Τι είναι ρίζα, γονέας, παιδιά, φύλλα και αδέρφια σε ένα δένδρο;

Ρίζα είναι ο μοναδικός αρχικός κόμβος του δένδρου. Γονέας είναι ο κόμβος από τον οποίο ξεκινούν άλλοι κόμβοι, που ονομάζονται παιδιά του. Φύλλα είναι οι κόμβοι χωρίς παιδιά και αδέρφια οι κόμβοι που έχουν τον ίδιο γονέα.

Τι είναι δυαδικό δένδρο και τι δυαδικό δένδρο αναζήτησης;

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

Ποια είναι η διαφορά κατευθυνόμενου και μη κατευθυνόμενου γράφου;

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

Ποια είναι η διαφορά λίστας, δένδρου και γράφου;

Η λίστα είναι γραμμική δομή με κεφαλή. Το δένδρο είναι μη γραμμική δομή με ρίζα και ιεραρχία γονέα και παιδιών. Ο γράφος είναι μη γραμμική δομή από κορυφές και ακμές, χωρίς απαραίτητα ρίζα, που περιγράφει δίκτυα σχέσεων.

Συνέχισε με τα υποπρογράμματα και όλες τις μεθοδολογίες ΑΕΠΠ. Διάβασε επίσης τη θεωρία της Πληροφορικής Γ΄ Λυκείου. Για εξάσκηση υπάρχουν οι ασκήσεις με λύσεις και τα διαγωνίσματα.