Εξεταστική περιόδος Σεπτεμβρίου 1999

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Πληροφοριακών και Επικοινωνιακών Συστημάτων

Γλώσσες προγραμματισμού και δομές δεδομένων
Διδάσκων: Διομήδης Σπινέλλης
Εξεταστική περίοδος
Σεπτεμβρίου 1999

Θέμα 1ο: (3 βαθμοί)

Να ορίσετε σε C μια δομή struct s_btree για την παράσταση ενός δυαδικού δένδρου αναζήτησης χαρακτήρων. Υλοποιήστε σε C τη συνάρτηση

  struct s_btree *find_char(struct s_btree *root, char c);

που επιστρέφει δείκτη στο στοιχείο του δένδρου που περιέχει τον ακέραιο c ή NULL αν αυτός δεν υπάρχει στο δένδρο.

Θέμα 2ο: (3 βαθμοί)

Ένα ταξιδιωτικό γραφείο σας ζητάει ένα πρόγραμμα που να μπορεί να απαντά σε ερωτήσεις του τύπου "ποιες πτήσεις πρέπει να ακολουθήσω για να πάω από τη Σάμο στο Κατμαντού;" (Σάμος - Αθήνα - Άμστερνταμ - Πεκίνο - Κατμαντού). Σε ποια δομή δεδομένων θα πρέπει να βασιστεί ένα τέτοιο πρόγραμμα; Περιγράψτε (με ένα μικρό παράδειγμα σε C) έναν τρόπο υλοποίησης της δομής αυτής.

Θέμα 3ο: (3 βαθμοί)

Για την παρακάτω κλάση της C++ που ορίζει μια ουρά 100 ακεραίων υλοποιήστε τις συναρτήσεις queue, add και remove. Γράψτε σε C++ ένα πρόγραμμα που να διαβάζει ακεραίους και, αφού διαβάσει τους πρώτους 20, να τους τυπώνει με τη σειρά ανάγνωσης: έναν αριθμό για κάθε νέο ακέραιο που θα διαβάζει. (Όταν δηλαδή διαβάσει τον 21ο θα τυπώσει τον 1ο, μετά τον 22ο θα τυπώσει τον 2ο, κ.ο.κ.)

class queue {
private:
        int head;		// Pointer to the queue head
        int tail;               // Pointer to the queue tail
        int elem[100];		// Queue elements
public:
        queue(void);		// Constructor
        void add(int i);	// Adds an integer to the queue tail
        int remove(void);	// Removes and returns an integer from
				// the queue head
};

Θέμα 4ο: (3 βαθμοί)

Τα παρακάτω κατηγορήματα της Prolog ορίζουν τους ακέραιους αριθμούς (nat) και την πρόσθεση με βάση τον όρο suc που ορίζει τον επόμενο ενός ακεραίου:

nat(0).
nat(suc(X)) :-
        nat(X).	

plus(0, X, X) :-
        nat(X).

plus(suc(X), Y, suc(Z)) :-
        plus(X, Y, Z).

Να ορίσετε, βασισμένοι στα παραπάνω, το κατηγόρημα double(X, Y) που είναι αληθές όταν και μόνο όταν το Υ είναι το διπλάσιο του Χ.

Το άριστα ορίζεται ως 10 βαθμοί.

Διάρκεια εξέτασης 2,5 ώρες Καλή επιτυχία!