(Α) Ερωτήσεις Σ/Λ
- Λάθος
- Σωστό
(Β) Ερωτήσεις Συμπλήρωσης Κενών
- κενό, κόμβους, ακμές
- αποθήκευση, αναζητήσω, ταξινομήσω, επεξεργαστώ, ανακτήσω
- κατευθυνόμενη, συγκεκριμένο
(Γ) Ερωτήσεις Αντιστοίχησης
(1) α, β, γ, δ, ζ
(2) α, γ, ε
(Δ) Ερωτήσεις Ανάπτυξης
(1)
Ένα δένδρο (tree) είναι μία δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων με βάση τους εξής κανόνες:
- Υπάρχει ένας ξεχωριστός κόμβος που ονομάζεται ρίζα. Αυτός είναι ένας κόμβος χωρίς γονέα.
- Για κάθε κόμβο, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο. Ο κόμβος αφετηρία ονομάζεται γονέας του και ο κόμβος προορισμός παιδί.
- Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή, μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο.
(2) Τα δένδρα είναι πολύ ισχυρά για δύο σημαντικούς λόγους:
- Ο πρώτος λόγος αναφέρεται στη δυναμικότητα των δένδρων. Είναι πολύ εύκολο να προσθέσουμε, να αφαιρέσουμε ή να αναζητήσουμε ένα στοιχείο σε ένα δένδρο.
- Ο δεύτερος βασικός λόγος είναι ότι η δομή των δένδρων μεταφέρει πληροφορίες.
(3) Δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί. Κατά συνέπεια κάθε κόμβος μπορεί να έχει αριστερό και δεξιό υποδένδρο.
(4) Ένα δυαδικό δένδρο αναζήτησης είναι ένα δυαδικό δένδρο, όπου για κάθε κόμβο γονέα, όλοι οι κόμβοι του αριστερού του υποδένδρου έχουν τιμές μικρότερες της τιμής του κόμβου γονέα και όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες (ή ίσες) της τιμής του κόμβου γονέα. Για λόγους απλούστευσης θεωρούμε ότι δεν υπάρχουν τιμές ίσες σε κόμβους.
(5) Ένας γράφος (graph) είναι μία δομή που αποτελείται από ένα σύνολο κόμβων (ή σημείων ή κορυφών) και ένα σύνολο γραμμών (ή ακμών ή τόξων) που ενώνουν μερικούς ή όλους τους κόμβους. Ο γράφος αποτελεί την πιο γενική δομή δεδομένων, με την έννοια ότι όλες οι προηγούμενες δομές που παρουσιάστηκαν μπορούν να θεωρηθούν περιπτώσεις γράφων.
(6) Στα δένδρα κάθε κόμβος μπορεί να συνδέεται και να οδηγεί σε δύο ή και περισσότερους κόμβους, αλλά σε κάθε κόμβο καταλήγει μόνο μία ακμή. Επίσης το δένδρο έχει μία ρίζα από όπου πηγάζουν όλοι οι κόμβοι και η οποία αποτελεί το σημείο αναφοράς τους.
Στους Γράφους δεν υπάρχει ρίζα και κάθε κόμβος μπορεί να συνδέεται με δύο ή περισσότερους κόμβους προς οποιαδήποτε κατεύθυνση.