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

Διαγώνισμα Α΄ τετραμήνου

Διαγώνισμα στις ενότητες: Ανάλυση προβλήματος · Βασικές έννοιες αλγορίθμων · Δομές δεδομένων: στοίβα και ουρά · Αναζήτηση και ταξινόμηση · Ταξινόμηση φυσαλίδας βήμα βήμα · Δυαδική αναζήτηση βήμα βήμα · Από τον αλγόριθμο στο πρόγραμμα · Δομή επιλογής · Δομές επανάληψης · Πίνακας τιμών βρόχων · Μετατροπές ανάμεσα σε ΓΙΑ, ΟΣΟ και ΜΕΧΡΙΣ_ΟΤΟΥ.

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

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

Διαγώνισμα Α΄ τετραμήνου

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

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

  1. 1.

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

    • Πρόταση αα)Ένα πρόβλημα βελτιστοποίησης ζητά την καλύτερη από ένα σύνολο δυνατών λύσεων.
    • Πρόταση ββ)Στη στοίβα η ώθηση και η απώθηση γίνονται από το ίδιο άκρο.
    • Πρόταση γγ)Το σώμα του βρόχου ΟΣΟ … ΕΠΑΝΑΛΑΒΕ εκτελείται τουλάχιστον μία φορά.
    • Πρόταση δδ)Η δυαδική αναζήτηση σε ταξινομημένο πίνακα 6464 στοιχείων κάνει στη χειρότερη περίπτωση 77 συγκρίσεις.
    • Πρόταση εε)Ο βρόχος ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10 ΜΕ_ΒΗΜΑ 3 εκτελεί το σώμα του 33 φορές.
  2. 2.

    Να γράψεις τα πέντε κριτήρια που πρέπει να ικανοποιεί κάθε αλγόριθμος και να εξηγήσεις τι απαιτεί η περατότητα.(5 μονάδες)

  3. 3.

    Να ξαναγράψεις το παρακάτω τμήμα με τη δομή ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ … ΜΕΧΡΙΣ_ΟΤΟΥ, ώστε να είναι ισοδύναμο. Γιατί εδώ η μετατροπή είναι ασφαλής; Τι εμφανίζεται;(6 μονάδες)

    S ← 0
    ΓΙΑ κ ΑΠΟ 3 ΜΕΧΡΙ 15 ΜΕ_ΒΗΜΑ 4
      S ← S + κ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ S
  4. 4.
    Ποια είναι η τιμή της έκφρασης (17 DIV 3) MOD 4 + 2 ^ 3 / 4;(4 μονάδες)

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

  1. 1.

    Το παρακάτω τμήμα εκτελεί δυαδική αναζήτηση της τιμής key σε πίνακα Α nn στοιχείων, ταξινομημένο σε αύξουσα σειρά. Να γράψεις τι πρέπει να μπει σε καθένα από τα κενά (1) έως (5).(10 μονάδες)

    first ← 1
    last ← n
    βρέθηκε ← ΨΕΥΔΗΣ
    ΟΣΟ first <= ..(1).. ΚΑΙ βρέθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
      μέση ← ..(2)..
      ΑΝ Α[μέση] = key ΤΟΤΕ
        βρέθηκε ← ..(3)..
        θέση ← μέση
      ΑΛΛΙΩΣ_ΑΝ Α[μέση] < key ΤΟΤΕ
        first ← ..(4)..
      ΑΛΛΙΩΣ
        last ← ..(5)..
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  2. 2.

    Δίνεται το παρακάτω τμήμα προγράμματος.

    x ← 1
    y ← 20
    κ ← 0
    ΟΣΟ x < y ΕΠΑΝΑΛΑΒΕ
      κ ← κ + 1
      ΑΝ κ MOD 2 = 1 ΤΟΤΕ
        x ← x * 2
      ΑΛΛΙΩΣ
        y ← y - 3
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ x, y, κ
    1. α)

      Να γράψεις τον πίνακα τιμών των x, y, κ στο τέλος κάθε επανάληψης.(8 μονάδες)

    2. β)

      Τι εμφανίζει το τμήμα;(4 μονάδες)

    3. γ)

      Πόσες φορές ελέγχεται η συνθήκη x < y;(3 μονάδες)

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

  1. Σε έναν αγώνα δρόμου καταγράφεται για κάθε δρομέα το όνομα, η ηλικία και ο χρόνος του σε δευτερόλεπτα. Οι κατηγορίες είναι: Παίδες (κάτω από 1818), Άνδρες (1818 έως 3939) και Βετεράνοι (4040 και πάνω). Να γράψεις πρόγραμμα σε ΓΛΩΣΣΑ που διαβάζει τα στοιχεία των δρομέων μέχρι να δοθεί ως όνομα η λέξη «ΤΕΛΟΣ» και κάνει τα παρακάτω.

    1. α)

      Να γράψεις τις δηλώσεις και τη δομή επανάληψης με το «ΤΕΛΟΣ» ως τιμή τερματισμού. Ο χρόνος να ελέγχεται ότι είναι θετικός.(6 μονάδες)

    2. β)

      Να εμφανίζεται για κάθε δρομέα το όνομα και ο χρόνος σε λεπτά και δευτερόλεπτα, και να μετριούνται οι δρομείς κάθε κατηγορίας.(6 μονάδες)

    3. γ)

      Να εμφανίζονται στο τέλος το πλήθος κάθε κατηγορίας, το όνομα του ταχύτερου δρομέα (θεωρούμε ότι είναι μοναδικός) και ο μέσος χρόνος σε λεπτά και δευτερόλεπτα (ακέραια). Αν δεν δόθηκε κανένας δρομέας, να εμφανίζεται κατάλληλο μήνυμα.(7 μονάδες)

    4. δ)

      Τι εμφανίζει το πρόγραμμα στο τέλος για τους δρομείς Άννα (1616 ετών, 27352735 s), Νίκος (2525 ετών, 26502650 s) και Ελένη (4545 ετών, 29002900 s);(6 μονάδες)

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

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

    i ← 2
    αλλαγή ← ΑΛΗΘΗΣ
    ΟΣΟ i <= n ΚΑΙ αλλαγή = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
      αλλαγή ← ΨΕΥΔΗΣ
      ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
        ΑΝ Α[j-1] > Α[j] ΤΟΤΕ
          temp ← Α[j-1]
          Α[j-1] ← Α[j]
          Α[j] ← temp
          αλλαγή ← ΑΛΗΘΗΣ
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      i ← i + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    1. α)

      Ποιο είναι το περιεχόμενο του πίνακα μετά το πρώτο πέρασμα (i=2i = 2); Να γράψεις τις αντιμεταθέσεις με τη σειρά που γίνονται.(6 μονάδες)

    2. β)

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

    3. γ)

      Πόσες συγκρίσεις θα έκανε η κλασική φυσαλίδα, χωρίς σημαία, στον ίδιο πίνακα; Σε ποιον πίνακα 66 στοιχείων η σημαία δεν γλιτώνει καμία σύγκριση;(6 μονάδες)

    4. δ)

      Στον ταξινομημένο πίνακα αναζητείται το 55 με δυαδική αναζήτηση, με μέση (first + last) DIV 2. Με ποια στοιχεία συγκρίνεται; Πόσες συγκρίσεις θα έκανε η σειριακή αναζήτηση;(6 μονάδες)

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

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

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