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

Αλγόριθμοι και δομές δεδομένων

Διαγώνισμα στις ενότητες: Αναζήτηση · Ταξινόμηση · Αναδρομή.

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

Πληροφορική · Γ΄ Γυμνασίου

Αλγόριθμοι και δομές δεδομένων

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

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

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

  1. 1.
    Η δυαδική αναζήτηση δίνει σίγουρα σωστή απάντηση μόνο όταν:(5 μονάδες)
  2. 2.
    Μια ταξινομημένη λίστα έχει 200200 στοιχεία. Πόσες συγκρίσεις κάνει η δυαδική αναζήτηση στη χειρότερη περίπτωση;(5 μονάδες)
  3. 3.
    Πόσες συγκρίσεις κάνει η ταξινόμηση φυσαλίδας (χωρίς σημαία) σε λίστα 88 στοιχείων;(5 μονάδες)
  4. 4.
    Τι θα εμφανίσει ο παρακάτω κώδικας;(5 μονάδες)
    def f(n):
        if n == 0:
            return 0
        return n % 10 + f(n // 10)
    
    print(f(472))
  5. 5.

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

    • Πρόταση αα)Η σειριακή αναζήτηση δουλεύει μόνο σε ταξινομημένη λίστα.
    • Πρόταση ββ)Οι εντολές x = y και μετά y = x ανταλλάσσουν τις τιμές των x και y.
    • Πρόταση γγ)Μετά το πρώτο πέρασμα της ταξινόμησης φυσαλίδας, το μεγαλύτερο στοιχείο βρίσκεται στο τέλος της λίστας.
    • Πρόταση δδ)Μια αναδρομική συνάρτηση χωρίς συνθήκη τερματισμού σταματά με σφάλμα RecursionError.
    • Πρόταση εε)Όταν μια λίστα διπλασιάζεται, οι συγκρίσεις της δυαδικής αναζήτησης στη χειρότερη περίπτωση διπλασιάζονται.

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

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

  1. 1.

    Η συνάρτηση dyadiki της ενότητας ψάχνει το 57 στη λίστα [4, 9, 13, 21, 30, 38, 45, 57, 61, 70, 82]. Να γράψεις, για κάθε βήμα, τα arxi, telos, mesi και την απόφαση. Τι επιστρέφει η συνάρτηση και μετά από πόσες συγκρίσεις;(12 μονάδες)

  2. 2.

    Να εκτελέσεις ταξινόμηση με επιλογή στη λίστα [35, 12, 48, 7, 20] και να γράψεις τη λίστα μετά από κάθε πέρασμα. Σε ποια περάσματα η λίστα δεν αλλάζει, και γιατί;(13 μονάδες)

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

  1. Η συνάρτηση fysalida της ενότητας ταξινομεί σε αύξουσα σειρά τη λίστα [16, 5, 23, 11].

    1. α)

      Να γράψεις τη λίστα μετά από κάθε σύγκριση του πρώτου περάσματος. Ποιο στοιχείο έχει πάρει την οριστική του θέση στο τέλος του;(9 μονάδες)

    2. β)

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

    3. γ)

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

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

  1. Δίνεται η παρακάτω αναδρομική συνάρτηση.

    def dynami(b, e):
        if e == 0:
            return 1
        return b * dynami(b, e - 1)
    1. α)

      Ποια είναι η συνθήκη τερματισμού και ποιο το αναδρομικό βήμα;(6 μονάδες)

    2. β)

      Να ακολουθήσεις τις κλήσεις της dynami(3, 4). Πόσες κλήσεις γίνονται συνολικά και τι επιστρέφει;(7 μονάδες)

    3. γ)

      Τι θα γίνει με την κλήση dynami(2, -1); Να αιτιολογήσεις.(6 μονάδες)

    4. δ)

      Να γράψεις αναδρομική συνάρτηση pollaplasiasmos(a, b) που υπολογίζει το a⋅ba \cdot b για b≥0b \geq 0 χρησιμοποιώντας μόνο προσθέσεις. Τι επιστρέφει η pollaplasiasmos(7, 4);(6 μονάδες)

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

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

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