THMMY.gr

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

Οι ασκήσεις που είναι ανεβασμένες καλύπτουν γενικά την ύλη;
Φέτος έκανε πολύ περισσότερες;
Αν ναι σε ποιο κομμάτι τις ύλης υστερούν αυτές των downloads;

To θεμα 1γ αυγουστος 07 που ανεβηκε ετημμυ το ελυσε κανεις ?
Το σωστο ειναι το Β ? και τι μορφη θα εχει το δεντρο ?

Οταν λεει κατακερματισμο με μεθοδο συνδεδεμενων λιστων τι εννοει ?

Γενικα καποιος που εχει ασχοληθει, ας ανεβασει/γραψει και τις λυσεις αν μπορει, εστω και σαν απαντησεις απλα. It would be much appreciated

Γραφω εδω οτι ελυσα απο θεματα φυσικα οπου εχω λαθος διορθωστε με !!

Θεματα Αυγουστος 2007

1α) σωστο το Δ) πολυπλοκοτητα Ο(n^3)
 η πρωτη λουπα 1---->n αρα O(n)
 η δευτερη λουπα 1--->3n αρα O(n)
 h τριτη λουπα  κ=j αρα παλι Ο(n)

1β) σωστο το Α το Β απλη περιστροφη στο 23 στο 31

1γ) σωστο το Β (πρωτα κανεις το δεντρο με προδιατεταγμενη και απο αυτο βρισκεις την μεταδιατεταγμενη)
 
2β) ii) 0  1   2   3   4   5  6  7  8  9  10  11  12  13  14  15  16
         Ρ  Ρ  Α   Γ  Τ   Υ  Ζ  Ι   Α  Ι   Κ               Ν   Ο   Π
        0  1   2   3   4   5  6  7  8  9  10  11  12  13  14  15  16
            Ρ  Α   Γ  Τ   Υ  Α     Ζ   Ι   Κ    Ο        Ν   Ρ   Α    Π (Δεν ειμαι 100% σιγουρος επισης το τελευταιο Ι δεν υπαρχει κενο για να μπει)

Για το 1γ πως κανεις το δεντρο?δεν εχω δει τετοιο παραδειγμα μεχρι τωρα

Θα ειναι πληρες το δεντρο αρα απο 2 παιδια καθε κομβος.
συνολικα δλδ 5 σειρες θα εχει το δεντρο 1,2,4,8 κομβους αντιστοιχα η καθε σειρα (μεχρι την 4η)
και 2 κομβους η τελευταια οι οποιοι κομβοι θα τοποθετηθουν στον τερμα αριστερα κομβο της 4ης σειρας.
Μετα βαζεις τα γραμματα σε καθε κομβο συμφωνα με την προδιατεταγμενη διασχυση

Φεβρουάριος 2008, Θέμα 2...Η λύση είναι η παρακάτω ή όχι;
Άξονας 1-->29
Άξονας 2-->3
Άξονας 3-->41

3 7 20 18 5 29 32 41 90 62

αυτό νομίζω δεν είναι σωστό, πάλι δεν θα είναι ισοζυγισμένο. Εγώ μάλλον θα έκανα απλή στο 27 αλλά δεν είναι στις επιλογές (έχει διπλή). Ίσως έβαζα το Ε) τότε

Απλή περιστροφή στο 31. Πάει δεξιά το 31 και ανεβαίνει το 27

ναι ακριβώς αυτό, απλά δε ήξερα αν λέγεται απλή περιστροφή στο 31 ή στο 27

edit: το ιδιο λεμε οντως τελικα? :p

Καμία ιδέα για το 1.δ  κανείς;

Ναι

Στο 1δ αν θυμάμαι καλά έβγαλα το Α

Το β τελικα σωστο διορθωνω και το αρχικο ποστ

Mπορεις μηπως να εξηγησεις πως το βρηκες ?

Fibo(1)  ---> Επιστρέφει 1

Fibo(2)  ---> Επιστρέφει 1

Fibo(3)   --->  Εκτυπώνει 3 και επιστρέφει Fibo(2)+Fibo(1)=2    (τελική εκτύπωση 3)

Fibo(4)  ---> Εκτυπώνει 4 και επιστρέφει Fibo(3)+Fibo(2)=3  αλλά λόγω Fibo(3) εκτυπώνει και 3   (τελική εκτύπωση 43)

Fibo(5) ---> Εκτυπώνει 5 και επιστρέφει Fibo(4)+Fibo(3)=5 αλλά λόγω Fibo(4) εκτυπώνει 43  και λόγω Fibo(3) εκτυπώνει 3  (τελική εκτύπωση 5433)

Fibo(6) την οποία θέλουμε ---> Εκτυπώνει 6 και επιστρέφει Fibo(5)+Fibo(4)=8 αλλά λόγω Fibo(5) εκτυπώνει 5433 και λόγω Fibo(4) εκτυπώνει 43.   Τέλος εκτυπώνεται και το 8.  (τελική εκτύπωση 65433438)

πολύ δυνατός γουελ πλέιντ

το i) που ζητουσε με συνδεδεμενη λιστα το εκανες??

οχι δεν βρηκα τι ειναι συνδεδεμενη λιστα.

Σελιδα 14 απο σημειωσεις που ανεβασε ο βλασης στην 2 με την insertion sort
γιατι εχει κενο μεταξυ i=4 και i=5 ?

σελ 4. στο pdf Lecture7 (Hashing) Απλά ζωγραφίζεις την αντίστοιχη λίστα όποτε έχεις σύγκρουση, φαντάζομαι

για το i=4, δηλαδη το στοιχειο 1 κανεις καποιους ελεγχους, και οταν τελειωσεις τοτε ελεγχεις το στοιχειο i=5 που ειναι το 7..

4 άτομα ψάχνουμε τόση ώρα τι λάθος κάναμε. Έχεις χάσει ένα Α. Θέλει 3 >:(

εμενα μου βγαινουν
Άξονας 1-->29
Άξονας 2-->3
Άξονας 3-->41

3 7 20 18 5 29 41 32 90 62

μπορει και να χω καποιο λαθος...(νομιζω ομως ο δεικτης left θα περασει τη θεση που ειναι το 41 γιατι ικανοποιει την συνθηκη 41<=pivot(=41) οποτε θα παει στο επομενο που ειναι το 62  ενω ο δεικτης right θα μεινει στο 32 οποτε θα κανουμε αυτα τα δυο swap...μετα την αλλαγη ο δεικτης right θα γινει μικροτερος απο τον low) αμα εχω πει/καταλαβει κατι λαθος διορθωστε με

ξεχασα το τελευταιο βημα...συμφωνω με αυτο που εγραψες

για το 3ο Α τι λέμε ελέγχουμε το 1+1^2=2(γεματο) μετα το 1+2^2=5(γεματο) μετα το 1+3^2=10 (γεματος) και μετα το 1+4^2 =17 17-17 =0 άρα θα μπει στο 0;Μπορεί κάποιος να επιβεβαιώσει;


επίσης για  hashing με συνδεδεμένες λίστες ξέρει κανείς πως να λυθεί; το ξέρω οτι το λέει στη θεωρία αλλά δεν το πιάνω

Ξέχασες να αλλάξεις τον right=32 με το pivot=41 στο τέλος του αλγορίθμου. Γενικά για να καταλαβαίνεις αν το έκανες σωστά, να κοιτάς αν τα νούμερα δεξιά του άξονα είναι μεγαλύτερα του άξονα, και αν τα νούμερα αριστερά του άξονα είναι μικρότερα από τον άξονα.

νομιζω το 3ο Α παει στο 15 γιατι 1+1^2=2(γεματο) 2+2^2=6(γεματο) 6+2^3=15 δεν προσθετεις απλα 1,4,9,16 κλπ αν σου δινει τον αλγοριθμο.

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

γιατι όχι 3 7 20 18 5 29 41 62 90 32  ??? που κανω λαθος???  :-\

Παιδια στις ασκησεις κατακερματισμου οταν κανεις τετραγωνικη εξεταση το i τι ειναι;

Μήπως δε σταμάτησες απευθείας το δείκτη right από την αρχή, αφού 32<41?

   νομίζω ότι το λέω σωστά και στις λύσεις 2014-2015 το έχει λάθος ας επιβεβαιώσει ένας

;Έστω λ η θέση του πίνακα  τοότε αν έχει h(k)=kmod 7 και h'(κ)=i^2, οπου i η συγκρουση.Αν έχεις τον αριθμο 40 θα πεις
40mod7=5 άρα θα μπει στη θεση λ=5 το 40 του πινακα αν είναι πιασμένη(συγκρουση) θα πάει στην  5+1^2 =8=λ(για μια συγκρουση) ,αν είναι και αυτη γεμάτη τότε θα παει στη θεση 5+2^2=9 (i=2) κλπ κλπ

Παιδια στην quickshort  τους 2008 οι αριθμοι 6,2,8 που ακριβώς χρησιμεύουν;

απαντησεις καποιος στα θεματα του 8 για να τα τσεκαρουμε? Αυτα που απαντιουνται ευκολα μονο μη καθιστε να γραψετε ολοκληρο δεντρο  :P

Μια ερώτηση γιατί έχω μπερδευτεί λίγο.. Πότε ένα δέντρο είναι ισοζυγισμένο;

Έχει κάνει κάποιος το 3β του 2008; Αν ναι, wtf ειναι η απάντηση στο ερώτημα ii; Απαιτεί σκέψη and i won't even...

ναι το ειδα μετα  :o ευχαριστω!! ::)

ισοζυγισμενα πρεπει να ειναι τα AVL δέντρα.
για να δεις αν ειναι ξεκινάς από τη ρίζα και πας απο το αριστερο παιδι προς τα κατω στο τελευταιο φυλλο και απο το δεξιο παιδι στο τελευταιο φυλλο. τελευταιο εννοω το φυλλο που φτανει σε μεγαλυτερο βαθος
αν για καθε κομβο μετρας +1 πρεπει η διαφορα στο τελος απο τα αριστερα και τα δεξια να ειναι 0 ή 1 συνολικα

Καμία ιδέα για το Hashing με συνδεδεμένες λίστες;

Mporeis mipos kapoios na eksigisei pos linete to thema 2b tou febrouariou 08?
Μπορεί μήπως κάποιος να εξηγήσει πως λύνεται το θέμα 2β του φεβρουαρίου 08?

edit: όχι greeklish

Hashing με Συνδεδεμένες Λίστες.
Δεν είμαι σίγουρος για τη λύση αλλά πιστεύω πως θεωρητικά είναι σωστή τουλάχιστον .
Ευπρόσδεκτη κάθε κριτική .

Μηπως  μπορει να ανεβασει καποιος λυση γ αυτην?

2) Η φραση
ΝΕΟΣΑΡΧΙΕΠΙΣΚΟΠΟΣ
προκυπτει αν διασχισουμε ενα σχεδον πληρες δυαδικο δενδρο με προδιατεταγμενη διασχιση Αν .
διασχισουμε το ιδιο δενδρο με μεταδιατεταγμενη διασχιση ποια φραση προκυπτει ;
( : ) Απ ΑΡΣΧΟΕΠΙΕΚΟΣΟΣΠΙ

Διορθωσα το 2β πειτε μου αν εχω λαθος....

Υπάρχουν πολλοί τρόποι να διαγραφεί ένα στοιχείο από τα Β δέντρα ή ένας κ μοναδικός ;;;

εγώ βρήκα:
0 1  2  3  4   5  6 7  8  9 10  11 12 13 14 15 16
Α Ρ Α  Γ  Τ  Α  Ζ _  Π  Ι  Κ    Ι   Υ  Ν   _  Ο   Ρ

Υπάρχουν διαφορές διότι ο ένας προσθέτει το h'(k) από το αρχικό σημείο, ενώ ο άλλος από το τελευταίο σημείο σύγκρουσης. Ανάλογα το τι θα λέει η εκφώνηση.

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

Νομίζω το έχεις λάθος Η σειρα είναι ΡΑΔ οπότε ξεκινάς απο την ρίζα πας αριστερά μετα πρέπει να εφαρμόσεις το ΡΑΔ για τον υποκόμβο και πάει λέγοντας, είναι σαν εμφωλευμένα  ΡΑΔ για κάθε κόμβο,ελπίζω να σε βοήθησα.
Σωστό το έχεις νόμιζα η λέξη είναι αρχιεπίσκοπος αλλά είναι Νεοςαρχιεπισκοπος, σορρυ μαν.

Η συνάρτηση σφάλματος f(j) πως βγαίνει; :P

τι ειν τουτο;  :o

Προκύπτει απο τον Αλγοριθμο KMP (σελ 11 διαφ αναζητησης)
Αυγουστ 2007 θεμα 3γ

ααα δεν ηξερα οτι λεγεται ετσι
μου εστειλε ο navi.mitsos αυτο το βιντεακι (https://youtu.be/5i7oKodCRJo)  που το εξηγει καλα, απο εδω το καταλαβα και γω.. μετα το 5ο λεπτο περιπου δες το ..

Ευχαριστω ήταν πολύ βοηθητικό!!
για την f βρήκα 0 1 0 1 2 2 3 0 0
μπορει καποιος να πει αν βρηκε το ιδιο;

Θα κοπείς ότι και να σου πούμε...

Αυτό βρήκα και εγώ

(https://i.imgflip.com/q5g0l.jpg)

χαχαχα καλή επιτυχία ρε

Αν έχει κανείς στο D αποτελέσματα συγκρίνετε λίγο με τα δικά μου:

Θέμα Α: n^2,3,3,Β=δυαδική

Στον κατακερματισμό:

---

                                              0         1         2         3         4         5      6      7        8        9

---

Με γραμμική διερεύνηση:    6949 | 3461 | 9199 | 3143 | 1603 | 3434 |      |       |          | 1539

---

Με τετραγωνική εξέταση:     6949 | 3461 |          | 3143 | 1603 | 3434 |      |       | 9199 | 1539

---

Με διπλό κατακερματισμό:   1603 | 3461 | 9199 | 3143 | 3434 | 6949 |      |       | 9199 | 1539

---

Δυαδικό αναζήτησης:
                             18
                     10             21
                 7      12             22
              6             14             48
            4

AVL:
                                 56
                        33               65
                  24       39     61      82
                      32                    78
                   29

Heapsort:  68,97,53,83,66,4,41,55,69,21 (μάλλον απέτυχα οικτρά σε αυτό...)

δέντρο από heapsort:
                             97
                    83               53
             69         66      4      41
        55    68   21

Αργότερα όταν συνέλθω θα βγάλω και τις εκφωνήσεις στο περίπου.