Δομές Δεδομένων — Ιούνιος 2021 — Παραλλαγή Β¶
Μεταγραφή από το αρχείο themata2.pdf (μία σελίδα)· το image.png είναι φωτογραφία του ίδιου Θέματος 1.
themata2.pdf¶
Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ»¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ¶
Εαρινό Εξάμηνο 2020-21
Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος, Βονιτσάνος Γεράσιμος
ΔΙΑΡΚΕΙΑ 1:30 ΩΡΑ
ΘΕΜΑ 1 (3 μονάδες)¶
Γράψτε ΠΡΩΤΑ ΤΟ ΕΠΩΝΥΜΟ ΚΑΙ ΜΕΤΑ ΤΟ ΟΝΟΜΑ σας με λατινικούς κεφαλαίους χαρακτήρες χωρίς κενά και σταματήστε στους πρώτους 22 χαρακτήρες. Αν το ονοματεπώνυμο είναι λιγότεροι χαρακτήρες συμπληρώστε με το ονοματεπώνυμό σας πάλι, μέχρι να φτάσετε σε 22 χαρακτήρες. Ταξινομήστε την προκύπτουσα ακολουθία: με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=4, και ότι έχετε 8 ταινίες στις διάθεσή σας (p=4). (Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)
ΘΕΜΑ 2 (3 μονάδες)¶
Ταξινομήστε τον πίνακα ακεραίων: {4, 3, 51, 33, 1, 79, 13, 23, 24, 5, 9, 91} με χρήση του Quick Sort . Αναφέρετε την πολυπλοκότητα χειρότερης περίπτωσης.
ΘΕΜΑ 3 (3 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το (2,3) δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {8, 3, 2, 78, 7, 12, 4, 12, 6, 22, 11, 1 ,44}. Διαγράψτε 22 και 2, 1 και δείξτε βήμα-βήμα τη μορφή του δένδρου.
ΘΕΜΑ 4 (1 μονάδες)¶
Σας δίνεται το ακόλουθο δέντρο. Δείξτε το αποτέλεσμα της προδιάταξης
[Σχήμα: δυαδικό δέντρο. Ρίζα 9· αριστερό παιδί 41 (με παιδιά 3 αριστερά και 15 δεξιά)· δεξί παιδί 2 (με παιδιά 35 αριστερά και 39 δεξιά)· το 3 έχει παιδιά 12 αριστερά και 45 δεξιά· το 35 έχει παιδί 36 δεξιά.]
mmlab¶
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-06-b.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):image.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06-b¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: η ακολουθία εξαρτάται από το ονοματεπώνυμο του φοιτητή (και η μεταγραφή του image.png έχει ασυμφωνίες). Για τη μέθοδο βλ. τις λύσεις External Sorting των 2023-06-a / 2024-06-a.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Χρησιμοποιείται η κλασική Quick Sort του μαθήματος: pivot = στοιχείο στη μέση list[(left+right)/2], δείκτες που κινούνται από τα δύο άκρα, ανταλλαγή όταν leftArrow ≤ rightArrow, αναδρομή στα δύο μέρη (αν η εκφώνηση ζητά άλλη επιλογή pivot, τα ενδιάμεσα βήματα διαφέρουν, όχι το τελικό αποτέλεσμα).
Πίνακας: 4 3 51 33 1 79 13 23 24 5 9 91 (θέσεις 0–11).
1. Pivot = list[5] = 79: μία ανταλλαγή 79↔9 και το 79 καταλήγει στη θέση 10 → 4 3 51 33 1 9 13 23 24 5 | 79 91 (αριστερό μέρος θέσεις 0–9, δεξί θέσεις 10–11).
2. Αριστερό μέρος: pivot = list[4] = 1 → 1 | 3 51 33 4 9 13 23 24 5 (το 1 τοποθετείται στην αρχή).
3. 3 51 33 4 9 13 23 24 5: pivot = 9 → 3 5 9 4 | 33 13 23 24 51.
4. 3 5 9 4: pivot 5 → 3 4 | 9 5 → 3 4 και 5 9. 33 13 23 24 51: pivot 23 → 23 13 | 33 24 51 → 13 23 και (pivot 24) 24 33 51.
5. 79 91 είναι ήδη ταξινομημένο.
Ταξινομημένος πίνακας: 1 3 4 5 9 13 23 24 33 51 79 91
(Η ακολουθία των διαμερίσεων επαληθεύτηκε με πρόγραμμα.) Πολυπλοκότητα χειρότερης περίπτωσης: \(O(n^2)\) (όταν το pivot χωρίζει διαρκώς πολύ άνισα, π.χ. min/max), μέση \(O(n\log n)\).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Συμβάσεις: (2,3)-δέντρο με κλειδιά σε όλους τους κόμβους (κάθε κόμβος έως 2 κλειδιά, 3 παιδιά)· υπερχείλιση (3 κλειδιά) → διάσπαση, το μεσαίο ανεβαίνει. Το διπλό 12 αγνοείται (σύνολο κλειδιών). Διαγραφή: από εσωτερικό κόμβο αντικατάσταση με τον διάδοχο· αν ο κόμβος μείνει κενός: δανεισμός από αριστερό αδελφό (αν έχει 2 κλειδιά), αλλιώς από δεξιό, αλλιώς συγχώνευση (προτίμηση αριστερού αδελφού). Άλλη σύμβαση (π.χ. προτεραιότητα δεξιού) μπορεί να δώσει διαφορετικό σχήμα.
Σημειογραφία [κλειδιά | παιδιά].
| Βήμα | Δέντρο |
|---|---|
| +8 | [8] |
| +3 | [3 8] |
| +2 | υπερχείλιση [2 3 8] → [3 | [2] [8]] |
| +78 | [3 | [2] [8 78]] |
| +7 | [3 8 | [2] [7] [78]] (διάσπαση [7 8 78]) |
| +12 | [3 8 | [2] [7] [12 78]] |
| +4 | [3 8 | [2] [4 7] [12 78]] |
| +12 | διπλότυπο, αγνοείται |
| +6 | ο [4 6 7] σπάει, το 6 ανεβαίνει, η ρίζα [3 6 8] σπάει → [6 | [3 | [2] [4]] [8 | [7] [12 78]]] |
| +22 | [6 | [3 | [2] [4]] [8 22 | [7] [12] [78]]] |
| +11 | [6 | [3 | [2] [4]] [8 22 | [7] [11 12] [78]]] |
| +1 | [6 | [3 | [1 2] [4]] [8 22 | [7] [11 12] [78]]] |
| +44 | [6 | [3 | [1 2] [4]] [8 22 | [7] [11 12] [44 78]]] |
Διαγραφές: - Διαγραφή 22 (εσωτερικός): αντικαθίσταται από τον διάδοχο 44 → [6 | [3 | [1 2] [4]] [8 44 | [7] [11 12] [78]]]. - Διαγραφή 2: φύλλο [1 2] → [1], χωρίς πρόβλημα → [6 | [3 | [1] [4]] [8 44 | [7] [11 12] [78]]]. - Διαγραφή 1: το φύλλο μένει κενό, ο δεξιός αδελφός [4] έχει 1 κλειδί → συγχώνευση σε [3 4]· ο γονέας (πρώην [3]) μένει κενός· ο αδελφός του [8 44] έχει 2 κλειδιά → δανεισμός μέσω της ρίζας (6 κάτω, 8 πάνω, το παιδί [7] περνά αριστερά).
Τελικό δέντρο: [8 | [6 | [3 4] [7]] [44 | [11 12] [78]]]
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Προδιάταξη (ρίζα, αριστερό, δεξί): 9 → 41(3(12,45),15) → 2(35(-,36),39).
Αποτέλεσμα: 9 41 3 12 45 15 2 35 36 39