Δομές Δεδομένων Αλγόριθμοι και Πίνακες Θεωρία
Πληροφορική Γ Λυκείου ΑΕΠΠ
Σημαντική έννοια για την Πληροφορική Γ λυκείου ΑΕΠΠ είναι και η έννοια των «δεδομένων». Τα δεδομένα αποθηκεύονται στον υπολογιστή με τη βοήθεια των λεγόμενων «δομών δεδομένων». Στο κεφάλαιο αυτό γίνεται μία εισαγωγή στις σπουδαιότερες δομές δεδομένων και τις αντίστοιχες πράξεις που μπορούμε να κάνουμε με αυτές, όπως είναι η αναζήτηση, η εισαγωγή και η εξαγωγή στοιχείων, καθώς και η ταξινόμηση.
Παρουσιάζονται οι μονοδιάστατοι καθώς και οι δισδιάστατοι πίνακες, ο τρόπος με τον οποίο ορίζονται και οι κοινές διαδικασίες πάνω στους πίνακες, όπως η εύρεση μεγίστου και ελαχίστου, η αναζήτηση, η ταξινόμηση και η συγχώνευση πινάκων. Σε θεωρητικό επίπεδο αναφέρονται όλες οι θεωρίες που χρειάζεται να ξέρετε για να πετύχετε στο Α και στο Β θέμα των πανελλαδικών εξετάσεων. Ασκήσεις Σωστό Λάθος, Ερωτήσεις ανάπτυξης, Πολλαπλής επιλογής και Αντιστοίχισης από τα κεφάλαια 3 και 9 του μαθήματος ΑΕΠΠ Γ λυκείου.
3.1 Οι σκοπιές που μελετά η Πληροφορική τα προγράμματα ΑΕΠΠ
Η Πληροφορική μελετά τα δεδομένα από τις ακόλουθες σκοπιές:
| Σκοπιά | Τι μελετά |
|---|---|
| 1) Υλικού | Το υλικό επιτρέπει στα δεδομένα ενός προγράμματος να αποθηκεύονται στην κύρια μνήμη και στις περιφερειακές συσκευές του υπολογιστή με διάφορες αναπαραστάσεις. |
| 2) Γλωσσών προγραμματισμού | Οι γλώσσες προγραμματισμού υψηλού επιπέδου επιτρέπουν τη χρήση διάφορων τύπων μεταβλητών για να περιγράψουν ένα δεδομένο. |
| 3) Δομών δεδομένων | Είναι ένα σύνολο δεδομένων μαζί με ένα σύνολο επιτρεπτών λειτουργιών επί αυτών. |
| 4) Ανάλυσης δεδομένων | Τρόποι καταγραφής και αλληλοσυσχέτισης των δεδομένων μελετώνται έτσι ώστε να αναπαρασταθεί η γνώση για πραγματικά γεγονότα. |
3.2 Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
Δομή δεδομένων ΑΕΠΠ Γ λυκείου
Τα δεδομένα ενός προβλήματος αποθηκεύονται στον υπολογιστή, είτε στην κύρια μνήμη του είτε στη δευτερεύουσα μνήμη του. Η αποθήκευση αυτή δεν γίνεται κατά έναν τυχαίο τρόπο αλλά συστηματικά, δηλαδή χρησιμοποιώντας μία δομή. Η έννοια της δομής δεδομένων είναι σημαντική για την Πληροφορική και ορίζεται με τον ακόλουθο τυπικό ορισμό:
Οι βασικές λειτουργίες επί των δομών δεδομένων στο ΑΕΠΠ
Κάθε μορφή δομής δεδομένων αποτελείται από ένα σύνολο κόμβων. Οι βασικές λειτουργίες επί των δομών δεδομένων είναι οι ακόλουθες:
| Λειτουργία | Τι σημαίνει |
|---|---|
| 1) Προσπέλαση | Πρόσβαση σε έναν κόμβο με σκοπό να εξεταστεί ή να τροποποιηθεί το περιεχόμενό του. |
| 2) Εισαγωγή | Η προσθήκη νέων κόμβων σε μία υπάρχουσα δομή. |
| 3) Διαγραφή | Το αντίστροφο της εισαγωγής: ένας κόμβος αφαιρείται από μία δομή. |
| 4) Αναζήτηση | Προσπελαύνονται οι κόμβοι μιας δομής, προκειμένου να εντοπιστούν ένας ή περισσότεροι που έχουν μια δεδομένη ιδιότητα. |
| 5) Ταξινόμηση | Οι κόμβοι μιας δομής διατάσσονται κατά αύξουσα ή φθίνουσα σειρά. |
| 6) Αντιγραφή | Όλοι οι κόμβοι ή μερικοί από τους κόμβους μίας δομής αντιγράφονται σε μία άλλη δομή. |
| 7) Συγχώνευση | Δύο ή περισσότερες δομές συνενώνονται σε μία ενιαία δομή. |
| 8) Διαχωρισμός | Η αντίστροφη πράξη της συγχώνευσης. |
3.3 Πίνακες: Στατικές δομές δεδομένων ΑΕΠΠ Γ Λυκείου
Μία άλλη σημαντική διαφορά σε σχέση με τις δυναμικές δομές είναι ότι τα στοιχεία των στατικών δομών αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
| Χαρακτηριστικό | Στατικές δομές | Δυναμικές δομές |
|---|---|---|
| Μέγεθος μνήμης | Καθορίζεται κατά τη μετάφραση του προγράμματος. | Καθορίζεται κατά την εκτέλεση του προγράμματος. |
| Αλλαγή μεγέθους | Δεν μπορεί να αλλάξει. | Μπορεί να μεταβληθεί (δυναμική παραχώρηση μνήμης). |
| Θέσεις μνήμης | Συνεχόμενες. | Συνήθως δεν είναι συνεχόμενες. |
| Παραδείγματα | Πίνακες. | Λίστες, δέντρα, γράφοι. |
Τι είναι ο πίνακας στο ΑΕΠΠ θεωρία
Στην πράξη, οι στατικές δομές υλοποιούνται με πίνακες, που μας είναι γνωστοί από άλλα μαθήματα και υποστηρίζονται από κάθε γλώσσα προγραμματισμού. Μπορούμε να ορίσουμε τον πίνακα ως μια δομή που περιέχει στοιχεία του ίδιου τύπου. Η δήλωση των στοιχείων ενός πίνακα και η μέθοδος αναφοράς τους εξαρτάται από τη συγκεκριμένη γλώσσα υψηλού επιπέδου που χρησιμοποιείται. Όμως, γενικά η αναφορά στα στοιχεία ενός πίνακα γίνεται με τη χρήση του συμβολικού ονόματος του πίνακα, ακολουθούμενου από την τιμή ενός ή περισσότερων δεικτών σε παρένθεση ή αγκύλη.
Πολυδιάστατοι και δισδιάστατοι πίνακες στο ΑΕΠΠ Γ Λυκείου
Ένας πίνακας μπορεί να είναι μονοδιάστατος, αλλά στη γενικότερη περίπτωση μπορεί να είναι δισδιάστατος, τρισδιάστατος και γενικά ν-διάστατος πίνακας.
- Αν το μέγεθος των δύο διαστάσεων ενός δισδιάστατου πίνακα είναι ίσο, τότε ο πίνακας λέγεται τετραγωνικός και γενικά συμβολίζεται ως πίνακας n x n.
- Μπορούμε να θεωρήσουμε το δισδιάστατο πίνακα ως έναν μονοδιάστατο πίνακα, όπου κάθε θέση του περιέχει ένα νέο μονοδιάστατο πίνακα.
9.1-9.3 Μονοδιάστατοι πίνακες και Τυπικές επεξεργασίες στο ΑΕΠΠ Γ Λυκείου
9.1 Μονοδιάστατοι πίνακες Θεωρία στο ΑΕΠΠ
Οι πίνακες που χρησιμοποιούν ένα μόνο δείκτη για την αναφορά των στοιχείων τους ονομάζονται μονοδιάστατοι πίνακες.
- Το όνομα του πίνακα μπορεί να είναι οποιοδήποτε δεκτό όνομα της ΓΛΩΣΣΑΣ και ο δείκτης είναι μία ακέραια έκφραση, σταθερή ή μεταβλητή, που περικλείεται μέσα στα σύμβολα [ ... ].
- Κάθε πίνακας πρέπει υποχρεωτικά να περιέχει δεδομένα του ίδιου τύπου, δηλαδή ακέραια, πραγματικά, λογικά ή αλφαριθμητικά.
- Ο τύπος του πίνακα δηλώνεται μαζί με τις άλλες μεταβλητές του προγράμματος στο τμήμα δήλωσης μεταβλητών. Εκτός από τον τύπο πρέπει να δηλώνεται και ο αριθμός των στοιχείων που περιέχει, ή καλύτερα ο μεγαλύτερος αριθμός στοιχείων που μπορεί να έχει ο συγκεκριμένος πίνακας, ώστε να δεσμευτούν οι αντίστοιχες συνεχόμενες θέσεις μνήμης.
- Ο δείκτης είναι μία μεταβλητή που μπορεί να έχει οποιοδήποτε δεκτό όνομα. Είναι σύνηθες όμως στον προγραμματισμό ως δείκτες να χρησιμοποιούνται οι μεταβλητές i, j, k.
9.2 Πότε χρησιμοποιούμε πίνακες στις ασκήσεις ΑΕΠΠ Γ Λυκείου
Η χρήση πινάκων είναι ένας βολικός τρόπος για τη διαχείριση πολλών δεδομένων ίδιου τύπου, αλλά συχνά η χρήση τους είναι περιττή και επιζήμια στην ανάπτυξη του προγράμματος. Πέρα από τα πλεονεκτήματα που αναφέρθηκαν, υπάρχουν και δύο μειονεκτήματα από τη χρήση πινάκων:
- Οι πίνακες απαιτούν μνήμη. Κάθε πίνακας δεσμεύει από την αρχή του προγράμματος πολλές θέσεις μνήμης. Σε ένα μεγάλο και σύνθετο πρόγραμμα η άσκοπη χρήση μεγάλων πινάκων μπορεί να οδηγήσει ακόμη και σε αδυναμία εκτέλεσης του προγράμματος.
- Οι πίνακες περιορίζουν τις δυνατότητες του προγράμματος. Αυτό γιατί οι πίνακες είναι στατικές δομές και το μέγεθός τους πρέπει να δηλώνεται στην αρχή του προγράμματος, ενώ παραμένει υποχρεωτικά σταθερό κατά την εκτέλεση του προγράμματος.
9.4 Τυπικές επεξεργασίες πινάκων θεωρία ΑΕΠΠ
Τα προγράμματα τα οποία χρησιμοποιούν πίνακες πολύ συχνά απαιτούν συγκεκριμένες επεξεργασίες στα στοιχεία του πίνακα. Οι τυπικές αυτές επεξεργασίες είναι:
- Υπολογισμός αθροισμάτων στοιχείων του πίνακα.
- Εύρεση του μέγιστου ή του ελάχιστου στοιχείου.
- Ταξινόμηση των στοιχείων του πίνακα.
- Αναζήτηση ενός στοιχείου του πίνακα.
- Συγχώνευση δύο πινάκων.
Θεωρία Στοίβα και ουρά: LIFO - FIFO ΑΕΠΠ Γ λυκείου
Θεωρία Στοίβα στο ΑΕΠΠ
Τα δεδομένα που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία. Αυτή η μέθοδος επεξεργασίας ονομάζεται Τελευταίο Μέσα Πρώτο Έξω (LIFO), Last-In-First-Out.
Δύο είναι οι κύριες λειτουργίες σε μία στοίβα:
- η ώθηση στοιχείου στην κορυφή της στοίβας, και
- η απώθηση στοιχείου από τη στοίβα.
Η διαδικασία της ώθησης πρέπει οπωσδήποτε να ελέγχει αν η στοίβα είναι γεμάτη, οπότε λέγεται ότι συμβαίνει υπερχείλιση της στοίβας. Αντίστοιχα, η διαδικασία απώθησης ελέγχει αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα, δηλαδή ελέγχει αν γίνεται υποχείλιση της στοίβας.
Μια στοίβα μπορεί να υλοποιηθεί πολύ εύκολα με τη βοήθεια ενός μονοδιάστατου πίνακα. Μια βοηθητική μεταβλητή (top) χρησιμοποιείται για να δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας.
- Ώθηση: αυξάνεται η μεταβλητή top κατά ένα και στη θέση αυτή εισέρχεται το στοιχείο.
- Απώθηση: εξέρχεται πρώτα το στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η top μειώνεται κατά ένα, για να δείχνει τη νέα κορυφή.
Θεωρία Ουρά στο ΑΕΠΠ
Σε μία ουρά αναμονής συμβαίνει να εξυπηρετείται εκείνος που στάθηκε στην ουρά πρώτος από όλους τους άλλους. Η μέθοδος αυτή επεξεργασίας ονομάζεται Πρώτο Μέσα Πρώτο Έξω (FIFO), First-In-First-Out. Δύο είναι οι κύριες λειτουργίες που εκτελούνται σε μία ουρά:
- η εισαγωγή στοιχείου στο πίσω άκρο της ουράς, και
- η εξαγωγή στοιχείου από το εμπρός άκρο της ουράς.
Σε αντίθεση με τη δομή της στοίβας, στην ουρά απαιτούνται δύο δείκτες: ο εμπρός (front) και ο πίσω (rear). Μας δίνουν τη θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί και τη θέση του στοιχείου που μόλις εισήλθε.
Μια ουρά μπορεί να υλοποιηθεί με τη βοήθεια ενός μονοδιάστατου πίνακα. Για την εισαγωγή ενός νέου στοιχείου αυξάνεται ο δείκτης rear κατά ένα και στη θέση αυτή αποθηκεύεται το στοιχείο. Για την εξαγωγή, εξέρχεται το στοιχείο που δείχνει ο δείκτης front, ο οποίος στη συνέχεια αυξάνεται κατά ένα, για να δείχνει το επόμενο στοιχείο που πρόκειται να εξαχθεί. Σε κάθε περίπτωση, πρέπει να ελέγχεται πριν από οποιαδήποτε ενέργεια αν υπάρχει ελεύθερος χώρος στον πίνακα για την εισαγωγή και αν υπάρχει ένα τουλάχιστον στοιχείο για την εξαγωγή.
| Στοίβα | Ουρά | |
|---|---|---|
| Μέθοδος | LIFO | FIFO |
| Λειτουργίες | Ώθηση, απώθηση | Εισαγωγή, εξαγωγή |
| Δείκτες | Ένας (top) | Δύο (front, rear) |
| Έλεγχοι | Υπερχείλιση, υποχείλιση | Ελεύθερος χώρος για εισαγωγή, ένα στοιχείο τουλάχιστον για εξαγωγή |
3.6 Σειριακή και δυαδική αναζήτηση στη ΓΛΩΣΣΑ ΑΕΠΠ Γ Λυκείου
Σειριακή αναζήτηση στο ΑΕΠΠ
Η πιο απλή μορφή αναζήτησης στοιχείου σε πίνακα είναι η σειριακή ή γραμμική μέθοδος. Στον επόμενο αλγόριθμο αναζητείται η τιμή key στο μη ταξινομημένο πίνακα table. Μετά την εκτέλεση του αλγορίθμου η μεταβλητή position επιστρέφει την τιμή 0, αν η αναζήτηση είναι ανεπιτυχής. Αν η αναζήτηση είναι επιτυχής, τότε επιστρέφει τη θέση του στοιχείου στον πίνακα, δηλαδή έναν αριθμό από 1 ως n.
Αλγόριθμος ΑΝΑΖΗΤΗΣΗ
Δεδομένα // n, table, key //
done ← ψευδής
position ← 0
i ← 1
Όσο (done = ψευδής) και (i <= n) επανάλαβε
Αν table[i] = key τότε
done ← αληθής
position ← i
αλλιώς
i ← i + 1
Τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα // done, position //
Τέλος ΑΝΑΖΗΤΗΣΗ
Δυαδική αναζήτηση στο ΑΕΠΠ
Η δυαδική αναζήτηση είναι αποτελεσματικότερη από τη σειριακή, διότι χρειάζεται πολύ λιγότερο χρόνο εκτέλεσης, κάτω από τον μισό χρόνο από ό,τι η σειριακή αναζήτηση. Απαραίτητη προϋπόθεση είναι ότι ο πίνακας πρέπει να είναι ταξινομημένος. Θεωρούμε ότι τα στοιχεία του πίνακα Α είναι ταξινομημένα κατά αύξουσα σειρά.
! Ο πίνακας Α έχει 100 στοιχεία, ταξινομημένα κατά αύξουσα σειρά
ΓΡΑΨΕ 'Δώσε αριθμό για αναζήτηση στον πίνακα Α.'
ΔΙΑΒΑΣΕ KEY
αρχ <- 1
τέλ <- 100
βρεθηκε <- ΨΕΥΔΗΣ
ΟΣΟ αρχ <= τέλ ΚΑΙ βρεθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
μέση <- (αρχ + τέλ) DIV 2
ΑΝ KEY < Α[μέση] ΤΟΤΕ
τέλ <- μέση - 1
ΑΛΛΙΩΣ_ΑΝ KEY > Α[μέση] ΤΟΤΕ
αρχ <- μέση + 1
ΑΛΛΙΩΣ
βρεθηκε <- ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ βρεθηκε = ΑΛΗΘΗΣ ΤΟΤΕ
ΓΡΑΨΕ 'Βρέθηκε στη θέση ', μέση
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Δε βρέθηκε'
ΤΕΛΟΣ_ΑΝ
| Σειριακή | Δυαδική | |
|---|---|---|
| Πίνακας | Δεν χρειάζεται να είναι ταξινομημένος. | Πρέπει υποχρεωτικά να είναι ταξινομημένος. |
| Χρόνος εκτέλεσης | Μεγαλύτερος. | Πολύ λιγότερος, κάτω από τον μισό χρόνο της σειριακής. |
3.7 Ταξινόμηση ευθείας ανταλλαγής (φυσαλίδα) στο ΑΕΠΠ Γ Λυκείου
Η τακτοποίηση των κόμβων μίας δομής με μία ιδιαίτερη σειρά είναι μία πολύ σημαντική λειτουργία που ονομάζεται ταξινόμηση ή διάταξη. Συνήθως η σειρά αυτή είναι η αύξουσα τάξη της τιμής των μεγεθών προς ταξινόμηση. Αξίζει να σημειωθεί ότι η προηγούμενη διάταξη μπορεί να τροποποιηθεί, ώστε να καλύπτει και την περίπτωση που η ταξινόμηση γίνεται με φθίνουσα τάξη μεγέθους.
Ταξινόμηση ευθείας ανταλλαγής θεωρία ΑΕΠΠ
Η μέθοδος της ταξινόμησης ευθείας ανταλλαγής βασίζεται στην αρχή της σύγκρισης και ανταλλαγής ζευγών γειτονικών στοιχείων, μέχρις ότου διαταχθούν όλα τα στοιχεία. Σύμφωνα με τη μέθοδο αυτή, κάθε φορά γίνονται διαδοχικές προσπελάσεις στον πίνακα και μετακινείται το μικρότερο κλειδί της ακολουθίας προς το αριστερό άκρο του πίνακα.
Η ταξινόμηση ευθείας ανταλλαγής υλοποιείται με τον επόμενο αλγόριθμο:
Αλγόριθμος Φυσαλίδα
Δεδομένα // table, n //
Για i από 2 μέχρι n
Για j από n μέχρι i με_βήμα -1
Αν table[j-1] > table[j] τότε
αντιμετάθεσε table[j-1], table[j]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος Φυσαλίδα
Σωστό / Λάθος και ασκήσεις θεωρίας στις Δομές Δεδομένων και στους Πίνακες ΑΕΠΠ Γ Λυκείου
Ερωτήσεις Σωστό / Λάθος για τη Θεωρία ΑΕΠΠ Κεφάλαια 3 & 9
Απαντήστε πρώτα μόνοι σας και μετά ελέγξτε τις απαντήσεις στον πίνακα.
- Σε μία στατική δομή, το ακριβές μέγεθος της απαιτούμενης κύριας μνήμης καθορίζεται κατά την εκτέλεση του προγράμματος.
- Ο πίνακας είναι μία δομή που μπορεί να περιέχει στοιχεία διαφορετικού τύπου.
- Η εισαγωγή και η διαγραφή ως λειτουργίες μπορούν να εφαρμοστούν μόνο σε δυναμικές δομές δεδομένων.
- Σε έναν μονοδιάστατο πίνακα μπορούμε να καταχωρίσουμε τα ονόματα και τους βαθμούς 23 μαθητών.
- Ο δισδιάστατος πίνακας είναι μία δυναμική δομή δεδομένων, γιατί χρησιμοποιεί δύο δείκτες.
- Στη στοίβα το στοιχείο που μπαίνει πρώτο βγαίνει πρώτο.
- Σε έναν πίνακα δύο διαστάσεων μπορούν να αποθηκευτούν τα ονόματα και οι ηλικίες 100 ανθρώπων.
- Για να προσπελάσουμε όλα τα στοιχεία ενός δισδιάστατου πίνακα χρησιμοποιούμε συνήθως εμφωλευμένες επαναληπτικές δομές.
- Η εισαγωγή και η εξαγωγή είναι οι δύο βασικές λειτουργίες της ουράς.
- Σε έναν πίνακα δύο διαστάσεων Α[10, 3] το πλήθος των στοιχείων του είναι το πολύ 30.
| Α/Α | Απάντηση | Γιατί |
|---|---|---|
| 1 | Λάθος | Το μέγεθος της μνήμης των στατικών δομών καθορίζεται κατά τη μετάφραση του προγράμματος, όχι κατά την εκτέλεση. |
| 2 | Λάθος | Ο πίνακας περιέχει στοιχεία του ίδιου τύπου. |
| 3 | Σωστό | Το μέγεθος μιας στατικής δομής δεν αλλάζει, άρα δεν προστίθενται ούτε αφαιρούνται κόμβοι. |
| 4 | Λάθος | Τα ονόματα είναι αλφαριθμητικά και οι βαθμοί αριθμοί, δηλαδή διαφορετικοί τύποι. |
| 5 | Λάθος | Ο δισδιάστατος πίνακας είναι στατική δομή, όπως κάθε πίνακας. |
| 6 | Λάθος | Η στοίβα λειτουργεί με τη μέθοδο LIFO: το τελευταίο στοιχείο που μπαίνει βγαίνει πρώτο. |
| 7 | Λάθος | Ονόματα (αλφαριθμητικά) και ηλικίες (αριθμοί) είναι διαφορετικοί τύποι, και ο πίνακας περιέχει στοιχεία ίδιου τύπου. |
| 8 | Σωστό | Για τα στοιχεία ενός δισδιάστατου πίνακα χρειάζονται δύο δείκτες, γι' αυτό χρησιμοποιούμε εμφωλευμένους βρόχους. |
| 9 | Σωστό | Οι δύο κύριες λειτουργίες της ουράς είναι η εισαγωγή στο πίσω άκρο και η εξαγωγή από το εμπρός άκρο. |
| 10 | Σωστό | Ο πίνακας Α[10, 3] έχει 10 × 3 = 30 θέσεις, άρα το πολύ 30 στοιχεία. |
Ερωτήσεις ανάπτυξης στα κεφάλαια 3 & 9 του ΑΕΠΠ
Οι λύσεις είναι γραμμένες όπως θα ζητηθούν στις πανελλήνιες εξετάσεις.
1. Από ποιες σκοπιές μελετά η Πληροφορική τα δεδομένα;
2. Γλωσσών προγραμματισμού: οι γλώσσες προγραμματισμού υψηλού επιπέδου επιτρέπουν τη χρήση διάφορων τύπων μεταβλητών για να περιγράψουν ένα δεδομένο.
3. Δομών δεδομένων: δομή δεδομένων είναι ένα σύνολο δεδομένων μαζί με ένα σύνολο επιτρεπτών λειτουργιών επί αυτών.
4. Ανάλυσης δεδομένων: τρόποι καταγραφής και αλληλοσυσχέτισης των δεδομένων μελετώνται έτσι ώστε να αναπαρασταθεί η γνώση για πραγματικά γεγονότα.
2. Ποιες είναι οι βασικές λειτουργίες επί των δομών δεδομένων;
II. Εισαγωγή: προσθήκη νέων κόμβων σε μία υπάρχουσα δομή.
III. Διαγραφή: το αντίθετο της εισαγωγής, δηλαδή η αφαίρεση ενός ή περισσότερων κόμβων από μία δομή.
IV. Αναζήτηση: εκτελείται προσπέλαση των κόμβων ώστε να εντοπιστούν ένας ή περισσότεροι κόμβοι που έχουν μία συγκεκριμένη ιδιότητα.
V. Ταξινόμηση: οι κόμβοι μίας δομής διατάσσονται σε αύξουσα ή φθίνουσα σειρά.
VI. Αντιγραφή: όλοι ή κάποιοι κόμβοι από μία δομή αντιγράφονται σε μία άλλη δομή.
VII. Συγχώνευση: δύο ή περισσότερες δομές συνενώνονται σε μία ενιαία δομή.
VIII. Διαχωρισμός: η αντίστροφη πράξη της συγχώνευσης.
3. Τι ονομάζουμε στατική δομή δεδομένων και τι δυναμική δομή δεδομένων;
α) το ακριβές μέγεθος της απαιτούμενης μνήμης καθορίζεται κατά τη στιγμή της μετάφρασης του προγράμματος,
β) δεν μπορεί να αλλάξει το μέγεθός τους,
γ) αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
Χαρακτηριστική στατική δομή δεδομένων είναι οι πίνακες.
II. Δυναμικές δομές δεδομένων:
α) το ακριβές μέγεθος της μνήμης καθορίζεται κατά την εκτέλεση του προγράμματος,
β) μπορούμε να μεταβάλλουμε το μέγεθός τους (δυναμική παραχώρηση μνήμης),
γ) συνήθως δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
Χαρακτηριστικές δυναμικές δομές δεδομένων είναι οι λίστες, τα δέντρα και οι γράφοι.
Ερωτήσεις πολλαπλής επιλογής ΑΕΠΠ στη θεωρία Κεφάλαια 3 & 9
Σε κάθε ερώτηση να επιλέξετε τη σωστή απάντηση. Υπάρχει μόνο μία σωστή επιλογή.
1. Ποια από τις παρακάτω δομές δεδομένων είναι στατική;
- Λίστα
- Πίνακας
- Δέντρο
- Γράφος
2. Ποια μέθοδο επεξεργασίας ακολουθεί η στοίβα;
- FIFO
- LIFO
- Τυχαία επεξεργασία
- Ταξινομημένη επεξεργασία
3. Πότε συμβαίνει υπερχείλιση της στοίβας;
- Όταν γίνεται ώθηση σε γεμάτη στοίβα.
- Όταν γίνεται απώθηση από άδεια στοίβα.
- Όταν ο πίνακας της στοίβας είναι ταξινομημένος.
- Όταν η μεταβλητή top μειώνεται κατά ένα.
4. Ποια προϋπόθεση πρέπει να ισχύει για να εφαρμοστεί η δυαδική αναζήτηση σε έναν πίνακα;
- Ο πίνακας να είναι ταξινομημένος.
- Ο πίνακας να έχει ακριβώς 100 στοιχεία.
- Ο πίνακας να είναι δισδιάστατος.
- Ο πίνακας να μην έχει ίδια στοιχεία.
5. Πόσα στοιχεία έχει ο πίνακας Α[4, 5];
- 9
- 10
- 20
- 45
| Ερώτηση | Σωστή απάντηση | Γιατί |
|---|---|---|
| 1 | β | Χαρακτηριστική στατική δομή είναι ο πίνακας. Οι λίστες, τα δέντρα και οι γράφοι είναι δυναμικές δομές. |
| 2 | β | Η στοίβα λειτουργεί με τη μέθοδο LIFO (Τελευταίο Μέσα Πρώτο Έξω). Η FIFO ανήκει στην ουρά. |
| 3 | α | Η διαδικασία της ώθησης ελέγχει αν η στοίβα είναι γεμάτη. Αν είναι, συμβαίνει υπερχείλιση. Η απώθηση από άδεια στοίβα λέγεται υποχείλιση. |
| 4 | α | Απαραίτητη προϋπόθεση της δυαδικής αναζήτησης είναι ο πίνακας να είναι ταξινομημένος. |
| 5 | γ | Το πλήθος των στοιχείων ισούται με το γινόμενο των διαστάσεων: 4 × 5 = 20. |
Αντιστοίχιση ΑΕΠΠ στα κεφάλαια 3 & 9
Να αντιστοιχίσετε κάθε έννοια της στήλης Α με την περιγραφή της στη στήλη Β. Στη στήλη Β υπάρχουν δύο περιγραφές που περισσεύουν.
| Στήλη Α | Στήλη Β |
|---|---|
| 1. Προσπέλαση | α. Πρόσβαση σε έναν κόμβο με σκοπό να εξεταστεί ή να τροποποιηθεί το περιεχόμενό του. |
| 2. Συγχώνευση | β. Δύο ή περισσότερες δομές συνενώνονται σε μία ενιαία δομή. |
| 3. Ώθηση | γ. Εισαγωγή στοιχείου στην κορυφή της στοίβας. |
| 4. Δείκτης front | δ. Δείχνει τη θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί από την ουρά. |
| 5. Ταξινόμηση φυσαλίδας | ε. Σύγκριση και ανταλλαγή ζευγών γειτονικών στοιχείων, μέχρις ότου διαταχθούν όλα τα στοιχεία. |
| – | στ. Αφαίρεση ενός κόμβου από μία δομή. |
| – | ζ. Εξαγωγή στοιχείου από τη στοίβα. |
| Στήλη Α | Αντιστοιχία | Γιατί |
|---|---|---|
| 1. Προσπέλαση | α | Η προσπέλαση είναι η πρόσβαση σε έναν κόμβο, για να εξεταστεί ή να τροποποιηθεί το περιεχόμενό του. |
| 2. Συγχώνευση | β | Δύο ή περισσότερες δομές συνενώνονται σε μία. Η αντίστροφη πράξη είναι ο διαχωρισμός. |
| 3. Ώθηση | γ | Ώθηση είναι η εισαγωγή στοιχείου στην κορυφή της στοίβας. Η εξαγωγή από τη στοίβα λέγεται απώθηση (ζ). |
| 4. Δείκτης front | δ | Ο εμπρός δείκτης δείχνει το στοιχείο που σε πρώτη ευκαιρία θα εξαχθεί από την ουρά. |
| 5. Ταξινόμηση φυσαλίδας | ε | Στηρίζεται στη σύγκριση και ανταλλαγή ζευγών γειτονικών στοιχείων. |
Αν θέλετε περισσότερες ερωτήσεις τύπου ανάπτυξης ή γενικότερα ερωτήσεις θεωρίας στην ύλη της Πληροφορικής Γ Λυκείου στο κεφάλαιο Δομές Δεδομένων και Αλγόριθμοι Πίνακες, δείτε τα τεστ, τα διαγωνίσματα και τις θεωρίες που έχουμε δημιουργήσει, για να καταφέρετε τον καλύτερο δυνατό βαθμό στις πανελλήνιες εξετάσεις.
Συχνές ερωτήσεις για τις Δομές Δεδομένων και τους Πίνακες ΑΕΠΠ Γ λυκείου
Τι είναι δομή δεδομένων;
Δομή δεδομένων είναι ένα σύνολο αποθηκευμένων δεδομένων που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών. Η αποθήκευση των δεδομένων στον υπολογιστή γίνεται συστηματικά, με τη χρήση μιας δομής.
Ποιες είναι οι βασικές λειτουργίες επί των δομών δεδομένων;
Οι οκτώ βασικές λειτουργίες είναι η προσπέλαση, η εισαγωγή, η διαγραφή, η αναζήτηση, η ταξινόμηση, η αντιγραφή, η συγχώνευση και ο διαχωρισμός.
Ποια είναι η διαφορά ανάμεσα σε στατική και δυναμική δομή δεδομένων;
Στις στατικές δομές το μέγεθος της μνήμης καθορίζεται κατά τη μετάφραση του προγράμματος, δεν μπορεί να αλλάξει και τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης. Στις δυναμικές δομές το μέγεθος καθορίζεται κατά την εκτέλεση, μπορεί να μεταβληθεί και συνήθως οι θέσεις μνήμης δεν είναι συνεχόμενες. Στατική δομή είναι ο πίνακας. Δυναμικές είναι οι λίστες, τα δέντρα και οι γράφοι.
Τι είναι ο πίνακας;
Πίνακας είναι ένα σύνολο αντικειμένων ίδιου τύπου, τα οποία αναφέρονται με ένα κοινό όνομα. Κάθε αντικείμενο λέγεται στοιχείο του πίνακα και η αναφορά σε αυτό γίνεται με το όνομα του πίνακα ακολουθούμενο από έναν δείκτη.
Ποια είναι η διαφορά ανάμεσα σε μονοδιάστατο και δισδιάστατο πίνακα;
Ο μονοδιάστατος πίνακας χρησιμοποιεί έναν δείκτη για την αναφορά των στοιχείων του, ενώ ο δισδιάστατος χρησιμοποιεί δύο. Αν οι δύο διαστάσεις έχουν ίσο μέγεθος, ο πίνακας λέγεται τετραγωνικός και συμβολίζεται n x n. Ο δισδιάστατος πίνακας μπορεί να θεωρηθεί ως μονοδιάστατος, όπου κάθε θέση περιέχει έναν νέο μονοδιάστατο πίνακα.
Ποια είναι τα μειονεκτήματα της χρήσης πινάκων;
Οι πίνακες απαιτούν μνήμη, γιατί δεσμεύουν από την αρχή του προγράμματος πολλές θέσεις μνήμης. Επίσης περιορίζουν τις δυνατότητες του προγράμματος, γιατί είναι στατικές δομές και το μέγεθός τους δηλώνεται στην αρχή και μένει σταθερό κατά την εκτέλεση.
Πώς λειτουργεί η στοίβα;
Η στοίβα λειτουργεί με τη μέθοδο LIFO (Τελευταίο Μέσα Πρώτο Έξω). Οι κύριες λειτουργίες της είναι η ώθηση στοιχείου στην κορυφή και η απώθηση στοιχείου. Υπερχείλιση συμβαίνει όταν γίνεται ώθηση σε γεμάτη στοίβα και υποχείλιση όταν γίνεται απώθηση από άδεια. Υλοποιείται με μονοδιάστατο πίνακα και τη βοηθητική μεταβλητή top.
Πώς λειτουργεί η ουρά;
Η ουρά λειτουργεί με τη μέθοδο FIFO (Πρώτο Μέσα Πρώτο Έξω). Οι κύριες λειτουργίες της είναι η εισαγωγή στοιχείου στο πίσω άκρο και η εξαγωγή στοιχείου από το εμπρός άκρο. Χρειάζεται δύο δείκτες, τον front και τον rear.
Ποια είναι η διαφορά ανάμεσα στη σειριακή και στη δυαδική αναζήτηση;
Η σειριακή αναζήτηση είναι η πιο απλή μορφή αναζήτησης και δεν απαιτεί ταξινομημένο πίνακα. Η δυαδική αναζήτηση είναι αποτελεσματικότερη, γιατί χρειάζεται κάτω από τον μισό χρόνο εκτέλεσης, αλλά προϋποθέτει ότι ο πίνακας είναι ταξινομημένος.
Τι είναι η ταξινόμηση ευθείας ανταλλαγής (φυσαλίδα);
Η ταξινόμηση ευθείας ανταλλαγής βασίζεται στη σύγκριση και ανταλλαγή ζευγών γειτονικών στοιχείων, μέχρις ότου διαταχθούν όλα τα στοιχεία. Σε κάθε προσπέλαση του πίνακα, το μικρότερο κλειδί μετακινείται προς το αριστερό άκρο. Είναι γνωστή και ως ταξινόμηση φυσαλίδας.

