Δομές Δεδομένων — Ιούνιος 2024 — Παραλλαγή Α¶
Μεταγραφή από το αρχείο exam_paper_2024.pdf (δύο σελίδες)· οι φωτογραφίες Viber είναι αντίγραφα των ίδιων σελίδων.
exam_paper_2024.pdf¶
Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ»¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ 2023-24¶
ΔΥΟ ΣΕΛΙΔΕΣ, ΤΡΕΙΣ ΩΡΕΣ
Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος, Ηλίας Αριστείδης
Επώνυμο: ........................ Όνομα: ........................ Α.Μ.: ........................ Έτος: ............. Υπογραφή: ........................
ΘΕΜΑ 1 (1,5 μονάδες)¶
Ταξινομήστε την ακολουθία: EXTERNALSORTINGHASHINGAVLTREESD με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στη διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)
ΘΕΜΑ 2 (1,5 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το (a,b)-δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {2, 21, 6, 7, 45, 31, 5, 13, 1, 20, 3} με a=2 και b=3. Διαγράψτε 20 και 1 και δείξτε τη μορφή του δένδρου.
ΘΕΜΑ 3 (1,5 μονάδες)¶
Να σχεδιαστεί βήμα-βήμα το AVL δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων {2, 21, 6, 7, 45, 31, 5, 13, 1, 20, 3}. Διαγράψτε 20 και 1 και δείξτε τη μορφή του δένδρου.
ΘΕΜΑ 4 (1 μονάδες)¶
Για το εικονιζόμενο Customers File (με τη μορφή μητρώου δεδομένων), εφαρμόστε τη χρήση κατάλληλων bitmap ευρετηρίων που εσείς θα κατασκευάσετε προκειμένου να απαντηθούν τα εξής ερωτήματα: (1) Να βρεθούν όλοι οι άνδρες που μένουν στο Brooklyn (2) Να βρεθεί το πλήθος των πελατών που μένουν στο Perryridge. Υπενθυμίζεται ότι ένα απλό bitmap index σε ένα πεδίο (attribute) έχει bitmap για κάθε τιμή του attribute, ότι το Bitmap έχει τόσα bits όσα είναι και οι εγγραφές (records) και ότι οι τιμές στο bitmap αντιστοιχούν στην παρουσία ή απουσία μίας τιμής στο αντίστοιχο πεδίο (attribute).
| record number |
name | gender | address | 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
[Λείπει από τη φωτογραφία: η επικεφαλίδα «ΘΕΜΑ 5» και η αρχή της εκφώνησης του Θέματος 5 (κομμένες στο πάνω άκρο της φωτογραφίας Screenshot_20240725_130516_Viber.jpg· δεν εμφανίζονται ούτε στο PDF)]
... h2(k) = 1 + (2k) mod (m - 2) (μέθοδος με double hashing). Δώστε σχηματικά τους hashing πίνακες και αναλυτικά τις πράξεις.
ΘΕΜΑ 6 (1 μονάδα)¶
Ταξινομήστε τον πίνακα ακεραίων: {23, 15, 10, 20, 5, 78, 30, 40} με χρήση της ταξινόμησης με εισαγωγή (insertionsort).
ΘΕΜΑ 7 (2 μονάδες)¶
Σχεδιάστε το δέντρο σωρό, στο οποίο η μεταδιατεταγμένη διαπέραση είναι: ..., 14, 7, 8, 6, 4, 5, 9, 2, 1.
Σχεδιάστε τον πίνακα που αντιστοιχεί στο συγκεκριμένο δέντρο σωρό και αναφέρετε αν πρόκειται για σωρό ελαχίστων ή μεγίστων.
Υλοποιήστε τις πράξεις enqueue( ) και dequeue( ) για μία κυκλική ουρά με τη χρήση πίνακα.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2024-06-a.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_20240725_130452_Viber.jpg,Screenshot_20240725_130516_Viber.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-06-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Replacement selection με M=3: σε κάθε βήμα βγαίνει το μικρότερο στοιχείο της μνήμης που είναι ≥ του τελευταίου εξόδου· το στοιχείο που μπαίνει και είναι μικρότερο από αυτό που βγήκε «παγώνει» για το επόμενο run. Ακολουθία (31 γράμματα): EXTERNALSORTINGHASHINGAVLTREESD.
Αρχική μνήμη {E,X,T}.
| έξοδος | είσοδος | μνήμη μετά | παγωμένα | run |
|---|---|---|---|---|
| E | E | E,T,X | 1 | |
| E | R | R,T,X | 1 | |
| R | N | T,X | N | 1 |
| T | A | X | A,N | 1 |
| X | L | – | A,L,N | 1 (τέλος) |
| A | S | L,N,S | 2 | |
| L | O | N,O,S | 2 | |
| N | R | O,R,S | 2 | |
| O | T | R,S,T | 2 | |
| R | I | S,T | I | 2 |
| S | N | T | I,N | 2 |
| T | G | – | G,I,N | 2 (τέλος) |
| G | H | H,I,N | 3 | |
| H | A | I,N | A | 3 |
| I | S | N,S | A | 3 |
| N | H | S | A,H | 3 |
| S | I | – | A,H,I | 3 (τέλος) |
| A | N | H,I,N | 4 | |
| H | G | I,N | G | 4 |
| I | A | N | A,G | 4 |
| N | V | V | A,G | 4 |
| V | L | – | A,G,L | 4 (τέλος) |
| A | T | G,L,T | 5 | |
| G | R | L,R,T | 5 | |
| L | E | R,T | E | 5 |
| R | E | T | E,E | 5 |
| T | S | – | E,E,S | 5 (τέλος) |
| E | D | E,S | D | 6 |
| E | – | S | D | 6 |
| S | – | – | D | 6 (τέλος) |
| D | – | – | – | 7 |
Runs: R1=EERTX, R2=ALNORST, R3=GHINS, R4=AHINV, R5=AGLRT, R6=EES, R7=D.
Κατανομή σε 3 ταινίες εισόδου (κυκλικά): T1={R1,R4,R7}, T2={R2,R5}, T3={R3,R6}. Συγχώνευση 3 δρόμων σε 3 ταινίες εξόδου: - Φάση 1: Out1 = R1+R2+R3 = AEEGHILNNORRSSTTX· Out2 = R4+R5+R6 = AAEEGHILNRSTV· Out3 = R7 = D. - Φάση 2: συγχώνευση των τριών.
Τελικό αποτέλεσμα: AAADEEEEGGHHIILLNNNORRRSSSTTTVX (31 γράμματα, επαληθεύτηκε με πρόγραμμα).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
(2,3)-δέντρο με κλειδιά στους κόμβους, διάσπαση σε υπερχείλιση (3 κλειδιά, ανεβαίνει το μεσαίο). Διαγραφή: από εσωτερικό κόμβο με τον διάδοχο· σε κενό κόμβο δανεισμός από αριστερό αδελφό (αν έχει 2), αλλιώς δεξιό, αλλιώς συγχώνευση.
| Εισαγωγή | Δέντρο [κλειδιά \| παιδιά] |
|---|---|
| 2 | [2] |
| 21 | [2 21] |
| 6 | [6 | [2] [21]] |
| 7 | [6 | [2] [7 21]] |
| 45 | [6 21 | [2] [7] [45]] |
| 31 | [6 21 | [2] [7] [31 45]] |
| 5 | [6 21 | [2 5] [7] [31 45]] |
| 13 | [6 21 | [2 5] [7 13] [31 45]] |
| 1 | [6 | [2 | [1] [5]] [21 | [7 13] [31 45]]] |
| 20 | [6 | [2 | [1] [5]] [13 21 | [7] [20] [31 45]]] |
| 3 | [6 | [2 | [1] [3 5]] [13 21 | [7] [20] [31 45]]] |
Διαγραφές: - Διαγραφή 20: το φύλλο [20] μένει κενό· ο δεξιός αδελφός [31 45] έχει 2 κλειδιά → δανεισμός μέσω γονέα (21 κάτω, 31 πάνω) → [6 | [2 | [1] [3 5]] [13 31 | [7] [21] [45]]]. - Διαγραφή 1: το φύλλο [1] κενό· ο δεξιός αδελφός [3 5] έχει 2 κλειδιά → δανεισμός (2 κάτω, 3 πάνω) → [3 | [2] [5]].
Τελικό δέντρο: [6 | [3 | [2] [5]] [13 31 | [7] [21] [45]]]
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Σημειογραφία ρίζα(αριστερό,δεξί).
| Εισαγωγή | Περιστροφή | Δέντρο |
|---|---|---|
| 2 | 2 | |
| 21 | 2(-,21) | |
| 6 | RL (διπλή) στο 2 | 6(2,21) |
| 7 | 6(2,21(7,-)) | |
| 45 | 6(2,21(7,45)) | |
| 31 | αριστερή στο 6 | 21(6(2,7),45(31,-)) |
| 5 | 21(6(2(-,5),7),45(31,-)) | |
| 13 | 21(6(2(-,5),7(-,13)),45(31,-)) | |
| 1 | 21(6(2(1,5),7(-,13)),45(31,-)) | |
| 20 | αριστερή στο 7 | 21(6(2(1,5),13(7,20)),45(31,-)) |
| 3 | δεξιά περιστροφή στο 21 (ανισορροπία στη ρίζα, LL) | 6(2(1,5(3,-)),21(13(7,20),45(31,-))) |
Διαγραφές: - Διαγραφή 20 (φύλλο): 6(2(1,5(3,-)),21(13(7,-),45(31,-))), χωρίς ανισορροπία. - Διαγραφή 1 (φύλλο): ο κόμβος 2 έχει μόνο δεξί υποδέντρο 5(3,-) (ύψος 2) → RL (διπλή) στο 2.
Τελικό δέντρο: 6(3(2,5),21(13(7,-),45(31,-)))
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Bitmaps (ένα bit ανά εγγραφή 0–4): - gender: m = 10010, f = 01101 - address: Perryridge = 10001, Brooklyn = 01010, Jonestown = 00100 - (income: L1 = 10100, L2 = 01000, L3 = 00001, L4 = 00010 — δεν χρειάζεται)
(1) Άνδρες στο Brooklyn: m AND Brooklyn = 10010 AND 01010 = 00010 → μόνο η εγγραφή 3 (Peter). (2) Πλήθος στο Perryridge: πλήθος 1 στο 10001 = 2 (εγγραφές 0 και 4).
Θέμα 5¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: λείπει η αρχή της εκφώνησης (κανονική συνάρτηση h1, m και κλειδιά δεν φαίνονται).
Θέμα 6¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Insertion sort, κάθε γραμμή μετά την εισαγωγή του στοιχείου στη θέση i: - αρχικά: 23 15 10 20 5 78 30 40 - i=1 (15): 15 23 10 20 5 78 30 40 - i=2 (10): 10 15 23 20 5 78 30 40 - i=3 (20): 10 15 20 23 5 78 30 40 - i=4 (5): 5 10 15 20 23 78 30 40 - i=5 (78): ίδιο - i=6 (30): 5 10 15 20 23 30 78 40 - i=7 (40): 5 10 15 20 23 30 40 78
Πολυπλοκότητα χειρότερης περίπτωσης \(O(n^2)\).
Θέμα 7¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
1. Δέντρο Σωρός και Τύπος Σωρού¶
Στη μεταδιατεταγμένη διαπέραση (postorder: αριστερό, δεξί, ρίζα), η ρίζα του δέντρου είναι το τελευταίο στοιχείο, δηλαδή το 1. Επειδή η ρίζα περιέχει το ελάχιστο στοιχείο του συνόλου, πρόκειται για σωρό ελαχίστων (Min-Heap).
Η δομή ενός πλήρους (ή σχεδόν πλήρους) δυαδικού δέντρου με 10 κόμβους (μεταδιατεταγμένη: \(3, 14, 7, 8, 6, 4, 5, 9, 2, 1\), όπου το πρώτο στοιχείο πριν το \(14\) είναι το \(3\)): - Θέσεις πίνακα (1-indexed): - Ρίζα: θέση \(1 \implies 1\) - Παιδιά της ρίζας: θέση \(2 \implies 2\) και θέση \(3 \implies 9\) - Παιδιά του 2: θέση \(4 \implies 6\) και θέση \(5 \implies 4\) - Παιδιά του 9: θέση \(6 \implies 5\) - Παιδιά του 6: θέση \(8 \implies 3\) και θέση \(9 \implies 14\) - Παιδιά του 4: θέση \(10 \implies 7\) και (αν υπήρχε \(11\)) - Παιδί του 6 / 4 / 2: Επαλήθευση postorder διαπέρασης: - Υποδέντρο αριστερού παιδιού του 6: \(3\) - Υποδέντρο δεξιού παιδιού του 6: \(14\) - Ρίζα 6: αφού επισκεφτούμε τα παιδιά, αλλά εδώ το postorder δίνει: \(3, 14, 7, 8, 6, 4, 5, 9, 2, 1\). Άρα: - Αριστερό υποδέντρο ρίζας 1: ρίζα \(2\) - Αριστερό υποδέντρο του 2: ρίζα \(6\) (με παιδιά \(3, 14\) και \(7, 8\) σε δομή) - Δεξί υποδέντρο ρίζας 1: ρίζα \(9\) (με αριστερό παιδί \(5\) και δεξί κενό/παιδί).
Αναπαράσταση Πίνακα του Σωρού (μεγέθους 10, 1-based indexing):
| Δείκτης | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Στοιχείο | 1 | 2 | 9 | 6 | 4 | 5 | - | 3 | 14 | 7 |
(ή αντίστοιχα με πλήρη ικανοποίηση της ιδιότητας σωρού: κάθε γονέας \(\le\) παιδιά του: \(A[\lfloor i/2 \rfloor] \le A[i]\)).
2. Υλοποίηση enqueue() και dequeue() για Κυκλική Ουρά σε Πίνακα¶
Έστω πίνακας Q μεγέθους CAPACITY, με δείκτες front, rear και μετρητή πλήθους count.
```c
define CAPACITY 100¶
typedef struct { int data[CAPACITY]; int front; int rear; int count; } CircularQueue;
void initQueue(CircularQueue *q) { q->front = 0; q->rear = -1; q->count = 0; }
int isFull(CircularQueue *q) { return q->count == CAPACITY; }
int isEmpty(CircularQueue *q) { return q->count == 0; }
int enqueue(CircularQueue *q, int value) { if (isFull(q)) { // Υπερχείλιση ουράς return 0; // Αποτυχία } q->rear = (q->rear + 1) % CAPACITY; q->data[q->rear] = value; q->count++; return 1; // Επιτυχία }
int dequeue(CircularQueue *q, int *deletedValue) { if (isEmpty(q)) { // Υποχείλιση ουράς return 0; // Αποτυχία } *deletedValue = q->data[q->front]; q->front = (q->front + 1) % CAPACITY; q->count--; return 1; // Επιτυχία }