ΔΔΑ(Δεντρο δυαδικης αναζητησης)

Ξεκίνησε από Milspil, 16 Ιουν 2017, 03:30:32 ΠΜ

« προηγούμενο - επόμενο »

Milspil

Καλησπερα σας.Ειμαι πρωτοετης φοιτητης στο τμημα ναυτιλιας στην Χιο και εχω καποιες αποριες σχετικα με το μαθημα της πληροφορικης  για την εξεταστικη μου.Συγκεκριμενα εχω 2 αποριες πανω σε κατι ασκησεις.Δεν παρακολουθουσα το μαθημα και προσπαθοντας να διαβασω λιγο μονος μου μεσω google δεν καταφερα και πολλα.Ειμαι μελος απο οταν πηγαινα τριτη λυκειου και απο οσο θυμαμαι,δεν επιτρεπεται να ζητησω να μου λυσετε την ασκηση,αλλα εχω το δικαιωμα να ανεβασω αυτο που εχω κανει μονος και αν υπαρχει λαθος να με διορθωσει καποιος.Επομενως παραθετω τις 2 ασκησεις με τις λυσεις τους(τις δικες μου) και θα ημουν ευγνωμων αν καποιος με βοηθουσε λιγακι.
Ασκηση 1:Να δημιουργήσετε ένα ζυγισμένο δέντρο δυαδικής αναζήτησης με στοιχεία τους παρακάτω αριθμους:3,31,45,27,56,39,23.
Ασκηση 2:Να αποτυπώσετε την αριθμητική παράσταση 7^2*(4+3)/2+7*(5-9) σε μορφή δέντρου με τους τελεστές στους κόμβους και τους αριθμούς στα φύλλα.

odysseas

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

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

Για ένα παράδειγμα μπορείς να δεις το σχετικό λήμμα στη Wikipedia ή απλά να αναζητήσεις για binary search tree.

Αυτά τα δέντρα τα κατασκευάζουμε γιατί είναι πολύ γρήγορο να αναζητήσουμε στοιχεία μέσα σε αυτά (ξεκινάμε από τη ρίζα και 'στρίβουμε' αριστερά ή δεξιά, ανάλογα με το αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο από τον κόμβο στο οποίο βρισκόμαστε).

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

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

Milspil

Κατατοπιστικότατη η απάντηση όπως πάντα άλλωστε!Ευχαριστώ πολύ.Κάτι τελευταίο αν γίνεται,που δεν είχα προσέξει προηγουμένως.Το ρωτάω εδώ,μην σπαμμάρω άλλο θέμα.Στις "και καλά ερωτήσεις προετοιμασίας" τσέκαρα αυτήν εδώ την ο Θεός να την κάνει ερώτηση.
Δωστε έναν τύπο για την καταχώρηση στη i-o στη σειρά και στη j-o στην στήλη ενός δυσδιάστατου πίνακα αν αυτός έχει αποθηκευτεί σε διάταξη κατά στήλες αντί κατά γραμμές. Πως αποθηκεύουμε έναν αραιό πίνακα;

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

odysseas

Παράθεση από: Milspil στις 16 Ιουν 2017, 02:15:25 ΜΜ
Κατατοπιστικότατη η απάντηση όπως πάντα άλλωστε!

Όταν τις ξαναπροσπαθήσεις μπορείς και πάλι να αναρτήσεις τις λύσεις σου για μια γνώμη.

Παράθεση από: Milspil στις 16 Ιουν 2017, 02:15:25 ΜΜ
Δωστε έναν τύπο για την καταχώρηση στη i-o στη σειρά και στη j-o στην στήλη ενός δυσδιάστατου πίνακα αν αυτός έχει αποθηκευτεί σε διάταξη κατά στήλες αντί κατά γραμμές.

Δεν καταλαβαίνω τι λέει. Πιθανώς να ζητάει έναν τρόπο ν' απεικονίζει κανείς τη θέση ενός στοιχείου του δισδιάστατου πίνακα σε έναν δείκτη μονοδιάστατου. Ουσιαστικά μια συνάρτηση από το (i, j) σε ένα ακέραιο k. Για διάταξη κατά γραμμές, αυτός ο "τύπος" είναι i*n + j, όπου n είναι το πλήθος των στηλών και η αρίθμηση των i kαι j ξεκινά από το 0. Πιθανώς όμως να ζητάει και το αντίστροφο, δηλαδή πως πας από το k στα (i, j). Πιθανότατα να μη ζητάει τίποτα από τα παραπάνω...