Δομές Δεδομένων — Ιούνιος 2025¶
Μεταγραφή από το αρχείο exam_paper_2025.pdf (δύο σελίδες)· η φωτογραφία 508649524 είναι η πρώτη σελίδα.
exam_paper_2025.pdf¶
Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ»¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΣ 2024-2025¶
Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος
Δύο σελίδες – επιλέγετε τόσα θέματα, όσα χρειάζονται για να φτάσετε σε 10 μονάδες
| Επώνυμο: ........................ Όνομα: ........................ |
Α.Μ.: ........................ | Έτος: ............. | Υπογραφή: ........................ |
|---|---|---|---|
ΘΕΜΑ 1 (1,5 μονάδες)¶
Ταξινομήστε την ακολουθία: ANOTHERSORTINGANDDEEPLEARNINGALGORITHM με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=4, και ότι έχετε 8 ταινίες στις διάθεσή σας (p=4). (Υπόδειξη: Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)
ΘΕΜΑ 2 (1,5 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το (a,b)-δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {1, 21, 31, 17, 5, 31, 18, 14, 19, 20, 5, 23, 45} με a=2 και b=3. Διαγράψτε 21 και 19 και δείξτε τη μορφή του δένδρου.
ΘΕΜΑ 3 (1,5 μονάδες)¶
Αποθηκεύστε σε δομή Trie χτισμένη στο αλφάβητο Σ={0, 2, 4, 6} τα στοιχεία {000046, 0020444, 024046, 040064, 224064, 224404, 400066, 400222, 420066, 444644, 444066, 640024}. Προτείνετε την αποθήκευση που καταλαμβάνει το μικρότερο χώρο.
ΘΕΜΑ 4 (1,5 μονάδες)¶
Πως προκύπτει το επιμερισμένο κόστος O(1) ενθέσεων σε φυλλοπροσανατολισμένα (2,3) δέντρα, αν υποθέσουμε ότι σε κάθε ένθεση η θέση εισαγωγής είναι γνωστή; Εξηγήστε πως το συγκεκριμένο αποτέλεσμα μπορεί να χρησιμοποιηθεί για να διατάξει πίνακες στους οποίους υπάρχει ήδη μερική προδιάταξη στα στοιχεία τους (ταξινόμηση προταξινομημένων πινάκων).
ΘΕΜΑ 5 (1,5 μονάδες)¶
(α) Σχεδιάστε το δέντρο σωρό, στο οποίο η ενδοδιατεταγμένη διαπέραση είναι: 10, 20, 8, 30, 4,7,2,40,6,15,3 Σχεδιάστε τον πίνακα που αντιστοιχεί στο συγκεκριμένο δέντρο σωρό και αναφέρετε αν πρόκειται για σωρό ελαχίστων ή μεγίστων.
(β) Σε ποιες περιπτώσεις χρησιμοποιούμε τη μέθοδο του Extendible Hashing; Ποια η πολυπλοκότητα προσβάσεων στο δίσκο; Μπορεί το Extendible Hashing να υλοποιηθεί με χρήση Tries;
ΘΕΜΑ 6 (1 μονάδες)¶
Ταξινομήστε τον πίνακα ακεραίων: {25, 21, 12, 13, 20, 7, 78, 32, 30, 40} με χρήση της ταξινόμησης σωρού (Heapsort)
ΘΕΜΑ 7 (1,5 μονάδες)¶
Έστω ότι θέλουμε να ενθέσουμε τα κλειδιά 12, 15, 27, 56, 34, 7, 45, 64 σε ένα πίνακα μήκους m=8 με τη σειρά που δίνονται χρησιμοποιώντας hashing με αλυσίδες και hashing με open addressing. Και στις δύο μεθόδους η βασική hash συνάρτηση είναι h1(k) = k mod m . Στο hashing με open addressing έστω η h2(k) = R - (key mod R) όπου το R=7 (μέθοδος με double hashing). Δώστε σχηματικά τους hashing πίνακες και αναλυτικά τις πράξεις.
ΘΕΜΑ 8 (1 μονάδες)¶
Για το εικονιζόμενο Customers File (με τη μορφή μητρώου δεδομένων), εφαρμόστε τη χρήση κατάλληλων bitmap ευρετηρίων που εσείς θα κατασκευάσετε προκειμένου να απαντηθούν τα εξής ερωτήματα: (1) Να βρεθούν όλες οι γυναίκες που μένουν στο Perryridge (2) Να βρεθεί το πλήθος των πελατών που μένουν στο Brooklyn. Υπενθυμίζεται ότι ένα απλό bitmap index σε ένα attribute έχει bitmap για κάθε τιμή του attribute, ότι το Bitmap έχει τόσα bits όσα είναι και τα records και ότι οι τιμές στο bitmap αντιστοιχούν στην παρουσία ή απουσία μίας τιμής στο αντίστοιχο attribute.
name gender address
| record number |
income _level |
|||
|---|---|---|---|---|
| 0 | John | m | Perryridge | L1 |
| 1 | Diana | f | Brooklyn | L2 |
| 2 | Mary | f | Jonestown | L1 |
| 3 | Peter | m | Brooklyn | L4 |
| 4 | Kathy | f | Perryridge | L3 |
Customers File
ΘΕΜΑ 9 (1 μονάδες)¶
Να κατασκευάσετε ένα IST (Interpolation Search Tree) για το παρακάτω σύνολο στοιχείων U. U={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}. Εξηγήστε τα βήματα που ακολουθούμε για την εύρεση του στοιχείου 15.
ΘΕΜΑ 10 (1 μονάδες)¶
Κατασκευάστε ένα complete binary tree για το σύνολο στοιχείων U={1,...,15}. Εξηγείστε τα βήματα που ακολουθούμε για την εύρεση του κοντινότερου κοινού πρόγονου των κόμβων 2 και 7. Δηλαδή LCA(2,7) ή LCA(0010, 0111).
ΘΕΜΑ 11 (2 μονάδες)¶
(α) Συμπληρώστε τους παρακάτω πίνακες:
| Αλγόριθμος Ταξινόμησης σε Πίνακα ακεραίων μεγέθους n |
Χρονική Πολυπλοκότητα μέσης περίπτωσης |
Χρονική Πολυπλοκότητα χειρότερης περίπτωσης |
|---|---|---|
| Quick-sort | ||
| Heap-sort | ||
| Merge-sort | ||
| Αλγόριθμος Εύρεσης κλειδιού σε ταξινομημένη είσοδο μεγέθους n |
Χρονική Πολυπλοκότητα μέσης περίπτωσης |
Χρονική Πολυπλοκότητα χειρότερης περίπτωσης |
| Linear-searching | ||
| Binary-searching | ||
| Interpolation searching | ||
| Binary Interpolation Searching (BIS) | ||
| Παραλλαγή Binary Interpolation Searching (BIS*) που βελτιώνει τη χειρότερη περίπτωση |
(β) Περιγράψτε το Binary Interpolation Search. Δώστε τις πολυπλοκότητες μέσης και χειρότερης περίπτωσης. Περιγράψτε αναλυτικά την παραλλαγή που πετυχαίνει χειρότερο χρόνο ψαξίματος Ο(logn) .
Καλή επιτυχία
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2025-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):508649524_1041606031423473_1597885228406098735_n.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)
Προσοχή
Θέματα 1, 2, 6, 9 και 10: δεν μεταφέρθηκε λύση. Τα Θέματα 1 και 2 έχουν μόνο σύντομη περιγραφή χωρίς αποτελέσματα· τα Θέματα 6, 9 και 10 δεν υπάρχουν στο παλιό αρχείο. Θέμα 3: η απάντηση είναι περιγραφική, χωρίς σχήμα ή μέτρηση χώρου για τις δύο αναπαραστάσεις. Θέμα 5(α): η λύση θεωρεί ρίζα τον 2 επειδή είναι το ελάχιστο στοιχείο· αυτό δεν προκύπτει από τη διάταξη inorder. Η αντιστοιχία του πίνακα με το δένδρο δεν επαληθεύτηκε. Θέμα 7: η λύση καλύπτει μόνο το hashing ανοικτής διεύθυνσης και όχι τον πίνακα με αλυσίδες. Με h1(k)=k mod 8 και βήμα 6 οι προσβάσιμες θέσεις του 64 είναι οι 0, 2, 4 και 6, όλες κατειλημμένες· η λύση δεν το δηλώνει ρητά και η θέση 1 μένει κενή και μη προσβάσιμη. Θέμα 11: οι τιμές πολυπλοκότητας για BIS και BIS* δεν επαληθεύτηκαν.
Λύσεις — Δομές Δεδομένων — Ιούνιος 2025¶
Μεταφέρθηκαν μόνο τα τμήματα λύσεων του παλιού αρχείου που απαντούν σε θέματα αυτής της συνεδρίας (χωρίς τις εκφωνήσεις).
ΘΕΜΑ 3 (1,5 μονάδες): Trie στο Αλφάβητο \(\Sigma=\{0, 2, 4, 6\}\)¶
- Βέλτιστη αποθήκευση: Radix Trie / Compressed Trie με σύμπτυξη κοινών προθεμάτων μήκους \(>1\).
ΘΕΜΑ 4 (1,5 μονάδες): Επιμερισμένο Κόστος \(O(1)\) σε \((2,3)\)-Δέντρα & Ταξινόμηση Προταξινομημένων Πινάκων¶
Απάντηση: 1. Επιμερισμένη Ανάλυση (Amortized Analysis): - Σε ένα φυλλοπροσανατολισμένο \((2,3)\)-δένδρο, όταν η θέση εισαγωγής είναι γνωστή (π.χ. μέσω δείκτη - finger), η εισαγωγή προκαλεί διάσπαση (split) ενός κόμβου μόνο αν αυτός περιέχει ήδη 3 παιδιά. - Μία σειρά διασπάσεων μπορεί να διαδοθεί προς τα πάνω. Ωστόσο, κάθε διάσπαση μετατρέπει έναν κόμβο με 3 παιδιά σε δύο κόμβους με 2 παιδιά. Με τη μέθοδο των δυναμικών (potential method), ορίζουμε δυναμικό \(\Phi = \sum (\text{αριθμός κόμβων με 3 παιδιά})\). Κάθε split μειώνει το δυναμικό, απορροφώντας το κόστος της διάσπασης. - Έτσι, το επιμερισμένο κόστος ένθεσης είναι \(O(1)\). 2. Ταξινόμηση Προταξινομημένων Πινάκων: - Όταν τα δεδομένα έχουν μερική προδιάταξη (λίγες αναστροφές / inversions \(Inv\)), εισάγουμε τα στοιχεία διαδοχικά χρησιμοποιώντας finger search στο σημείο της προηγούμενης εισαγωγής. - Ο συνολικός χρόνος ταξινόμησης μειώνεται από \(O(n \log n)\) σε \(O(n \log(Inv / n))\), το οποίο προσεγγίζει το γραμμικό \(O(n)\) όταν το πλήθος αναστροφών είναι μικρό.
ΘΕΜΑ 5 (1,5 μονάδες): Ανακατασκευή Σωρού & Extendible Hashing¶
(α) Ανακατασκευή Σωρού από In-order Διαπέραση: - Δίνεται In-order διαπέραση: \(10, 20, 8, 30, 4, 7, 2, 40, 6, 15, 3\). - Επειδή σε ένα δυαδικό δέντρο το ελάχιστο στοιχείο είναι το 2, και σε έναν σωρό ελαχίστων (Min-Heap) η ρίζα είναι το ελάχιστο όλων, το 2 είναι η ρίζα του δένδρου. - Το δέντρο είναι Min-Heap (Σωρός Ελαχίστων). - Πίνακας συνεχόμενης αναπαράστασης (\(A[1 \dots n]\)): - \(A[1] = 2\) - Αριστερό παιδί: \(A[2] = 4\), Δεξιό παιδί: \(A[3] = 3\) - Παιδιά του 4: \(A[4] = 8, A[5] = 7\) - Παιδιά του 3: \(A[6] = 6, A[7] = 30\) κ.ο.κ.
(β) Extendible Hashing: - Χρησιμοποιείται σε εξωτερική μνήμη (δευτερεύουσα μνήμη / δίσκοι) για μεγάλα αρχεία δεδομένων που μεταβάλλονται δυναμικά, αποφεύγοντας την ανάγκη πλήρους επανακατακερματισμού (rehash). - Πολυπλοκότητα: Απαιτεί το πολύ \(\le 2\) προσβάσεις στο δίσκο (1 πρόσβαση στον πίνακα καταλόγου directory και 1 πρόσβαση στον κάδο bucket δεδομένων). - Υλοποίηση με Tries: Ο πίνακας καταλόγου (directory) μπορεί να αναπαρασταθεί πλήρως από ένα Trie βάθους ίσου με το καθολικό βάθος (global depth) \(d\), όπου κάθε φύλλο δείχνει στον αντίστοιχο κάδο (bucket).
ΘΕΜΑ 7 (1,5 μονάδες): Double Hashing με \(R=7\)¶
Υπολογισμοί: 1. \(k=12: h_1(12) = 4 \implies\) Θέση 4 = 12. 2. \(k=15: h_1(15) = 7 \implies\) Θέση 7 = 15. 3. \(k=27: h_1(27) = 3 \implies\) Θέση 3 = 27. 4. \(k=56: h_1(56) = 0 \implies\) Θέση 0 = 56. 5. \(k=34: h_1(34) = 2 \implies\) Θέση 2 = 34. 6. \(k=7: h_1(7) = 7\) (Σύγκρουση με 15). - \(h_2(7) = 7 - (7 \bmod 7) = 7 - 0 = 7\). - \(i=1: (7 + 1 \cdot 7) \bmod 8 = 14 \bmod 8 = 6 \implies\) Θέση 6 = 7. 7. \(k=45: h_1(45) = 5 \implies\) Θέση 5 = 45. 8. \(k=64: h_1(64) = 0\) (Σύγκρουση με 56). - \(h_2(64) = 7 - (64 \bmod 7) = 7 - 1 = 6\). - \(i=1: (0 + 1 \cdot 6) \bmod 8 = 6\) (Σύγκρουση με 7). - \(i=2: (0 + 2 \cdot 6) \bmod 8 = 12 \bmod 8 = 4\) (Σύγκρουση με 12). - \(i=3: (0 + 3 \cdot 6) \bmod 8 = 18 \bmod 8 = 2\) (Σύγκρουση με 34). - \(i=4: (0 + 4 \cdot 6) \bmod 8 = 24 \bmod 8 = 0\) (Σύγκρουση). - \(i=5: (0 + 5 \cdot 6) \bmod 8 = 30 \bmod 8 = 6\) (Σύγκρουση). - (Σημείωση: Το βήμα 6 δεν είναι σχετικά πρώτο με το \(m=8\), \(\gcd(6, 8)=2\), οδηγώντας σε κύκλο άρτιων θέσεων \(0, 6, 4, 2\)). Στην πράξη επιλέγεται \(m\) πρώτος αριθμός.
ΘΕΜΑ 11 (2 μονάδες): Πίνακες Πολυπλοκοτήτων & Binary Interpolation Search (BIS)¶
(α) Συμπλήρωση Πινάκων Πολυπλοκότητας¶
Πίνακας 1: Αλγόριθμοι Ταξινόμησης σε Πίνακα μεγέθους \(n\) | Αλγόριθμος Ταξινόμησης | Χρονική Πολυπλοκότητα Μέσης Περίπτωσης | Χρονική Πολυπλοκότητα Χειρότερης Περίπτωσης | |:---|:---:|:---:| | Quick-sort | \(O(n \log n)\) | \(O(n^2)\) | | Heap-sort | \(O(n \log n)\) | \(O(n \log n)\) | | Merge-sort | \(O(n \log n)\) | \(O(n \log n)\) |
Πίνακας 2: Αλγόριθμοι Εύρεσης Κλειδιού σε Ταξινομημένη Είσοδο μεγέθους \(n\) | Αλγόριθμος Εύρεσης | Χρονική Πολυπλοκότητα Μέσης Περίπτωσης | Χρονική Πολυπλοκότητα Χειρότερης Περίπτωσης | |:---|:---:|:---:| | Linear-searching | \(O(n)\) | \(O(n)\) | | Binary-searching | \(O(\log n)\) | \(O(\log n)\) | | Interpolation searching | \(O(\log \log n)\) | \(O(n)\) | | Binary Interpolation Searching (BIS) | \(O(\log \log n)\) | \(O(\sqrt{n})\) | | Παραλλαγή BIS (BIS*) | \(O(\log \log n)\) | \(O(\log n)\) |
(β) Περιγραφή του Binary Interpolation Search (BIS & BIS*)¶
- Κλασικό BIS: Συνδυάζει την παρεμβολή (interpolation) με τη δυαδική αναζήτηση. Υπολογίζει εκτιμώμενη θέση με παρεμβολή και κατόπιν ελέγχει ένα υποδιάστημα μεγέθους \(\sqrt{n}\). Πετυχαίνει μέσο χρόνο \(O(\log \log n)\), αλλά στη χειρότερη περίπτωση φτάνει στο \(O(\sqrt{n})\).
- Παραλλαγή BIS* (Εγγύηση \(O(\log n)\) στη χειρότερη περίπτωση):
- Σε κάθε βήμα, εκτελείται παράλληλα (ή εναλλάξ) ένα βήμα παρεμβολής και ένα κλασικό βήμα δυαδικής αναζήτησης (διχοτόμηση ακριβώς στη μέση του υπολειπόμενου διαστήματος).
- Με τον τρόπο αυτό, το εύρος του διαστήματος αναζήτησης υποδιπλασιάζεται τουλάχιστον κάθε 2 βήματα, διασφαλίζοντας αυστηρά ότι ακόμα και στη χειρότερη δυνατή κατανομή κλειδιών, ο χρόνος αναζήτησης δεν θα υπερβεί ποτέ το \(O(\log n)\).