THMMY.gr

Καθώς έχουν σταλεί κάποια email σχετικά με το αν θα υπάρξει κάποιο θέμα σε Java:

Θα υπάρχει θέμα που θα ζητηθεί να υλοποιήσετε κάποιες απλές μεθόδους σε Java (οι οποίες θα σχετίζοντες με απλές Δομές Δεδομένων). Για να γράψετε αυτές τις συναρτήσεις, θα απαιτηθούν βασικές γνώσεις Java (δηλαδή κλάσεις, constructors, δημιουργία πινάκων, απλή κληρονομικότητα κτλ). Όλα αυτά περιέχονται στις σημειώσεις που σας έχουν δοθεί.

Φώτης

θα πρέπει να τα απαντήσουμε σε JAVA ή μπορουμε να χρησιμοποήσουμε και ψευδογλώσσα΄ή κάτι παρόμοιο τεσπα?

Σε Java λεει ο Φωτης παραπάνω, όχι σε ψευδογλώσσα

 μου ειχαν πει οτι ανεβαζουν στο e-thmmy κατι τεστ προσομοίωσης.ισχύει κάτι τέτοιο???

ευχαριστώ...

Είναι το module "Αυτοαξιολόγηση". Θα το βρείτε μόνο στο 5ο εξάμηνο στο eTHMMY. οπότε απλά κάνετε μια εγγραφή και στο μάθημα "Δομές Δεδομένων (νέο πρόγραμμα σπουδών)".

Φώτης

Πως γίνεται να κάνουμε επανεξέταση στην αυτοαξιολόγηση αν έχουμε επιτύχει στο τεστ?

Στείλτε μου ένα mail με τα στοιχεία σας, ώστε να διαγράψω τα προηγούμενα γραπτά...

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

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

Και 'γω με την ίδια απορία έχω μείνει... :-\

Ας βγει κανενας Ψωμοπουλος να δωσει τις απαντησεις γιατι ειναι εκνευριστικο να κανεις το τεστ και να μην ξερεις τα αποτελεσματα!

Ο αραιός πίνακας μπορεί να αποθηκευτεί ως τριάδες αριθμών και μάλιστα τόσες τριάδες όσα και τα μη μηδενικά στοιχεία Ν.Αρα για κάθε μη μηδενικό στοιχείο χρειάζεται να αποθηκεύσουμε 3 ακεραίους,δηάδή 3*4=12 βιτ.Συνολικά 12Ν βιτ για όλο τον πίνακα.
Η αμέσως λιγότερη συμφέρουσα αποθήκευση αραιών πιθνάκων για μικρά Ν είναι στη διαφάνεια 9 σελ2-4.
Εκεί χρειαζόμαστε n*m(5*6 ή 6*6) βιτς για την αποθήκευση του δυαδικού πίνακα συν 4Ν βιτς για την αποθήκευση του πίνακα των ακεραίων.
Αρα λύνοιυμε την ανίσωση 12Ν<n*m+4Ν και βάζουμε το μεγαλύτερο Ν που ικανοποιεί την ανίσωση,όχι την ισότητα.

Παρατηρήσεις:1)Μπορεί κατα τύχη να μου επαληθεύτηκαν τα αποτελέσματα οπότε ας το επιβεβαιώσει ο Φώτης
2)Αφού έχω πίνακα 5 ή 6 γραμμών γιατί αναπαριστώ αυτό το νούμερο με ακέραιο και δεν το κάνω με 3 βιτ γλιτώνοντας έτσι χώρο μνήμης?
Στη θεωρία λέει ότι βάζουμε ακέραιο,αλλά είναι πιο οικονομικό αν χρησιμοποιήσουμε λιγότερα βιτ.

Μόλις ολοκλήρωσα την αυτοαξιολόγηση λύνωντας τα δύο τελευταία ερωτήματα όπως ακριβώς περιέγραψε ο ikoufis από πάνω (συγκεκριμένα με αποτέλεσμα Ν=3 για πίνακα 5*6 και Ν=4 για 6*6) αλλά μου τα πήρε και τα δύο λάθος :(
Μου διαφεύγει κάτι??? Εμένα πάντως η λύση μου φαίνεται σωστή...
Είναι βέβαια και προχωρημένη η ώρα οπότε μπορεί να έκανα καμιά χαζομάρα και να μην μπορώ να τη δω τώρα...(ikoufis??? καμιά ιδέα?? :D)

παιδια ,κατι πηρε το αυτι μου οτι γραφουμε με ανοιχτες τις σημειώσεις. Ισχύει?

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

ενταξει Μανόλη
εχεις δίκιο
μη μας μαλώνεις






:P

sorry... ::)

E, ναι βγαίνει 5*6/8=3,75 και 6*6/8=4,5. Την ισότητα ικανοποιούν τα 3,75 και 4,5 εγώ έβαλα την αμέσως μικρότερη ακέραι ποσότητα δηλ 3 και 4. Γιατί αυτό είναι λάθος;

Και γω βάζω αυτα ακριβώς και είναι λαθος..Ας απαντήσει κάποιος..

Σε σχετικό μέιλ προς κο Ψωμόπουλο, μου απάντησε το εξής:
Από την θεωρία έχουμε ότι για Ν μη μηδενικά στοιχεία χρειαζομαστε   3Ν λέξεις
(σελ.2-5, διαφάνεια 11). Έτσι εάν δεσμεύουμε στην μνήμη   έναν πίνακα 6x6 κάποιου
τύπου μεταβλητής τότε αυτόματα δεσμεύουμε   μνήμη 6x6x(αριθμό των λέξεων που
καταλαμβάνει η μεταβλητή).

Για παράδειγμα εάν η μεταβλητή ακέραιος αντιστοιχεί σε μία λέξη μνήμης τότε ένας
πίνακας ακεραίων 6x6 θα δεσμεύσει 36 λέξεις   μνήμης. Εάν για κάθε μη μηδενικό
στοιχείο χρειάζονται 3 λέξεις   μνήμης τότε  ο μέγιστος αριθμός μη μηδενικών
στοιχείων Ν που   μπορεί να  αποθηκευτεί σε αυτήν την δεσμευμένη μνήμη είναι 11   
(για Ν=12 έχουμε  ακριβώς την ίδια κατανάλωση μνήμης, και άρα δεν  μιλάμε για
βέλτιστη  λύση).

Στη συνέχεια, καθώς κι εγώ είχα μείνει με την εντύπωση ότι για την υλοποίηση του πίνακα της διαφάνειας 9 δεσμεύεται 1bit/κελλί, ρώτησα και πάλι σχετικά και πήρα την εξής απάντηση:
(...)και ο πίνακας απαιτεί για κάθε στοιχείο του χώρο
ίσο με w (δηλαδή δεν ισχύει το ένα bit ανά κελί).

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

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

Αυτά λοιπόν  ;)

Καλό διάβασμα σε όλους(μας)  :)

εγώ ουτε τώρα κατάλαβα. Αν κάποιος καταλαβε ας γραψει την εξίσωση παρακαλώ
(η ειναι η (x*y)>3N? και αν ειναι το 4bits τι το δινει?)

κανονικα πρεπει να γραψεις


3*Ν*4 <  6*6*4
οποτε το 4 απλοποιείται κ εχουμε 3*Ν<6*6  -> Ν<12,αρα Ν=11

Ο κώδικας που θα ζητηθεί σε τι επίπεδα δυσκολίας θα κινηθεί;

Δλδ πίνακες και κανένα bublesort ή μπορεί να φτάσουμε σε υλοποίηση κανενός δέντρου;

Είπαμε ότι είμαστε βάρβαροι, αλλά όχι και σε βαθμό να σας βάλουμε να υλοποιήσετε δένδρο σε java...!   ;) Κατά τα άλλα, καλά τα λες...

Φώτης

Θα ήθελα να αναφέρω 2 απορίες που έχω, αν μπορεί κάποιος να βοηθήσει...

Στις σημειώσεις σελ.4α-29 στη διαγραφη σε δυαδικό δέντρο, αντικαθιστά το στοιχείο προς διαγραφή 88 με το 82. Δεν θα έπρεπε να το αντικαταστήσει με το στοιχείο 97 που είναι το αμέσως επόμενο του 88; :(
 Γιατί στο βιβλίο των δομών σελ.393 λέει πως για κάθε κόμβο, ο κόμβος με το επόμενο υψηλότερο κλειδί είναι ο διάδοχός του και τον αντικαθιστά σε περίπτωση διαγραφής του...Δηλαδή εδώ στο συγκεκριμένο παράδειγμα είναι το 97. Ε; Υπάρχει μήπως λάθος στις σημειώσεις;


Επίσης κατά τη διαγραφή κλειδιού από β-δέντρο σελ. 4b-12 που διαγράφεται το στοιχείο 112 της προηγούμενης σελίδας δεν θα έπρεπε το 112 που βρίσκεται σε εσωτερικό κόμβο να εγκατασταθεί από το επόμενό του, δηλ.το 131 και στη συνέχεια ο κόμβος φύλλο στον οποίο απομένει μόνο το κλειδι 158 να ενσωματηθεί με το δεξί του υπόδεντρο(231 283);

Ας απαντήσει κάποιος αν ξέρει...  ^beg^ ^beg^ ^beg^

Υπαρχουν καπου παραδειγματα για εξασκηση στην java?

Διευκρινιστική ερώτηση: Οι σημειώσεις που επιτρέπεται να έχουμε είναι αυτές στο site που λένε "Δομές Δεδομένων - Σημειώσεις Διδάσκοντος" ή και αυτές που λένε "Java: Οδηγός Java - Σημειώσεις Διδάσκοντος "; Ή είναι μέσα και οι ψευδοκώδικες αλγορίθμων;

Από τη γραμματεία ποιες μοιράζονταν;

Απ'οτι καταλαβα θα εχουμε ανοιχτες τις σημειωσεις του Μητκα...Δομες Δεδομενων-Σημειωσεις μαθηματος.

Thx

Πάντως οι σημειώσεις που μοιράστηκαν περιλαμβάνουν κ έναν σύντομο οδηγό java του κου Μήτκα, 30-40 σελίδων περίπου, που λογικά θα είναι το ίδιο μ'αυτό στο σάιτ(δεν τις έχω κοιτάξει οπότε δεν παίρνω και όρκο).
Οπότε και τα δύο φαντάζομαι...

Ο οδηγος java που βρισκετα στο ethhmy ειναι το τελευταιο κεφαλαιο των σημειωσεων που μας εδωσαν...
Κι εγώ τωρα το ειδ... ;)

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

Όσα και να θυμάται...

Ευχαριστώ.

ΕDIT:

Ερώτηση:

Δίνεται η παρακάτω μέθοδος showString:

void showString(int n) {
    switch (n) {
        case 1:
            System.out.print("!");
        break;
        case 2:
            System.out.print("snow");
            showString(n+1);
        break;
        case 3:
            System.out.print("man");
            showString(n-2);
        break;
        default:
            while (n > 4) {
                for (int i=0; i<n; i++) {
                    System.out.print("*");
                }
                n--;
            }
            System.out.print("*");
            showString(n-2);
        break;
    }
}



Ποια είναι η συμβολοσειρά που θα εκτυπωθεί στη κονσόλα μετά την κλήση της παραπάνω μεθόδου για n = 5;



Α/Α Απάντηση  Απάντηση φοιτητή
1. snowman***!     
2. man***snow!     
3. snow******man!     
4. ******snowman!     
5. snow!***man     

Ποια είναι η απάντηση και πως βγαίνει?

το 4 ειναι το σωστό
αφού το n είναι 5, τότε θα μπει στην default επιλογή της switch
επομένως εκεί θα εκτυπώσει 5 αστεράκια με τη φορ που βρίσκεται μέσα στη while, μετά θα φύγει απο εκεί θα εκτυπώσει ακόμη ένα αστεράκι και θα δείξει στη συνέχεια το string με τη κλήση της μεθόδου showString

Ευχαριστώ για την άμεση απάντηση! ;)

Ελπίζω να είσαι εδώ μήπως έχω και άλλες απορίες...

Μολις μου δημιουργήθηκε μία.. Αυτη με το DATASTRUCTURESROCK...
Ποια είναι οι απάντηση?

Ποια είναι η συμβολοσειρά που θα εκτυπωθεί στη κονσόλα μετά την κλήση της μεθόδου encode για t = 5;


1.   Y V O V N O M P X O P M Z N M J X F     

2.   D A T A S T R U C T U R E S R O C K     

3.   I F Y F X Y W Z H Y Z W J X W T H P     

4.   K C O R S E R U T C U R T S A T A D      

5.   T R U C T U R E S R O C K D A T A S     

Σίγουρα πάντως δεν είναι η 2 και η 5 ...

Εγω νομιζω ειχα βαλει το 3,αλλα ηταν λαθος...

3

ευχαριστώ

Μπορεί κάποιος να μου πει ποια είναι η σωστή απάντηση στην παρακάτω ερώτηση της Αυτοαξιολόγησης και αν μπορεί να μου εξηγήσει το γιατί; Κάθε φορά γίνεται νέα κλήση της showStars με διαφορετικό όρισμα και έχω μπερδευτεί για το τι συμβαίνει στις υπόλοιπες σειρές του if. Ευχαριστώ!


void showStars(int n) {
    if (n >= 3) {
        showStars(n-3);
        System.out.print("*");
        showStars(n-1);
        System.out.print("**");
        showStars(n-2);
    }
}

Ποιος είναι ο αριθμός των αστερίσκων (*) που θα εκτυπωθούν στη κονσόλα μετά την κλήση της παραπάνω μεθόδου για n = 5;

Και σε μένα έπεσε κάτι παρόμοιο. Αρχικά έλεγε έστω Α(n) ο αριθμός των (*) που εκτυπώνονται στην κονσόλα και έπειτα είχε τον παρακάτω αλγόριθμο για n>=3.

void showStars(int n) {
    if (n >= 3) {
        showStars(n-1);
        System.out.print("***");
        showStars(n-2);
        System.out.print("*");
        showStars(n-1);
    }
}

Η σωστή απάντηση ήταν Α(n)=2Α(n-1)+Α(n-2)+4

Άρα λογικά στην περίπτωσή σου η σωστή απάντηση θα είναι:

Α(n)=Α(n-1)+Α(n-2)+Α(n-3)+3

Δηλ 12

Γιατί +3 ???

διότι System.out.print("*"); --> 1 αστέρι
System.out.print("**");--> 2 αστερια
2+1=3

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

Μία ακόμη :

1) Ερώτηση: Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 3, 5, 6, 10, 18, 19, 20, 23, 27, 74, 99 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με δυαδική αναζήτηση.

2) Ποιος είναι ο ελάχιστος αριθμός κόμβων που μπορεί να έχει ένα πλήρες τετραδικό δέντρο ύψους 6. Θεωρούμε πως η ρίζα είναι το επίπεδο 0.

3)Δίνεται ο παρακάτω πίνακας ακεραίων αριθμών:
1, 60, 24, 7, 28, 8, 4

Να εισάγετε τα στοιχεία του πίνακα σε δυαδικό δένδρο αναζήτησης με τη σειρά που δίνονται.
1)Ποιο είναι το ύψος του δένδρου;
2)Πόσους κόμβους πρέπει να διασχίσουμε για την εύρεση του αριθμού 4;

3)Πόσους κόμβους πρέπει να διασχίσουμε για την εύρεση του αριθμού 24;

Όποιος μπορεί...

   Παιδιά υπάρχει τόπικ ειδικά για τις απαντήσεις του τεστ αυτοικανοποίησης-αυτοαξιολόγησης.

1) 4

2) (4^7-1)/(4-1)

3) 4
    5
    3

ΤΥ Λαιδηβιρδ

1) Ερώτηση: Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 3, 5, 6, 10, 18, 19, 20, 23, 27, 74, 99 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με αναζήτηση ΑΛΜΑΤΟΣ.

δεν δινει το βημα αλματος;

Με τι αλμα? 2? Τοτε νομίζω είναι 5.

Με το βήμα 2 και απάντηση 5 εμένα το πήρε λάθος...
Μήπως έχει ΒUG το τεστάκι?

η απαντηση ειναι 6. συγκρινει και το πρωτο.

Ευχαριστώ και πάλι Ladybird.

Ερώτηση

2) Ποιος είναι ο ελάχιστος αριθμός κόμβων που μπορεί να έχει ένα πλήρες τετραδικό δέντρο ύψους 6. Θεωρούμε πως η ρίζα είναι το επίπεδο 0.

Απάντηση

2) (4^7-1)/(4-1)

Ο τύπος στο βιβλίο στην 4α-5 διαφάνεια 11, ισχύει δλδ για δένδρα τα οποία θεωρούμε πως η ρίζα είναι το επίπεδο 1?

αυτο που λες πρεπει να ισχυει.

ξερει κανεις τι ακριβως εννοουσε ο ποιητης στα τελευταια ερωτηματα της αξιολογησης για ταξινομηση, οπου εδινε ενα πινακα με αριθμους απο 1-9 και ρωτουσε ποιοι απο τους αριθμους μπορουν να βρεθουν με 2 επαναληψεις με δυαδικη και σειριακη αναζητηση?!?....

θα βρει τα πρώτα δύο.
το 1 και το 2 δηλαδή.
Εφόσον είναι και ταξινομημένοι.

Επεσε σε κανενα εκεινη η ερωτηση με την απλη η διπλη περιστροφη σε δεντρο AVL??
Ποια ειναι η απαντηση? Ευχαριστω

Για ποιο λογο 5 και 3 οι δυο τελευταιες απαντησεις????
Αφου το δεντρο παιρνει την εξης μορφη 1 (24 (7(4 8) 28) 60) δηλαδη 4 κομβοι και 2 που ειναι το λαθος???????

Πρόσεξε να φτιάξεις ΣΩΣΤΑ το δυαδικό δενδρο...
Αριστερά τα μικρότερα και δεξιά τα μεγαλύτερα κάθε κομβου.
Αυτο κάνεις λάθος.

Η ρίζα (1) μετράει κι αυτή για κόμβος?

κατι σου ξεφυγε cyber δε κανεις για κηπουρος.... ;)

Δίνεται ο παρακάτω πίνακας ακεραίων αριθμών:
1, 60, 24, 7, 28, 8, 4

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

ρε παιδια μηπως μπορει να μου πει καποιος πώς φτιάχνω το δεντρο γιατί εχω μπερδευτεί;

Βάζεις ρίζα το 1. Μετά ξεκινάς υποδένδρο δεξιά με το 60 κτλ όπως φαίνεται παρακάτω
             1
                    60
                 24
               7    28
             4  8

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

και το 28 γιατί έχει πατέρα το 24 και δεν ειναι το δεξί παιδί του 7?

λειπει και το 8!

το 8 είναι δεξί παιδί του 7.

δηλαδή:
                 1
                    60
                 24
               7   28
             4 8
?

Ρε μαγκες και το 24 γιατι να μην μπει αριστερο παιδι της ριζας????????

Την ερωτηση που εκανα για την περιστροφη την ξερει κανεις???

Το 24 ΔΕΝ είναι μικρότερο του 1 για να μπει από αριστερά του. Σόρυ για πριν ξέχασα το 8.
Το έκανα modify.

πωωωωωωωωωωωωωωωωωωωωωω τι μαλακια εκανα με αρεσει που επιμενω δεν τον ειδα καν :(

ευχαριστώωωωωωωωωω

Στις δυο ερωτησεις με το  L.next.next=L.next.next.next και το L.next.next.next<---- L.next.next ποιες ειναι οι σωστες απαντησεις?

να ρωτησω, αν οταν κανουμε αναζήτηση, μετράμε στον αριθμόσυγκρίσεων το 1ο στοιχείο κ αν μετράμε κ το στοιχείο που ψάχνουμε.
πχ σε σειριακή, αν το 80 ειναι το 10 στοιχείο, 8α έχουμε 8,9 ή 10 συγκρίσεις?

Ναι μετράς και τα δύο.

στο παράδειγμα σου 8α έχουμε 10 συγκρίσεις δλδ.