Δομές Δεδομένων — Ιούνιος 2023 — Παραλλαγή Β¶
Μεταγραφή από τις φωτογραφίες Screenshot_2023-06-21_130222.png και IMG_3884.jpg.
Screenshot_2023-06-21_130222.png¶
ΘΕΜΑ 3 (3 μονάδες)
Δίνονται οι ακόλουθες διαπεράσεις ενός δυαδικού δένδρου:
ΜΕΤΑΔΙΑΤΑΞΗ: QLDEFGKHIJA
ΣΥΜΜΕΤΡΙΚΗ ΔΙΑΤΑΞΗ: QDLAEKGFJHI
Ανασχηματίστε τη μορφή του συγκεκριμένου δυαδικού δένδρου.
IMG_3884.jpg¶
8. Εφαρμόστε το weighted union rule για τα παρακάτω Unions από 1 έως 7. Οι αριθμοί δηλώνουν τον αριθμό των στοιχείων (weight) κάθε συνόλου που λαμβάνει μέρος στο Union. Τα κεφαλαία γράμματα είναι ονόματα συνόλων.
- U(4,2,A)
- U(3,5,B)
- U(A,B,C)
- U(6,9,D)
- U(2,6,E)
- U(D,C,F)
- U(F,E,G)
9. Σας δίνεται ο ταξινομημένος πίνακας ακεραίων: {4, 9, 11, 12, 13, 16, 17, 20, 21, 30, 40, 92}.
[Λείπει από τη φωτογραφία: το υπόλοιπο της ερώτησης 9 (κάτω άκρο της φωτογραφίας IMG_3884.jpg)]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-06-b.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_2023-06-21_193138.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-06-b¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η μεταδιάταξη τελειώνει με τη ρίζα: A. Στη συμμετρική, αριστερά του A είναι QDL (αριστερό υποδέντρο, 3 κόμβοι) και δεξιά EKGFJHI (7 κόμβοι). Στη μεταδιάταξη: πρώτοι 3 κόμβοι QLD (αριστερό), επόμενοι EFGKHIJ (δεξί).
- Αριστερό: μεταδιάταξη QLD → ρίζα D, συμμετρική Q D L → παιδιά Q (αριστερά), L (δεξιά).
- Δεξί: μεταδιάταξη EFGKHIJ → ρίζα J. Συμμετρική E K G F J H I → αριστερά του J: EKGF, δεξιά HI.
- EKGF (μεταδιάταξη EFGK): ρίζα K, αριστερά E, δεξιά GF (μεταδ. FG, ρίζα G, συμμετρική G F → F δεξί παιδί του G).
- HI (μεταδιάταξη HI): ρίζα I, αριστερό παιδί H.
Δέντρο: A(D(Q,L), J(K(E,G(-,F)), I(H,-))). Έλεγχος: η μεταδιάταξη δίνει QLDEFGKHIJA και η συμμετρική QDLAEKGFJHI.
Θέμα 8¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Weighted union με σύμβαση: η ρίζα του βαρύτερου συνόλου γίνεται ρίζα (σε ισοβαρή, η ρίζα του πρώτου ορίσματος)· βάρος νέου = άθροισμα.
| # | Union | Βάρη | Αποτέλεσμα |
|---|---|---|---|
| 1 | U(4,2,A) | 4, 2 | A = 6, ρίζα του συνόλου των 4 |
| 2 | U(3,5,B) | 3, 5 | B = 8, ρίζα του συνόλου των 5 |
| 3 | U(A,B,C) | 6, 8 | C = 14, ρίζα του B |
| 4 | U(6,9,D) | 6, 9 | D = 15, ρίζα του συνόλου των 9 |
| 5 | U(2,6,E) | 2, 6 | E = 8, ρίζα του συνόλου των 6 |
| 6 | U(D,C,F) | 15, 14 | F = 29, ρίζα του D |
| 7 | U(F,E,G) | 29, 8 | G = 37, ρίζα του F |
Τελικό σύνολο G με βάρος 37, ρίζα η ρίζα του D (το σύνολο των 9 στοιχείων του βήματος 4).
Θέμα 9¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στη φωτογραφία IMG_3884.jpg το κάτω μέρος της ερώτησης 9 είναι κομμένο, αλλά από τις επίσημες διαφάνειες του μαθήματος (endeiktikes_askiseis_eksaskisis_2.pdf, σελ. 2) που απεικονίζονται στην οθόνη ανακτάται πλήρως η εκφώνηση:
«9. Σας δίνεται ο ταξινομημένος πίνακας ακεραίων: \(\{4, 9, 11, 12, 13, 16, 17, 20, 21, 30, 40, 92\}\). Εκτελέστε το Interpolation Search για τους αριθμούς 13, 92 και 25. Για κάθε αναζήτηση καταγράψτε ποιο είναι το στοιχείο που ελέγχεται σε κάθε βήμα και πόσα βήματα εκτελούνται. Συγκρίνετε τις πολυπλοκότητες μέσης και χειρότερης περίπτωσης του αλγορίθμου με αυτές του Binary Search.»
Ο πίνακας \(A\) έχει μήκος \(n = 12\) με δείκτες \(0, \dots, 11\): $\(A = [4, 9, 11, 12, 13, 16, 17, 20, 21, 30, 40, 92]\)$ Ο τύπος παρεμβολής για τον υπολογισμό της θέσης είναι: $\(pos = low + \left\lfloor \frac{key - A[low]}{A[high] - A[low]} \cdot (high - low) \right\rfloor\)$
1. Αναζήτηση του \(key = 13\)¶
- Βήμα 1: \(low = 0\), \(high = 11\), \(A[0] = 4\), \(A[11] = 92\). $\(pos = 0 + \left\lfloor \frac{13 - 4}{92 - 4} \cdot 11 \right\rfloor = \left\lfloor \frac{99}{88} \right\rfloor = 1\)$ Ελέγχεται το στοιχείο \(A[1] = 9\). Επειδή \(9 < 13\), θέτουμε \(low = 2\).
- Βήμα 2: \(low = 2\), \(high = 11\), \(A[2] = 11\), \(A[11] = 92\). $\(pos = 2 + \left\lfloor \frac{13 - 11}{92 - 11} \cdot (11 - 2) \right\rfloor = 2 + \left\lfloor \frac{18}{81} \right\rfloor = 2\)$ Ελέγχεται το στοιχείο \(A[2] = 11\). Επειδή \(11 < 13\), θέτουμε \(low = 3\).
- Βήμα 3: \(low = 3\), \(high = 11\), \(A[3] = 12\), \(A[11] = 92\). $\(pos = 3 + \left\lfloor \frac{13 - 12}{92 - 12} \cdot (11 - 3) \right\rfloor = 3 + \left\lfloor \frac{8}{80} \right\rfloor = 3\)$ Ελέγχεται το στοιχείο \(A[3] = 12\). Επειδή \(12 < 13\), θέτουμε \(low = 4\).
- Βήμα 4: \(low = 4\), \(high = 11\), \(A[4] = 13\), \(A[11] = 92\). $\(pos = 4 + \left\lfloor \frac{13 - 13}{92 - 13} \cdot (11 - 4) \right\rfloor = 4\)$ Ελέγχεται το στοιχείο \(A[4] = 13 = key\). Βρέθηκε!
Αποτέλεσμα για 13: Ελέγχθηκαν διαδοχικά τα στοιχεία \(A[1]=9\), \(A[2]=11\), \(A[3]=12\), \(A[4]=13\). Εκτελέστηκαν 4 βήματα.
2. Αναζήτηση του \(key = 92\)¶
- Βήμα 1: \(low = 0\), \(high = 11\), \(A[0] = 4\), \(A[11] = 92\). $\(pos = 0 + \left\lfloor \frac{92 - 4}{92 - 4} \cdot 11 \right\rfloor = 11\)$ Ελέγχεται το στοιχείο \(A[11] = 92 = key\). Βρέθηκε άμεσα!
Αποτέλεσμα για 92: Ελέγχθηκε μόνο το στοιχείο \(A[11]=92\). Εκτελέστηκε 1 βήμα.
3. Αναζήτηση του \(key = 25\)¶
- Βήμα 1: \(low = 0\), \(high = 11 \implies pos = 0 + \lfloor \frac{21}{88} \cdot 11 \rfloor = \lfloor 2.625 \rfloor = 2\). Ελέγχεται το \(A[2] = 11 < 25 \implies low = 3\).
- Βήμα 2: \(low = 3\), \(high = 11 \implies pos = 3 + \lfloor \frac{13}{80} \cdot 8 \rfloor = 3 + 1 = 4\). Ελέγχεται το \(A[4] = 13 < 25 \implies low = 5\).
- Βήμα 3: \(low = 5\), \(high = 11 \implies pos = 5 + \lfloor \frac{9}{76} \cdot 6 \rfloor = 5 + 0 = 5\). Ελέγχεται το \(A[5] = 16 < 25 \implies low = 6\).
- Βήμα 4: \(low = 6\), \(high = 11 \implies pos = 6 + \lfloor \frac{8}{75} \cdot 5 \rfloor = 6 + 0 = 6\). Ελέγχεται το \(A[6] = 17 < 25 \implies low = 7\).
- Βήμα 5: \(low = 7\), \(high = 11 \implies pos = 7 + \lfloor \frac{5}{72} \cdot 4 \rfloor = 7 + 0 = 7\). Ελέγχεται το \(A[7] = 20 < 25 \implies low = 8\).
- Βήμα 6: \(low = 8\), \(high = 11 \implies pos = 8 + \lfloor \frac{4}{71} \cdot 3 \rfloor = 8 + 0 = 8\). Ελέγχεται το \(A[8] = 21 < 25 \implies low = 9\).
- Βήμα 7: \(low = 9\), \(high = 11\), όπου \(A[9] = 30\). Επειδή \(key = 25 < A[low] = 30\), η συνθήκη \(A[low] \le key \le A[high]\) παύει να ισχύει και ο αλγόριθμος τερματίζει: Το 25 δεν υπάρχει στον πίνακα.
Αποτέλεσμα για 25: Ελέγχθηκαν διαδοχικά τα στοιχεία \(A[2]=11\), \(A[4]=13\), \(A[5]=16\), \(A[6]=17\), \(A[7]=20\), \(A[8]=21\). Εκτελέστηκαν 6 βήματα ελέγχου (συγκρίσεις).
4. Σύγκριση Πολυπλοκοτήτων: Interpolation Search vs Binary Search¶
| Αλγόριθμος | Μέση Περίπτωση (Average Case) | Χειρότερη Περίπτωση (Worst Case) |
|---|---|---|
| Interpolation Search | \(\mathcal{O}(\log \log n)\) (για ομοιόμορφα κατανεμημένα κλειδιά) | \(\mathcal{O}(n)\) (όταν τα δεδομένα αποκλίνουν έντονα από την ομοιομορφία) |
| Binary Search | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(\log n)\) (εγγυημένη, ανεξάρτητα από την κατανομή) |
Σχόλιο: Η παρεμβολική αναζήτηση πλεονεκτεί σημαντικά στη μέση περίπτωση για ομοιόμορφη κατανομή (\(\mathcal{O}(\log \log n)\) έναντι \(\mathcal{O}(\log n)\)), ωστόσο σε μη ομοιόμορφες κατανομές (όπως στον συγκεκριμένο πίνακα όπου το \(92\) προκαλεί έντονη ασυμμετρία) μπορεί να υποπέσει στη γραμμική συμπεριφορά \(\mathcal{O}(n)\), όπου η δυαδική αναζήτηση παραμένει αυστηρά αποδοτικότερη.