Δομές Δεδομένων — Ιούνιος 2022¶
Μεταγραφή των διαθέσιμων φωτογραφιών θεμάτων· οι φωτογραφίες με χειρόγραφες λύσεις φοιτητή δεν μεταγράφονται εδώ.
-_.png¶
Δίνονται οι ακόλουθες διαπεράσεις ενός δυαδικού δένδρου:
ΜΕΤΑΔΙΑΤΑΞΗ: EFCDBVWLMGA
ΣΥΜΜΕΤΡΙΚΗ ΔΙΑΤΑΞΗ: ECFBDAVLWGM
Ανασχηματίστε τη μορφή του συγκεκριμένου δυαδικού δένδρου.
unknown.png¶
ΘΕΜΑ 2 (3 μονάδες)
Να σχεδιαστεί βήμα-βήμα ένα Β δέντρο που προκύπτει από την εισαγωγή των εξής στοιχείων {9, 2, 7, 72, 5, 3, 12, 13, 1, 21, 33, 44, 58} με μέγιστο βαθμό διακλάδωσης ίσο με 4. Διαγράψτε 21 και 3 και δείξτε τη μορφή του δένδρου.
IMG_6437.png¶
ΘΕΜΑ 3 (3 μονάδες)
Ταξινομήστε την ακολουθία: WTTFRIED12ILHELGOLEIBNIZ με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στη διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης A B C D E F G H I K L M N O P Q R S T V X Y Z Ø1....9)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
image0.png¶
4. Ταξινομήστε την ακολουθία: GOTTFRIED 1 WILHELM 2 LEIBNIZ με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στις διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης A….Ζ Ø1….9)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_6478.png¶
7. Αποθηκεύστε σε δομή Trie χτισμένη στο αλφάβητο Σ={4,5,6,7} τα στοιχεία {4444, 4454, 4567, 5467, 5476, 6457, 6455, 7654}. Σχεδιάστε την πλήρη αποθήκευση και την αποθήκευση που καταλαμβάνει το μικρότερο χώρο.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (χειρόγραφες λύσεις ή διπλότυπες φωτογραφίες, δεν μεταφέρονται στη συνεδρία· λύσεις →
2022-06.solutions.md):20220623_235214.jpg,IMG_6438.png,IMG_6446.png,IMG_6447.png,IMG_6478.png.jpg.
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφίες λύσεων φοιτητών (χειρόγραφες· όχι επίσημη πηγή)
Προσοχή
Οι μεταγραφές των φωτογραφιών είναι προσχέδια (Gemini) και δεν ελέγχθηκαν με τα πρωτότυπα. Θέμα 3 (IMG_6437.png): η τελική σειρά «B D E E F F G H I I I I I L L O R T T W Z» έχει 21 στοιχεία αντί για 24. Λείπουν τα 1, 2, ένα E, ένα L και ένα N, ενώ εμφανίζονται επιπλέον ένα F και ένα I. Η σειρά δεν είναι συνεπής με την ακολουθία της εκφώνησης. Θέμα 4 (image0.png, ακολουθία GOTTFRIED…): η τελική ακολουθία της φωτογραφίας έχει ένα επιπλέον I και δεν περιέχει το N. Οι φωτογραφίες image0.png (ακολουθία GOTTFRIED…) και IMG_6437.png (ακολουθία WTTFRIED…) αφορούν διαφορετικές ακολουθίες· η αντιστοίχιση τους στη συνεδρία 2022-06 είναι εκτιμώμενη. Θέμα 7 (IMG_6478.png): η μεταγραφή περιέχει μόνο περιγραφές σχημάτων χωρίς κείμενο· η λύση δεν είναι ελέγξιμη από αυτή τη φωτογραφία.
Λύσεις — Δομές Δεδομένων — Ιούνιος 2022¶
Φωτογραφίες λύσεων φοιτητών, μεταγραφές όπως είναι (προσχέδια Gemini). Ταυτόσημες φωτογραφίες χωρίς επιπλέον κείμενο: IMG_6438.png (ίδια με IMG_6437.png) και IMG_6478.png.jpg (ίδια με IMG_6478.png).
20220623_235214.jpg¶
Μέτα: E F C D B V W L M G (A)
Συμ: E C F B D (A) V L W G M
Δέντρο αποσύνθεσης: - Ρίζα A - Αριστερό υποδένδρο: - Μέτα: E F C D (B) - Συμ: E C F (B) D - Ρίζα B, δεξί παιδί D, αριστερό: - Μέτα: E F (C) - Συμ: E (C) F - Ρίζα C, αριστερό παιδί E, δεξί παιδί F - Δεξί υποδένδρο: - Μέτα: V W L M (G) - Συμ: V L W (G) M - Ρίζα G, δεξί παιδί M, αριστερό: - Μέτα: V W (L) - Συμ: V (L) W - Ρίζα L, αριστερό παιδί V, δεξί παιδί W
Τελικό δυαδικό δένδρο:
A
/ \
B G
/ \ / \
C D L M
/ \ / \
E F V W
Επιβεβαίωση:
Μέτα: E F C D B V W L M G A
Συμ: E C F B D A V L W G M
Σημείωση: η φωτογραφία περιέχει χειρόγραφες σημειώσεις και επίλυση φοιτητή.
IMG_6437.png¶
ΘΕΜΑ 3 (3 μονάδες)
Ταξινομήστε την ακολουθία: WTTFRIED12ILHELGOLEIBNIZ με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στις διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης A B C D E F G H I K L M N O P Q R S T V X Y Z 0 1....9)
| heap | ρίζα heap | εισόdomain (εισόδομενο) | έξοδος |
|---|---|---|---|
| W T T | T | F | T |
| W T \(F^*\) | T | R | T T |
| W \(F^* R^*\) | W | I | T T W (ταινία 1) |
| \(I^* F^* R^*\) | \(F^*\) | E | \(F^*\) |
| \(E^* I^* R^*\) | \(E^*\) | D | \(F^* E^*\) |
| D \(I^* R^*\) | \(I^*\) | 1 | \(F^* E^* I^*\) |
| D 1 \(R^*\) | \(R^*\) | 2 | \(F^* E^* I^* R^*\) |
| D 1 \(2^*\) | \(1^*\) | I | \(F^* E^* I^* R^* 1^*\) |
| D I \(2^*\) | \(2^*\) | L | \(F^* E^* I^* R^* 1^* 2^*\) (ταινία 2) |
| D I L | D | H | D |
| H I L | H | E | D H |
| E I L | I | L | D H I |
| E L L | L | G | D H I L |
| E G L | L | O | D H I L |
| \(F^* G^* O\) | O | L | D H I L O (ταινία 3) |
| \(F^* G^* L^*\) | \(F^*\) | E | \(F^*\) |
| E \(G^* L^*\) | \(G^*\) | I | \(F^* G^*\) |
| E \(I^* L^*\) | \(I^*\) | B | \(F^* G^* I^*\) |
| E B \(L^*\) | \(L^*\) | N | \(F^* G^* I^* L^*\) |
| E B \(N^*\) | \(N^*\) | Z | \(F^* G^* I^* L^* N^*\) (ταινία 4) |
| E B Z | E B I Z (ταινία 5) |
Συγχώνευση (Runs): - TTW | DEFHIILORTTW12 - \(F^* E^* I^* R^* 1^* 2^*\) - DHILO
- \(F^* G^* I^* L^*\) | BEFGIILZ
- EBIZ
Τελική σειρά: B D E E F F G H I I I I I L L O R T T W Z
Σημείωση: η φωτογραφία περιέχει χειρόγραφη επίλυση φοιτητή σε ψηφιακό σημειωματάριο.
IMG_6446.png¶
WTTFRIED12ILHELGOLEIBNIZ
Χειρόγραφα βήματα Replacement Selection: - WTT -> T -> F -> T - \(W F^* T\) -> T -> R -> TT - \(W F^* R^*\) -> W -> I -> (TTW) => 1η ταινία - \(I^* F^* R^*\) -> \(F^*\) -> E -> \(F^*\) - \(I^* E^* R^*\) -> \(I^*\) -> D -> \(F^* I^*\) - D E \(R^*\) -> \(R^*\) -> 1 -> \(F^* I^* R^*\) => 2η ταινία - D E \(1^*\) -> \(1^*\) -> 2 -> \(F^* I^* R^* 1^*\) - D E \(2^*\) -> \(2^*\) -> I -> ( \(F^* I^* R^* 1^* 2^*\) ) - D E I -> D -> L -> D - L E I -> E -> H -> D E - L H I -> H -> E -> D E H => 3η ταινία - L \(E^* I\) -> I -> L -> D E H I - L \(E^* L\) -> L -> G -> D E H I L - G* \(E^* L\) -> L -> O -> D E H I L L - \(G^* E^* O\) -> O -> L -> (D E H I L L O) - \(G^* E^* L^*\) -> \(E^*\) -> E -> \(E^*\) - \(G^* E^* L^*\) -> \(E^*\) -> I -> \(E^* E^*\) => 4η ταινία - \(G^* I^* L^*\) -> \(G^*\) -> B -> \(E^* E^* G^*\) - B \(I^* L^*\) -> \(I^*\) -> N -> \(E^* E^* G^* I^*\) - B N \(L^*\) -> \(L^*\) -> I -> \(E^* E^* G^* I^* L^*\) - B N \(I^*\) -> \(N^*\) -> 2 -> (\(E^* E^* G^* I^* L^* N^*\)) - B \(2^* I\) -> - -> - -> (\(B 2^* I\))
Συνοπτικά runs: - Ταινία 1: TTW - Ταινία 2: F I R 1 2 - Ταινία 3: DEHILLO - Ταινία 4: EEGILN - Ταινία 5: BZI
Σημείωση: η φωτογραφία περιέχει χειρόγραφες σημειώσεις επίλυσης φοιτητή σε χαρτί.
IMG_6447.png¶
ΤΤWFIR12DHILLO | DFHHIILLORTTW12 EEGILNBZI | BEGGIILNZ
Σημείωση: η φωτογραφία περιέχει χειρόγραφο κείμενο: «καλό δω πως προκύπτει η τελική».
image0.png¶
4. Ταξινομήστε την ακολουθία: GOTTFRIED 1 WILHELM 2 LEIBNIZ
με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στις διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης Α....Ζ01....9)
| Heap | Ρίζα | Επόμ. | Output | |
|---|---|---|---|---|
| G O T | G | T | G | |
| O T T | O | F | G O | \(F < O \to F^*\) |
| \(F^*\) T T | T | R | G O T | \(R < T \to R^*\) |
| \(F^*\) \(R^*\) T | T | I | G O T T | \(I < T \to I^*\) / 1ο μπλοκ - 1η ταινία |
| \(F^*\) \(I^*\) \(R^*\) | \(F^*\) | E | \(F^*\) | \(E < F \to E^*\) |
| \(E^*\) \(I^*\) \(R^*\) | \(I^*\) | D | \(F^* I^*\) | \(D < I \to D^*\) |
| D E \(R^*\) | \(R^*\) | 1 | \(F^* I^* R^*\) | 2ο μπλοκ - 2η ταινία |
| D E 1 | D | W | D | |
| E W 1 | E | I | D E | |
| I W 1 | I | L | D E I | |
| L W 1 | L | H | D E I L | \(H < L \to H^*\) |
| \(H^*\) W 1 | W | E | D E I L W | \(E < W \to E^*\) |
| \(H^*\) \(E^*\) 1 | 1 | L | D E I L W 1 | \(L < 1 \to L^*\) / 3ο μπλοκ - 3η ταινία |
| \(E^*\) \(H^*\) \(L^*\) | \(E^*\) | M | \(E^*\) | |
| \(H^*\) \(L^*\) M | \(H^*\) | 2 | \(E^* H^*\) | |
| \(L^*\) M \(2^*\) | \(L^*\) | L | \(E^* H^* L^*\) | |
| \(L^*\) M \(2^*\) | \(L^*\) | E | \(E^* H^* L^* L^*\) | \(E < L \to E^*\) |
| E M \(2^*\) | \(M^*\) | I | \(E^* H^* L^* L^* M^*\) | \(I < M \to I^*\) |
| E I \(2^*\) | \(2^*\) | B | \(E^* H^* L^* L^* M^* 2^*\) | \(B < 2 \to B^*\) / 4ο μπλοκ - 1η ταινία |
| B E I | B | N | B | |
| E I N | E | I | B E | |
| I I N | I | Z | B E I | 5ο μπλοκ - 2η ταινία |
| I I Z | I I Z | 6ο μπλοκ - 3η ταινία |
Κατανομή στις ταινίες: - Ταινία 1: G O T T | E H L L M 2 - Ταινία 2: F I R | B E I - Ταινία 3: D E I L W 1 | I I Z
Συγχώνευση (Merge): - Ταινία 4: D E F G I I L O R T T W 1 - Ταινία 5: B E E H I I I L L M 2 Z - Ταινία 6: B D E E E F G H I I I I I L L L M O R T T W 2 1 Z
Σημείωση: η φωτογραφία περιέχει χειρόγραφη επίλυση φοιτητή σε ψηφιακό σημειωματάριο.
IMG_6478.png¶
7. Αποθηκεύστε σε δομή Trie χτισμένη στο αλφάβητο \(\Sigma=\{4,5,6,7\}\) τα στοιχεία \(\{4444, 4454, 4567, 5467, 5476, 6457, 6455, 7654\}\). Σχεδιάστε την πλήρη αποθήκευση και την αποθήκευση που καταλαμβάνει το μικρότερο χώρο.
[Σχήμα: Χειρόγραφο δένδρο Trie για «πλήρη αποθήκευση» με διακλαδώσεις για τα ψηφία 4, 5, 6, 7 και φύλλα τα κλειδιά 4444, 4454, 4567, 5467, 5476, 6457, 6455, 7654.]
[Σχήμα: Χειρόγραφο δένδρο συμπιεσμένου Trie / Patricia για «μικρότερο χώρο» με συνεπτυγμένους κόμβους και ακμές όπως 4, 5;2, 6;3, 7;4 κ.λπ.]
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις/σχεδιαγράμματα φοιτητή.