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

Η στοίβα να φυλάσσεται σε πίνακα 2000 θέσεων.

Θέμα 2ο:

1. Ορίστε ποιο γράφο ονομάζουμε συνεκτικό και ποιο μη κυκλικό.
2. Σχεδιάστε γραφικά ένα συνεκτικό, μη κυκλικό γράφο με 8 κόμβους και 7 ακμές.
3. Ποιες από τις παρακάτω προτάσεις είναι αληθείς για έναν συνεκτικό μη κυκλικό γράφο με ν > 0 κόμβους:

1. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
2. Δύο διαφορετικοί κόμβοι συνδέονται από τουλάχιστον μια απλή διαδρομή.
3. Ο γράφος περιέχει ν + 1 ακμές.
4. Αν προστεθεί οποιαδήποτε ακμή ο γράφος θα αποκτήσει μια τουλάχιστον κυκλική διαδρομή.
5. Ο γράφος περιέχει λιγότερες από 2ν ακμές.
6. Αν προστεθεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
7. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
8. Ο γράφος περιέχει ν - 1 ακμές.
9. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα αποκτήσει μια τουλάχιστον κυκλική διαδρομή.

Θέμα 3ο:

1. Ορίστε μια διπλά συνδεδεμένη λίστα ακεραίων σε Pascal.
2. Υλοποιήστε συνάρτηση η οποία δέχεται ως όρισμα την παραπάνω διπλά συνδεδεμένη λίστα και ένα ακέραιο αριθμό που υπάρχει στη λίστα και επιστρέφει το μέσο όρο: του αριθμού αυτού, του αριθμού που προηγείται από αυτόν στη λίστα και του αριθμού που τον ακολουθεί. Αν δεν υπάρχει προηγούμενος ή επόμενος αριθμός ο μέσος όρος να υπολογιστεί από τους υπόλοιπους αριθμούς.

Θέμα 4ο:

Τα ονόματα των κατόχων και τα αντίστοιχα τηλέφωνα των 5.328.690 συνδέσεων που παρέχει ο ΟΤΕ πρέπει να καταχωρηθούν σε δομή δεδομένων που να επιτρέπει την ταχύτερη δυνατή εύρεση του τηλεφώνου με βάση το όνομα. Ποια δομή δεδομένων θα χρησιμοποιήσετε; Ποια δομή δεδομένων θα χρησιμοποιήσετε αν επιπλέον απαιτείται η άμεση ταξινομημένη ανάκτηση των ονομάτων για την εκτύπωση των τηλεφωνικών καταλόγων.

Διάρκεια εξέτασης 2 ώρες

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

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

Τμήμα Μαθηματικών

ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ Διδάσκων: Διομήδης Σπινέλλης

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

Θέμα 1ο:

Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:

     { Ορισμός του τύπου της συνδεδεμένης λίστας }
          type
              charList = ...
     { Επιστρέφεται μια άδεια συνδεδεμένη λίστα }
          function newCharList : charList; 
     { Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της }
          function addCharList(l : charList; c : char) : charList; 
     { Επιστρέφεται μια συνδεδεμένη λίστα με το πρώτο στοιχείο διαγραμμένο. Κατά
        την επιστροφή η μεταβλητή c περιέχει την τιμή του. }
          function delCharListHead(l : charList; var c : char) : charList; 
     { Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή c }
          function searchCharList(l : charList; c : char) : charList; 
     { Επιστρέφεται αληθές αν η λίστα είναι κενή }
          function isEmtyCharList(l : charList) : boolean;