[Δομές Δεδομένων] Αυτοαξιολόγηση - απαντήσεις;

[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 με προσοχή στα ονόματα των αρχείων!

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

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

[diutinus]

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

[iliasT]

Μια παραλλαγη της quicksort ειναι αντι για το κλασσικο pivot σε καθε διαμεριση, να επιλεγεται ενα
τυχαιο στοιχειο της συγκεκριμενης διαμερισης και να γινεται swap με το στοιχειο στη θεση low, ωστε
καθε φορα στη θεση low να βρισκεται τυχαιο pivot.Γραψτε τους τρεις αξονες(pivot) για τους τρεις
πρωτους διαμερισμους, καθως και την τελικη μορφη του πινακα που δινεται 19 6 33 19 3 75 30 60 43 1.

Αυτό πώς γίνεται; (από τα θέματα του 2008)

[ΚΗΜΜΥ]

Oταν διαγραφουμε σε σωρο και ανεβαζουμε το τελευταιο φυλλο
πηγαινουμε στο μικροτερο παιδι αν ειναι ελαχιστων κ στο μεγαλυτερο αν ειναι μεγιστων ή κατι άλλο?

[Sunshine]

Μια παραλλαγη της quicksort ειναι αντι για το κλασσικο pivot σε καθε διαμεριση, να επιλεγεται ενα
τυχαιο στοιχειο της συγκεκριμενης διαμερισης και να γινεται swap με το στοιχειο στη θεση low, ωστε
καθε φορα στη θεση low να βρισκεται τυχαιο pivot.Γραψτε τους τρεις αξονες(pivot) για τους τρεις
πρωτους διαμερισμους, καθως και την τελικη μορφη του πινακα που δινεται 19 6 33 19 3 75 30 60 43 1.

Αυτό πώς γίνεται; (από τα θέματα του 2008)

αυτό και εγώ δεν το καταλβαίνω.. τι εννοεί? πως να βρούμε τους άξονες pivot αφού επιλέγονται τυχαία :S

[Sunshine]

Oταν διαγραφουμε σε σωρο και ανεβαζουμε το τελευταιο φυλλο
πηγαινουμε στο μικροτερο παιδι αν ειναι ελαχιστων κ στο μεγαλυτερο αν ειναι μεγιστων ή κατι άλλο?

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

αυτο με την quickosrt μήπως το κτλβαίνεις?


edit :
το ξαναδιάβασα, μήπως εννοεί διαλέξτε τυχαίο pivot, φέρτε το στη πρώτη θέση, καντε διαμερισμό, σπαστε τον πινάκα σε δύο μικρότερους, διαλέξτε τυχαίο pivot στο καθένα, καντε διαμερισμό, συγχωνεύστε τα όλα?

[iliasT]

ναι αλλά και πάλι είναι τυχαίο! η σωστή απάντηση ποια θα είναι; Βασικά δίνει αυτό: (Απ: 30 1 43) αλλά δε μπορώ να καταλάβω πώς βγαίνει!

[Sunshine]

ναι αλλά και πάλι είναι τυχαίο! η σωστή απάντηση ποια θα είναι; Βασικά δίνει αυτό: (Απ: 30 1 43) αλλά δε μπορώ να καταλάβω πώς βγαίνει!

ε ισως να μην υπραχει standard απαντηση.. αναλογα τι θα παρεις, ε αυτος αυτα πηρε αυτα βρηκε
εγω τουλαχιστον ετσι το αντιλαμβανομαι

[iliasT]

Μπορεί κάποιος να μου εξηγήσει ψιλοαναλυτικά πώς προκύπτει η απάντηση γιατί χάθηκα λίγο!

Βρειτε την πολυπλοκοτητα
x=1;
for i=0: <10
for j=n: >=0: j--
for k=0: <n
x+=n;
(Απ:n ^2)

[ΚΗΜΜΥ]

To πρωτο φορ γινεται 10 φορες
το δευτερο απο ν μεχρι 0 δηλ ν
το τριτο απο 0 μεχρι ν δηλ ν

συνολο 10*ν*ν που ειναι ταξης ν^2

[iliasT]

Ευχαριστώ πολύ! Και μια βοήθεια εδώ αν γίνεται:

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

Με μπερδεύει αρκετά ο συγκεκριμένος αλγόριθμος...

[ΚΗΜΜΥ]

Tωρα δεν προλαβαινω και βαριεμαι να το δω, αλλα αν βαλει κατι τετοιο τι να πω

[Sunshine]

Ευχαριστώ πολύ! Και μια βοήθεια εδώ αν γίνεται:

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

Με μπερδεύει αρκετά ο συγκεκριμένος αλγόριθμος...

με αυτό ασχολούμαι και εγώ τώρα, θα το προσπαθήσω και θα ποστάρω, στο μεταξύ πάρε κατι να σε βοηθήσει να καταλάβεις(και αν καταλάβεις πες κ σε μας )
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/strMatching/KMPMatching/kmp.html

λοιπόν εγώ βρήκα
6+2+5+1+6 = 20

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

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

[arashi]

Δικιο εχει ο sunshine

Παρακάτω δίνεται ένας πίνακας χαρακτήρων μαζί με τη συχνότητα εμφάνισής τους. Αν δημιουργήσουμε τον βέλτιστο κώδικα Huffman για τους παραπάνω χαρακτήρες, τότε ποιο θα είναι το μήκος (σε bits) της αναπαράστασης του χαρακτήρα “Α” στον κώδικα Huffman;

Χαρακτήρας: syxnotita

V 1
Α 1
L  2
Ε 3
Ν 3
Τ  5
Ι  8

Πιθανες απαντησεις: 3,4,5,6,7
7 δεν ειναι το σωστο? Τι 3 γραφει η μαλακια?

4 είναι το σωστό όπως το έκανα εγώ
εμένα μου βγήκε

V 1000
Α 1001
L  101
Ε 000
Ν 001
Τ  11
Ι  01

εδω συμφωνω με το 4 αλλα δεν ειναι για το Α 0001?

αφου το βαζω διαρκως αριστερα?

εδιτ βασικα πιο σωστα να ρωτησω

πρωτα παιρνω 1-1 μετα το 2 που βγαινει με το 2 που εχω
με τα τα 3-3 μετα το 4 των 2-2 με το 5 το αρχικο και μετα το 6 απο τα 3-3 με το 8 και τελος με το 9? συνολο επανω στη ριζα 23?

ξανα εδιτ νομιζω το καταλαβα οκ!

[iliasT]

Ερώτηση: Δίνεται ο πίνακας ακεραίων αριθμών: 34, 135, 58, 24, 71, 60, 5, 10 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας
επιλογής να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις.

Μετά από 5 συγκρίσεις ο πίνακας δεν παραμένει ίδιος; Έτσι όπως το σκέφτομαι δεν έχει προλάβει ακόμη να γίνει ανταλλαγή!
1η: 34 με 135
2η: 34 με 58
3η: 34 με 24 -> βαζω στο min το 24
4η: 24 με 71
5η: 24 με 60

Από τη στιγμή που δεν έχει τελειώσει ο πίνακας δεν έχει γίνει και καμία ανταλλαγή, έτσι δεν είναι;

[ΚΗΜΜΥ]

Φανταζομαι ναι