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

Θέμα 2ο:

  1. Τι ονομάζουμε βαθμό και τι ύψος ενός δένδρου;
  2. Πότε ένα δένδρο καλείται πλήρες;
  3. Αποδείξτε τις παρακάτω προτάσεις. Στην απόδειξη μπορεί να σας φανεί χρήσιμη η μέθοδος της επαγωγής.

  1. Ένα πλήρες δένδρο βαθμού d και ύψους h θα έχει κόμβους.
  2. Ένα πλήρες δυαδικό δένδρο ύψους h θα έχει κόμβους.
  3. Ένα πλήρες δυαδικό δένδρο με n κόμβους θα έχει ύψος.

Θέμα 3ο:

  1. Περιγράψτε με πληρότητα έναν αποδοτικό τρόπο ταξινόμησης αρχείου του οποίου τα στοιχεία δε χωράνε στην κεντρική μνήμη.
  2. Περιγράψτε περιληπτικά δομές αναζήτησης που μπορούν να χρησιμοποιηθούν για γρήγορη πρόσβαση στα στοιχεία ενός αρχείου που φυλάσσεται σε βοηθητική μνήμη.

Θέμα 4ο:

  1. Περιγράψτε με ψευδοκώδικα τη διαδικασία της δυαδικής αναζήτησης για την εύρεση μιας εγγραφής σε ταξινομημένο πίνακα.
  2. Αν ο πίνακας έχει Ν στοιχεία δώστε τον ελάχιστο και το μέγιστο αριθμό συγκρίσεων που μπορεί να απαιτηθούν για την παραπάνω διαδικασία αναζήτησης.

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

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