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

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

Τμήμα Μαθηματικών
ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ

Διδάσκων: Διομήδης Σπινέλλης

Εξεταστική περίοδος

Ιουνίου 1997

Θέμα 1ο:

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

     { Αρχικοποιείται η στοίβα }
          procedure stackInitialize; 
     { Το στοιχείο i εισάγεται στην κορυφή της στοίβας }
          procedure stackPush(i :boolean); 
     { Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }
          function stackPop : boolean; 
     { Επιστρέφεται αληθές αν η στοίβα είναι κενή }
          function stackIsEmpty : bool;

Η στοίβα να φυλάσσεται σε πίνακα 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 ώρες Καλή επιτυχία!

Creative Commons License  Τελευταία αλλαγή: Κυριακή, 2 Απριλίου 2000 12:55 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».