ΛΙΣΤΕΣ-ΔΕΝΔΡΑ-ΓΡΑΦΟΙ Γ ΛΥΚΕΙΟΥ ΑΣΚΗΣΕΙΣ PDF

ΠΛΗΡΟΦΟΡΙΚΗ Γ ΛΥΚΕΙΟΥ ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΛΙΣΤΕΣ-ΔΕΝΔΡΑ-ΓΡΑΦΟΙ Θέμα 1 Να εισαχθούν σε κενό δυαδικό δένδρο αναζήτησης οι εξής τιμές: 50,30,39,40,60, 50, 32,28,69,67,66. Θέμα 2 Να σχεδιάσετε το δένδρο που προκύπτει από τις ακ...

ΠΛΗΡΟΦΟΡΙΚΗ Γ ΛΥΚΕΙΟΥ ΔΥΝΑΜΙΚΕΣ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΛΙΣΤΕΣ-ΔΕΝΔΡΑ-ΓΡΑΦΟΙ Θέμα 1 Να εισαχθούν σε κενό δυαδικό δένδρο αναζήτησης οι εξής τιμές: 50,30,39,40,60, 50, 32,28,69,67,66. Θέμα 2 Να σχεδιάσετε το δένδρο που προκύπτει από τις ακόλουθες πληροφορίες: 1) ο κόμβος Α έχει παιδιά τους κόμβους Β, Γ και Δ 2) οι κόμβοι Ε και Ζ έχουν πατέρα τον κόμβο Δ 3) ο κόμβος Κ έχει αδέλφια τους κόμβους Λ και Μ και πατέρα τον κόμβο Γ 4) κόμβος Π έχει παιδί τον κόμβο Ρ και πατέρα τον κόμβο Β. Θέμα 3 Δίνονται οι αριθμοί 11,7, 16, 19, 35, 23. Να δημιουργήσετε ένα δυαδικό δένδρο αναζήτησης. Θέμα 4 Να δημιουργήσετε ένα δένδρο απόφασης, που θα κατηγοριοποιεί τα παρακάτω ζώα: λιοντάρι, κότα, χελιδόνι, πρόβατο, σκύλος, γάτα, άλογο, σύμφωνα με τα χαρακτηριστικά: 1)αν έχουν δύο πόδια ή όχι 2) στην περίπτωση που δεν έχουν δύο πόδια, αν είναι χορτοφάγα ή σαρκοφάγα. Θέμα 5 Να δημιουργήσετε ένα δένδρο το οποίο θα αναπαριστά την λύση της πράξης (α+β)^(γ-2). Θέμα 6 Δίνεται η επόμενη ακολουθία αριθμών : 14, 18, 2, 5, 9, 13. 1. Ποια λειτουργία θα χρησιμοποιήσετε για την τοποθέτηση των αριθμών σε ουρά; 2. Να σχεδιάσετε την ουρά έπειτα από την τοποθέτηση των αριθμών. 3. Ποια λειτουργία θα χρησιμοποιήσετε για την εξαγωγή των αριθμών από την ουρά; 4. Πόσες φορές θα πρέπει να εκτελεστεί η προηγούμενη λειτουργία στην ουρά για να εξαχθεί ο αριθμός 5; Θέμα 7 Επιμέλεια: Απόστολος Χριστοδούλου ΠΕ86 1 Παρουσιάστε σχηματικά όλα τα διαφορετικά δυαδικά δέντρα αναζήτησης που μπορούν να παραχθούν με κόμβους με τιμές 10, 15, 5, και 20 έχοντας ως ρίζα πάντα τον κόμβο με την τιμή 10. Θέμα 8 Δίνεται το εξής στιγμιότυπο στη μνήμη του υπολογιστή: ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ ΤΙΜΗ 110 A 229 B 280 C 300 D 500 E 618 F 700 G A. Να σχηματιστεί απλά συνδεδεμένη λίστα με κόμβους που θα σχηματίζουν τη λέξη BADGE. B. Να ανασχηματιστεί η συνδεδεμένη λίστα αφού διαγραφεί ο κόμβος μετιμή D. C. Να σχηματιστεί διπλά συνδεδεμένη λίστα με κόμβους που θα σχηματίζουν τη λέξη CAB. Θέμα 9 Δίνεται η παρακάτω συνδεδεμένη λίστα : Α. Ξεκινώντας από την κεφαλή και πηγαίνοντας προς το τέλος της λίστας, να εισάγετε τα δεδομένα και τη διεύθυνση μνήμης κάθε κόμβου της λίστας σε στοίβα Α (άρα για κάθε κόμβο θα γίνονται δύο ωθήσεις στην στοίβα). Να δείξετε σταδιακά την στοίβα και τις τιμές του δείκτη top. Β. Να γίνει απώθηση των τιμών της στοίβας και να ωθηθούν αυτές σε ένα δένδρο δυαδικής αναζήτησης. Επιμέλεια: Απόστολος Χριστοδούλου ΠΕ86 2  Θέμα 10 Απαντήστε με Σωστό ή Λάθος για τα παρακάτω: 1. Σε ένα δένδρο, όλοι οι κόμβοι έχουν ακριβώς ένα γονέα. 2. Οι κόμβοι χωρίς παιδιά σε ένα δένδρο ονομάζονται φύλλα. 3. Οι κόμβοι με τον ίδιο πατέρα ονομάζονται αδέρφια. 4. Ένας κόμβος-πατέρας, μπορεί να έχει μόνο ένα κόμβο-παιδί. 5. Στα δένδρα μπορούμε εύκολα να προσθέσουμε και να αφαιρέσουμε κόμβους. 6. Ένα δένδρο μπορεί να έχει περισσότερες από μία ρίζες. 7. Ένα από τα προβλήματα στην επίλυση των οποίων βοηθούν τα δένδρα είναι η αυτόματη συμπλήρωση λέξεων σε συσκευές κινητών. 8. Σε ένα δυαδικό δένδρο αναζήτησης, κάθε κόμβος μπορεί να έχει 2 ή περισσότερα παιδιά. 9. Σε ένα δυαδικό δένδρο αναζήτησης, κάθε κόμβος έχει τιμή μεγαλύτερη από όλους τους κόμβους του αριστερού υποδένδρου του και τιμή μικρότερη ή ίση από όλους τους κόμβους του δεξιού υποδένδρου του. 10. Τα δυαδικά δένδρα αναζήτησης προσφέρουν πλεονεκτήματα στην λειτουργία της αναζήτησης. 11. Σε ένα δυαδικό δένδρο αναζήτησης, κάποιος κόμβος μπορεί να έχει ένα μόνο παιδί. 12. Υπάρχουν δένδρα που βοηθούν στην μοντελοποίηση των κινήσεων σε παιχνίδια όπως η τρίλιζα. 13. Σε ένα δένδρο, υπάρχει μία μοναδική διαδρομή για κάθε κόμβο, δηλαδή μία ακολουθία ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο. 14. Ένας κόμβος που είναι παιδί για έναν κόμβο, μπορεί να είναι πατέρας για κάποιον άλλο κόμβο. 15. Σε ένα δυαδικό δένδρο, κάποιος κόμβος μπορεί να έχει τρία υποδένδρα. ΓΡΑΦΟΙ Θέμα 11 1. Παράδειγμα 1 – Δημιουργία γράφου: Να σχεδιάσετε μία μορφή δεδομένων «Γράφος» θα αναπαριστά οδικές συνδέσεις μεταξύ των πόλεων Α, Β, Γ, Δ, Ε, με βάση τις ακόλουθες πληροφορίες: I. Η πόλη Α ενώνεται με τις πόλεις Β και Γ. II. Η πόλη Γ ενώνεται με τις πόλεις Ε και Δ. III. Η πόλη Β συνδέεται με τις πόλεις Ε και Δ Θέμα 12 2. Να σχεδιάσετε έναν γράφο, για την αναπαράσταση οδικών διαδρομών, με βάση τις παρακάτω πληροφορίες. Να εξηγήσετε επίσης τι είδους ακμές θα χρησιμοποιήσετε και γιατί. I. Η πόλη Α συνδέεται με τις πόλεις Β και Ε. II. Η πόλη Β συνδέεται με τις πόλεις Γ και Ζ. III. Η πόλη Γ συνδέεται με τις πόλεις Ζ και Δ. IV. Η πόλη Ε συνδέεται με τις πόλεις Δ και Ζ Θέμα 13 3. Να σχεδιάσετε έναν γράφο, για την αναπαράσταση σύνδεσης Επιμέλεια: Απόστολος Χριστοδούλου ΠΕ86 3 ιστοσελιδών, με βάση τις παρακάτω πληροφορίες. Να εξηγήσετε επίσης τι είδους ακμές θα χρησιμοποιήσετε και γιατί. I. Η ιστοσελίδα Α συνδέεται με τις ιστοσελίδες Β και Γ με αμφίδρομη σχέση. II. Η ιστοσελίδα Β συνδέεται με τις ιστοσελίδες Δ και Ε με αμφίδρομη σχέση. III. Η ιστοσελίδα Ε μπορεί να συνδεθεί με την ιστοσελίδα Ζ αλλά όχι το αντίθετο. IV. Η ιστοσελίδα Γ μπορεί να συνδεθεί με την ιστοσελίδα Π αλλά όχι το αντίθετο. Θέμα 14 4. Απαντήστε με Σωστό ή Λάθος για τα παρακάτω: A. Ένας γράφος έχει υποχρεωτικά μία ρίζα. B. Ο γράφος είναι η πιο γενική δομή δεδομένων. C. Σε ένα γράφο, ένας κόμβος μπορεί να συνδέεται μέχρι και με δύο άλλους κόμβους. D. Σε μία γραμμική δομή δεδομένων, τα δεδομένα ακολουθούν μία συγκεκριμένη σειρά. E. Ένα δένδρο είναι πάντα γράφος. F. Ένας γράφος είναι πάντα δένδρο. G. Υπάρχουν δύο είδη ακμών, οι κατευθυνόμενες και οι μη κατευθυνόμενες. H. Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος.. I. Σε μία μη κατευθυνόμενη ακμή, η σύνδεση των κόμβων είναι αμφίδρομη. J. Στο Facebook, υπάρχει μη αμφίδρομη σχέση μεταξύ των χρηστών. Επιμέλεια: Απόστολος Χριστοδούλου ΠΕ86 4