Θέματα εξετάσεων

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εξεταστική περιόδος Ιουνίου 1999

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

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

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

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

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

struct s_list *find_int(int i);

που επιστρέφει δείκτη στο πρώτο στοιχείο της λίστας που περιέχει τον ακέραιο i ή NULL αν αυτός δεν υπάρχει στη λίστα. Σε μια λίστα με N στοιχεία πόσα κατά μέσο όρο στοιχεία θα εξεταστούν για να βρεθεί ο ακέραιος i;

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

Μια εφαρμογή αναγνώρισης κλήσεων για γνωστή αλυσίδα διανομής φαγητού πρέπει να μπορεί γρήγορα να εμφανίσει το όνομα που αντιστοιχεί σε κάθε έναν από 5.000.000 αριθμούς τηλεφώνου. Περιγράψτε αδρά (σε λιγότερο από μια σελίδα) μια κατάλληλη τεχνολογία ή δομή δεδομένων που να ικανοποιεί την απαίτηση αυτή καθώς και την τεχνική αναζήτησης που θα πρέπει να χρησιμοποιηθεί.

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

Για την παρακάτω κλάση της C++ που ορίζει μια στοίβα 100 ακεραίων υλοποιήστε τις συναρτήσεις stack, push και pop. Γράψτε σε C++ ένα πρόγραμμα που να διαβάζει 40 ακεραίους και να τους τυπώνει με ανάποδη σειρά (από το τέλος προς την αρχή).

class stack {
private:
        int sp;			// Stack pointer
        int elem[100];		// Stack elements
public:
        stack(void);		// Constructor
        void push(int i);
        int pop(void);
};

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

Η παρακάτω συνάρτηση της Lisp επιστρέφει το παραγοντικό του αριθμού n:

(defun factorial (n)
        (if (equal n 0)
        1
        (* n (factorial (- n 1)))))

Ορίστε με ανάλογο τρόπο συνάρτηση σε Lisp που να υπολογίζει τον νοστό όρο της ακολουθίας Fibonacci δεύτερης τάξης:

F₀= 0, F₁= 1, F_{n + 2}= F_{n + 1} + F_n + F_n

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

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

Εξεταστική περιόδος Σεπτεμβρίου 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 ώρες Καλή επιτυχία!

Περιεχόμενα