Κεφ 3 Και 9

Question 1

Τι μελετάει η «Θεωρία Πληροφοριών»;

Answer 1

Η Θεωρια Πληροφοριων είναι ένα σημαντικό κομμάτι τις Πληροφορικής και ως στόχο έχει τη μελέτη της μέτρησης, της κωδικοποίησης και της μετάδοσης της πληροφορίας

Question 2

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

Answer 2

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

Υλικού: αναφέρεται στη μηχανή (υπολογιστή), η οποία δίνει τη δυνατότητα στα δεδομένα ενός προγράμματος να αποθηκεύονται με διάφορες μορφές αναπαράστασης στη κυρια μνημη και στις περιφερειακές συσκευές του υπολογιστή. Οι πιο μορφες αναπαραστασης δεδομενων είναι το συμπλήρωμα κατα 1, ή το συμπλήρωμα κατά 2, η δυαδική αναπαράσταση, η αναπαράσταση με βάση τον κώδικα ASCII, και η αναπαράσταση με βάση τον κώδικα EBCDIC

Γλωσσών Προγραμματισμού: εξετάζει πώς οι γλώσσες προγραμματισμού υψηλού επιπέδου μπορούν να αναπαραστήσουν τα δεδομένα, χρησιμοποιώντας μεταβλητές διαφόρων τύπων δεδομένων. Ο μεταφραστής κάθε γλώσσας είναι υπεύθυνος για την αποδοτικότερη μορφή αποθήκευσης κάθε μεταβλητής στον υπολογιστή..

Δομών Δεδομένων: αποτελείται από ένα σύνολο δεδομένων μαζί με ένα σύνολο επιτρεπτών λειτουργιών οι οποίες μπορούν να γίνουν πάνω σε αυτά τα δεδομένα. Τέτοιες δομές είναι η εγγραφή, η οποία αποτελείται από πεδία και το αρχείο που αποτελείται από εγγραφές. Παράδειγμα η εγγραφή μπορεί να περιγράφει ένα πρόσωπο, το όνομά του, το φύλο του, τον αριθμό ταυτότητας του, τα οποία αποτελούν και τα πεδία της εγγραφής

Ανάλυσης Δεδομένων: μελετάει τους τρόπους με τους οποίους καταγράφονται και συσχετίζονται τα δεδομένα μεταξύ τους, ώστε να αναπαρασταθεί η γνώση για πραγματικά γεγονότα. Οι τεχνολογίες των Βάσεων Δεδομένων, οι τεχνικές Μοντελοποίησης Δεδομένων καθώς και οι τεχνολογίες Αναπαράστασης Γνώσης ανήκουν σε αυτή τη σκοπια

Question 3

Τι είναι μια «Δομή Δεδομένων

Answer 3

Δομή Δεδομένων είναι ένα σύνολο από δεδομένα που είναι αποθηκευμένα και τα οποία δέχονται επεξεργασία από ένα σύνολο λειτουργιών.

Question 4

. Ποιες είναι οι βασικές λειτουργίες-πράξεις που μπορούν να γίνουν σε μία δομή δεδομένων;

Answer 4

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

Question 5

Σε μία δομή δεδομένων χρησιμοποιούνται και οι οκτώ λειτουργίες:

Answer 5

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

Question 6

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

Answer 6

Μεταξύ της δομής δεδομένων και του αλγόριθμου που επεξεργάζεται τη δομή, υπάρχει μεγάλη εξάρτηση, η οποία περιγράφεται από την εξίσωση που διατυπώθηκε το 1976 από τον Wirth: Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα,

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

Question 7

Ποιες είναι οι δύο κυριότερες κατηγορίες δομών δεδομένων

Answer 7

Οι δομές δεδομένων διακρίνονται σε δύο μεγάλες κατηγορίες: τις στατικές και τις δυναμικές,

Question 8

Τι είναι δυναμική δομή δεδομένων

Answer 8

Οι δυναμικές δομές δεδομένων έχουν τα εξής χαρακτηριστικά:

Τα στοιχεία τους δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.

Δεν έχουν σταθερό μέγεθος.

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

Question 9

Τι είναι στατική δομή δεδομένων;

Answer 9

Χαρακτηριστικά των στατικών δομών δεδομένων είναι:

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

Τα στοιχεία των στατικών δομών αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.

Έχουν σταθερό μέγεθος

Question 10

Τι ονομάζεται πίνακας;

Answer 10

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

Question 11

Τι είναι οι δείκτες του πίνακα;

Answer 11

Ο δείκτης του πίνακα είναι μια ακέραια εκφραση που ποποθετείται μέσα στα συμβολα [και]. Η αχερια εκφραση μπορεί να είναι σταθερή ( να αποτελείται από ακέραιο αριθμός ή να είναι μια μεταβλητή. Όταν ο δείκτης είναι για μεταβλητής τοτε μπορεί να έχει ένα οποιοδήποτε αποδεκτό όνομα, αν και συνηθίζεται στον προγραμματισμό να χρησιμοποιούνται ως ονόματα δεικτών οι μεταβλητέ ς ij κ

Question 12

Ποια η διαφορά του πίνακα και του στοιχείο του πίνακα,

Answer 12

Απάντηση:

Ο πίνακας είναι ένα σύνολο από αντικείμενα ιδίου τύπου δεδομένων, στα οποία αναφερόμαστε με ένα κοινό όνομα, και το κάθε ένα από αυτά τα αντικείμενα αποτελεί ένα στοιχείο του πίνακα, δηλαδή ο πίνακας είναι ένα σύνολο στοιχείων. Αντίθετα, το καθε στοιχείο είναι ένα κομμάτι του πίνακα και προσδιορίζεται από το όνομα του πίνακα και έναν δεικτη

Question 13

128. Τι διάσταση μπορεί να έχει ένας πίνακας;

Answer 13

Ένας πίνακας μπορεί να είναι μονοδιάστατος, δισδιάστατος, τρισδιάστατος και γενικά ν-διάστατος. Ο αριθμός των δεικτών καθορίζει τη διάσταση του πίνακα.

Question 14

Τι είδους δομή είναι ένας πίνακας;

Answer 14

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

Question 15

Πού αποθηκεύονται τα στοιχεία ενός πίνακα;

Answer 15

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

Question 16

Για ποιο λόγο χρησιμοποιούνται οι πίνακες;

Answer 16

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

Question 17

Ποιος είναι τα μειονεκτήματα χρήσης πινάκων

Answer 17

τα μειονεκτήματα από τη χρηση των πινάκων είναι τα εξης:
Ο ι πίνακες απαιτούν μνήμη. Αυτό συμβαινει, γιατι κάθε πίνακας δεσμεύει από αρχή του προγράμματος ένα μεγάλο αριθμό θέσεων μνήμης. Έτσι όταν σε ένα μεγάλο πρόγραμμα χρησιμοποιούμε άσκοπα μεγάλους πίνακες, μπορούμε να οδηγηθούμε σε αδυναμία εκτέλεσης του ίδιου του προγράμματος.
Οι πίνακες περιορίζουν τις δυνατότητες του προγράμματος, γιατί η χρήση τους απαιτεί τη δήλωση εξαρχής του μεγέθους του πίνακα, για να δεσμευτούν οι απαραί τητες Θέσεις μνήμα, ( είναι στατική δομή | Αυτό έχει ως συνέπεια το μέγεθος τους να παραμένει υπαρχειωτικά σταθερό κατα τη διάρκεια εκτέλεσης του προγράμματος και ν α μη μπορεί να μεταβληθεί

Question 18

Ποιες είναι οι τυπικές επεξεργασίες που μπορούν να γίνουν σε έναν πίνακα;

Answer 18

Απάντηση:

Υπολογισμός αθροισμάτων στοιχείων του πίνακα.

Εύρεση του μέγιστου ή του ελάχιστου στοιχείου του πίνακα,

Ταξινόμηση των στοιχείων του πίνακα,

Αναζήτηση ενός στοιχείου του πίνακα.

Συγχώνευση δύο πινάκων.

Question 19

. Πότε ένας πίνακας ονομάζεται μονοδιάστατος;

Answer 19

ένας πίνακας που χρησιμοποιει μονο έναν δείκτη, για να γίνεται αναφορά στα στοιχεία του, ονομάζεται μονοδιάστατο ς πινακας

Question 20

Πώς δηλώνεται ένας πίνακας σε ένα πρόγραμμα γραμμένο σε ΓΛΩΣΣΑ

Answer 20

Απάντηση:

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

Question 21

Όλες οι λειτουργίες που εφαρμόζονται σε μια δομή δεδομένων, μπορούν να χρησιμοποιηθούν στους πίνακες;

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

Answer 21

Στους πίνακες δεν μπορούν να εφαρμοστούν και οι οχτώ λειτουργίες που εφαρ μόζονται πάνω σε μια δομή δεδομένων.

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

Question 22

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

Answer 22

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

Question 23

. Για την ταξινόμηση των δεδομένων (κόμβων) μιας δομής δεδομένων, ποιες σειρές διάταξης μπορούμε να εφαρμόσουμε;

Answer 23

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

Question 24

Να δώσετε τον ορισμό της ταξινόμησης Ν. στοιχείων (α1, α2, …. αν.) σε αύξουσα σειρά.

Answer 24

Απάντηση:

Δοθέντων των στοιχείων α1 α2…. αν, η ταξινόμηση συνίσταται στη μετάθεση της θέσης των στοιχείων, ώστε να τοποθετηθούν σε μία σειρά ακ1, άκ2,…ακν ώστε, δοθείσης μιας συνάρτησης διάταξης φ, να ισχύει f(aκ1) <= f(aκ2) ……<=φ(ακν)
Στην φθίνουσα ταξινόμηση ισχύει f(aκ1) >= f(aκ2) ……>=φ(ακν)

Question 25

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

Answer 25

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

Question 26

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

Answer 26

Την ταξινόμηση ευθείας ανταλλαγής ή αλλιώς ταξινόμηση «φυσαλίδας». Η μέθοδος αυτή είναι η πιο απλή από όλες τις μεθόδους ταξινόμησης, αλλά ταυτόχρονομησης και η λιγότερο αποδοτική, καθώς είναι u πιο αργή από όλες τις γνωστές μεθόδους ταξινόμησης.

Question 27

ποια είναι τα κριτήρια με τα οποια επιλέγεται ο καλύτερος αλγόριθμος ταξινόμησης ενος πίνακα

Answer 27

η επιλογή του καλύτερου αλγορίθμου ταξινόμησης ενός πίνακα εξαρτάται από δύο κριτήρια:

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

Question 28

Πως λειτουργεί η μεθοδος ταξινόμησης με επιλογή

Answer 28

Απάντηση:

Η εφαρμογή της μεθόδου «ταξινόμηση με επιλογή» πραγματοποιείται με διαδοχικές προσπελάσεις του πίνακα, βασίζεται στην επιλογή του μικρότερου ή του μεγαλύτερου στοιχείου (για αύξουσα ή φθίνουσα ταξινόμηση) από αυτά που δεν έχουν ταξινομηθεί και την τοποθέτησή του στην αρχή του πίνακα.

Question 29

Δίνεται πίνακας table με Ν στοιχεια. Να παρουσιάσετε και να εξηγήσετε τον αλγόριθμο της ταξινόμησης ευθείας ανταλλαγής (φυσαλίδα) που ταξινομεί τον πίνακα table κατα αύξουσα σειρα

Answer 29

Αλγόριθμος Ταξινόμηση_ ευθείας_ ανταλλαγής
Δεδομένα // N, table //
Για 1 από 2 μέχρι Ν !Ο εξωτερικός βρόχος εκτελείται Ν-1 φορές
Για j από Ν μέχρι ί με βήμα -1 !Ο εσωτερικός βρόχος αρχίζει τη σύγκριση από το τέλος του πίνακα
Av table[j-1]> table[j] τότε
Αντιμετάθεσε table[j - 1], table[j] !Αύξουσα ταξινόμηση
Τέλος_ αν
Τέλος επανάληψης
Τέλος επανάληψης
Αποτελέσματα // table //

Τέλος Ταξινόμηση_ ευθείας_ ανταλλαγής

Question 30

Τι γνωρίζετε για τη μέθοδο «Ταξινόμηση με επιλογή»;

Answer 30

Η εφαρμογή της μεθόδου «ταξινόμηση με επιλογή» πραγματοποιείται με διαδοχικές προσπελάσεις του πίνακα, βασίζεται στην επιλογή του μικρότερου ή του μεγαλύτερου στοιχείου (για αύξουσα ή φθίνουσα ταξινόμηση) από αυτά που δεν έχουν ταξινομηθεί και την τοποθέτησή του στην αρχή του πίνακα.

Αλγόριθμος Ταξ_με_επιλογή_2
Δεδομένα // N, table //
Για ί από 1 μέχρι Ν !η Ν-1
min <-table[i]
θέση< – 1
Για j από i +1 μέχρι Ν
Av table[j] <min τότε
min ← table[j]
θέση <– j
Τέλος αν
Τέλος επανάληψης
table[θέση) <-table[i]
table[i] ← min
Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος Ταξ με επιλογή_2

Question 31

Τι είναι οι δομές δεδομένων δευτερεύουσας μνήμης;

Answer 31

Λόγω του ότι ο όγκων των δεδομένων που επεξεργάζονται μεγάλες εμπορικές επ ιστημονικέ ς εφαρμογές είναι μεγάλος, αυτό έχει σαν επακόλουθο το μέγεθος της κύριας μνημης του υπολογιστή να μην ε παρκεί για την αποθηκευση τους . Για να μην χαθούν τα δεδομενα χρησιμοποιούνται ειδικες δένει που αποθηκεύουν τα δεδομενα στη δευτερεύουσα (μαγνητικός δίσκος) και όχι στην κύρια μνήμη. Αυτές είναι οι δομές δεδομέδων δευτερεύουσας μνήμης και είναι γνωστές ως αρχεία

Question 32

Ποια σημαντική διαφορά υπάρχει μεταξύ των δομών δεδομένων κύριας και

δευτερεύουσας μνήμης

Answer 32

Απάντησης

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

Question 33

Να περιγράψετε τις έννοιες «εγγραφή», «πεδία», «πρωτεύον κλειδί», «δευτε ρεύον κλειδί» που συναντάμε σε ένα αρχείο. Να δώσετε ένα παράδειγμα μιας εγγραφής και να εξηγήσετε τις παραπάνω έννοιες.

Answer 33

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

Question 34

Πώς εφαρμόζεται η λειτουργία της αναζήτησης σε έναν μονοδιάστατο πίνακα,

Answer 34

Απάντηση,

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

Question 35

.

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

Answer 35

Απάντηση :

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

Question 36

Ποιες γνωστές μεθόδους αναζήτησης γνωρίζετε και ποιες είναι οι διαφορές τουςΟι πιο γνωστοί αλγόριθμοι αναζήτησης είναι δύο:

Answer 36

Οι πιο γνωστοι αλγόριθμοι αναζήτησης είναι δυο:
•Η σειριακή αναζήτηση. Μπορεί να χρησιμοποιηθεί σε πίνακες που είναι ταξινόμη μένοι, αλλά υποχρεωτικά χρησιμοποιείται σε μη ταξινομημένους πίνακες. Είναι η πιο απλή από όλες τις μεθόδους αναζήτησης, αλλά και η λιγότερο αποτελεσματική
•Η δυαδική αναζήτηση. Χρησιμοποιείται μόνο σε ταξινομημένους πίνακες και είναι πιο αποδοτική από τη σειριακή αναζήτηση.

Question 37

. Από τι εξαρτάται η εφαρμογή μιας μεθόδου αναζήτησης σε έναν πίνακα;

Answer 37

εξαρταται από το εαν ο πίνακας είναι ταξινομημένοι ή όχ ι και αν ο πίνακας περιέχει στοιχεία που είναι όλα διαφορετικά μεταξύ τους ή περιέχει στοιχεια που είναι ορισμένα ιδια

Question 38

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

Answer 38

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

Question 39

Δίνεται μονοδιάστατος μη ταξινομημένος πίνακας table με Ν διαφορετικά στοιχεία. Να γράψετε τον αλγόριθμο σειριακής αναζήτησης της τιμής μιας μεταβλητής key στον πίνακα table.

Answer 39

Με τον αλγόριθμο της σειριακής αναζήτησης ψάχνουμε την τιμή key στον πίνακα table[N]:

Αλγόριθμος Σειριακή_ Αναζήτηση_ 1
Δεδομένα // N, table, key //
flag< – Ψευδής. ! θεωρούμε στην αρχή ότι το key δεν υπάρχει μέσα στον πίνακα
θέση <– Ο. ! γι’ αυτό και η θέση του είναι μηδέν
Ι<-1 ! δείκτης για να λαμβάνουμε ένα – ένα τα στοιχεία του πίνακα

Όσο flag = Ψευδής ΚΑΙ 1 <= Ν επανάλαβε. ! ξεκινώντας με το πρώτο στοιχείο όσο το key δεν βρέθηκε και δεν έχει τελειώσει ο πίνακας συνέχισε την αναζήτηση

Av table[I] = key τότε.  ! αν ένα στοιχείο είναι ίσο με το key τότε βρέθηκε και κάνε τη flag «αληθής»
     flag< – Αληθής
     θέση <-Ι.     ! τοποθέτησε στη μεταβλητή «θέση» το 1    αλλιώς
   Θεση<-Ι+1!αν το στοιχείο δεν είναι ίσο με το key τότε πήγαινε στο επόμενο στοιχείο Τέλος αν

Τέλος επανάληψης
Av flag = Αληθής τότε !αν η flag είναι «αληθής», σημαίνει πως το στοιχείο βρέθηκε
Εμφάνισε “Η τιμή βρέθηκε στη θέση”, θέση

αλλιώς! αν η flag είναι «ψευδής», σημαίνει πως το στοιχείο δεν βρέθηκε Εμφάνισε “Η τιμή δεν βρέθηκε μέσα στον πίνακα”

Τέλος αν! μπορούμε να ελέγξουμε και τη μεταβλητή «θέση»

Τέλος Σειριακή Αναζήτηση_1

Question 40

Δίνεται μονοδιάστατος ταξινομημένος πίνακας table κατά αύξουσα σειρά, με Ν διαφορετικά στοιχεία. Να γράψετε τον αλγόριθμο δυαδικής αναζήτησης μιας τιμής κευ στον πίνακα τάβλε

Answer 40

με τον αλγόριθμο της δυα δικης αναζήτησης ψάχνουμε την τιμή key στον ταξινομημένο κατα αύξουσα σειρά, πίνακα table[N]. Η μέθοδος λειτουργεί ως εξής

Αλγόριθμος Δυαδική αναζήτηση
Δεδομένα // N, table, key //
f!ag <- Ψευδής! θεωρούμε στην αρχή ότι το key δεν υπάρχει μέσα στον πίνακα
θέση<-ο! γι’ αυτό και η θέση του είναι μηδέν
αρχικός<- 1!δείκτης για την αρχή του διαστήματος αναζήτησης
τελικός< - Ν!δείκτης για το τέλος του διαστήματος αναζήτησης

Oσο flag = Ψευδής ΚΑΙ αρχικός <= τελικός επανάλαβε
μέσος <- (αρχικός +τελικοσ)/διβ 2! δείκτης για το μέσο του διαστήματος αναζήτησης
Αν ταβλε[μεσος]=κευ τότε !αν το μεσαίο στοιχείο είναι ίσο με το κευ τότε βρέθηκε
flag <– Αληθής! κάνε τη flag «αληθής»
θέση <– μέσος ! και τοποθέτησε στη μεταβλητή «θέση» τον δείκτη μεσο

αλλιώς αν table[μέσος) <key τότε !αν το μεσαίο στοιχείο είναι μικρότερα από το key
αρχικός <– μέσος +1. !η αρχή της αναζήτησης γίνεται ο επόμενος του μέσου

αλλιώς_αν table(μέσος) >key)! το μεσαίο στοιχείο είναι μεγαλύτερο από το key (table(μέσος) >key)
τελικός< – μέσος - 1 !το τέλος της αναζήτησης γίνεται ο προηγούμενος του μέσου

Τέλος αν

Τέλος επανάληψης

Αν flag = Αληθής τότε !αν η flag είναι «αληθής», σημαίνει πως το στοιχείο βρέθηκε

Εμφάνισε Η τιμή βρέθηκε στη θέση, θέση

αλλιώς !αν η flag είναι «ψευδής», σημαίνει πως το στοιχείο δεν βρέθηκε Εμφάνισε. “Η τιμή δεν βρέθηκε μέσα στον πίνακα”

Τέλος αν

Τέλος Δυαδική αναζήτηση

Question 41

Πότε χρησιμοποιείται η δυαδική αναζήτηση;

Answer 41

Η δυαδική αναζήτηση χρησιμοποιείται μόνο σε περιπτώσεις στις οποίες ο πίνακας είναι ταξινομημένος

Question 42

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

Answer 42

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

Η σειριακή αναζητής ειναι η πιο απλή και λιγότερο αποτελεσματική μέθοδος, Αντίθετα, η δυαδική αναζήτηση είναι πιο αποδοτική από τη σειριακή αναζήτηση Στο προηγούμενο παράδειγμα είχρειάστηκαν 3 επαναλήψεις με τη δυαδική εναζήτηση για να εντοπιστεί το στοιχείο κεν, ενώ αντίστοιχα θα χρειαζόταν 5 επαναλήψεις με τη σειριακή αναζήτηση

επαναλήψεις με τη σειριακή αναζήτηση

Question 43

. Πότε ένας πίνακας ονομάζεται δισδιάστατος

Answer 43

ένας πίνακας που χρησιμοποιεί δυο δείκτες για να γίνεται αναφορά στα στοιχεια του, ονομάζεται δισδιάστατος π ινακας

Question 44

πότε εναι δισδιάστατο, πίνακας λέγεται τετραγωνικό)

Answer 44

ένας δισδιάστατος πίνακας λέγεται τετραγωνικών όταν το μέ γεθος των δυο διαστάσεων είναι ισο δηλαδη έχει ιδιο αρι θμό γραμμών και στύλων και συμβολίζεται ως πίνακας N xN