Μετάβαση στο περιεχόμενο

Αλγόριθμοι

Διαγώνισμα στις ενότητες: Ανάλυση προβλήματος · Βασικές έννοιες αλγορίθμων · Δομές δεδομένων: στοίβα και ουρά · Αναζήτηση και ταξινόμηση · Ταξινόμηση φυσαλίδας βήμα βήμα · Δυαδική αναζήτηση βήμα βήμα.

Λύσε το στην οθόνη ή στο χαρτί. Τα ανοιχτά θέματα τα γράφεις στο τετράδιο. Με την «Παράδοση» η σελίδα βαθμολογεί τις κλειστές ερωτήσεις και σου δείχνει τις λύσεις για τις υπόλοιπες.

Πληροφορική · Γ΄ Λυκείου

Αλγόριθμοι

Διάρκεια 45΄ · 100 μονάδες

Θέμα Α25 μονάδες

Στις ερωτήσεις 1–3 να επιλέξεις τη σωστή απάντηση. Στην ερώτηση 4 να χαρακτηρίσεις κάθε πρόταση ως Σωστή ή Λανθασμένη.

  1. 1.
    Ένα πρόβλημα για το οποίο έχει αποδειχθεί ότι δεν υπάρχει λύση χαρακτηρίζεται:(5 μονάδες)
  2. 2.
    Μια συνταγή γράφει «ανακάτεψε για λίγο». Ποιο κριτήριο αλγορίθμου παραβιάζει αυτή η εντολή;(5 μονάδες)
  3. 3.
    Σε άδεια στοίβα ωθούνται με τη σειρά τα 44, 77, 11, 88. Ακολουθούν δύο απωθήσεις και μία ώθηση του 55. Ποια στοιχεία περιέχει η στοίβα, από τη βάση προς την κορυφή;(5 μονάδες)
  4. 4.

    Χαρακτήρισε κάθε πρόταση ως Σωστή (Σ) ή Λανθασμένη (Λ).(10 μονάδες)

    • Πρόταση αα)Ένας αλγόριθμος μπορεί να μη δέχεται καμία τιμή εισόδου.
    • Πρόταση ββ)Ένας αλγόριθμος μπορεί να μην παράγει καμία τιμή εξόδου.
    • Πρόταση γγ)Η δυαδική αναζήτηση μπορεί να εφαρμοστεί σε οποιονδήποτε πίνακα, αρκεί να είναι μεγάλος.
    • Πρόταση δδ)Στην ουρά η εισαγωγή γίνεται από το ένα άκρο και η εξαγωγή από το άλλο.
    • Πρόταση εε)Ο πίνακας είναι δυναμική δομή δεδομένων.

Θέμα Β25 μονάδες

Να απαντήσεις και να αιτιολογήσεις.

  1. 1.

    Να κατατάξεις το πρόβλημα «ποιος είναι ο φθηνότερος συνδυασμός πτήσεων για ένα ταξίδι σε τρεις πόλεις» και με τα τρία κριτήρια ταξινόμησης των προβλημάτων.(8 μονάδες)

  2. 2.

    Πόσες συγκρίσεις κάνει η ταξινόμηση φυσαλίδας σε πίνακα 88 στοιχείων; Πόσες αντιμεταθέσεις κάνει, αν ο πίνακας είναι ήδη ταξινομημένος;(8 μονάδες)

  3. 3.

    Ο πίνακας Α έχει 1515 στοιχεία ταξινομημένα σε αύξουσα σειρά: 3,6,9,…,453, 6, 9, \dots, 45 (δηλαδή Α[i] = 3 * i). Με δυαδική αναζήτηση αναζητείται το 3333, όπου το μεσαίο στοιχείο είναι στη θέση (first + last) DIV 2. Με ποια στοιχεία συγκρίνεται διαδοχικά το 3333 και πόσες συγκρίσεις χρειάζονται;(9 μονάδες)

Θέμα Γ25 μονάδες

  1. Ο πίνακας Α έχει n=5n = 5 στοιχεία: 7,4,9,1,57, 4, 9, 1, 5. Ταξινομείται με τον παρακάτω αλγόριθμο φυσαλίδας.

    ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n
      ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
        ΑΝ A[j-1] > A[j] ΤΟΤΕ
          temp ← A[j-1]
          A[j-1] ← A[j]
          A[j] ← temp
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    1. α)

      Ποιο είναι το περιεχόμενο του πίνακα μετά το πρώτο πέρασμα (i=2i = 2);(8 μονάδες)

    2. β)

      Ποιο είναι το περιεχόμενο του πίνακα μετά το δεύτερο πέρασμα (i=3i = 3);(7 μονάδες)

    3. γ)

      Πόσες συγκρίσεις και πόσες αντιμεταθέσεις γίνονται συνολικά μέχρι να τελειώσει ο αλγόριθμος;(6 μονάδες)

    4. δ)

      Ο πίνακας είναι ήδη ταξινομημένος μετά το τρίτο πέρασμα. Γιατί ο αλγόριθμος κάνει και το τέταρτο, και τι θα έπρεπε να προστεθεί για να σταματήσει νωρίτερα;(4 μονάδες)

Θέμα Δ25 μονάδες

  1. Μια ουρά υλοποιείται σε πίνακα Q πέντε θέσεων με δύο δείκτες. Αρχικά είναι άδεια, με front = 1 και rear = 0. Η εισαγωγή του x γίνεται με rear ← rear + 1 και Q[rear] ← x· η εξαγωγή επιστρέφει το Q[front] και κάνει front ← front + 1. Εκτελούνται με τη σειρά: εισαγωγή 1212, εισαγωγή 55, εισαγωγή 99, εξαγωγή, εισαγωγή 33, εξαγωγή.

    1. α)

      Ποιες τιμές βγαίνουν από τις δύο εξαγωγές, ποια στοιχεία μένουν στην ουρά και ποιες είναι οι τελικές τιμές των front και rear;(7 μονάδες)

    2. β)

      Στη συνέχεια επιχειρούνται δύο ακόμη εισαγωγές, του 77 και του 44. Τι συμβαίνει στη δεύτερη, και γιατί αυτό είναι παράξενο;(6 μονάδες)

    3. γ)

      Να γράψεις τμήμα αλγορίθμου για την εισαγωγή ενός στοιχείου x στην ουρά, με έλεγχο υπερχείλισης.(6 μονάδες)

    4. δ)

      Αν οι ίδιες έξι λειτουργίες της αρχικής εκφώνησης γίνονταν σε στοίβα (εισαγωγή = ώθηση, εξαγωγή = απώθηση), ποιες τιμές θα έβγαιναν και τι θα έμενε;(6 μονάδες)

Καλή επιτυχία!

8 κλειστές απαντήσεις είναι ακόμα κενές.

Όλες οι ενότητες