Πληροφορική · Γ΄ Λυκείου
Αλγόριθμοι
Διάρκεια 45΄ · 100 μονάδες
Θέμα Α25 μονάδες
Στις ερωτήσεις 1–3 να επιλέξεις τη σωστή απάντηση. Στην ερώτηση 4 να χαρακτηρίσεις κάθε πρόταση ως Σωστή ή Λανθασμένη.
- 1.
- 2.
- 3.
- 4.
Χαρακτήρισε κάθε πρόταση ως Σωστή (Σ) ή Λανθασμένη (Λ).(10 μονάδες)
Θέμα Β25 μονάδες
Να απαντήσεις και να αιτιολογήσεις.
- 1.
Να κατατάξεις το πρόβλημα «ποιος είναι ο φθηνότερος συνδυασμός πτήσεων για ένα ταξίδι σε τρεις πόλεις» και με τα τρία κριτήρια ταξινόμησης των προβλημάτων.(8 μονάδες)
- 2.
Πόσες συγκρίσεις κάνει η ταξινόμηση φυσαλίδας σε πίνακα στοιχείων; Πόσες αντιμεταθέσεις κάνει, αν ο πίνακας είναι ήδη ταξινομημένος;(8 μονάδες)
- 3.
Ο πίνακας Α έχει στοιχεία ταξινομημένα σε αύξουσα σειρά: (δηλαδή
Α[i] = 3 * i). Με δυαδική αναζήτηση αναζητείται το , όπου το μεσαίο στοιχείο είναι στη θέση(first + last) DIV 2. Με ποια στοιχεία συγκρίνεται διαδοχικά το και πόσες συγκρίσεις χρειάζονται;(9 μονάδες)
Θέμα Γ25 μονάδες
Ο πίνακας Α έχει στοιχεία: . Ταξινομείται με τον παρακάτω αλγόριθμο φυσαλίδας.
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1 ΑΝ A[j-1] > A[j] ΤΟΤΕ temp ← A[j-1] A[j-1] ← A[j] A[j] ← temp ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ- α)
Ποιο είναι το περιεχόμενο του πίνακα μετά το πρώτο πέρασμα ();(8 μονάδες)
- β)
Ποιο είναι το περιεχόμενο του πίνακα μετά το δεύτερο πέρασμα ();(7 μονάδες)
- γ)
Πόσες συγκρίσεις και πόσες αντιμεταθέσεις γίνονται συνολικά μέχρι να τελειώσει ο αλγόριθμος;(6 μονάδες)
- δ)
Ο πίνακας είναι ήδη ταξινομημένος μετά το τρίτο πέρασμα. Γιατί ο αλγόριθμος κάνει και το τέταρτο, και τι θα έπρεπε να προστεθεί για να σταματήσει νωρίτερα;(4 μονάδες)
- α)
Θέμα Δ25 μονάδες
Μια ουρά υλοποιείται σε πίνακα Q πέντε θέσεων με δύο δείκτες. Αρχικά είναι άδεια, με
front = 1καιrear = 0. Η εισαγωγή του x γίνεται μεrear ← rear + 1καιQ[rear] ← x· η εξαγωγή επιστρέφει τοQ[front]και κάνειfront ← front + 1. Εκτελούνται με τη σειρά: εισαγωγή , εισαγωγή , εισαγωγή , εξαγωγή, εισαγωγή , εξαγωγή.- α)
Ποιες τιμές βγαίνουν από τις δύο εξαγωγές, ποια στοιχεία μένουν στην ουρά και ποιες είναι οι τελικές τιμές των
frontκαιrear;(7 μονάδες) - β)
Στη συνέχεια επιχειρούνται δύο ακόμη εισαγωγές, του και του . Τι συμβαίνει στη δεύτερη, και γιατί αυτό είναι παράξενο;(6 μονάδες)
- γ)
Να γράψεις τμήμα αλγορίθμου για την εισαγωγή ενός στοιχείου x στην ουρά, με έλεγχο υπερχείλισης.(6 μονάδες)
- δ)
Αν οι ίδιες έξι λειτουργίες της αρχικής εκφώνησης γίνονταν σε στοίβα (εισαγωγή = ώθηση, εξαγωγή = απώθηση), ποιες τιμές θα έβγαιναν και τι θα έμενε;(6 μονάδες)
- α)
Καλή επιτυχία!