Δομές Δεδομένων — Ιούνιος 2023 — Παραλλαγή Α¶
Μεταγραφή από το αρχείο exam_paper_2023.pdf (δύο σελίδες).
exam_paper_2023.pdf¶
ΕΡΩΤΗΜΑ 1 (1 μονάδες)¶
Ο παρακάτω ψευδοκώδικας αντιστοιχεί στον αναδρομικό αλγόριθμο γρήγορης ταξινόμησης (quick sort) ενός πίνακα Α μεγέθους n=right-left+1. Αρχικά left=0 και right=n-1. Συμπληρώστε τα κομμάτια κώδικα που λείπουν:
void QuickSort(int list[ ], int left, int right)
{
int pivot, leftArrow, rightArrow;
leftArrow = left;
rightArrow = right;
pivot = list[(left + right) / 2];
do
{
while (list[rightArrow] > pivot)
..........................................;
while (..........................................)
++leftArrow;
if (leftArrow <= rightArrow)
{
Swap_Data(list[leftArrow], list[rightArrow]);
..........................................
..........................................
}
} while (rightArrow >= leftArrow);
if (left < rightArrow)
..........................................;
if (leftArrow < right)
..........................................;
}
ΘΕΜΑ 2 (1 μονάδες)¶
Ταξινομήστε την ακολουθία: CHATGPTQUANTUMCOMPUTERS με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection , δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=4 , και ότι συνολικά έχετε 8 ταινίες στη διάθεσή σας ( p=4 ). (Υπόδειξη: Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)
ΘΕΜΑ 3 (2 μονάδες)¶
α. Περιγράψτε το Binary Interpolation Search. Δώστε τις πολυπλοκότητες μέσης και χειρότερης περίπτωσης. Περιγράψτε αναλυτικά πώς θα γίνει ο χειρότερος χρόνος ψαξίματος ίσος με O(logn)
β. Σχεδιάστε το δέντρο σωρό, στο οποίο η μεταδιατεταγμένη διαπέραση να επισκέπτεται τους κόμβους με τη σειρά: 8, 10, 6, 5, 3, 4, 7, 2, 1. Γράψτε τον πίνακα της συνεχόμενης αναπαράστασης που αντιστοιχεί στο συγκεκριμένο δέντρο σωρό και αναφέρετε αν πρόκειται για σωρό ελαχίστων ή μεγίστων.
ΘΕΜΑ 4 (1,5 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το (2,3)-δένδρο που προκύπτει από την εισαγωγή σε ένα άδειο δένδρο με τη σειρά των εξής στοιχείων {17, 12, 11, 2, 30, 41, 20, 32, 19, 6}. Στην συνέχεια διαγράψτε βήμα-βήμα τα στοιχεία {11, 2}.
ΘΕΜΑ 5 (1,5 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το AVL δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {17, 12, 11, 2, 30, 41, 20, 32, 19, 6}. Στην συνέχεια διαγράψτε βήμα-βήμα τα στοιχεία {11, 2}.
ΘΕΜΑ 6 (1 μονάδες)¶
Ταξινομήστε τον πίνακα ακεραίων: {20, 2, 4, 3, 18, 8, 1, 23, 29, 21} με χρήση Ταξινόμησης Σωρού (Heap Sort). Αναφέρετε την πολυπλοκότητα χειρότερης περίπτωσης.
ΘΕΜΑ 7 (1 μονάδες)¶
Ταξινομήστε τον πίνακα ακεραίων: {7, 5, 2, 2, 4, 3, 3, 6, 4, 5} με χρήση ταξινόμησης με μέτρηση (Counting Sort). Αναφέρετε την πολυπλοκότητα χειρότερης περίπτωσης.
ΘΕΜΑ 8 (1 μονάδες)¶
Έστω ότι θέλουμε να ενθέσουμε τα κλειδιά 8,20,29,2,13,26,15,86 σε ένα πίνακα μήκους m=10 με τη σειρά που δίνονται χρησιμοποιώντας hashing με αλυσίδες και hashing με open addressing.
Και στις δύο μεθόδους η βασική hash συνάρτηση είναι h1(k) = k mod m . Στο hashing open addressing έστω η h2(k) = (p + 7 - k mod 7) mod m (μέθοδος με double hashing), όπου p το τελευταίο ψηφίο του αριθμού μητρώου σας . Δώστε σχηματικά τους hashing πίνακες και αναλυτικά τις πράξεις.
ΚΑΛΗ ΕΠΙΤΥΧΙΑ!¶
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-06-a.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):IMG_20230622_154707.jpg,IMG_20230622_153934.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-06-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Ερώτημα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Κενά με τη σειρά εμφάνισης:
1. --rightArrow
2. list[leftArrow] < pivot
3. και 4. μέσα στο if, μετά την ανταλλαγή: ++leftArrow; και --rightArrow;
5. QuickSort(list, left, rightArrow)
6. QuickSort(list, leftArrow, right)
Συμπλήρωση: --rightArrow, list[leftArrow] < pivot, ++leftArrow; --rightArrow;, QuickSort(list,left,rightArrow), QuickSort(list,leftArrow,right).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Ακολουθία CHATGPTQUANTUMCOMPUTERS (23 γράμματα), M=4. 8 ταινίες συνολικά = 4 εισόδου + 4 εξόδου. Αρχική μνήμη {C,H,A,T}.
Run 1: έξοδοι με σειρά A, C, G, H, P, Q, T, T, T, U, U. Τα στοιχεία που μπαίνουν και είναι μικρότερα από το τελευταίο έξοδο παγώνουν για το επόμενο run: A (όταν έχει βγει το Q), N (όταν έχει βγει το T), M και C. Όταν η μνήμη αδειάσει (έξοδος U), παγωμένα: {A, C, M, N}. Run 2: μνήμη {A,C,M,N}: έξοδοι A, C, M, M, N, O, P, R, S, T, U· μόνο το E παγώνει (μπαίνει όταν έχει βγει το O) και δημιουργεί το τρίτο run. Run 3: {E}.
Runs: R1 = ACGHPQTTTUU, R2 = ACMMNOPRSTU, R3 = E.
Κατανομή στις 4 ταινίες εισόδου: T1=R1, T2=R2, T3=R3, T4=∅. Συγχώνευση 3 runs σε μία ταινία εξόδου:
Αποτέλεσμα: AACCEGHMMNOPPQRSTTTTUUU (23 γράμματα, επαληθεύτηκε με πρόγραμμα· 1 φάση συγχώνευσης).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: χαμηλή
α) Binary Interpolation Search¶
Η απλή interpolation search εκτιμά τη θέση \(pos = lo + \frac{x-A[lo]}{A[hi]-A[lo]}(hi-lo)\) και συγκρίνει. Η binary interpolation search ακολουθεί την ίδια εκτίμηση αλλά, αντί να συνεχίσει με νέα εκτίμηση ανεξάρτητα από την ποιότητά της, ψάχνει γύρω από το \(pos\) με βήματα (της τάξης \(\sqrt{n}\), επαναλαμβανόμενα/διπλασιαζόμενα) μέχρι να «πιάσει» το κλειδί σε διάστημα μεγέθους \(\sqrt n\) και στη συνέχεια επαναλαμβάνει μέσα σε αυτό. Για ομοιόμορφα κατανεμημένα δεδομένα: μέση πολυπλοκότητα \(O(\log\log n)\). Χειρότερη περίπτωση \(O(\log n)\) (ενώ η απλή interpolation έχει \(O(n)\)). Πώς φτάνει το \(O(\log n)\): όταν η κατανομή είναι πολύ άνιση (π.χ. εκθετικά αυξανόμενες τιμές) κάθε εκτίμηση πέφτει μακριά, αλλά τα βήματα διπλασιασμού εντοπίζουν το διάστημα σε \(O(\log)\) κόστος και το διάστημα που μένει μειώνεται σε κάθε γύρο τουλάχιστον στο μισό (συμπεριφορά ίδια με binary search). Αυτή η περιγραφή είναι από μνήμη των τυπικών αποτελεσμάτων (Perl–Reingold) και δεν συγκρίθηκε με τις διαφάνειες του μαθήματος.
β) Σωρός από μεταδιάταξη¶
Εμπιστοσύνη: υψηλή
9 κόμβοι → πλήρες δέντρο, θέσεις 1..9 (παιδιά του i: 2i, 2i+1). Μεταδιάταξη θέσεων: 8, 9, 4, 5, 2, 6, 7, 3, 1. Με τιμές 8, 10, 6, 5, 3, 4, 7, 2, 1: θέση 8=8, 9=10, 4=6, 5=5, 2=3, 6=4, 7=7, 3=2, 1=1.
Δέντρο: 1(3(6(8,10),5),2(4,7)). Πίνακας: [1, 3, 2, 6, 5, 4, 7, 8, 10] — κάθε γονέας ≤ παιδιά: σωρός ελαχίστων.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Συμβάσεις όπως στις λοιπές λύσεις: κλειδιά στους κόμβους, διάσπαση σε 3 κλειδιά, στη διαγραφή κενού κόμβου δανεισμός από αριστερό/δεξιό αδελφό αλλιώς συγχώνευση (προτίμηση αριστερού αδελφού).
| Εισαγωγή | Δέντρο |
|---|---|
| 17 | [17] |
| 12 | [12 17] |
| 11 | [12 | [11] [17]] |
| 2 | [12 | [2 11] [17]] |
| 30 | [12 | [2 11] [17 30]] |
| 41 | [12 30 | [2 11] [17] [41]] |
| 20 | [12 30 | [2 11] [17 20] [41]] |
| 32 | [12 30 | [2 11] [17 20] [32 41]] |
| 19 | [19 | [12 | [2 11] [17]] [30 | [20] [32 41]]] (διάσπαση [17 19 20], ύστερα της ρίζας) |
| 6 | [19 | [6 12 | [2] [11] [17]] [30 | [20] [32 41]]] |
Διαγραφές: - 11: το φύλλο [11] μένει κενό, οι αδελφοί [2] και [17] έχουν από 1 κλειδί → συγχώνευση με τον αριστερό: [2 6], ο γονέας γίνεται [12] → [19 | [12 | [2 6] [17]] [30 | [20] [32 41]]]. - 2: το φύλλο [2 6] γίνεται [6], χωρίς πρόβλημα.
Τελικό δέντρο: [19 | [12 | [6] [17]] [30 | [20] [32 41]]]
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
| Εισαγωγή | Περιστροφή | Δέντρο |
|---|---|---|
| 17 | 17 | |
| 12 | 17(12,-) | |
| 11 | δεξιά περιστροφή στο 17 (LL) | 12(11,17) |
| 2 | 12(11(2,-),17) | |
| 30 | 12(11(2,-),17(-,30)) | |
| 41 | αριστερή στο 17 (RR) | 12(11(2,-),30(17,41)) |
| 20 | 12(11(2,-),30(17(-,20),41)) | |
| 32 | 12(11(2,-),30(17(-,20),41(32,-))) | |
| 19 | RL στο 17 | 12(11(2,-),30(19(17,20),41(32,-))) |
| 6 | LR στο 11 | 12(6(2,11),30(19(17,20),41(32,-))) |
Διαγραφές: - 11 (φύλλο, μετά το LR είναι δεξί παιδί του 6): 12(6(2,-),30(19(17,20),41(32,-))). - 2 (φύλλο): η ρίζα 12 έχει αριστερά ύψος 1 (μόνο το 6), δεξιά ύψος 3 → ανισορροπία. Το 30 έχει ισορροπία 0 → απλή αριστερή περιστροφή στη ρίζα.
Τελικό δέντρο: 30(12(6,19(17,20)),41(32,-))
Θέμα 6¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Heap sort (max-heap), πίνακας {20,2,4,3,18,8,1,23,29,21}.
Κατασκευή σωρού (από τον τελευταίο εσωτερικό κόμβο προς τη ρίζα): - μετά το 18/21: [20,2,4,3,21,8,1,23,29,18] - μετά το 3: [20,2,4,29,21,8,1,23,3,18] - μετά το 4: [20,2,8,29,21,4,1,23,3,18] - μετά το 2: [20,29,8,23,21,4,1,2,3,18] - μετά το 20: [29,23,8,20,21,4,1,2,3,18]
Εξαγωγές (ανταλλαγή ρίζας με το τελευταίο και επαναδόμηση): [23,21,8,20,18,4,1,2,3 | 29] → [21,20,8,3,18,4,1,2 | 23,29] → [20,18,8,3,2,4,1 | 21,23,29] → [18,3,8,1,2,4 | 20,…] → [8,3,4,1,2 | 18,…] → [4,3,2,1 | 8,…] → [3,1,2 | 4,…] → [2,1 | 3,…] → [1 | 2,…].
Αποτέλεσμα: 1 2 3 4 8 18 20 21 23 29. Χειρότερη περίπτωση: \(O(n\log n)\).
Θέμα 7¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Τιμές 2..7. Πίνακας μετρητών C[2..7]: C[2]=2, C[3]=2, C[4]=2, C[5]=2, C[6]=1, C[7]=1. Αθροιστικά: 2, 4, 6, 8, 9, 10. Τοποθέτηση από το τέλος για σταθερότητα (θέση = αθροιστικό − 1).
Αποτέλεσμα: 2 2 3 3 4 4 5 5 6 7. Πολυπλοκότητα \(O(n+k)\) με k το εύρος των τιμών (εδώ k=6)· δεν βασίζεται σε συγκρίσεις· χειρότερη περίπτωση επίσης \(O(n+k)\).
Θέμα 8¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
m=10, \(h_1(k)=k \bmod 10\), \(h_2(k)=(3+7-(k \bmod 7)) \bmod 10\). Κλειδιά: 8, 20, 29, 2, 13, 26, 15, 86.
h1: 8→8, 20→0, 29→9, 2→2, 13→3, 26→6, 15→5, 86→6.
Αλυσίδες: θέση 0: 20· 2: 2· 3: 13· 5: 15· 6: 26 → 86· 8: 8· 9: 29.
Ανοικτή διεύθυνση: μόνο το 86 συγκρούεται (θέση 6, κατειλημμένη από το 26). \(h_2(86)=(10-(86 \bmod 7))\bmod 10=(10-2)\bmod 10=8\) → επόμενη θέση \((6+8)\bmod 10=4\), ελεύθερη.
Πίνακας: 0:20, 2:2, 3:13, 4:86, 5:15, 6:26, 8:8, 9:29 (1, 7 κενές). Αν το p είναι διαφορετικό, αλλάζει μόνο το \(h_2(86)\) και άρα η θέση του 86 (η συνάρτηση h2 εφαρμόζεται μόνο στη σύγκρουση).