Εξεταστικη σε Δομες δεδομενων.

[zisis13]

Παιδια συγνωμη αν ειμαι σε λαθος μερος.Και γενικα αν δεν επιτρεπεται αυτο που κανω.

Αλλα εχω εξεταστικη,συνεχεια ο καθηγητης βαζει μια απο τις 3 παρακατω ασκησεις για θεωρια που ειναι απλες αποδειξεις.Τις ασκησεις που βαζει που θελουνε μεθοδολογια τις ξερω,ειμαι διαβασμενος...στις παρακατω δεν μπορω να βρω την λυση.Δεν μπορω πουθενα να βρω καποια ακρη.Δεν υπαρχουνε στις σημειωσεις του.Και ουτε τα κανει ποτε στο μαθημα.Εχω googlarei αλλα και παλι δεν βρισκω αποτελεσμα.Αν ξερει καποιος και μπορει ας με βοηθησει.

 

1)Εστω ενας μοναδιαιος πινακας με διαστασεις 1000*1000.Θελετε να αποθηκευσετε αυτον τον πινακα στη μνημη.Ποιος εινα ο βελτιστος τροπος γνα να το επιτυχετε αυτο?Αιτιολογηση.

 

2)Να δειξετε οτι εαν καποιος κομβος ενος δυαδικου δενδρου αναζητησης εχει δυο θυγατρικους,τοτε ο προκατοχος του δεν εχει δεξιο θυγατρικο.

 

3)Ποιο ειναι το μεγιστο και το ελαχιστο πληθος των στοιχειων σε εναν σωρο με υψος h?

 

Στην τελευταια με το πληθος ειχα βαλει με το μυαλο μου την απαντηση αλλα ειπε οτι το θελει με αποδειξη.Εγω το εκανα μπακαλιστικα με το μυαλο μου.Δεν ξερω πως μπορω να το αποδειξω.

Οποιοσδηποτε γνωριζει ας με διαφωτησει αν μπορει.

[albNik]

Ο μοναδιαίος εχει ολα τα στοιχειά μηδέν εκτος απο τη διαγώνιο (σωστα?)

Αποθηκεύεις μονο τη διαγώνιο 1000 στοιχεια αντι για 1000000.

Λαθος. Διαγώνιος λεγεται αυτος 

 

Μοναδιαιος :διαγώνιος όλα 1, τα υπολοιπα 0.  Αρκει να αποθηκευσεις το μεγεθος του δλδ τον αριθμο 1000.

[zisis13]

Α ναι....ητανε τοσο απλο   Ευχαριστω πολυ.

 

Αν καποιος ξερει απο δυαδικα δενδρα αναζητησης να με διαφωτησει...γιατι εγω ξεκιναω να λυνω αυτη η αποδειξη σαν "εστω οτι ο προκατοχος του EXEI δεξιο θυγατρικο" παει κατι στραβα?Εγω δεν βλεπω κατι στραβο ωστε να καταληξω στο να αποδειξω οτι δεν γινεται να εχει δεξιο θυγατρικο αν ο απο κατω κομβος εχει δυο θυγατρικους.

[gon1332]

Τι σημαίνει "θυγατρικός";

[paparovic]

2)Να δειξετε οτι εαν καποιος κομβος ενος δυαδικου δενδρου αναζητησης εχει δυο θυγατρικους,τοτε ο προκατοχος του δεν εχει δεξιο θυγατρικο.

 

Είσαι σίγουρος ότι αυτή είναι η εκφώνηση? Δες το (6). Το (7) έχει προφανώς δεξί child node.

[albNik]

Α ναι....ητανε τοσο απλο   Ευχαριστω πολυ.

 Μπορει να εννοει κατι αλλο (για να μην σε παρω στο λαιμο).

 

@paparovic Στο αναζητησης τα αριστερα παιδια ειναι παντα μικροτερα απο τα δεξια (και ο parent αναμεσα). 7>5.

αλλα και παλι δεν ισχυει

[zisis13]

http://prntscr.com/5t861k

 

Να ετσι οπως στη φωτο ειναι η εκφωνηση.Ειναι οντως πραγματικα περιεργο.Γιατι και εγω απο αυτα που ξερω γινεται να εχει δεξιο θυγατρικο.Δεν ξερω τι παιζει.Η ερωτηση παιδες πεφτει εξεταστικη και δεν μπορω να βρω ακρη...μας δουλευει ο καθηγητης?Τον ρωτησα την ωρα της εξετασης "Δασκαλε ειναι σιγουρα σωστη η ασκηση αυτη?Γινεται να εχει δεξι θυγατρικο...και με γελακι ειμαι εξυπνος στυλ...μου απαντησε εισαι σιγουρος?"

 

Οταν εδωσα το γραπτο μου και τον επιασα και τον ρωτησα εν τελη πως λυνεται μου λεει "δεν μπορω να σου πω γιατι θελω να την βαλω και του χρονου" Γιαυτο απευθυνομαι σε σας γιατι ακρη δεν βρισκω και ειναι ετοιμο θεμα αν λυθει.

[albNik]

Αφου και πληρη δυαδικά υπαρχουν

[paparovic]

http://prntscr.com/5t861k

 

Να ετσι οπως στη φωτο ειναι η εκφωνηση.Ειναι οντως πραγματικα περιεργο.Γιατι και εγω απο αυτα που ξερω γινεται να εχει δεξιο θυγατρικο.Δεν ξερω τι παιζει.Η ερωτηση παιδες πεφτει εξεταστικη και δεν μπορω να βρω ακρη...μας δουλευει ο καθηγητης?Τον ρωτησα την ωρα της εξετασης "Δασκαλε ειναι σιγουρα σωστη η ασκηση αυτη?Γινεται να εχει δεξι θυγατρικο...και με γελακι ειμαι εξυπνος στυλ...μου απαντησε εισαι σιγουρος?"

 

Οταν εδωσα το γραπτο μου και τον επιασα και τον ρωτησα εν τελη πως λυνεται μου λεει "δεν μπορω να σου πω γιατι θελω να την βαλω και του χρονου" Γιαυτο απευθυνομαι σε σας γιατι ακρη δεν βρισκω και ειναι ετοιμο θεμα αν λυθει.

 

Παιδεία... Να φανταστώ Ελληνικό Ανώτατο Εκπαιδευτικό Ίδρυμα? 

[Alithinos]

άκυρο αυτό το ποστ.

Επεξ/σία 17 Ιανουαρίου 2015 από Alithinos

[zisis13]

Alithinos ναι...ξερω οτι γινεται.Αλλα ξερω επισης οτι γινεται να εχει και δεξιο.

Αν ξερεις να μου πεις εστω υπο ποια προυποθεση δεν βαζουμε δεξιο θυγατρικο στον προκατοχο του.Γιατι η ερωτηση ειναι αποδειξη και καλα.

 

Paparovic γ@μησετα...αντε να τελειωνουμε να ξεμπερδευω.

[defacer]

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

[Alithinos]

Βασικά ξέχνα το προηγούμενο σχέδιο που έβαλα,θα σε μπερδέψει.

 

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

 

πχ

 

 

 

 

 

 

υ.γ. όταν λες 'έχω googlάρει' εννοείς στα Ελληνικά ?

ότι θέλεις να το ψάχνεις στα Αγγλικά, και για αυτό καλό είναι να ξέρεις την Αγγλική ορολογία.

Την απάντηση δεν την ήξερα ο ίδιος (είμαι πιο αρχάριος, ακόμα μαθαίνω λούπες και enums) αλλά με ένα δικό μου googlάρισμα μου πέταξε απαντήσεις από πανεπιστήμια Princeton και Berkley.

 

https://www.cs.berkeley.edu/~jrs/61b/lec/26

http://algs4.cs.princeton.edu/32bst/

[gon1332]

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

Γι' αυτό και ρώτησα τί εννοεί με το "θυγατρικός". Δεν το έχω ξανακούσει στα ελληνικά

σε συνδυασμό με δένδρα.

[albNik]

Γι' αυτό και ρώτησα τί εννοεί με το "θυγατρικός". Δεν το έχω ξανακούσει στα ελληνικά

σε συνδυασμό με δένδρα.

Μαλλον εννοει siblings, τους κομβους που ειναι στο ιδιο υψος (το "αδερφακι" και τα "ξαδερφια").

 

3)Αν καθε κομβος εχει ενα παιδι (ειναι σαν αλυσίδα) τοτε εχει min=h κομβους. 

Αν ειναι πληρες δεντρο τοτε εχει max= 1+2+4+8+...+2^h=2^h+1-1 κομβους