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