ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Τμήμα Ηλεκτρονικών Μηχ. και Μηχ. Υπολογιστών ΛΟΓ 102: Τεχνολογία Λογισμικού Ι http://www.softlab.ntua.gr/~nickie/TUC/log102/

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

Άσκηση 1 (60%)

Έστω n και m δυο φυσικοί αριθμοί. Ο μέγιστος κοινός διαιρέτης των n και m είναι ο μέγιστος φυσικός αριθμός που διαιρεί ακριβώς και τους δυο αυτούς αριθμούς. Συμβολίζεται ως ΜΚΔ(n, m). Ο μέγιστος κοινός διαιρέτης των n και m μπορεί να υπολογιστεί λαμβάνοντας υπόψη τις εξής δυο παρατηρήσεις που οφείλονται στον αρχαίο μαθηματικό Ευκλείδη:

1. Αν ο αριθμός m είναι ίσος με μηδέν, τότε ΜΚΔ(n, m) = n.
2. Διαφορετικά, ΜΚΔ(n, m) = ΜΚΔ(m, k), όπου k το υπόλοιπο της ακέραιας διαίρεσης n δια m.

Παράδειγμα

Να υλοποιήσετε τη συνάρτηση υπολογισμού του ΜΚΔ δυο φυσικών αριθμών με δυο τρόπους: επαναληπτικά και αναδρομικά. Η συνάρτηση θα πρέπει να δέχεται ως παραμέτρους τους αριθμούς n και m και να επιστρέφει τον αριθμό ΜΚΔ(n, m). Στην αναδρομική υλοποίηση δεν επιτρέπεται να χρησιμοποιήσετε τοπικές ή καθολικές μεταβλητές.

Άσκηση 2 (40%)

Να γραφεί συνάρτηση σε C που να εκτυπώνει και συγχρόνως να καταστρέφει ένα δυαδικό δένδρο. Ο τύπος του δένδρου και η επικεφαλίδα της ζητούμενης συνάρτησης δίνονται παρακάτω:

   typedef struct node_tag {
      double data;
      struct node_tag * left, * right;
   } node, * tree;

   void printAndDestroy (tree t);

Η εκτύπωση των στοιχείων του δένδρου μπορεί να γίνει με οποιαδήποτε σειρά, αρκεί κάθε ένα στοιχείο να εμφανίζεται σε μια ξεχωριστή γραμμή. Υπόδειξη: η χρήση αναδρομής προσφέρεται για την υλοποίηση της συνάρτησης.

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