Ενοτητα 1

Question 1

Να δώσετε τον ορισμό της δομής δεδομένων «Στοίβα»,

Answer 1

Απάντηση:

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

Question 2

228. Ποια μέθοδο επεξεργασίας δεδομένων χρησιμοποιεί η δομή δεδομένων «Στοίβα»;

Answer 2

Απάντηση:

Τη μέθοδο Τελευταίο Μέσα, Πρώτο Έξω, ή αλλιώς LIFO, από τα αρχικά των λέξεων «Last In First Out». Κατά τη μέθοδο αυτήν το δεδομένο που εισάγεται τελευταίο και βρίσκεται στην κορυφή της στοίβας, είναι αυτό που εξάγεται πρώτο. Αντίθετα, το δεδομένο που βρίσκεται στο βάθος της στοίβας είναι και αυτό που εξάγεται τελευταίο,

Question 3

229. α. Πώς ονομάζονται οι κύριες λειτουργίες που εκτελούνται στη δομή δεδομένων «Στοίβα»;
     β. Ποια λειτουργία επιτελούν και τι πρέπει να ελέγχεται πριν την εκτέλεσή τους

Answer 3

Απάντηση:

Στη δομή δεδομένων «Στοίβα» χρησιμοποιούνται δύο λειτουργίες

•η ώθηση (push) με την οποία εισάγουμε ένα στοιχείο στην κορυφή της στοίβας και

•η απώθηση (pop) με την οποία αφαιρούμε ένα στοιχείο από την κορυφή της στοίβας
Β Βλέπε 230η και 231η ερώτηση θεωρίας.

Question 4

230. Τι πρέπει να προσέχουμε κατά την εκτέλεση της λειτουργίας της ώθησης ενός στοιχείου στη «Στοίβα 》

Answer 4

Κατά την εκτέλεση της λειτουργίας της ώθησης ενός στοιχείου στη στοίβα, πρέπει να εξετάζουμε αν αυτή είναι γεμάτη δηλαδή αν υπάρχει διαθέσιμος χώρος, ώστε να μπορούμε να τοποθετήσουμε το στοιχείο σε αυτήν. Διαφορετικά, αν η στοίβα είναι γεμάτη και προσπαθήσουμε να εισαγάγουμε ένα στοιχείο σε αυτήν, τότε λέμε ότι συμβαίνει υπερχείλιση της στοίβας

Question 5

231. Τι πρέπει να προσέχουμε κατά την εκτέλεση της λειτουργίας της απώθησης ενός στοιχείου από τη «Στοίβα»

Answer 5

Κατα την εκτέλεση της λειτουργίας της απώθησης ενός στοιχείου από τη στοίβα, πρέπει να εξετάζουμε αν υπάρχει ένα τουλάχιστον στοιχείο σε αυτήν για να εξαχθεί (να μην είναι κενή). Διαφορετικά, αν η στοίβα είναι κενή και προσπαθήσουμε να αφαιρέσουμε ένα στοιχείο από αυτήν, τότε λέμε ότι συμβαίνει υποχείλιση της στοίβας.

Question 6

232. Να περιγράψετε την υλοποίηση «Στοίβας» με τη βοήθεια μονοδιάστατου πίνακα.

Answer 6

Απάντηση:

Μια στοίβα μπορούμε να την υλοποιήσουμε με τη βοήθεια ενός μονοδιάστατου πίνακα Ν θέσεων. Για να τη διαχειριστούμε, χρειαζόμαστε μία βοηθητική μεταβλητή-δείκτη με την ονομασία top, η οποία δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στη στοίβα, δηλαδή δείχνει το στοιχείο που υπάρχει στην κορυφή της. Στο διπλανό σχήμα χρησιμοποιούμε έναν πίνακα Ν θέσεων για τη δημιουργία μιας στοίβας, η οποία έχει μέσα δύο στοιχεία. Η μεταβλητή τορ έχει την τιμή 2 και δείχνει την κορυφή της στοίβας.

Ν []
• []
• []
3[]
2[Β] <-top=2
1[Α]
Υλοποιηση στοίβας με πίνακα

Question 7

233. Να δώσετε τον ορισμό της δομής δεδομένων «Ουρά».

Answer 7

Ουρά ονομάζεται μια δομή δεδομένων στην οποία το σύνολο των στοιχείων είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που τοποθετήθηκαν πρώτα στην ουρά να λαμβάνονται επίσης πρώτα.

Question 8

234. Ποια μέθοδο επεξεργασίας δεδομένων χρησιμοποιεί η δομή δεδομένων «Ουρά»;

Answer 8

Απάντηση:

Τη μέθοδο Πρώτο Μέσα, Πρώτο Έξω, ή αλλιώς FIFO, από τα αρχικά των λέξεων «First In First Out». Κατά τη μέθοδο αυτήν το δεδομένο που εισάγεται πρώτο, είναι αυτό που εξάγεται πρώτο. Αντίθετα, το δεδομένο που βρίσκεται στο τέλος της ουράς είναι και αυτό που εξάγεται τελευταίο.

Question 9

235. Ποιες είναι οι κύριες λειτουργίες στη δομή δεδομένων «Ουρά»;

Answer 9

Στη δομή δεδομένων ουρά χρησιμοποιούνται δύο λειτουργίες:

•η εισαγωγή (enqueue) ενός στοιχείου στο πίσω άκρο της ουράς και

•η εξαγωγή (dequeue) ενός στοιχείου από το μπροστινό άκρο της ουράς.

Question 10

236. Τι πρέπει να προσέχουμε κατά την εκτέλεση της λειτουργίας της εισαγωγής ενός στοιχείου στην «Ουρά》

Answer 10

Κατά την εκτέλεση της λειτουργίας της εισαγωγής ενός στοιχείου στην ουρά, πρέπει να εξετάζουμε αν υπάρχει διαθέσιμος χώρος στην ουρά (να μην είναι γεμάτη), για να τοποθετήσουμε το στοιχείο σε αυτήν.

Question 11

237. Τι πρέπει να προσέχουμε κατά την εκτέλεση της λειτουργίας της εξαγωγής ενός στοιχείου από την «Ουρά»;

Answer 11

Απάντηση:

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

Question 12

238. Να εξηγήσετε πώς γίνεται η υλοποίηση της δομής δεδομένων «Ουρά» με τη βοήθεια ενός μονοδιάστατου πίνακα.

Answer 12

Τη δομή δεδομένων «Ουρά» μπορούμε να την υλοποιήσουμε με τη βοήθεια ενός μονοδιάστατου πίνακα Ν θέσεων και για να τη διαχειριστούμε, θα χρησιμοποιήσουμε δύο δείκτες: τον δείκτη «εμπρός (front)», που δείχνει το πρώτο στοιχείο της ουράς, και τον δείκτη «πίσω (rear)», που δείχνει το τελευταίο στοιχείο της ουράς. Αν στην ουρά έχουν εισαχθεί τα στοιχεία 50, 70, 90, τότε η κατάσταση της ουράς και οι τιμές των δεικτών απεικονίζονται δίπλα.

1. 2. 3. 4. ……….. Ν
            [50][70][90][] [ ][]
            ^ ^
            | |
            Front =1 rear=3

Question 13

239. Τι είναι η «διεύθυνση επιστροφής» κατά την κλήση ενός υποπρογράμματος,

Answer 13

Απάντηση:

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

Question 14

240. Τι είναι η «στοίβα χρόνου εκτέλεσης»;

Answer 14

Απάντηση:

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

Question 15

241. Ποιες δομές δεδομένων γνωρίζετε, στις οποίες οι κόμβοι δεν είναι απαραίτη το να κατέχουν συνεχόμενες θέσεις μνήμης;

Answer 15

Απάντηση:

Δομές δεδομένων, στις οποίες οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης είναι οι λίστες, τα δέντρα και οι γράφοι.

Question 16

242. Οι δομές δεδομένων, λίστες, δέντρα και οι γράφοι είναι στατικές ή δυναμικές δομές δεδομένων;

Answer 16

Γνωρίζουμε ότι τα στοιχεία των δυναμικών δομών δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης. Επειδή, στις λίστες, τα δέντρα και στους γράφους, οι κόμβοι από τους οποίους αποτελούνται δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης, μπορούμε να πούμε ότι είναι δυναμικές δομές δεδομένων.

Question 17

243. Τι είναι μια συνδεδεμένη λίστα;

Answer 17

Απάντηση:

Μια «συνδεδεμένη λίστα» είναι ένα σύνολο κόμβων που συνήθως βρίσκονται σε απομακρυσμένες θέσεις μνήμης και είναι γραμμικά διατεταγμένοι (ο ένας μετά τον άλλον).

Question 18

244. Η «λίστα» είναι γραμμική ή μη γραμμική δομή δεδομένων;

Answer 18

Απάντηση:

Η λίστα είναι γραμμική δομή δεδομένων γιατί τα δεδομένα της ακολουθούν μια σειρά, δηλαδή, ο δεύτερος κόμβος θα είναι πάντα μετά τον πρώτο κόμβο και πριν από τον τρίτο κόμβο κ.ο.κ. (ισχύει η σχέση της συνεχόμενης λογικής γειτονικότητας των στοιχείων της).

Question 19

245. Τι είναι ένας «δείκτης» γενικά στον προγραμματισμό;

Answer 19

Απάντηση:

Ο δείκτης γενικά, είναι ένας ιδιαίτερος τύπος δεδομένων που προσφέρεται στις σύγχρονες γλώσσες προγραμματισμού. Δεν λαμβάνει αριθμητικές τιμές όπως ακέραιες πραγματικές, αλλά οι τιμές που λαμβάνει, είναι διευθύνσεις στην κύρια μνήμη και χρησιμοποιείται για τη σύνδεση των διαφόρων στοιχείων μιας δομής που είναι αποθηκευμένα σε μη συνεχόμενες θέσεις μνήμης.

Question 20

246. Πότε μια λίστα λέμε ότι είναι απλά συνδεδεμένη;

Answer 20

Απάντηση:

Μία λίστα είναι απλά συνδεδεμένη όταν μπορούμε να κινηθούμε σε αυτήν προς μια κατεύθυνση ξεκινώντας πάντα από τον πρώτο κόμβο και μετακινούμενοι προς τον τελευταίο.

Question 21

247. Από τι αποτελείται ένας κόμβος στην απλά συνδεδεμένη λίστα;

Answer 21

Ένας κόμβος μιας λίστας αποτελείται από δύο τμήματα (πεδία) και η δομή του είναι

Το πρώτο τμήμα είναι το πεδίο «Δεδομένα», το οποίο περιέχει τα δεδομένα και το δεύτερο είναι το πεδίο «Δείκτης», το οποίο φιλοξενεί τη διεύθυνση του επόμενου κόμβου με τον οποίο συνδέεται, δηλαδή περιέχει έναν δείκτη (pointer) που δείχνει στον επόμενο κόμβο.

Δεδομένα | Δείκτης |

Question 22

247. Από τι αποτελείται ένας κόμβος στην απλά συνδεδεμένη λίστα;

Answer 22

Ένας κόμβος μιας λίστας αποτελείται από δύο τμήματα (πεδία) και η δομή του είναι

Το πρώτο τμήμα είναι το πεδίο «Δεδομένα», το οποίο περιέχει τα δεδομένα και το δεύτερο είναι το πεδίο «Δείκτης», το οποίο φιλοξενεί τη διεύθυνση του επόμενου κόμβου με τον οποίο συνδέεται, δηλαδή περιέχει έναν δείκτη (pointer) που δείχνει στον επόμενο κόμβο.

Δεδομένα | Δείκτης |

Question 23

248. α. Τι τιμές λαμβάνει το κάθε ένα πεδίο, ενός κόμβου μιας απλά συνδεδε μένης λίστας;

β. Γιατί χρησιμοποιείται το πεδίο «Δείκτης» μιας απλά συνδεδεμένης λίστας και πως τον απεικονίζουμε;

Answer 23

Το πεδίο «Δεδομένα» μπορεί να περιέχει μία ή περισσότερες αλφαριθμητικές ή αριθμητικές πληροφορίες. Το πεδίο «Δείκτης» δεν λαμβάνει αριθμητικές τιμές (ακέραιες, πραγματικές), αλλά οι τιμές του είναι διευθύνσεις στην κύρια μνήμη και συγκεκριμένα φιλοξενεί τη διεύθυνση του επόμενου κόμβου με τον οποίο συν δέεται, δηλαδή περιέχει έναν δείκτη (pointer) που δείχνει στον επόμενο κόμβο.

β. Το πεδίο «Δείκτης» χρησιμοποιείται για τη σύνδεση των στοιχείων (κόμβων) της λίστας που είναι αποθηκευμένα σε μη συνεχόμενες θέσεις μνήμης, δείχνοντας τον επόμενο κόμβο της λίστας. Τον απεικονίζουμε συμβολικά με ένα βέλος για να δηλώσουμε τη σύνδεση μεταξύ του προηγούμενου και το επόμενου κόμβου.

Question 24

249. Τι είναι η μεταβλητή/δείκτης «Κεφαλή» σε μια απλά συνδεδεμένη λίστα;

Answer 24

Απάντηση:

Για να προσπελάσουμε τους κόμβους μιας λίστας πρέπει να γνωρίζουμε τη διεύθυνση δηλαδή τη θέση μνήμης του πρώτου κόμβου της λίστας. Η διεύθυνση αυτή αποθηκεύεται σε μια ειδική μεταβλητή που ονομάζεται «Κεφαλή». Έτσι ο δείκτης/μεταβλητή «Κεφαλή (Head)» δείχνει στον πρώτο κόμβο μιας λίστας, δηλαδή περιέχει τη διεύθυνση του πρώτου κόμβου της λίστας.

Question 25

250. Τι τιμή έχει το πεδίο «Δείκτης» του τελευταίου κόμβου μιας απλά συν δεδεμένης λίστας;

Answer 25

Απάντηση:

Ο δείκτης του τελευταίου κόμβου μιας λίστας δε δείχνει σε κάποιον κόμβο, στην ουσία είναι ένας δείκτης στο κενό. Για να το δηλώσουμε αυτό λέμε ότι το πεδίο δείκτη του τελευταίου κόμβου έχει την τιμή NULL και τον αναπαριστούμε με το σύμβολο «●»,

Question 26

251. Να δώσετε ένα παράδειγμα μιας απλά συνδεδεμένης λίστας.

Answer 26

Απάντηση:

Στο παρακάτω σχήμα παρουσιάζεται μια απλά συνδεδεμένη λίστα με πέντε κόμβους που περιέχει ακέραιους αριθμούς.

[Κεφαλή]-
👇
[7][] ->[1][]->[9][]->[3][]->[5][●]

Στον δείκτη «Κεφαλή» υπάρχει η διεύθυνση του πρώτου κόμβου της λίστας. Σε κάθε κόμβο,στο πεδιο 《δεδομένο» υπάρχει ένας ακέραιος αριθμός που ειναι η αριθμητική πληροφορία που περιέχει και στο πεδίο «Δείκτης» περιέχεται η διεύθυνση του επόμενυ κομβου η οποία απεικονίζεται συμβολικά με ένα βέλος, ώστε να δείχει τη σύνδεση μεταξύ του προηγούμενου και το επόμενου κόμβου. Έτσι, στον πρώτο κόμβο, το πεδίο «Δεδομένο» περιέχει τον αριθμό 7 και ο δείκτης του πρώτου κόμβου δειχνει τον δεύτερο. Στον δεύτερο κόμβο, το πεδίο «Δεδομένο» περιέχει τον αριθμό 1 και ο δείκτης του δεύτερου κόμβου δειχνει στη διευθυνση του τριτου κκμβου κοκ. Ο δεικτης του τελευταιου κομβου εχει ως τιμη το NULL (σύμβολο «●») καθώς δεν δείχνει σε κάποιον επόμενο κόμβο

Question 27

252. Να εξηγήσετε πως γίνεται η προσπέλαση στους κόμβους μιας απλά συν δεδεμένης λίστας.

Answer 27

Απάντηση:

Οι κόμβοι μιας συνδεδεμένης λίστας δεν έχουν ονόματα και το μόνο που γνωρίζουμε για αυτούς είναι οι διευθύνσεις τους οι οποίες είναι αποθηκευμένες στους προηγούμενους κόμβους. Για να προσπελάσουμε τους κόμβους της λίστας αξιοποιούμε αυτές τις διευθύνσεις. Άμεση πρόσβαση έχουμε μόνο στον πρώτο κόμβο της λίστας μέσω της διεύθυνσης του η οποία βρίσκεται στον δείκτη «Κεφαλή». Για να εντοπίσουμε κάποιον από τους ενδιάμεσους κόμβους, ξεκινάμε από τον πρώτο κόμβο και ακολουθούμε τους δείκτες με τη σειρά μέχρι να φτάσουμε στον επιθυμητό κόμβο.

Question 28

253. Πως μπορούν να αξιοποιηθούν οι συνδεδεμένες λίστες;

Answer 28

Απάντηση:

Οι συνδεδεμένες λίστες μπορούν να αξιοποιηθούν για την υλοποίηση της στοίβας και της ουράς λόγω της δυνατότητας αυξομείωσης του μεγέθους τους.

Question 29

254. Πότε μια λίστα λέμε ότι είναι διπλά συνδεδεμένη;

Answer 29

Απάντηση:

Μία λίστα είναι διπλά συνδεδεμένη όταν μπορούμε να κινηθούμε σε αυτήν και προς τις δύο κατευθύνσεις.

Question 30

255. Πόσους δείκτες χρησιμοποιεί η διπλά συνδεδεμένη λίστα και γιατί;

Answer 30

Απάντηση:

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

Question 31

256. Από τι αποτελείται ένας κόμβος στη διπλά συνδεδεμένη λίστα;

Answer 31

Απάντηση:

Ένας κόμβος μιας διπλά συνδεδεμένης λίστας αποτελείται από τρία τμήματα (πεδία) και η δομή του είναι:

[Δείκτης Προηγούμενο][Δεδομένα][Δείκτης Επόμενο]

Στο πρώτο τμήμα υπάρχει ο δείκτης που δείχνει στον προηγούμενο κόμβο ακολουθεί το πεδίο «Δεδομένα», το οποίο περιέχει τα δεδομένα και έπειτα είναι ο δείκτης που δείχνει στον επόμενο κόμβο.

Question 32

257. Να δώσετε ένα παράδειγμα μιας διπλά συνδεδεμένης λίστας.

Answer 32

Απάντηση:

Στο παρακάτω σχήμα παρουσιάζεται μια διπλά συνδεδεμένη λίστα με τρείς κόμβους που περιέχει ακέραιους αριθμούς

[Κεφαλη]-> [●][10][]<=>[][6][]<=>[][9][●]<-[ουρα]

Στον δείκτη «Κεφαλή» υπάρχει η διεύθυνση του πρώτου κόμβου της λίστας. Στον πρώτο κόμβο ο δείκτης που δείχνει τον προηγούμενο κόμβο έχει ως τιμή το NULL (σύμβολο «●») καθώς δεν υπάρχει προηγούμενος κόμβος. Στον τελευταίο κόμβος ο δείκτης που δείχνει τον επόμενο κόμβο έχει ως τιμή το NULL (σύμβολο «●») καθώς δεν υπάρχει επόμενος κόμβος. Κάθε ενδιάμεσος κόμβος έχει δύο δείκτες, έναν που δείχνει στον προηγούμενο και έναν που δείχνει στον επόμενο κόμβο. Στον δείκτη «Ουρά» υπάρχει η διεύθυνση του τελευταίου κόμβου της λίστας.

Question 33

258. Τι πρόβλημα δημιουργεί η χρήση μιας διπλά συνδεδεμένης λίστας;

Answer 33

Απάντηση:

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

Question 34

259. Ποιες βασικές πράξεις μπορούν να γίνουν στις συνδεδεμένες λίστες; Απάντηση:

Answer 34

Οι βασικές πράξεις των συνδεδεμένων λιστών είναι:

Εισαγωγή κόμβου στη λίστα. Η εισαγωγή μπορεί να γίνει στην αρχή, στο τέλος ή στο ενδιάμεσο της λίστας.

Διαγραφή κόμβου από τη λίστα. Η διαγραφή μπορεί να γίνει στην αρχή, στο τέλος ή στο ενδιάμεσο της λίστας.

Έλεγχος αν η λίστα είναι κενή.

Αναζήτηση κόμβου για να βρεθεί ένα συγκεκριμένο στοιχείο.

Διάσχιση της λίστας και προσπέλαση των στοιχείων της. Παράδειγμα η εκτύπωση των δεδομένων που περιέχονται σε όλους τους κόμβους της λίστας.

Question 35

260. Ποιες διαφορές υπάρχουν μεταξύ απλών και διπλών συνδεδεμένων λιστών;

Answer 35

Απάντηση:

Οι βασικές διαφορές είναι:

Στην απλά συνδεδεμένη λίστα κάθε κόμβος συνδέεται μόνο με τον αμέσως επόμενο κόμβο, εκτός, από τον τελευταίο κόμβο. Στη διπλά συνδεδεμένη λίστα, κάθε κόμβος συνδέεται με τον αμέσως επόμενο και τον αμέσως προηγούμενο κόμβο, εκτός, από τον αρχικό κόμβο που συνδέεται μόνο με τον επόμενο και εκτός από τον τελευταίο κόμβο που συνδέεται μόνο με τον προηγούμενο,

Στην απλά συνδεδεμένη λίστα μπορούμε να κινηθούμε προς μία μόνο κατεύθυνση, ξεκινώντας από τον πρώτο κόμβο και μετακινούμενοι προς τον τελευταίο, Στη διπλά συνδεδεμένη μπορούμε κινηθούμε και προς τις δύο κατευθύνσεις, είτε ξεκινώντας από τον πρώτο κόμβο και μετακινούμενοι προς τον τελευταίο κόμβο είτε από τον τελευταίο μετακινούμενοι προς τον πρώτο κόμβο της λίστας.

Question 36

261. Ποιες διαφορές υπάρχουν ως προς τον τρόπο προσπέλασης (εισαγωγή και εξαγωγή στοιχείων) μεταξύ λίστας, στοίβας και ουράς,

Answer 36

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

Μια άλλη διαφορά εντοπίζεται στην εξαγωγή στοιχείου. Στη στοίβα ένα στοιχείο μπορεί να εξέλθει μόνο από την κορυφή (λειτουργία απώθηση), ενώ στην ουρά ένα στοιχείο μπορεί να εξέλθει μόνο από την αρχή της (λειτουργία εξαγωγή). Στη λίστα ένα στοιχείο (κόμβος) μπορεί να διαγραφεί από οποιοδήποτε σημείο της (αρχή, τέλος ή ενδιάμεσα).
.

Question 37

262. Ποιες σημαντικές διαφορές υπάρχουν μεταξύ της δομής δεδομένων «Πινακα» και της δομής δεδομένων «Λίστα»;

Answer 37

Απάντηση:

Οι διαφορές μεταξύ ενός «Πίνακα» και μιας «Λίστας» είναι:

Στον τρόπο προσπέλασης. Ο πίνακας θεωρείται μια δομή τυχαίας προσπέλασης καθώς μπορούμε να προσπελάσουμε οποιοδήποτε στοιχείο (κόμβο) του κατευθείαν. Η λίστα αντίθετα είναι μια δομή σειριακής ή ακολουθιακής προσπέλασης, δηλαδή για να φθάσουμε σε έναν κόμβο πρέπει να περάσουμε όλους τους προηγούμενους ξεκινώντας από τον πρώτο.

Στο μέγεθος. Ο πίνακας επειδή είναι στατική δομή, έχει σταθερός μέγεθος το οποίο δηλώνεται εξαρχής κατά την υλοποίηση του. Η λίστα είναι δυναμική δομή και το μέγεθος της μεταβάλλεται καθώς εισάγονται νέοι κόμβοι σε αυτήν ή δια γράφονται κάποιοι άλλοι

Στην αποθήκευση. Τα στοιχεία ενός πίνακα αποθηκεύονται σε συνεχόμενες θέσεις μνήμης ενώ οι κόμβοι της λίστας αποθηκεύονται σε μη συνεχόμενες θέσεις μνήμης.

Question 38

263.

Να αναφέρετε τα πλεονεκτήματα της δομής δεδομένων της «Λίστας» έναντι της δομής δεδομένων του «Πίνακα».

Answer 38

Απάντηση:

Τα πλεονεκτήματα της «Λίστας» σε σχέση με τον «Πίνακα» είναι:

Το δυναμικό της μέγεθος.

Η ευκολία στην εισαγωγή και στη διαγραφή από οποιοδήποτε μέρος της.

Η μη αναγκαιότητα δήλωσης του μεγέθους της.

Question 39

264. Να αναφέρετε τα μειονεκτήματα της δομής δεδομένων της «Λίστας» έναντι της δομής δεδομένων του «Πίνακα».

Απάντηση:

Answer 39

Τα μειονεκτήματα της «Λίστας» σε σχέση με τον «Πίνακα» είναι:

Δεν επιτρέπεται η τυχαία προσπέλαση στη «Λίστα». Δεν μπορούμε να φτάσουμε σε έναν συγκεκριμένο κόμβο μιας λίστας χωρίς να μην έχουμε περάσει διαδοχικά από όλους τους προηγούμενους. Στην περίπτωση της απλά συνδεδεμένης λίστας ξεκινάμε από τον πρώτο και διαδοχικά περνάμε από όλους τους κόμβους μέχρι να φτάσουμε στον επιθυμητό. Ενώ στην περίπτωση της διπλά συνδεδεμένης λίστας μπορούμε να ξεκινήσουμε και από τον τελευταίο κόμβο. Έτσι δεν μπορούμε να πραγματοποιήσουμε με αποτελεσματικό τρόπο δυαδική αναζήτηση σε συνδεδεμένες λίστες

Οι συνδεδεμένες λίστες έχουν μεγαλύτερη επιβάρυνση από τους πίνακες. Οι συνδεδεμένοι κόμβοι είναι δυναμικά κατανεμημένοι και κάθε κόμβος πρέπει να αποθηκεύσει έναν πρόσθετο δείκτη που δείχνει στον επόμενο κόμβο με αποτέλεσμα να είναι λιγότερο αποτελεσματικοί στη χρήση της μνήμης. Μάλιστα στην περίπτωση των διπλά συνδεδεμένων λιστών χρειάζεται να αποθηκεύεται για κάθε κόμβο και ένας επιπλέον δεύτερος δείκτης που δείχνει στον προηγούμενο κόμβο.

Question 40

. Τι είναι η δομή δεδομένων «δένδρο»;

Answer 40

Απάντηση:

Ένα «δένδρο» είναι μια δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων.

Question 41

266. Τι ονομάζουμε «γονέα» στη δομή δένδρο;

Answer 41

Απάντηση:

Όταν δύο κόμβοι συνδέονται μεταξύ τους με μία ακμή, ονομάζουμε «γονέα» τον κόμβο από τον οποίο ξεκινάει η ακμή.

Question 42

267. Τι ονομάζουμε «παιδί» στη δομή δένδρο;

Answer 42

Απάντηση:

Όταν δύο κόμβοι συνδέονται μεταξύ τους με μία ακμή, ονομάζουμε «παιδί» τον κόμβο στον οποίο καταλήγει η ακμή.

Question 43

268. Τι ονομάζουμε «ρίζα» στη δομή δένδρο;

Answer 43

Απάντηση:

Ο κόμβος που δεν έχει γονέα ονομάζεται «ρίζα» και βρίσκεται στην κορυφή του δένδρου.

Question 44

269. Ποιοι κόμβοι ονομάζονται «αδέλφια» στη δομή δένδρο;

Answer 44

Απάντηση:

Οι κόμβοι που έχουν τον ίδιο γονέα ονομάζονται «αδέλφια»,

Question 45

270. Ποιοι κόμβοι ονομάζονται «φύλλα» στη δομή δένδρο;

Answer 45

Απάντηση:

Οι κόμβοι που δεν έχουν παιδιά ονομάζονται «φύλλα».

Question 46

271. Μπορούμε να έχουμε δένδρο με έναν μόνο κόμβο;

Answer 46

Απάντηση:

Ναι μπορούμε να έχουμε ένα απλό δένδρο με ένα μόνο κόμβο, ο οποίος κόμβος είναι «ρίζα» του δένδρου καθώς δεν έχει γονέα αλλά και «φύλλο» διότι δεν έχει παιδιά.

Question 47

272. Ποιοι κανόνες ισχύουν στη δομή «δένδρο»;

Answer 47

Απάντηση:

Ένα δένδρο είναι μία δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων με βάση τους εξής κανόνες:

Υπάρχει ένας ξεχωριστός κόμβος που ονομάζεται ρίζα. Αυτός είναι ένας κόμβος χωρίς γονέα.

Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c είναι το παιδί του p

Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή, μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο.

Question 48

. Τι είναι το «κενό δένδρο»;

Answer 48

Απάντηση:

«Κενό δένδρο» είναι το δένδρο που δεν έχει ούτε κόμβους ούτε ακμές και είναι το μόνο που δεν έχει ρίζα.

Question 49

274. Τι είναι τα «υποδένδρα»;
     ,

Answer 49

Απάντηση:

Τα «υποδένδρα» είναι μικρότερα δένδρα που μπορούμε να εντοπίσουμε μέσα σε ένα δένδρο.

Question 50

275. Τι είναι το «διατεταγμένο δένδρο»;

Answer 50

Απάντηση:

«Διατεταγμένο δένδρο» είναι το δένδρο στο οποίο για κάθε κόμβο υπάρχει μια γραμμική σχέση μεταξύ των παιδιών του κόμβου αυτού, δηλαδή έχει σημασία η διάταξη των παιδιών κάθε κόμβου.

Question 51

276. Το «δένδρο» είναι γραμμική ή μη γραμμική δομή δεδομένων;

Answer 51

Απάντηση:

Το δένδρο είναι μη γραμμική δομή δεδομένων, καθώς τα δεδομένα δεν ακολουθούν μια σειρά. Δηλαδή, σε ένα δένδρο που περιλαμβάνει τους κόμβους x1, x2, x3, οι κόμβοι δεν θα είναι πάντα σε μια σειρά τέτοια ώστε ο κόμβος x2 να είναι πάντα μετά τον κόμβο χ1 και πριν από τον κόμβο χ3, αλλά μπορούν να έχουν οποιαδήποτε διάταξη και μετά από έναν κόμβο να υπάρχουν περισσότεροι από ένας κόμβοι.

Question 52

277. Τα «δένδρα» σε ποιους τομείς της επιστήμης των υπολογιστών χρησιμοποιούνται;

Answer 52

Απάντηση:

Τα δένδρα είναι μια ευέλικτη δομή δεδομένων που χρησιμοποιούνται σε πολλούς τομείς της επιστήμης των υπολογιστών, όπως των γραφικών, των συστημάτων βάσεων δεδομένων, των λειτουργικών συστημάτων, των παιχνιδιών, της τεχνητής νοημοσύνης και της δικτύωσης υπολογιστών.

Question 53

278. α. Για ποιους λόγους η δομή δεδομένων «δένδρο» είναι τόσο ισχυρή; Να αναφέρετε αντίστοιχο παράδειγμα.

β. Τι προσφέρει η δομή δεδομένων «δένδρο»;

Answer 53

Απάντηση:

Η δομή δεδομένων « δένδρο» είναι ισχυρή για δύο λόγους:

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

Ο δεύτερος βασικός λόγος είναι ότι η δομή των δένδρων μεταφέρει πληροφορίες.

β. Η δομή δεδομένων «δένδρο» προσφέρει μια αποτελεσματική οργάνωση και διαχείριση δεδομένων

Question 54

Τα δένδρα αποτελούν τη βάση αρκετών αλγορίθμων. Να αναφέρετε ορισμένους από αυτούς.

Answer 54

Απάντηση:

Τα δένδρα αποτελούν τη βάση αρκετών αλγορίθμων επίλυσης προβλήματος, όπως είναι η συμπίεση εικόνων, η ταξινόμηση, η αυτόματη συμπλήρωση λέξεων σε συσκευές κινητων τηλεφώνων, η μεταγλώττιση ενός προγράμματος και η λήψη αποφάσεων.

Question 55

280. α. Τι είναι τα «δένδρα απόφασης»;

β. Που χρησιμοποιούνται;

γ. Να δώσετε ένα παράδειγμα σχεδιασμού ενός δένδρου απόφασης.

Answer 55

Απάντηση:

Τα δένδρα απόφασης, είναι δένδρα στα οποία κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό (ιδιότητα), κάθε ακμή αντιπροσωπεύει μια απόφαση (κανόνα) και κάθε φύλλο αντιπροσωπεύει ένα αποτέλεσμα.

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

Question 56

281. Τι είναι το «δένδρο παιχνιδιού» και που χρησιμοποιείται;

Answer 56

Απάντηση:

Το δένδρο παιχνιδιού είναι ένα ειδικό δένδρο που χρησιμοποιείται από τον υπολογιστή όταν παίζουμε παιχνίδια σε αυτόν, όπως είναι το σκάκι, η τρίλιζα, το τάβλι και άλλα, το οποίο μοντελοποιεί όλες τις πιθανές κινήσεις των παικτών για να βρει τον νικητή. Κάθε κόμβος στο δένδρο, θα μπορούσε να αντιπροσωπεύει μία συγκεκριμένη κατά σταση παιχνιδιού, να περιέχει πληροφορίες σχετικά με το ποιος παίκτης έχει τη μεγα λύτερη πιθανότητα να κερδίσει από οποιαδήποτε πιθανή κίνηση.

Question 57

282. Μπορεί η δομή «δένδρο» να χρησιμοποιηθεί για αναπαράσταση αριθμη τικών εκφράσεων;

Answer 57

Απάντηση:

Η δομή «δένδρο» μπορεί να χρησιμοποιηθεί για την αναπαράσταση και κατ’ επέκταση τον υπολογισμό αριθμητικών εκφράσεων.

Παράδειγμα το διπλανό δέντρο αναπαριστά την αριθμητική έκφραση α*(β + γ).

(*)
👇 👇
(α) (+)
👇👇
(β)(γ)

Question 58

283. Τι ονομάζεται «δυαδικό δένδρο»;

Answer 58

Απάντηση:

Ένα «δυαδικό δένδρα» είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξί παιδί δηλαδή μιλάμε για αριστερό και δεξιό υποδένδρο ενός κόμβου.

Question 59

284. Τι είναι ένα «δυαδικό δένδρο αναζήτησης

Answer 59

Ενα «δυαδικό δένδρο αναζήτησης» είναι ένα δυαδικό δένδρο, όπου για κάθε κόμβο u, όλοι οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες της τιμής του κόμβου u και όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες τη ίσες) της τιμής του κόμβου u.

.

Question 60

285. Πού χρησιμοποιούνται τα «δυαδικά δένδρα αναζήτησης»;

Answer 60

Απάντηση:

Τα «δυαδικά δένδρα αναζήτησης» χρησιμοποιούνται για να αποθηκεύσουμε δεδομένα με έναν τρόπο που θα μας επιτρέψει να τα βρίσκουμε πιο εύκολα. Η ιδέα πίσω από ένα δυαδικό δένδρο αναζήτησης είναι παρόμοια με αυτήν της δυαδικής ανα ζήτησης σε έναν ταξινομημένο πίνακα.

Για παράδειγμα, οι αλγόριθμοι της αναζήτησης όλων των email που έχουμε λάβει ή στείλει σε μία συγκεκριμένη περίοδο ή της εύρεσης όλων των λέξεων, που αρχίζουν από την συμβολοσειρά «πληρ», αξιοποιούν τα δυαδικά δένδρα αναζήτησης.

Question 61

286. Ποιο είναι το πλεονέκτημα των «δυαδικών δένδρων αναζήτησης»;

Answer 61

Απάντηση:

Το πλεονέκτημα των «δυαδικών δένδρων αναζήτησης» βρίσκεται στον τρόπο αναζήτησης καθώς η αναζήτηση για μια συγκεκριμένη τιμή γίνεται ταχύτερα χάρη στον τρόπο αποθήκευσης των τιμών.

Question 62

287. Τι είναι ένας «γράφος»;

Answer 62

Απάντηση:

Ένας «γράφος» είναι μία δομή που αποτελείται από ένα σύνολο κόμβων (ή σημείων ή κορυφών) και ένα σύνολο γραμμών (ή ακμών ή τόξων) που ενώνουν ορι σμένους ή όλους τους κόμβους.

Question 63

288. Γιατί ο «γράφος» αποτελεί την πιο γενική δομή δεδομένων;

Answer 63

Απάντηση:

Ο «γράφος» αποτελεί την πιο γενική δομή δεδομένων, γιατί όλες οι προηγού μενες δομές, δηλαδή οι λίστες και τα δένδρα, μπορούν να θεωρηθούν περιπτώσεις γράφων.

Question 64

289. Ο «γράφος» είναι γραμμική ή μη γραμμική δομή δεδομένων;

Answer 64

Απάντηση:

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

Question 65

290. Ποια είναι τα χαρακτηριστικά της δομής «γράφος»;

Answer 65

Απάντηση:

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

Question 66

α. Ποια είδη ακμών υπάρχουν σε έναν γράφο;

β. Ποιες είναι οι διαφορές τους;

γ. Γιατί η διαφοροποίηση τους είναι σημαντική;

Answer 66

Απάντηση:

Σε έναν γράφο μπορούν να υπάρχουν δύο είδη ακμών.

•οι κατευθυνόμενες ακμές, δηλαδή οι ακμές που έχουν κατεύθυνση και

•οι μη κατευθυνόμενες ακμές, δηλαδή οι ακμές που δεν έχουν κατεύθυνση.

β. Σε μια κατευθυνόμενη ακμή, οι δύο κόμβοι συνδέονται με συγκεκριμένο τρόπο όπως φαίνεται δίπλα και μπορούμε να ταξιδέψουμε μεταξύ αυτών των δύο κόμβων με έναν μόνο τρόπο, από τον κόμβο Α στον κόμβο Β. Ο κόμβος από τον οποίο ξεκινάμε ονομάζεται «προέλευση» και ο κόμβος στον οποίο ταξιδεύουμε ονομάζεται «προορισμός». Σε μια κατευθυνόμενη ακμή, μπορούμε να ταξιδέψουμε μόνο από την προέλευση στον προορισμό και ποτέ το αντίστροφο.
(Α)—>(Β) !κατευθυνομενη ακμή
Σε μια μη κατευθυνόμενη ακμή, όπως αυτή που φαίνεται δίπλα, η διαδρομή μεταξύ των δύο κόμβων είναι αμφίδρομη, πράγμα που σημαίνει ότι οι κόμβοι προέλευσης και προορισμού δεν είναι σταθεροί. Έτσι μπορούμε να ταξιδέψουμε είτε από τον κόμβο Α προς τον κόμβο Β, είτε από τον κόμβο Β προς τον κόμβο Α.
(Α)——(β) !μη κατευθυνομενη ακμή

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

Question 67

292. Ποιοι τύποι γράφων υπάρχουν;

Answer 67

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

Question 68

293. Ποιες είναι οι διαφορές ανάμεσα στη δομή «δένδρο» και στη δομή «γράφος»;

Answer 68

Απάντηση:

○Τα δένδρα ξεκινούν πάντα με έναν κόμβο-ρίζα ενώ στους γράφους δεν υπάρχει η έννοια του κόμβου ρίζα καθώς οι κόμβοι μπορούν να συνδεθούν με οποιον δήποτε τρόπο.

○Τα δένδρα, διέπονται από συγκεκριμένους κανόνες ενώ σε ορισμένα ισχύουν ιδιαίτεροι κανόνες, όπως στα δυαδικά δένδρα αναζήτησης, στα οποία οι κόμβοι μπορεί να έχουν μέχρι δύο συνδέσεις με δύο κόμβους ανά πάσα στιγμή. Αντίθετα οι γράφοι δεν διέπονται από κανόνες που να καθορίζουν τον τρόπο που ο ένας κόμβος συνδέεται με έναν άλλο κόμβο.

○Ένα δένδρο πάντα έχει ακμές με κατεύθυνση και μπορεί μόνο να ρέει προς μία κατεύθυνση από τον κόμβο ρίζα σε κόμβους φύλλων ή κόμβους παιδιών (μονοκατευθυντικη ροη)Αντίθετα ένας γράφος μπορεί να έχει ακμές με κατεύθυνση ή και χωρίς κατεύθυνση.

○Η δομή δένδρο έχει μόνο μονόδρομες συνδέσεις, δηλαδή ένας κόμβος παιδιού μπορεί να έχει μόνο έναν γονέα. Αντίθετα η δομή γράφος έχει αμφίδρομες συνδέσεις επιτρέποντας την μετακίνηση από έναν κόμβο σε έναν άλλο και αντίστροφα.

○Ένα δένδρο δεν μπορεί να έχει βρόχους ή κυκλικούς δεσμούς σε αντίθεση με τον γράφο που επιτρέπεται η δημιουργία βρόχων.

○Σε κάθε κόμβο ενός γράφου μπορούν να καταλήγουν, μία ή περισσότερες ακμές ενώ σε κάθε κόμβου ενός δένδρου καταλήγει πάντα μία μόνο ακμή.