Δομές Δεδομένων — Ιούνιος 2021 — Παραλλαγή Α¶
Μεταγραφή από το αρχείο themata1.pdf (μία σελίδα).
themata1.pdf¶
Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ»¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ¶
Εαρινό Εξάμηνο 2020-21
Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος, Βονιτσάνος Γεράσιμος
ΔΙΑΡΚΕΙΑ 1:30 ΩΡΑ
ΘΕΜΑ 1 (3 μονάδες)¶
Γράψτε το ονοματεπώνυμο σας με λατινικούς κεφαλαίους χαρακτήρες χωρίς κενά και σταματήστε στους πρώτους 20 χαρακτήρες. Αν το ονοματεπώνυμο είναι λιγότεροι χαρακτήρες συμπληρώστε με το ονοματεπώνυμό σας πάλι, μέχρι να φτάσετε σε 20 χαρακτήρες. Ταξινομήστε την προκύπτουσα ακολουθία: με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στις διάθεσή σας (p=3). (Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)
ΘΕΜΑ 2 (3 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το AVL δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {1, 11, 12, 10, 70, 13, 3, 22, 14, 20, 2}. Διαγράψτε 1 και 2,3 και δείξτε τη μορφή του δένδρου.
ΘΕΜΑ 3 (3 μονάδες)¶
Δίνονται οι ακόλουθες διαπεράσεις ενός δυαδικού δένδρου: ΠΡΟΔΙΑΤΑΞΗ: BAWCHJKIEFG ΣΥΜΜΕΤΡΙΚΗ ΔΙΑΤΑΞΗ: WAJHKCIBFEG
Ανασχηματίστε τη μορφή του συγκεκριμένου δυαδικού δένδρου.
ΘΕΜΑ 4 (1 μονάδες)¶
Δείξτε το αποτέλεσμα της μεταδιάταξης:
[Σχήμα: δυαδικό δέντρο. Ρίζα 4· αριστερό παιδί 1 (με παιδιά 2 αριστερά και 10 δεξιά)· δεξί παιδί 2 (με παιδιά 15 αριστερά και 49 δεξιά)· το 15 έχει παιδιά 3 αριστερά και 11 δεξιά· το 49 έχει παιδί 4 δεξιά.]
mmlab¶
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: η ακολουθία εισόδου προκύπτει από το ονοματεπώνυμο του κάθε φοιτητή, άρα δεν υπάρχει μία μοναδική απάντηση. (Μέθοδος: βλ. τη λύση των Θεμάτων External Sorting στις παραλλαγές 2023-06-a και 2024-06-a: γέμισμα μνήμης M, έξοδος του μικρότερου στοιχείου ≥ του τελευταίου εξόδου, «πάγωμα» των μικρότερων για το επόμενο run, και μετά συγχώνευση p runs κάθε φορά.)
Θέμα 2¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
Εισαγωγές (σημειογραφία ρίζα(αριστερό, δεξί), - = κενό). Εκτελέστηκε με πρόγραμμα προσομοίωσης.
| Εισαγωγή | Περιστροφή | Δέντρο μετά |
|---|---|---|
| 1 | – | 1 |
| 11 | – | 1(-,11) |
| 12 | RR → αριστερή περιστροφή στο 1 | 11(1,12) |
| 10 | – | 11(1(-,10),12) |
| 70 | – | 11(1(-,10),12(-,70)) |
| 13 | RL στο 12 (διπλή) | 11(1(-,10),13(12,70)) |
| 3 | RL στο 1 (διπλή) | 11(3(1,10),13(12,70)) |
| 22 | – | 11(3(1,10),13(12,70(22,-))) |
| 14 | LL στο 70 (δεξιά περιστροφή) | 11(3(1,10),13(12,22(14,70))) |
| 20 | RL στο 13 (διπλή) | 11(3(1,10),14(13(12,-),22(20,70))) |
| 2 | – | 11(3(1(-,2),10),14(13(12,-),22(20,70))) |
Διαγραφές: - Διαγραφή 1 (έχει μόνο δεξί παιδί, το 2): 11(3(2,10),14(13(12,-),22(20,70))). - Διαγραφή 2 (φύλλο): 11(3(-,10),14(13(12,-),22(20,70))). - Διαγραφή 3 (έχει μόνο δεξί παιδί 10): το 3 αντικαθίσταται από το 10, το αριστερό υποδέντρο της ρίζας 11 έχει πλέον ύψος 1 και το δεξί ύψος 3 → ανισορροπία στη ρίζα. Το δεξί παιδί 14 έχει συντελεστή ισορροπίας 0 (ύψη 2 και 2) → απλή αριστερή περιστροφή στη ρίζα (το 13 γίνεται δεξί παιδί του 11).
Τελικό δέντρο: 14(11(10,13(12,-)),22(20,70)) — ρίζα 14, αριστερά 11 με παιδιά 10 και 13 (το 13 έχει αριστερό παιδί 12), δεξιά 22 με παιδιά 20 και 70.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η προδιάταξη δίνει τη ρίζα (πρώτο γράμμα), η συμμετρική χωρίζει αριστερό/δεξί υποδέντρο. Ρίζα B → αριστερά WAJHKCI (7 κόμβοι), δεξιά FEG. Αναδρομικά: ρίζα A (αριστερά W, δεξιά JHKCI), ρίζα C (αριστερά JHK, δεξιά I), ρίζα H (J, K). Δεξιά: ρίζα E (F, G).
Δέντρο: B(A(W,C(H(J,K),I)),E(F,G)). Έλεγχος: προδιάταξη BAWCHJKIEFG και συμμετρική WAJHKCIBFEG ταιριάζουν.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Μεταδιάταξη (αριστερό, δεξί, ρίζα): αριστερό υποδέντρο του 4 = 1(2,10) → 2 10 1· δεξί υποδέντρο = 2(15(3,11),49(-,4)) → 3 11 15 4 49 2· τέλος η ρίζα 4.
Αποτέλεσμα: 2 10 1 3 11 15 4 49 2 4