Name: ______ Class: ____ Date: ____
Φύλλο εργασίας: Αλγόριθμοι, πίνακες και επεξεργασία δεδομένων
1. Σωστό ή Λάθος
Να γράψετε Σ αν η πρόταση είναι σωστή ή Λ αν είναι λανθασμένη.
- Σε κάθε εκτέλεση ενός αλγορίθμου, η περατότητα απαιτεί να ολοκληρώνεται η διαδικασία μετά από πεπερασμένο αριθμό βημάτων. _____
- Σε αύξουσα ταξινομημένο πίνακα, αν το πρώτο και το τελευταίο στοιχείο είναι ίσα, τότε όλα τα στοιχεία είναι ίσα. _____
- Η ολίσθηση ενός μη αρνητικού δυαδικού ακέραιου κατά μία θέση προς τα δεξιά ισοδυναμεί με τον πολλαπλασιασμό του επί 2. _____
- Μια τιμή-φρουρός πρέπει να είναι διαφορετική από κάθε επιτρεπτή τιμή δεδομένων, ώστε να σηματοδοτεί με σαφήνεια τον τερματισμό. _____
- Σε αλγόριθμο εύρεσης του μέγιστου από τρεις τιμές, η χρήση αυστηρών συγκρίσεων (
>) και η ανάθεση της τρίτης τιμής στην τελευταία περίπτωση χειρίζεται σωστά κάθε ισοπαλία. _____
2. Συμπλήρωση κενών
Οι κωδικοί έξι προϊόντων που σαρώθηκαν είναι:
Κ[1..6] = Α12, Α12, Β07, Γ31, Γ31, Α12
Για το πρώτο προϊόν απαιτούνται 3 δευτερόλεπτα. Για κάθε επόμενο προϊόν απαιτούνται 1 δευτερόλεπτο αν έχει τον ίδιο κωδικό με το αμέσως προηγούμενο, διαφορετικά 3 δευτερόλεπτα. Να συμπληρώσετε τα κενά στον αλγόριθμο και να υπολογίσετε τον συνολικό χρόνο.
Χρόνος ← _____
Για i από _____ μέχρι _____
Αν Κ[i] = Κ[_____] τότε
Χρόνος ← Χρόνος + _____
αλλιώς
Χρόνος ← Χρόνος + _____
Τέλος_αν
Τέλος_επανάληψης
Συνολικός χρόνος: __________ δευτερόλεπτα
3. Αντιστοίχιση
Να αντιστοιχίσετε κάθε έννοια της στήλης Ι με τον κατάλληλο ορισμό της στήλης ΙΙ. Οι ορισμοί είναι ανακατεμένοι.
| Στήλη Ι | Στήλη ΙΙ |
|---|---|
| 1. Δυαδική αναζήτηση | α. Δομή ομοειδών στοιχείων, τα οποία προσπελαύνονται με δείκτη. |
| 2. Σειριακή αναζήτηση | β. Υποπρόγραμμα που εκτελεί ενέργειες χωρίς να επιστρέφει απευθείας μια τιμή. |
| 3. Πίνακας | γ. Αναζήτηση που εξετάζει διαδοχικά τα στοιχεία μέχρι να βρεθεί το ζητούμενο ή να εξαντληθούν τα στοιχεία. |
| 4. Συνάρτηση | δ. Αναζήτηση σε ταξινομημένα δεδομένα, κατά την οποία περιορίζεται επανειλημμένα το διάστημα αναζήτησης. |
| 5. Διαδικασία | ε. Υποπρόγραμμα που επιστρέφει μία τιμή. |
Απαντήσεις: 1–_____ 2–_____ 3–_____ 4–_____ 5–_____
4. Σύντομη απάντηση
Ο παρακάτω αλγόριθμος επιχειρεί να εμφανίσει το μέγιστο από τρεις αριθμούς:
Διάβασε α, β, γ
Αν α > β και α > γ τότε
max ← α
αλλιώς_αν β > α και β > γ τότε
max ← β
αλλιώς
max ← γ
Τέλος_αν
Εμφάνισε max
- Να δώσετε τιμές για τις οποίες ο αλγόριθμος εμφανίζει λανθασμένο αποτέλεσμα και να εξηγήσετε γιατί.
- Να διορθώσετε τον αλγόριθμο, ώστε να λειτουργεί και όταν δύο ή περισσότερες τιμές είναι ίσες.
Τιμές και εξήγηση:
Διορθωμένος αλγόριθμος:
5. Ιχνηλάτηση αλγορίθμου
Δίνεται ο πίνακας Α[1..5] με αρχικές τιμές 8, -2, 5, 0, 7.
S ← 0
P ← 0
Για i από 1 μέχρι 5
Αν Α[i] > 0 τότε
S ← S + Α[i]
P ← P + 1
Τέλος_αν
Αν i < 5 τότε
Αν Α[i] mod 2 = 0 τότε
Α[i+1] ← Α[i+1] + Α[i]
αλλιώς
Α[i+1] ← Α[i+1] - Α[i]
Τέλος_αν
Τέλος_αν
Τέλος_επανάληψης
Να υπολογίσετε τις τελικές τιμές των S, P και του πίνακα Α. Να λάβετε υπόψη ότι κάθε μεταβολή του Α[i+1] γίνεται πριν αυτό εξεταστεί στην επόμενη επανάληψη.
S = _____ P = _____
Α = [_____, _____, _____, _____, _____]
6. Δημιουργική δραστηριότητα: Σύγκριση σειράς σάρωσης
Χρησιμοποιήστε ακριβώς τα ίδια προϊόντα και στις δύο σειρές: δύο Α12, δύο Β07 και ένα Γ31.
| Κωδικός | Τιμή |
|---|---|
| Α12 | 2,50 € |
| Β07 | 1,20 € |
| Γ31 | 4,00 € |
Δημιουργήστε δύο διαφορετικές σειρές σάρωσης. Σε κάθε σειρά, τουλάχιστον ένα ζευγάρι ίδιων προϊόντων πρέπει να είναι διαδοχικό. Υπολογίστε το συνολικό κόστος και τον χρόνο σάρωσης κάθε σειράς. Το πρώτο προϊόν απαιτεί 3 δευτερόλεπτα· κάθε επόμενο απαιτεί 1 δευτερόλεπτο αν είναι ίδιο με το αμέσως προηγούμενο, διαφορετικά 3 δευτερόλεπτα. Συγκρίνετε τους χρόνους και εξηγήστε ποια σειρά είναι ταχύτερη.
Σειρά 1: ________________________________________________________
Κόστος: __________ € Χρόνος: __________ δευτερόλεπτα
Σειρά 2: ________________________________________________________
Κόστος: __________ € Χρόνος: __________ δευτερόλεπτα
Σύγκριση: _______________________________________________________
7. Συμπλήρωση κενών
Στον πίνακα ΕΙΣ[5,30] αποθηκεύεται το πλήθος εισιτηρίων για πέντε προορισμούς και τριάντα ημέρες. Οι γραμμές 1–3 αντιστοιχούν σε προορισμούς εσωτερικού και οι γραμμές 4–5 σε προορισμούς εξωτερικού. Να συμπληρώσετε τα κενά, ώστε ένας αλγόριθμος να υπολογίζει χωριστά τα συνολικά εισιτήρια εσωτερικού και εξωτερικού.
ΣΕΣ ← 0
ΣΕΞ ← 0
Για i από 1 μέχρι 5
Για j από 1 μέχρι 30
Αν i _____ 3 τότε
ΣΕΣ ← ΣΕΣ + _____
αλλιώς
ΣΕΞ ← ΣΕΞ + _____
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
8. Σύντομη απάντηση
Ο πίνακας Τ[1..100] περιέχει αριθμητικές τιμές σε αύξουσα σειρά.
- Ποιες δύο θέσεις αρκεί να συγκριθούν για να διαπιστωθεί αν όλα τα στοιχεία είναι ίσα; Να γράψετε τη συνθήκη που πρέπει να ισχύει και να αιτιολογήσετε.
- Αν ο πίνακας δεν ήταν ταξινομημένος, θα αρκούσε ο ίδιος έλεγχος; Να δώσετε ένα αντιπαράδειγμα.
Θέσεις και συνθήκη: _____________________________________________
Αιτιολόγηση για τον ταξινομημένο πίνακα:
Απάντηση και αντιπαράδειγμα για τον μη ταξινομημένο πίνακα:
9. Δημιουργική δραστηριότητα: Καταχώριση και έλεγχος εισιτηρίων
Για δύο ημέρες, δημιουργήστε πέντε έγκυρες καταχωρίσεις πτήσεων. Για κάθε καταχώριση να συμπληρώσετε την ημέρα, τον προορισμό και το πλήθος εισιτηρίων. Να χρησιμοποιήσετε προορισμούς από τους Α, Β, Γ, Δ, Ε, μη αρνητικούς ακέραιους αριθμούς εισιτηρίων και να καταχωρίσετε τουλάχιστον δύο πτήσεις προς τον ίδιο προορισμό την ίδια ημέρα. Προσθέστε επίσης ένα παράδειγμα μη έγκυρης καταχώρισης και εξηγήστε γιατί απορρίπτεται. Μετά τις καταχωρίσεις κάθε ημέρας δίνεται ο χαρακτήρας Χ ως τιμή-φρουρός.
| Καταχώριση | Ημέρα | Προορισμός | Πλήθος εισιτηρίων |
|---|---|---|---|
| 1 | _____ | _____ | _____ |
| 2 | _____ | _____ | _____ |
| 3 | _____ | _____ | _____ |
| 4 | _____ | _____ | _____ |
| 5 | _____ | _____ | _____ |
Τιμή-φρουρός μετά την ημέρα 1: _____ Τιμή-φρουρός μετά την ημέρα 2: _____
Μη έγκυρη καταχώριση: Ημέρα _____, προορισμός _____, πλήθος _____
Αιτιολόγηση απόρριψης: __________________________________________
Να θεωρήσετε ότι οι γραμμές του πίνακα αντιστοιχούν ως εξής: 1→Α, 2→Β, 3→Γ, 4→Δ, 5→Ε. Να γράψετε τις μη μηδενικές θέσεις του πίνακα ΕΙΣ που προκύπτουν από τις καταχωρίσεις σας και να υπολογίσετε τα συνολικά εισιτήρια εσωτερικού και εξωτερικού.
Μη μηδενικές θέσεις ΕΙΣ: _______________________________________
Σύνολο εσωτερικού: __________ Σύνολο εξωτερικού: __________
Απαντήσεις για τον/την εκπαιδευτικό
1. Σωστό ή Λάθος
- Σ
- Σ
- Λ — η ολίσθηση προς τα δεξιά ισοδυναμεί με ακέραιη διαίρεση διά του 2 για μη αρνητικό ακέραιο.
- Σ
- Λ — αν οι δύο μεγαλύτερες τιμές είναι ίσες και η τρίτη μικρότερη, οι δύο αυστηρές συγκρίσεις αποτυγχάνουν και επιλέγεται λανθασμένα η τρίτη τιμή.
2. Συμπλήρωση κενών
Συμπληρώσεις, με τη σειρά: 3, 2, 6, i−1, 1, 3.
Συνολικός χρόνος: 14 δευτερόλεπτα.
3. Αντιστοίχιση
1–δ, 2–γ, 3–α, 4–ε, 5–β
4. Σύντομη απάντηση
Ενδεικτικό παράδειγμα: α = 8, β = 8, γ = 3. Και οι δύο συνθήκες είναι ψευδείς, επομένως εμφανίζεται το 3, ενώ το μέγιστο είναι 8.
Ενδεικτική διόρθωση:
Διάβασε α, β, γ
max ← α
Αν β > max τότε
max ← β
Τέλος_αν
Αν γ > max τότε
max ← γ
Τέλος_αν
Εμφάνισε max
5. Ιχνηλάτηση αλγορίθμου
S = 43, P = 4
Α = [8, 6, 11, -11, 18]
6. Δημιουργική δραστηριότητα
Ενδεικτική απάντηση:
- Σειρά 1:
Α12, Α12, Β07, Β07, Γ31
Κόστος: 11,40 €. Χρόνος: 11 δευτερόλεπτα. - Σειρά 2:
Α12, Β07, Α12, Β07, Γ31
Κόστος: 11,40 €. Χρόνος: 15 δευτερόλεπτα.
Η πρώτη σειρά είναι ταχύτερη κατά 4 δευτερόλεπτα, επειδή περιλαμβάνει περισσότερα διαδοχικά ίδια προϊόντα. Γίνονται δεκτές άλλες έγκυρες σειρές και σωστοί υπολογισμοί.
7. Συμπλήρωση κενών
Συμπληρώσεις, με τη σειρά: ≤, ΕΙΣ[i,j], ΕΙΣ[i,j].
8. Σύντομη απάντηση
- Θέσεις: Τ[1] και Τ[100]. Συνθήκη: Τ[1] = Τ[100]. Εφόσον ο πίνακας είναι ταξινομημένος σε αύξουσα σειρά, το πρώτο στοιχείο είναι το μικρότερο και το τελευταίο το μεγαλύτερο. Αν είναι ίσα, όλα τα ενδιάμεσα στοιχεία έχουν επίσης την ίδια τιμή.
- Όχι. Ενδεικτικό αντιπαράδειγμα:
[2, 5, 2]. Τα δύο άκρα είναι ίσα, αλλά το μεσαίο στοιχείο είναι διαφορετικό.
9. Δημιουργική δραστηριότητα
Ενδεικτική απάντηση:
| Καταχώριση | Ημέρα | Προορισμός | Πλήθος εισιτηρίων |
|---|---|---|---|
| 1 | 1 | Α | 10 |
| 2 | 1 | Δ | 4 |
| 3 | 1 | Α | 5 |
| 4 | 2 | Β | 6 |
| 5 | 2 | Ε | 7 |
Τιμή-φρουρός μετά την ημέρα 1: Χ · τιμή-φρουρός μετά την ημέρα 2: Χ.
Μη έγκυρη καταχώριση: π.χ. ημέρα 1, προορισμός Ζ, πλήθος 3 — ο προορισμός δεν ανήκει στους επιτρεπτούς.
Μη μηδενικές θέσεις: ΕΙΣ[1,1]=15, ΕΙΣ[4,1]=4, ΕΙΣ[2,2]=6, ΕΙΣ[5,2]=7.
Σύνολο εσωτερικού: 21 · σύνολο εξωτερικού: 11.
Γίνονται δεκτές άλλες έγκυρες καταχωρίσεις, εφόσον τηρούν τους περιορισμούς και οι πίνακες και τα σύνολα υπολογίζονται σωστά.