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

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

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

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

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

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

Στατικές και Δυναμικές Δομές: Οι 3 Βασικές Διαφορές

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

Λίστες

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

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

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

Οι Βασικές Λειτουργίες στις Λίστες

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

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

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

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

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

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

Διπλά Συνδεδεμένη Λίστα

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

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

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

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

Δένδρα

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

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

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

Πώς Αναγνωρίζω και Αναφέρω τα Βασικά Χαρακτηριστικά σε ένα Δένδρο;

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

Το δένδρο έχει τρία επίπεδα: στο πρώτο βρίσκεται η ρίζα, στο δεύτερο οι κόμβοι 8 και 22 και στο τρίτο τα φύλλα. Το ύψος του, όταν μετράμε επίπεδα, είναι τρία.
Πολύ μεγάλη προσοχή: Μπορεί στις πανελλήνιες εξετάσεις στο Α ή στο Β θέμα να μας ζητήσουν να αναφέρουμε από ένα δένδρο που μας δίνεται όλα τα παραπάνω, δηλαδή "Στο παραπάνω δυαδικό δένδρο που δίνεται να αναφέρετε α) τη ρίζα β) τους γονείς και τα παιδιά τους γ) τα φύλλα δ) τα αδέρφια"

Τι Είναι Δυαδικό Δένδρο;

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

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

Γράφοι

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

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

Σχηματική Αναπαράσταση Μη Κατευθυνόμενου Γράφου

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

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

Συνοπτικά οι διαφορές σε Λίστες, Δένδρα και Γράφους

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

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

Λυμένα Παραδείγματα Λιστών (απλές και διπλά συνδεδεμένες)

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

Σε μία απλά συνδεδεμένη λίστα έχουν τοποθετηθεί διαδοχικά οι αριθμοί 5, 20, -3 και 8.

1. Σχεδίαση της απλά συνδεδεμένης λίστας στα πρότυπα των εξετάσεων

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

2. Προσθήκη νέου κόμβου σε απλά συνδεδεμένη λίστα στα πρότυπα των εξετάσεων

Προσθήκη του αριθμού 7 μετά τον αριθμό -3. Για να εισαγάγουμε το 7 μετά τον κόμβο με δεδομένο -3, δημιουργούμε έναν νέο κόμβο με τιμή 7. Στη συνέχεια, ο δείκτης του νέου κόμβου 7 πρέπει να δείχνει στον κόμβο 8 και ο δείκτης του κόμβου -3 πρέπει να αλλάξει, ώστε να δείχνει στον νέο κόμβο 7.

Η σειρά των κόμβων μετά την εισαγωγή είναι:

5 → 20 → -3 → 7 → 8 → NULL

3. Διαγραφή κόμβου από απλά συνδεδεμένη λίστα στα πρότυπα των εξετάσεων

Διαγραφή του δεύτερου κόμβου της λίστας. Μετά την εισαγωγή του 7, η λίστα είναι: 5 → 20 → -3 → 7 → 8.
Ο δεύτερος κόμβος είναι ο κόμβος με τιμή 20.

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

Η τελική σειρά των κόμβων είναι:

5 → -3 → 7 → 8 → NULL

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

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

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

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

Από την αρχή προς το τέλος ακολουθούμε τη διαδρομή:

Houston → Dallas → SanAntonio → Austin

Από το τέλος προς την αρχή μπορούμε να επιστρέψουμε ακολουθώντας τους προηγούμενους δείκτες:

Austin → SanAntonio → Dallas → Houston

Ο κόμβος Houston έχει προηγούμενο NULL, επειδή είναι ο πρώτος κόμβος. Ο κόμβος Austin έχει επόμενο NULL, επειδή είναι ο τελευταίος κόμβος. Αν λοιπόν στις πανελλαδικές εξετάσεις με ρωτήσουν σε θεωρητικό επίπεδο, πόσες προσπελάσεις χρειάζεται να γίνουν για να φτάσουμε στο κόμβο San Antonio η απάντηση είναι διπλή, 3 προσπελάσεις αν ξεκινήσουμε από την κεφαλή και 2 αν ξεκινήσουμε από την ουρά.

Λυμένες Ακήσεις Δένδρων Στα Πρότυπα Πανελληνίων Εξετάσεων

Άσκηση Α: Σχεδίαση Δένδρου Σχέσεις Γονέα–Παιδιού, Φύλλο, Ρίζα και Αδέρφια

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

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

Λύση

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

Η τελική ιεραρχία είναι:

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

Άσκηση Β: Δένδρο Απόφασης (πιθανό και για Α θέμα Πανελληνίων εξετάσεων)

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

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

Λύση

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

Κατηγοριοποίηση:

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

Λυμένη Άσκηση: Μη κατευθυνόμενος Γράφος (Στα πρότυπα των εξετάσεων)

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

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

Λύση

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

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

Σχέση	Είδος ακμής	Αναπαράσταση
Α – Β	Αμφίδρομη	Γραμμή χωρίς βέλος
Α – Γ	Αμφίδρομη	Γραμμή χωρίς βέλος
Β – Δ	Αμφίδρομη	Γραμμή χωρίς βέλος
Β – Ε	Αμφίδρομη	Γραμμή χωρίς βέλος
Ε → Ζ	Μονόδρομη	Γραμμή με βέλος προς Ζ
Γ → Π	Μονόδρομη	Γραμμή με βέλος προς Π

Σχηματική Αναπαράσταση του Γράφου

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

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

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

Ερωτήσεις Σωστό / Λάθος

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

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

Απαντήσεις Σωστό / Λάθος

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

Ερωτήσεις Πολλαπλής Επιλογής

Επίλεξε τη σωστή απάντηση σε κάθε ερώτηση.

1. Ποιο είναι βασικό χαρακτηριστικό μιας δυναμικής δομής δεδομένων;
   • α) Έχει υποχρεωτικά σταθερό μέγεθος.
   • β) Τα στοιχεία της βρίσκονται πάντα σε συνεχόμενες θέσεις μνήμης.
   • γ) Το πλήθος των κόμβων της μπορεί να μεταβάλλεται κατά την εκτέλεση.
   • δ) Δεν επιτρέπεται η εισαγωγή νέων στοιχείων.
2. Σε μια απλά συνδεδεμένη λίστα, η τιμή NULL στον τελευταίο κόμβο δηλώνει:
   • α) Ότι ο κόμβος είναι ο πρώτος της λίστας.
   • β) Ότι δεν υπάρχει επόμενος κόμβος.
   • γ) Ότι ο κόμβος δεν περιέχει δεδομένο.
   • δ) Ότι η λίστα είναι ταξινομημένη.
3. Πώς ονομάζεται ο μοναδικός αρχικός κόμβος ενός δένδρου;
   • α) Φύλλο
   • β) Ακμή
   • γ) Ρίζα
   • δ) Δείκτης
4. Ποια πρόταση ισχύει για ένα δυαδικό δένδρο;
   • α) Κάθε κόμβος έχει ακριβώς δύο παιδιά.
   • β) Κάθε κόμβος μπορεί να έχει το πολύ δύο παιδιά.
   • γ) Δεν έχει ρίζα.
   • δ) Περιέχει πάντα κύκλους.
5. Πώς ονομάζονται οι κόμβοι ενός γράφου;
   • α) Κορυφές
   • β) Φύλλα
   • γ) Δείκτες
   • δ) Εγγραφές
6. Ο βαθμός μιας κορυφής σε μη κατευθυνόμενο γράφο είναι:
   • α) Το πλήθος των κόμβων του γράφου.
   • β) Το πλήθος των ακμών που συνδέονται με την κορυφή.
   • γ) Το πλήθος των φύλλων του γράφου.
   • δ) Το ύψος του γράφου.

Απαντήσεις Πολλαπλής Επιλογής

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

Ασκήσεις Αντιστοίχισης

Να αντιστοιχίσετε τα στοιχεία της Στήλης Α με τα στοιχεία της Στήλης Β.

Άσκηση 1

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

Απαντήσεις Αντιστοίχισης

Άσκηση 1:

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

Άσκηση 2

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

Απαντήσεις Αντιστοίχισης

Άσκηση 2:

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

Συχνές Ερωτήσεις για Δυναμικές Δομές Δεδομένων