Γεωργακόπουλος Ανδρέας

ΘΕΜΑ Α

Α1        Για τις παρακάτω προτάσεις να σημειώσετε αν είναι Σωστές ή Λάθος:

1. Η χειρότερη περίπτωση εκτέλεσης ενός αλγορίθμου αφορά σε ένα κόστος μετρήσιμο σε υπολογιστικούς πόρους.
2. Το μέγεθος εισόδου ενός αλγορίθμου ισούται με τον αριθμό των βασικών πράξεων που θα εκτελέσει.
3. Ο χρόνος εκτέλεσης ενός προγράμματος δεν επηρεάζεται από τη γλώσσα προγραμματισμού που έχει χρησιμοποιηθεί για την ανάπτυξή του.
4. Στη σταθερή πολυπλοκότητα, ο χρόνος εκτέλεσης δεν εξαρτάται από το μέγεθος εισόδου.
5. Στις λίστες οι κόμβοι πρέπει να βρίσκονται σε συνεχόμενες θέσεις μνήμης.
6. Στο δέντρο υπάρχει ένας κόμβος από τον οποίο ξεκινούν όλοι οι άλλοι.

Α2        Στις παρακάτω προτάσεις, να συμπληρώσετε κάθε κενό με μια από τις παρακάτω λέξεις:           δυναμική, πινάκων, στατική, αποδοτικότητα, εκθετική, ουρά, πολυπλοκότητα, γράφων, λογαριθμική, στοιβα

1. Οι λίστες και τα δέντρα μπορούν να θεωρηθούν ειδικές κατηγορίες ………………………..
2. Μια δομή δεδομένων που χρησιμοποιεί δείκτες λέγεται …………………………………….
3. Ο συμβολισμός Ο(logn) εκφράζει τη …………………………………………… πολυπλοκότητα.
4. Για την επιλογή του καταλληλότερου αλγορίθμου χρησιμοποιείται η ……………………… του.
5. Η δομή δεδομένων ……………………… χρησιμοποιεί τη μέθοδο επεξεργασίας «Πρώτο Μέσα-Πρώτο Έξω».

Α3        Για τις παρακάτω προτάσεις να επιλέξετε το γράμμα που αντιστοιχεί στη σωστή απάντηση:

1. Η πολυπλοκότητα της δυαδικής αναζήτησης είναι
   1. Εκθετική
   2. Κυβική
   3. Γραμμική
   4. Λογαριθμική

1. Ο αλγόριθμος για την εισαγωγή και την εξαγωγή σε μια ουρά
   1. Εξαρτάται από το μέγεθος της ουράς και έχει σταθερή πολυπλοκότητα
   2. Εξαρτάται από το μέγεθος της ουράς και έχει γραμμική πολυπλοκότητα
   3. Είναι ανεξάρτητος από το μέγεθος της ουράς και έχει σταθερή πολυπλοκότητα.

1. Όταν οι δείκτες «μπροστα» και «πίσω» έχουν την τιμή 3, τότε η ουρά:
   1. Έχει 2 στοιχεία
   2. Είναι κενή
   3. Έχει 3 στοιχεία
   4. Έχει 1στοιχείο

Α4        Να σχεδιάσετε το δέντρο που αντιστοιχεί στις παρακάτω πληροφορίες:

• Ο κόμβος κ8 έχει πατέρα τον κόμβο κ4 και παιδιά τους κ14 και κ16
• Ο κόμβος κ2 έχει παιδιά τους κ6 και κ3
• Οι κόμβοι κ12 και κ4 έχουν πατέρα τον κόμβο κ6
• Ο κόμβος κ10 έχει πατέρα τον κόμβο κ4

ΘΕΜΑ Β

Β1        Δίνεται το παρακάτω πρόγραμμα και η συνάρτηση που καλεί:

Να σχεδιαστεί το αντίστοιχο λογικό διάγραμμα.

Β2        Τι θα εμφανίσει αν δοθεί ως είσοδος το 26 ;

ΘΕΜΑ Γ

Να αναπτύξετε πρόγραμμα σε γλώσσα που θα χρησιμοποιεί πίνακα Σ[50] ως στοίβα 50 θέσεων και θα πραγματοποιεί τις παρακάτω ενέργειες:

1. Θα διαβάζει το είδος της λειτουργίας που επιθυμεί ο χρήστης: «1» για ώθηση, «2» για απώθηση και «3» για τερματισμό, ελέγχοντας την εγκυρότητα των τιμών εισόδου. Για την  επιλογή «1» θα διαβάζει έναν ακέραιο και θα καλεί τη διαδικασία «ώθηση» (περιγράφεται στο ερώτημα ΙΙΙ), ενώ για την επιλογή «2» την διαδικασία «απώθηση» (περιγράφεται στο ερώτημα ΙV).
2. Μετά το τέλος της επαναληπτικής διαδικασίας θα εμφανίζει κατάλληλο μήνυμα για την κατάσταση της στοίβας (ΑΔΕΙΑ ή ΓΕΜΑΤΗ ή αριθμό στοιχείων της στοίβας).
3. Να υλοποιηθεί η διαδικασία «ώθηση», η οποία δέχεται ως παραμέτρους τη στοίβα, την κορυφή και έναν ακέραιο αριθμό. Αν υπάρχει χώρος, εισάγει τον αριθμό στη στοίβα, διαφορετικά εμφανίζει κατάλληλο μήνυμα. Επιστρέφει τη στοίβα και την κορυφή.
4. Να υλοποιηθεί η διαδικασία «απώθηση», η οποία δέχεται τη στοίβα και την κορυφή. Αν υπάρχουν στοιχεία στη στοίβα, εμφανίζει το κατάλληλο στοιχείο και εκτελεί την εξαγωγή του, διαφορετικά εμφανίζει κατάλληλο μήνυμα. Επιστρέφει τη στοίβα και την κορυφή.

ΘΕΜΑ Δ

α) Να γραφεί πρόγραμμα το οποίο να διαβάζει τα ονόματα και  τα τηλέφωνα των 100 κατοίκων ενός χωριού.

β) Να εμφανίζει τα ονόματα των κατοίκων αλφαβητικά και δίπλα τα αντίστοιχα τηλεφωνα.

γ) Να διαβάζει ένα όνομα και:

1. Να αναζητά το όνομα σειριακά.  Αν βρεθεί να εμφανίζει το τηλέφωνό του διαφορετικά μήνυμα ότι δεν βρέθηκε. Να εμφανίζει επίσης το πλήθος των αναζητήσεων που έκανε. (Επειδή ο πίνακας είναι ταξινομημένος να σταματά όταν ξεπεράσει το ζητούμενο όνομα)
2. Να αναζητά το όνομα δυαδικά.  Αν βρεθεί να εμφανίζει το τηλέφωνό του διαφορετικά μήνυμα ότι δεν βρέθηκε. Να εμφανίζει επίσης το πλήθος των αναζητήσεων που έκανε.

Απαντήσεις

Α1.       1-Σ,    2-Λ,    3-Λ,    4-Σ,    5-Λ,    6-Σ

Α2.       1-γράφων,  2-δυναμική, 3-λογαριθμική, 4-αποδοτικοτητα,      5-ουρα

Α3.       1-d,      2-c,      3-d

A4.      

B1.

Β2.       4

ΘΕΜΑ Γ

ΠΡΟΓΡΑΜΜΑ Γ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: τοπ, επ, στοιχειο, Σ[50] 
ΑΡΧΗ
  τοπ <-0
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
      ΓΡΑΨΕ"Επιλέξτε ενέργεια:"
      ΔΙΑΒΑΣΕ επ
    ΜΕΧΡΙΣ_ΟΤΟΥ επ =1Η επ =2Η επ =3
    ΑΝ επ =1ΤΟΤΕ
      ΔΙΑΒΑΣΕ στοιχειο
      ΚΑΛΕΣΕ ωθηση(Σ, τοπ, στοιχειο) 
    ΑΛΛΙΩΣ_ΑΝ επ =2ΤΟΤΕ
      ΚΑΛΕΣΕ απώθηση(Σ, τοπ) 
    ΤΕΛΟΣ_ΑΝ
  ΜΕΧΡΙΣ_ΟΤΟΥ επ =3
  ΑΝ τοπ =0ΤΟΤΕ
    ΓΡΑΨΕ"Αδεια"
  ΑΛΛΙΩΣ_ΑΝ τοπ =50ΤΟΤΕ
    ΓΡΑΨΕ"Γεμάτη"
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ τοπ," στοιχεία στην στοίβα."
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΔΙΑΔΙΚΑΣΙΑ ωθηση(Σ, τοπ, στοιχειο) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Σ[50], τοπ, στοιχειο
ΑΡΧΗ
  ΑΝ τοπ =50ΤΟΤΕ
    ΓΡΑΨΕ"Δεν υπάρχει χώρος"
  ΑΛΛΙΩΣ
    τοπ <- τοπ +1
    Σ[τοπ]<- στοιχειο
    ΓΡΑΨΕ"Ωθηση του:", Σ[τοπ] 
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

ΔΙΑΔΙΚΑΣΙΑ απώθηση (Σ, τοπ) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Σ[50], τοπ
ΑΡΧΗ
  ΑΝ τοπ =0ΤΟΤΕ
    ΓΡΑΨΕ"δεν υπάρχει στοιχείο"
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ"Απώθηση του: ", Σ[τοπ] 
    τοπ <- τοπ -1
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

ΘΕΜΑ Δ

ΠΡΟΓΡΑΜΜΑΔ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ:ι,τ[100],ξ,π2,μσ,μδ,αρ,τε,μ
ΧΑΡΑΚΤΗΡΕΣ:ον[100],π,κλειδι
ΛΟΓΙΚΕΣ:βρεθηκε
ΑΡΧΗ
ΓΙΑιΑΠΟ1ΜΕΧΡΙ100
  ΔΙΑΒΑΣΕον[ι],τ[ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑιΑΠΟ2ΜΕΧΡΙ100
  ΓΙΑξΑΠΟ100ΜΕΧΡΙιΜΕ_ΒΗΜΑ-1
   ΑΝον[ξ-1]>ον[ξ]ΤΟΤΕ
     π<-ον[ξ-1]
    ον[ξ-1]<-ον[ξ]
    ον[ξ]<-π
     π2<-τ[ξ-1]
    τ[ξ-1]<-τ[ξ]
    τ[ξ]<-π2
   ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑιΑΠΟ1ΜΕΧΡΙ100
  ΓΡΑΨΕον[ι],',',τ[ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕκλειδι
μσ<-0
ι<-1
βρεθηκε<-ΨΕΥΔΗΣ
ΟΣΟι<=100ΚΑΙκλειδι>=ον[ι]ΕΠΑΝΑΛΑΒΕ
  μσ<-μσ+1
  ΑΝκλειδι=ον[ι]ΤΟΤΕ
   βρεθηκε<-ΑΛΗΘΗΣ
  ΑΛΛΙΩΣ
    ι<-ι+1
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝβρεθηκεΤΟΤΕ
  ΓΡΑΨΕτ[ι],' (βρεθηκεμετααπο ',μσ,' &αναζητησεις)'
ΑΛΛΙΩΣ
  ΓΡΑΨΕ'Δεν βρεθηκε. Έγιναν ', μσ,' &αναζητησεις)'
  ΤΕΛΟΣ_ΑΝ
  μδ <-0
  βρεθηκε <-ΨΕΥΔΗΣ
  αρ <-1
  τε <-100
ΟΣΟ αρ <= τε ΚΑΙΟΧΙ(βρεθηκε)ΕΠΑΝΑΛΑΒΕ
    μ <-(αρ + τε)div2
    μδ <- μδ +1
    ΑΝ ον[μ]= κλειδι ΤΟΤΕ
      βρεθηκε <-ΑΛΗΘΗΣ
    ΑΛΛΙΩΣ_ΑΝ ον[μ]< κλειδι ΤΟΤΕ
      αρ <- μ +1
    ΑΛΛΙΩΣ
      τε <- μ -1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΑΝ βρεθηκε ΤΟΤΕ
    ΓΡΑΨΕ τ[ι],' (βρεθηκεμετααπο ', μδ,' &αναζητησεις)'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ'Δεν βρεθηκε. Έγιναν ', μδ,' &αναζητησεις)'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ