THMMY.gr

Στον Διπλο κατακερματισμο για την δευτερη συναρτηση μπορουμε να εχουμε h=c*i^2.
στις σημειωσεις το ι το αναφερει ως την ι-οστη εξεταση. :-\
καποιος που να μπορει να με βοηθησει να το καταλαβω?

thx

έστω ότι έχεις 3 συγκρούσεις στον πρώτο κατακερματισμό και επίσης, c =4 (δοθέν από την άσκηση)
Τότε, για την πρώτη σύγκρουση i =1 και h' = 4 *1^2 = 4
δεύτερη i =2 h' = 4* 2^2=16
τρίτη h'=4*3^2=36

Άρα οι θέσεις για το κάθε στοιχείο θα είναι α+h' όπου a το αποτέλεσμα του πρώτου κατακερματισμού

το i  ειναι κοινο για ολη την διαδικασια η καθε θεση του πινακα εχει ξεχωριστο?
δλδ
πες οτι εχουν γινει για την θεση 4 του πινακα, 2 συγκρουσεις δλδ το ι=2..
αν εχουμε αμεσως μετα συγκρουση για την θεση 5, το ι θα ειναι 3 η 1?

κοινο, αλλιώς θα είχαμε και δευτερεύουσα σύγκρουση

Μπορει καποιος απλα να κανει κοπυ-πειστ εδω τις ερωτησεις του 2ης εξετασης αυτοαξιολογησης που υπαρχει στο ethmmy?
Eυχαριστω.

B2. Σωροί, Αναζήτηση, Κατακερματισμός



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



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



Θέμα 3
Δίνεται ο παρακάτω πίνακας. Επιλέξτε όσα κλειδιά μπορεί να βρεθούν αν εξεταστούν το πολύ δύο στοιχεία του πίνακα με τη μέθοδο της δυαδικής αναζήτησης. 1 2 3 4 5 6 7
1.   1
2.   2
3.   3
4.   4
5.   5
6.   6
7.   7



Θέμα 4
Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 6, 10, 13, 20, 22, 27, 55, 58, 87, 99, 121 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με δυαδική αναζήτηση.



Θέμα 5
Έστω ότι θέλουμε να αναζητήσουμε το πρότυπο P = χαχοχα στη συμβολοσειρά S = χαχοχχαχοοχαχοχα Χρησιμοποιώντας τον αλγόριθμο KMP (Knuth-Morris-Pratt). Ποιος είναι ο συνολικός αριθμός των συγκρίσεων που θα χρειαστεί να εκτελεστούν; Θεωρείστε ότι ο αλγόριθμος σταματάει την πρώτη φορά που ανακαλύπτει το πρότυπο P.



Θέμα 6
Με βάση την συνάρτηση H(k) = k mod 9 , να αποθηκεύσετε σε πίνακα κατακερματισμού 11 θέσεων τα παρακάτω κλειδιά με τη σειρά που δίνονται: 12, 71, 52, 10, 19, 4, 56 Το πρώτο στοιχείο του πίνακα θεωρείται ότι έχει δείκτη 0. Η επίλυση των συγκρούσεων να γίνει με τη μέθοδο της τετραγωνικής εξέτασης με c = 1.



Θέμα 7
Δίνεται ο πίνακας ακεραίων αριθμών: 88, 127, 38, 19, 71, 63, 5, 1 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας επιλογής, να δώσετε τη μορφή του πίνακα μετά από 10 συγκρίσεις. Η ταξινόμηση γίνεται κατά αύξουσα σειρά.



Θέμα 8
Δίνεται ο παρακάτω πίνακας ακεραίων. Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις. Προσοχή! Συγκρίσεις μεταξύ δύο στοιχείων και όχι πλήρεις σαρώσεις του πίνακα. Σημειώστε πως τα αριθμητικά ψηφία έχουν μικρότερη τιμή από τα αλφαβητικά. ΑΡΧΙΚΟΣ ΠΙΝΑΚΑΣ Z A Γ Ο Ρ Α Κ Η Σ



Θέμα 9
Δίνεται ο πίνακας ακεραίων αριθμών: 5, 3, 8, 9, 1, 7, 0, 2, 6, 4 Να δώσετε τη μορφή του πίνακα αμέσως μετά την ολοκλήρωση του πρώτου διαμερισμού, με τον αλγόριθμο ταξινόμησης με διαμερισμό και ανταλλαγή (quick-sort). Ως άξονας (pivot) να ληφθεί το στοιχείο 5



Θέμα 10
Υποθέστε ότι θέλουμε να ταξινομήσουμε τον παρακάτω πίνακα: 24, 71, 34, 65, 43, 56, 75, 7, 12, 29 με τη μέθοδο ταξινόμησης με σωρό (heapsort). Δείξτε την τελική μορφή του σωρού, όταν από τα στοιχεία του πίνακα δημιουργήσουμε έναν σωρό και στη συνέχεια αναδιατάξουμε τα κλειδιά του σωρού, έτσι ώστε αυτός να είναι ένας σωρός μεγίστων.

Στα τεστ αξιολογησης στο προβλημα που λεει:Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 6 x 6. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η μέγιστη τιμή του Ν, ώστε ο βέλτιστος τρόπος αποθήκευσης του πίνακα να είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή); Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits.

Ποια ειναι η λυση?Εγω απαντησα 4 αλλα μου το εβγαλε λαθος ενω ημουν σιγουρος οτι το ειχα σωστο.Μπορει καποιος να εξηγησει τον τροπο λυσης???Ευχαριστω

Νομίζω η σωστή απάντηση είναι 11:

    6*6*4 > 3*Ν*4
=>    36 > 3Ν
=>    Ν <= 11

Αν κάποιος μπορεί ας το επιβεβαιώσει/με διορθώσει. Και εγώ στην αρχή 4 είχα βάλει αλλά μου το πήρε ως λάθος και δεν μπορώ να ξανακάνω το test τώρα για να το επιβεβαιώσω.

Με ανοιχτες σημειωσεις γραφουμε????

Ναι

και ανοιχτά βιβλία???

Σωστο ειναι, αλλα στην επομενη ερωτηση που ζηταει για πινακα 6Χ5 το ιδιο, μου το βγαζει λαθος με τον ιδιο τροπο..  :-\

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

Θεμα απο τις εξετασεις Φεβρουαριου 2008 :
Διαταξτε τη φραση ΔΙΑΠΛΟΚΗ για κατακερματισμο με γραμμικη εξεταση και με τετραγωνικη
εξεταση για c=2.Η συναρτηση κατακερματισμου ειναι k mod 9.

Πανω που εφαρμοσουμε τη συναρτηση κατακερματισμου?

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

Αυτό είναι σίγουρο;

Στο τόπικ "Γενικές πληροφορίες" δεν υπάρχει κάποια τέτοια αναφορά  :(

Ειναι σιγουρο, το εχει πει ο Μητκας μεσα στην αιθουσα  :)

οταν λες κοινο τι εννοεις δηλαδη θα είναι 1 η 3  βαση του παραδείγματος.....Νομίζω πως θα είναι 1

στον κατακερματισμο οταν κανουμε kmod13 για τον αριθομο 4 το αποτελεσμα 4 δεν ειναι?

yeap (ετσι θελω να πιστευω)

Div μας δίνει το ακέραιο πηλίκο της διαίρεσης δύο αριθμών

Mod μας δίνει το ακέραιο υπόλοιπο της διαίρεσης δύο αριθμών

μπορει καποιος να δει αυτο μου δινει 0,82 απο 1 βαθμο..... :'(

ρε παιδιά το Θέμα 5 μπορεί κάποιος να το λύσει ή να το εξηγήσει...θα τρελαθώ να πούμε

Εχει λύσει κανείς το θέμα 8 του Φεβρουαρίου 2008???να μ πει και εμένα πως γίνεται??? :(

Βασική ερώτηση...
Αν έχουμε κάνει τις 2 πρώτες εργασίες ολόκληρες, πόσο χρειαζόμαστε για να περάσουμε ????

μαλακία:
θεωρητικά 80/110 = 8


θεωρητικά:

100 μονάδες είναι το 8

αρα θέλεις περίπου 38/100 για το 3

3 + 2 από τις εργασίες = 5

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

Ευχαριστώ!!!!! :)

http://www.thmmy.gr/smf/index.php?topic=26988.msg523535#msg523535
για δες εδω...