Δομές Δεδομένων — Ιούνιος 2021 — Παραλλαγή Γ¶
Μεταγραφή από το αρχείο themata3.pdf (δύο σελίδες).
themata3.pdf¶
Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ»¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ¶
Εαρινό Εξάμηνο 2020-21
Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος, Βονιτσάνος Γεράσιμος
ΔΙΑΡΚΕΙΑ 1:30 ΩΡΑ¶
ΘΕΜΑ 1 (2 μονάδες)¶
Εφαρμόστε το weighted union rule για τα παρακάτω Unions (κλήση U(,,)) από 1 έως 7. Οι αριθμοί δηλώνουν το πλήθος των στοιχείων (weight) κάθε συνόλου που λαμβάνει μέρος στο Union . Αν δεν υπάρχουν αριθμοί στα ορίσματα τότε αναφέρονται ονόματα συνόλων. Τα κεφαλαία γράμματα είναι ονόματα συνόλων. Πάντα τα δύο πρώτα σύνολα στην κλήση ενώνονται στο τρίτο.
1. U(1, 1, A)
2. U(2, 3, B)
3. U(4, 2, C)
4. U(B,C,D)
5. U(1, 2, E)
6. U(A, E, F)
7. U(D, F,G)
ΘΕΜΑ 2 (3 μονάδες)¶
- α) Έστω στοίβα (stack) S με τα εξής στοιχεία (η τιμή του δείκτη κορυφής είναι 6 με τους δείκτες να ξεκινάνε από το 0 – κοιτάξτε σχήμα στη σελ. 28 του pdf του βιβλίου στο eclass και ο πίνακας είναι από αριστερά προς τα δεξιά), όπου στη θέση του Χ θα βάλετε τo τελευταίo ψηφίo του ΑΜ σας
| 38 | 43 | 39 | 23 | 36 | 24 | Χ |
|---|---|---|---|---|---|---|
Δώστε το δέντρο – σωρό (heap) που σχηματίζεται αν εξάγουμε ένα - ένα τα στοιχεία από τη στοίβα και τα εισάγουμε με την ίδια σειρά στο δέντρο. Στην απάντησή σας να φαίνεται η μορφή του δέντρου - σωρού που σχηματίζεται μετά από κάθε εισαγωγή.
-
β) Διαγράψτε τη ρίζα του δέντρου - σωρού δύο φορές, δείχνοντας τα δέντρα που θα προκύψουν μετά την πρώτη και τη δεύτερη διαγραφή αντίστοιχα.
-
γ) Έστω ότι στο αρχικό δέντρο - σωρό (πριν τις δύο διαγραφές), διαγράφουμε διαδοχικά τη ρίζα του και κάθε στοιχείο που διαγράφεται το εισάγουμε σε ένα (απλό χωρίς ζύγιση) Δυαδικό Δέντρο Αναζήτησης. Ποιο είναι το ύψος του δέντρου που προκύπτει μετά τη διαγραφή όλων των στοιχείων ; (αν θέλετε σχεδιάστε το δέντρο)
ΘΕΜΑ 3 (3 μονάδες)¶
Έστω ότι θέλουμε να ενθέσουμε τα κλειδιά 2, 1, 32, 15, 33, 44, 8, 5, 9 σε ένα πίνακα μήκους m=10 με τη σειρά που δίνονται χρησιμοποιώντας (α) κατακερματισμό (hashing) με αλυσίδες και (β) κατακερματισμό με ανοικτή διεύθυνση (hashing με open addressing).
Και στις δύο μεθόδους η βασική hash συνάρτηση είναι \(h_1(k) = (c * k) \bmod m\). Στο hashing με open addressing (κατακερματισμός με ανοικτή διεύθυνση) έστω ότι η \(h_2(k) = (k + c) \bmod m\) (μέθοδος με διπλό κατακερματισμό (double hashing)). Η τιμή c είναι το τελευταίο ψηφίο του αριθμού μητρώου σας. Δώστε σχηματικά τους hashing πίνακες,
ΘΕΜΑ 4 (2 μονάδες)¶
Σας δίνετε το αλφάβητο \(\Sigma = \{A, T, C, G\}\) που αποτελεί τις βάσεις του ανθρώπινου γονιδιώματος (DNA). Σύμφωνα με το αλφάβητο αυτό δημιουργούνται τα στοιχεία {AAAC, AATC, ATCG, ATGG, TCGC, TCGG, CTTT, CCTG, GCTA} τα οποία καλείστε να αποθηκεύστε σε δομή Trie χτισμένη στο παραπάνω αλφάβητο. Σχεδιάστε:
mmlab¶
i) Την πλήρη αποθήκευση (χωρίς σύμπτυξη)
ii) Την αποθήκευση που καταλαμβάνει το μικρότερο χώρο (συμπαγές trie).
mmlab¶
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06-c¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Weighted union: η ρίζα του μεγαλύτερου συνόλου γίνεται ρίζα του ενωμένου, η ρίζα του μικρότερου δείχνει σε αυτήν (σε ισοβαρή, ρίζα γίνεται η ρίζα του πρώτου ορίσματος – σύμβαση, δεν ορίζεται στην εκφώνηση). Το βάρος του νέου συνόλου είναι το άθροισμα.
| # | Union | Βάρη | Νέο σύνολο | Ρίζα προκύπτει από |
|---|---|---|---|---|
| 1 | U(1,1,A) | 1, 1 | A = 2 | πρώτο (ισοβαρή) |
| 2 | U(2,3,B) | 2, 3 | B = 5 | το σύνολο των 3 |
| 3 | U(4,2,C) | 4, 2 | C = 6 | το σύνολο των 4 |
| 4 | U(B,C,D) | 5, 6 | D = 11 | το C (6 > 5) |
| 5 | U(1,2,E) | 1, 2 | E = 3 | το σύνολο των 2 |
| 6 | U(A,E,F) | 2, 3 | F = 5 | το E (3 > 2) |
| 7 | U(D,F,G) | 11, 5 | G = 16 | το D (11 > 5) |
Τελικό σύνολο G με βάρος 16, με ρίζα τη ρίζα του D (που προέρχεται από το C, δηλαδή από το σύνολο των 4 στοιχείων του βήματος 3). Η τεχνική εξασφαλίζει ύψος ≤ log₂16 = 4.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Παράδειγμα με Χ = 5 και min-heap (μικρότερο στη ρίζα). Η στοίβα εξάγεται από την κορυφή: σειρά εισαγωγής 5, 24, 36, 23, 39, 43, 38 (πίνακας σωρού με ευρετήριο από 0).
α) Μετά από κάθε εισαγωγή: - 5: [5] - 24: [5, 24] - 36: [5, 24, 36] - 23: μπαίνει κάτω από το 24, ανταλλαγή με 24 → [5, 23, 36, 24] - 39: [5, 23, 36, 24, 39] - 43: [5, 23, 36, 24, 39, 43] - 38: [5, 23, 36, 24, 39, 43, 38]
Τελικό δέντρο: 5(23(24,39),36(43,38)).
β) Διαγραφή ρίζας: το τελευταίο (38) πάει στη ρίζα και κατεβαίνει. - Μετά την 1η: [23, 24, 36, 38, 39, 43] → 23(24(38,39),36(43,-)). - Μετά τη 2η: [24, 38, 36, 43, 39] → 24(38(43,39),36).
γ) Οι διαδοχικές διαγραφές ρίζας βγάζουν τα στοιχεία σε αύξουσα σειρά (5, 23, 24, 36, 38, 39, 43). Εισαγωγή αύξουσας ακολουθίας σε απλό ΔΔΑ δίνει αλυσίδα προς τα δεξιά. Με 7 στοιχεία: ύψος 6 ακμές (7 επίπεδα). Το ίδιο ισχύει για οποιοδήποτε Χ διακριτό από τα άλλα στοιχεία (και για max-heap, αλυσίδα προς τα αριστερά).
Θέμα 3¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε)
Με c = 9: h1(k) = 9k mod 10, h2(k) = (k+9) mod 10. Σειρά κλειδιών: 2, 1, 32, 15, 33, 44, 8, 5, 9.
h1: 2→8, 1→9, 32→8, 15→5, 33→7, 44→6, 8→2, 5→5, 9→1.
(α) Αλυσίδες (νέο στοιχείο στο τέλος της λίστας): - 1: 9 - 2: 8 - 5: 15 → 5 - 6: 44 - 7: 33 - 8: 2 → 32 - 9: 1 - (0, 3, 4 κενά)
(β) Ανοικτή διεύθυνση, διπλός κατακερματισμός, ακολουθία θέσεων (h1 + i·h2) mod 10: - 2 → 8, 1 → 9 - 32: h1=8 (κατειλημμένη), h2=1 → 9 (κατειλ.) → 0 ελεύθερη - 15 → 5, 33 → 7, 44 → 6, 8 → 2 - 5: h1=5 (κατ.), h2=4 → 9 (κατ.) → 3 ελεύθερη - 9: h1=1 ελεύθερη
Πίνακας: θέση 0:32, 1:9, 2:8, 3:5, 4:κενή, 5:15, 6:44, 7:33, 8:2, 9:1.
Σημείωση: για άλλα c το h2 συχνά έχει κοινό παράγοντα με το m=10 (π.χ. άρτια τιμή) και τότε η ακολουθία δοκιμών δεν καλύπτει όλο τον πίνακα· σε προσομοίωση με c=1,3,7 το κλειδί 9 δεν βρίσκει θέση, ενώ με c=9 όλα εισάγονται.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Λέξεις: AAAC, AATC, ATCG, ATGG, TCGC, TCGG, CTTT, CCTG, GCTA.
i) Πλήρες trie (ένας κόμβος ανά γράμμα, χωρίς σύμπτυξη), από τη ρίζα: - A → A → {A → C ✓ (AAAC), T → C ✓ (AATC)} - A → T → {C → G ✓ (ATCG), G → G ✓ (ATGG)} - T → C → G → {C ✓ (TCGC), G ✓ (TCGG)} - C → {T → T → T ✓ (CTTT), C → T → G ✓ (CCTG)} - G → C → T → A ✓ (GCTA)
Σύνολο 28 κόμβοι (με τη ρίζα· 27 γράμματα-κόμβοι: A-κλάδος 11, T 5, C 7, G 4). Στα κλασικά trie μπορεί να προστεθεί και τερματικό σύμβολο $ σε κάθε λέξη· εδώ όλες οι λέξεις έχουν το ίδιο μήκος 4 και δεν χρειάζεται.
ii) Συμπαγές (compressed) trie: οι κόμβοι με ένα παιδί συμπτύσσονται σε ακμές με ετικέτα συμβολοσειράς: - ρίζα → «A» → {«A» → {«AC», «TC»}, «T» → {«CG», «GG»}} (κόμβοι διακλάδωσης στα AA και AT) - ρίζα → «TCG» → {«C», «G»} - ρίζα → «C» → {«TTT», «CTG»} - ρίζα → «GCTA» (φύλλο)
Συμπαγές trie: 4 κλάδοι από τη ρίζα: A(A(AC,TC),T(CG,GG)), TCG(C,G), C(TTT,CTG), GCTA.