[Δομές δεδομένων] Απορίες στις ασκήσεις 2013/14

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

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

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Schro]

Στην quicksort εχω δυο δεικτες r και l. Εστω οτι σαν pivot επιλεγω το πρωτο στοιχειο του πινακα.
Μετα ο δεικτης r θα αρχισει να σκαναρει προς τα αριστερα μεχρι να βρει στοιχειο μικροτερο απο το πιβοτ. Θα σταματησει μολις βρει.
Μετα ο δεικτης l θα αρχισει να σκαναρει προς τα δεξια μεχρι να βρει στοιχειο μεγαλυτερο του πιβοτ. Θα σταματησει και αυτος και μετα οι δυο δεικτες θα ανταλλαξουν στοιχεια. Νομιζω μεχρι εδω ειμαι καλα. Αφου γινει η ανταλλαγη, ο δεικτης l προχωραει ενα στοιχειο προς τα δεξια και μετα αρχιζει παλι ο r να σκαναρει μεχρι να βρεθει αριστερα του l;; Βασικα με ενδιαφερει το τι γινεται μετα την ανταλλαγη. Συγγνωμη για τον μεγαλο προλογο.

[Exomag]

Μπορεί κάποιος ρε παιδιά να μου δώσει τα φώτα του με τον αλγόριθμο Knuth-Morris-Pratt...πως βγάζουμε την συνάρτηση αποτυχίας και γενικά πως δουλεύουμε στην αναζήτηση του προτύπου??

Αν δεις εδώ στη σελίδα 12 (σελίδα 45-46) λέει αναλυτικά τον αλγόριθμο.

[nvog1993]

Αυγ. 07.->Θεμα 1
1)Δ
2)Ε
3)Β
4)Α

Για το 1) μου φαίνεται ότι είναι n*n*(1+2+3+...+n)=n*n*n(n+1)/2=O(n⁴) (όποιος το ξέρει σίγουρα, ας το επαληθεύσει)
Για το 2) έχουμε περίπτωση RL, οπότε θα χρειαστεί διπλή στο 27.
Τα υπόλοιπα σωστά

το εξηγεις λιγο το 2)??

Τελικά λάθος το έχω απαντήσει. Η περίπτωση είναι LL στον κόμβο 27 και θα χρειαστεί μια απλή περιστροφή του 27. Αφού δεν υπάρχει τέτοια επιλογή, είναι όντως το Ε.

[nvog1993]

Στην quicksort εχω δυο δεικτες r και l. Εστω οτι σαν pivot επιλεγω το πρωτο στοιχειο του πινακα.
Μετα ο δεικτης r θα αρχισει να σκαναρει προς τα αριστερα μεχρι να βρει στοιχειο μικροτερο απο το πιβοτ. Θα σταματησει μολις βρει.
Μετα ο δεικτης l θα αρχισει να σκαναρει προς τα δεξια μεχρι να βρει στοιχειο μεγαλυτερο του πιβοτ. Θα σταματησει και αυτος και μετα οι δυο δεικτες θα ανταλλαξουν στοιχεια. Νομιζω μεχρι εδω ειμαι καλα. Αφου γινει η ανταλλαγη, ο δεικτης l προχωραει ενα στοιχειο προς τα δεξια και μετα αρχιζει παλι ο r να σκαναρει μεχρι να βρεθει αριστερα του l;; Βασικα με ενδιαφερει το τι γινεται μετα την ανταλλαγη. Συγγνωμη για τον μεγαλο προλογο.

Αφού γίνει η αναταλλαγή, ξεκινάει πάλι ο left να προχωράει μέχρι να βρει μεγαλύτερο του pivot. Όταν βρει, σταματάει αυτός και αρχίζει ο right μέχρι να βρει μικρότερο. Αν σταματήσει και αυτός αλλά έχουν προσπεράσει ο ένας τον άλλο, σημαίνει ότι ο left συνάντησε το πρώτο στοιχείο του πίνακα με τα μεγαλύτερα από το πιβοτ στοιχεία και ο right συνλαντησε το πρώτο στοιχείο του πίνακα με τα μικρότερα από το πίβοτ στοιχεία. Εφόσον ο πίνακας είναι συνεχής, τα δύο αυτά στοιχεία θα είναι γειτονικά και άρα και οι δείκτες Left και right θα είναι δίπλα δίπλα. Ο right θα είναι σε στοιχείο μικρότερο του πίβοτ. Άρα ανταλλάζεις το πιβοτ με αυτό το στοιχείο και τώρα ο πίνακας σου είναι χωρισμένος σε δύο, με σύνορο το πίβοτ. Τους παίρνεις έναν έναν και ξανα εκτελείς τον αλγόριθμο.

[Schro]

Ευχαριστω πολυ! 
Το εχω λαθος πανω btw ο l ξεκιναει πρωτος! 

[vouz]

Αυγ. 07.->Θεμα 1
1)Δ
2)Ε
3)Β
4)Α

Για το 1) μου φαίνεται ότι είναι n*n*(1+2+3+...+n)=n*n*n(n+1)/2=O(n⁴) (όποιος το ξέρει σίγουρα, ας το επαληθεύσει)
Για το 2) έχουμε περίπτωση RL, οπότε θα χρειαστεί διπλή στο 27.
Τα υπόλοιπα σωστά

το εξηγεις λιγο το 2)??

Τελικά λάθος το έχω απαντήσει. Η περίπτωση είναι LL στον κόμβο 27 και θα χρειαστεί μια απλή περιστροφή του 27. Αφού δεν υπάρχει τέτοια επιλογή, είναι όντως το Ε.

εστειλα στον αντωνη και με ειπε το Β

[nvog1993]

Αυγ. 07.->Θεμα 1
1)Δ
2)Ε
3)Β
4)Α

Για το 1) μου φαίνεται ότι είναι n*n*(1+2+3+...+n)=n*n*n(n+1)/2=O(n⁴) (όποιος το ξέρει σίγουρα, ας το επαληθεύσει)
Για το 2) έχουμε περίπτωση RL, οπότε θα χρειαστεί διπλή στο 27.
Τα υπόλοιπα σωστά

το εξηγεις λιγο το 2)??

Τελικά λάθος το έχω απαντήσει. Η περίπτωση είναι LL στον κόμβο 27 και θα χρειαστεί μια απλή περιστροφή του 27. Αφού δεν υπάρχει τέτοια επιλογή, είναι όντως το Ε.

εστειλα στον αντωνη και με ειπε το Β

Όντως. Έχω μπερδέψει τους κόμβους στους οποίους γίνονται οι διπλές και οι απλές περιστροφές.

[kourdisto_portokali]

Φεβ. 11 θεμα 1
Συμφωνειτε;
1)Β
2)Γ
3)Α
4)ξερεις κανεις να το εξηγησει

Επισης απο την ιδια χρονια στον πινακα κατακερματισμου για h'(k)=-1 παω προς τα αριστερα αλλα δεν υπαρχει καμια κενη θεση ...τι κανω σ αυτη την περιπτωση;;; (ή μηπως εχω κανει κατι αλλο λαθος; )...το ιδιο συμβαινει κ για την h'(k)=(kmod9)-9....

[nvog1993]

Φεβ. 11 θεμα 1
Συμφωνειτε;
1)Β
2)Γ
3)Α
4)ξερεις κανεις να το εξηγησει;

Στο 4, όπως είναι το δέντο χωρίς αλλαγή ισχύει ότι:
Σ=00 (2 ψηφία)
Ο=01(2 ψηφία)
Ε=0 (1 ψηφίο)
Α=1 (1 ψηφίο)
Άρα το κόστος έιναι ίσο με Κ=130*2( για το Σ) + 150*2 (για το Ο) + 1*250 (για το Α)=810
Αν αλλάξουν θέση, το Ο θα θέλει 1 ψηφίο και το Α θα θέλει 2. Άρα το νέο κόστος θα είναι:
Κ'=130*2+150*1+250*2=810
Άρα το κόστος θα μείνει το ίδιο. Ετσι νομίζω ότι βγαίνει. Όποιος μπορεί, ας το επαληθεύσει.



Το Γ) ερώτημα σωστό είναι το γ).Το 16 (leftChild) είναι μεγαλύτερο από το δεξί παιδί του πατέρα του 4 (δηλαδή το 4). Άρα θα μπει με το rightChild του 4, δηλαδή το 1. Μόλις μπει να εκτελέσει την Traverse για 1 και εκτυπώσει το 1, δεν θα μπει στην if και θα ξαναεκτυπώσει το 1. Έπειτα θα βγει από τη traverse(1) και τότε θα πάει να εκτελέσει την επόμενη εντολή της Traverse(4), η οποία είναι να εκτυπώσει το 4. Τέλος θα βγει και από την Traverse(4) και θα εκτελέσει την τελευταία εντολή της Traverse(10) Που είναι να εκτυπώσει το 10.
Αρα θα εκτυπώσει 10411410

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

[Gru]

Φεβρουάριος 2008 στο Θέμα 4 η κλάση Array κληρονομεί την Element?

[kourdisto_portokali]

Φεβ. 11 θεμα 1
Συμφωνειτε;
1)Β
2)Γ
3)Α
4)ξερεις κανεις να το εξηγησει;

Στο 4, όπως είναι το δέντο χωρίς αλλαγή ισχύει ότι:
Σ=00 (2 ψηφία)
Ο=01(2 ψηφία)
Ε=0 (1 ψηφίο)
Α=1 (1 ψηφίο)
Άρα το κόστος έιναι ίσο με Κ=130*2( για το Σ) + 150*2 (για το Ο) + 1*250 (για το Α)=810
Αν αλλάξουν θέση, το Ο θα θέλει 1 ψηφίο και το Α θα θέλει 2. Άρα το νέο κόστος θα είναι:
Κ'=130*2+150*1+250*2=810
Άρα το κόστος θα μείνει το ίδιο. Ετσι νομίζω ότι βγαίνει. Όποιος μπορεί, ας το επαληθεύσει.



Το Γ) ερώτημα σωστό είναι το γ).Το 16 (leftChild) είναι μεγαλύτερο από το δεξί παιδί του πατέρα του 4 (δηλαδή το 4). Άρα θα μπει με το rightChild του 4, δηλαδή το 1. Μόλις μπει να εκτελέσει την Traverse για 1 και εκτυπώσει το 1, δεν θα μπει στην if και θα ξαναεκτυπώσει το 1. Έπειτα θα βγει από τη traverse(1) και τότε θα πάει να εκτελέσει την επόμενη εντολή της Traverse(4), η οποία είναι να εκτυπώσει το 4. Τέλος θα βγει και από την Traverse(4) και θα εκτελέσει την τελευταία εντολή της Traverse(10) Που είναι να εκτυπώσει το 10.
Αρα θα εκτυπώσει 10411410

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

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

[Mr K]

Φεβρουάριος 2008 στο Θέμα 4 η κλάση Array κληρονομεί την Element?

οχι

[Mr K]

Έκανε κανεις το β-δενδρο του 2007 2α) ; πως βγαίνει;

[Dealan]

Στο 4, όπως είναι το δέντρο χωρίς αλλαγή ισχύει ότι:
Σ=00 (2 ψηφία)
Ο=01(2 ψηφία)
Ε=0 (1 ψηφίο)
Α=1 (1 ψηφίο)

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

[nvog1993]

Στο 4, όπως είναι το δέντρο χωρίς αλλαγή ισχύει ότι:
Σ=00 (2 ψηφία)
Ο=01(2 ψηφία)
Ε=0 (1 ψηφίο)
Α=1 (1 ψηφίο)

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

Σωστός! Τουλάχιστον δεν επηρρεάζει την άσκηση.