Λύσεις — Κεφάλαιο 8: Δομές Δεδομένων ΙΙ (σελ. 150-152) – ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ

ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ – ΛΥΣΕΙΣ – ΑΠΑΝΤΗΣΕΙΣ Ασκήσεων Σχολικού Βιβλίου Λύσεις — Κεφάλαιο 8: Δομές Δεδομένων ΙΙ (σελ. 150-152) – ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ

Λύσεις — Κεφάλαιο 8: Δομές Δεδομένων ΙΙ (σελ. 150-152)

Λύσεις των 8 Δραστηριοτήτων (κώδικας Python: συμβολοσειρές, στοίβα, λεξικό, λίστες) και των 10 Ερωτήσεων του κεφαλαίου 8, ελεγμένες με το επίσημο βιβλίο λύσεων.

Δραστηριότητα 1 — Τα γράμματα μιας λέξης, ένα σε κάθε γραμμή

Ερώτηση: Να γράψετε ένα πρόγραμμα το οποίο θα διαβάζει μία λέξη και θα εμφανίζει τα γράμματά της, ένα σε κάθε γραμμή.

Απάντηση:

Η συμβολοσειρά είναι ακολουθία χαρακτήρων, οπότε τη διασχίζουμε γράμμα-γράμμα με το ιδίωμα for … in … (σελ. 128-129) και τυπώνουμε κάθε γράμμα με ξεχωριστή print (η print αλλάζει γραμμή):

# Εμφανίζει κάθε γράμμα της λέξης σε ξεχωριστή γραμμή
word = raw_input('Δώσε μια λέξη: ')
for letter in word:
    print letter

Για τη λέξη PYTHON εμφανίζει P, Y, T, H, O, N σε έξι γραμμές. Εναλλακτικά με δείκτες: for i in range(len(word)): print word[i]. (Python 3: input() και print(letter).)

Σύνοψη: word = raw_input(...)· for letter in word: print letter.

Κριτήρια αξιολόγησης:

Διάσχιση με for … in και print ανά γράμμα.

Δραστηριότητα 2 — Πλήθος κεφαλαίων αγγλικών γραμμάτων μιας λέξης

Ερώτηση: Να γράψετε ένα πρόγραμμα το οποίο θα διαβάζει μία λέξη και θα εμφανίζει πόσα κεφαλαία αγγλικά γράμματα περιέχει η λέξη.

Απάντηση:

Κατασκευάζουμε μια συμβολοσειρά με όλα τα κεφαλαία αγγλικά γράμματα και, διασχίζοντας τη λέξη, ελέγχουμε κάθε γράμμα με τον υπαρξιακό τελεστή in (σελ. 128)· ένας μετρητής αυξάνεται για κάθε επιτυχία:

# Μετράει τα κεφαλαία αγγλικά γράμματα μιας λέξης
enCapSet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
word = raw_input('Δώσε μια λέξη: ')
countCapitals = 0
for letter in word:
    if letter in enCapSet:
        countCapitals += 1
print 'Κεφαλαία αγγλικά γράμματα:', countCapitals

Παράδειγμα: 'PyThON' → 4. Το ίδιο πρότυπο («σύνολο επιτρεπτών χαρακτήρων + in») χρησιμοποιεί το βιβλίο στην count_vowels (σελ. 129) και θα το ξαναχρησιμοποιήσουμε στη δραστηριότητα 8. Εναλλακτικά με το εύρος 'A' <= letter <= 'Z' (λεξικογραφική σύγκριση).

Σύνοψη: Συμβολοσειρά με τα 26 κεφαλαία· for letter in word: if letter in enCapSet: μετρητής += 1· εμφάνιση του μετρητή.

Κριτήρια αξιολόγησης:

Σωστό σύνολο κεφαλαίων + in + μετρητής.

Δραστηριότητα 3 — Αντιστροφή λέξης με στοίβα

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

Απάντηση:

Ιδέα: ωθούμε τα γράμματα της λέξης στη στοίβα με τη σειρά που διαβάζονται· το τελευταίο γράμμα είναι το τελευταίο που μπαίνει, άρα βρίσκεται στην κορυφή. Απωθώντας, βγαίνει πρώτα το τελευταίο, μετά το προτελευταίο κ.ο.κ. (LIFO) — τα γράμματα εμφανίζονται σε αντίστροφη σειρά. Χρησιμοποιούμε την υλοποίηση στοίβας του βιβλίου (σελ. 143):

# Υλοποίηση στοίβας (σελ. 143) — χρησιμοποιείται και στις επόμενες δραστηριότητες
def push(stack, item):
    stack.append(item)
def pop(stack):
    return stack.pop()
def isEmpty(stack):
    return len(stack) == 0
def createStack():
    return []

# Αντιστρέφει μια λέξη με τη χρήση στοίβας
word = raw_input('Δώσε μια λέξη: ')
stack = createStack()
for letter in word:
    push(stack, letter)          # ώθηση κάθε γράμματος
reverse = ''
while not isEmpty(stack):
    reverse = reverse + pop(stack)   # απώθηση: πρώτα το τελευταίο γράμμα
print reverse

Παράδειγμα: 'PYTHON' → στοίβα [P, Y, T, H, O, N] (κορυφή N) → απωθήσεις N, O, H, T, Y, P → 'NOHTYP'. Ο έλεγχος isEmpty πριν από κάθε απώθηση είναι απαραίτητος (σελ. 142). Ίδια λογική με την εφαρμογή «αντιστροφή αριθμών» της σελ. 143.

Σύνοψη: Ώθηση κάθε γράμματος στη στοίβα· όσο δεν είναι κενή, απώθηση και συνένωση σε νέα συμβολοσειρά· εμφάνιση — LIFO δίνει την αντίστροφη σειρά.

Κριτήρια αξιολόγησης:

Χρήση push/pop/isEmpty (όχι απλώς word[::-1]) + εξήγηση LIFO.

Δραστηριότητα 4 — isSubstring και πλήθος εμφανίσεων υποσυμβολοσειράς

Ερώτηση: Να γράψετε μια συνάρτηση isSubstring(string, substring) η οποία θα ελέγχει, αν η συμβολοσειρά substring περιέχεται στη συμβολοσειρά string και αν ναι, θα επιστρέφει True. Στη συνέχεια να υλοποιήσετε μια δεύτερη συνάρτηση, η οποία θα επιστρέφει πόσες φορές εμφανίζεται μια συμβολοσειρά μέσα σε μια άλλη.

Απάντηση:

Μέρος Α: ο υπαρξιακός τελεστής in λειτουργεί και για ολόκληρες υποσυμβολοσειρές ('Py' in 'Python' → True, σελ. 128), οπότε η συνάρτηση γράφεται σε μία γραμμή:

def isSubstring(string, substring):
    return substring in string

Μέρος Β — πλήθος εμφανίσεων: για κάθε θέση pos του string ελέγχουμε αν το substring «ξεκινά» εκεί, συγκρίνοντας χαρακτήρα-χαρακτήρα (βοηθητική isPrefix), και μετράμε τις επιτυχίες:

# Ελέγχει αν το substring εμφανίζεται στο string ξεκινώντας από τη θέση start
def isPrefix(string, substring, start):
    i = start
    j = 0
    count = 0
    while j < len(substring) and i < len(string):
        if string[i] == substring[j]:
            count = count + 1
        i = i + 1
        j = j + 1
    return count == len(substring)

# Μετρά πόσες φορές εμφανίζεται το substring μέσα στο string
def findSubstring(string, substring):
    pos = 0
    count = 0
    while pos < len(string):
        if isPrefix(string, substring, pos):
            count = count + 1
        pos = pos + 1
    return count

print isSubstring('Python', 'tho')          # True
print findSubstring('banana', 'ana')        # 2 (θέσεις 1 και 3 — επικαλυπτόμενες)
print findSubstring('abcabcab', 'ab')       # 3

Εναλλακτικά με τον τελεστή διαμέρισης: if string[pos:pos+len(substring)] == substring — ίδιο αποτέλεσμα, λιγότερος κώδικας. Σημείωση: η μέθοδος string.count(substring) της Python μετρά μη επικαλυπτόμενες εμφανίσεις ('banana'.count('ana') = 1), ενώ η δική μας και τις επικαλυπτόμενες.

Σύνοψη: isSubstring: return substring in string. Πλήθος: για κάθε θέση pos ελέγχουμε (χαρακτήρα-χαρακτήρα ή με string[pos:pos+len(sub)] == sub) αν το substring ξεκινά εκεί και μετράμε.

Κριτήρια αξιολόγησης:

in για το Α· σάρωση θέσεων με σύγκριση για το Β· δοκιμή με παράδειγμα.

Δραστηριότητα 5 — Στοίβα αριθμών: θετικοί ωθούνται, αρνητικοί απωθούν

Ερώτηση: Να γράψετε ένα πρόγραμμα το οποίο θα διαβάζει αριθμούς από το πληκτρολόγιο, μέχρι να δοθεί ο αριθμός 0. Κάθε φορά που θα διαβάζει έναν θετικό αριθμό, θα τον προσθέτει σε μια στοίβα. Όταν διαβάζει έναν αρνητικό αριθμό θα αφαιρεί τόσους αριθμούς από τη στοίβα, αν αυτό είναι δυνατόν και θα τους εμφανίζει στην οθόνη.

Απάντηση:

Σχέδιο: βρόχος while number != 0· αν ο αριθμός είναι θετικός → push· αν είναι αρνητικός → απωθούμε |number| στοιχεία (π.χ. −3 → τρεις απωθήσεις), αλλά μόνο όσο η στοίβα δεν είναι κενή («αν αυτό είναι δυνατόν» → έλεγχος isEmpty), και τυπώνουμε καθένα:

# Υλοποίηση στοίβας (σελ. 143) — χρησιμοποιείται και στις επόμενες δραστηριότητες
def push(stack, item):
    stack.append(item)
def pop(stack):
    return stack.pop()
def isEmpty(stack):
    return len(stack) == 0
def createStack():
    return []

stack = createStack()
number = input('Δώσε έναν αριθμό: ')
while number != 0:
    if number > 0:
        push(stack, number)
    else:
        i = 0
        while i < -number and not isEmpty(stack):   # -number = απόλυτη τιμή
            print pop(stack),
            i = i + 1
        print
    number = input('Δώσε έναν αριθμό: ')

Παράδειγμα εκτέλεσης: είσοδος 5, 8, 12, −2, 7, −5, 0 → στο −2 τυπώνει «12 8» (μένει [5])· στο −5 τυπώνει «7 5» και σταματά γιατί η στοίβα άδειασε (μόνο 2 στοιχεία ήταν διαθέσιμα). Οι απωθήσεις βγάζουν πάντα τον πιο πρόσφατο αριθμό πρώτα (LIFO).
Σημείωση: το επίσημο βιβλίο λύσεων γράφει while i <= number (με το number αρνητικό) — τυπογραφικό· η σωστή συνθήκη είναι i < -number (ή i < abs(number)).

Σύνοψη: Ανάγνωση μέχρι 0· θετικός → push· αρνητικός → έως |number| φορές: αν όχι κενή, print pop(stack)· LIFO.

Κριτήρια αξιολόγησης:

Χρήση της στοίβας με έλεγχο isEmpty + σωστό πλήθος απωθήσεων (απόλυτη τιμή).

Δραστηριότητα 6 — Συχνότητα κάθε γράμματος του αγγλικού αλφαβήτου με λεξικό

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

Απάντηση:

Λεξικό μετρητών: κλειδί = γράμμα, τιμή = πλήθος εμφανίσεων. Διασχίζουμε το κείμενο· για κάθε χαρακτήρα που είναι αγγλικό γράμμα (έλεγχος με in σε συμβολοσειρά αλφαβήτου, κεφαλαία και πεζά μαζί ή χωριστά): αν το κλειδί υπάρχει στο λεξικό αυξάνουμε την τιμή του, αλλιώς δημιουργούμε το ζεύγος με τιμή 1 (σελ. 147: ανάθεση σε νέο κλειδί = δημιουργία, σε υπάρχον = ενημέρωση):

# Συχνότητα γραμμάτων του αγγλικού αλφαβήτου σε ένα κείμενο (με λεξικό)
letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
text = raw_input('Δώσε ένα κείμενο: ')
frequency = dict()                     # κενό λεξικό
for letter in text:
    if letter in letters:              # μόνο αγγλικά γράμματα (όχι κενά, σημεία στίξης)
        if letter in frequency:        # το κλειδί υπάρχει -> ενημέρωση
            frequency[letter] += 1
        else:                          # νέο κλειδί -> δημιουργία με τιμή 1
            frequency[letter] = 1
print ' Letter  Frequency'
for letter in frequency:
    print '   ', letter, '     ', frequency[letter]

Παράδειγμα: 'banana' → a: 3, b: 1, n: 2 (σε τυχαία σειρά — τα λεξικά δεν είναι διατεταγμένα, σελ. 148). Αν θέλουμε να μετράμε τα Α και a μαζί, μετατρέπουμε πρώτα text = text.upper(). Το επίσημο βιβλίο λύσεων δίνει και έναν τρόπο χωρίς λεξικό, με λίστα 26 μετρητών και συνάρτηση που επιστρέφει τη θέση κάθε γράμματος στο αλφάβητο.

Σύνοψη: Λεξικό frequency· for letter in text: αν είναι αγγλικό γράμμα, frequency[letter] += 1 αν υπάρχει αλλιώς = 1· εμφάνιση ζευγών κλειδί-τιμή.

Κριτήρια αξιολόγησης:

Σωστή διάκριση «υπάρχει κλειδί / νέο κλειδί» + φιλτράρισμα μόνο γραμμάτων.

Δραστηριότητα 7 — Η λέξη με το μεγαλύτερο μήκος σε λίστα λέξεων

Ερώτηση: Να γράψετε μια συνάρτηση σε Python η οποία θα δέχεται μια λίστα από λέξεις και θα επιστρέφει τη λέξη με το μεγαλύτερο μήκος.

Απάντηση:

Κλασικός αλγόριθμος εύρεσης μεγίστου (σελ. 134, Παράδειγμα 3), με κριτήριο το μήκος len(word): κρατάμε το μέγιστο μήκος και τη λέξη που το έδωσε, διασχίζοντας τη λίστα:

def maxLength(wordList):
    maxLen = 0
    maxWord = ''
    for word in wordList:
        if len(word) > maxLen:
            maxLen = len(word)
            maxWord = word
    return maxWord

print maxLength(['Python', 'is', 'a', 'programming', 'language'])   # programming

Σε ισοπαλία επιστρέφεται η πρώτη λέξη με το μέγιστο μήκος (η σύγκριση είναι με αυστηρό >)· για κενή λίστα επιστρέφει ''. Εναλλακτικά με αρχικοποίηση maxWord = wordList[0] (απαιτεί μη κενή λίστα).

Σύνοψη: Διάσχιση της λίστας με μεταβλητές maxLen/maxWord· αν len(word) > maxLen ενημέρωση· return maxWord.

Κριτήρια αξιολόγησης:

Εύρεση μεγίστου με κριτήριο len.

Δραστηριότητα 8 — Πλήθος φωνηέντων λέξης και λέξη με τα περισσότερα φωνήεντα

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

Απάντηση:

Πρώτη συνάρτηση: όπως η count_vowels του βιβλίου (σελ. 129) — συμβολοσειρά με τα φωνήεντα (κεφαλαία και πεζά) και έλεγχος letter in vowels. Δεύτερη: εύρεση μεγίστου με κριτήριο την τιμή της πρώτης συνάρτησης (όπως στη δραστηριότητα 7):

def num_of_Vowels(word):
    vowels = 'AEIOUaeiou'
    count = 0
    for letter in word:
        if letter in vowels:
            count += 1
    return count

def maxVowels(wordList):
    maxV = -1
    maxWord = ''
    for word in wordList:
        v = num_of_Vowels(word)        # μία κλήση ανά λέξη
        if v > maxV:
            maxV = v
            maxWord = word
    return maxWord

print num_of_Vowels('education')                          # 5
print maxVowels(['sky', 'queue', 'python', 'education'])  # education

Σημείωση: το επίσημο βιβλίο λύσεων περιλαμβάνει και το y/Y στα φωνήεντα ('AEIOUYaeiouy')· το βιβλίο μαθητή (σελ. 129) χρησιμοποιεί 'AEIOUaeiou' — και οι δύο επιλογές γίνονται δεκτές αν δηλωθούν. Με maxV = -1 επιστρέφεται λέξη ακόμη κι αν καμία δεν έχει φωνήεντα (η πρώτη).

Σύνοψη: num_of_Vowels: μετρητής με letter in 'AEIOUaeiou'· maxVowels: εύρεση μεγίστου με κριτήριο num_of_Vowels(word).

Κριτήρια αξιολόγησης:

Δύο συναρτήσεις, η δεύτερη καλεί την πρώτη.

Ερώτηση 1 — Η δομή συμβολοσειρά (str) και οι τελεστές της

Ερώτηση: Να περιγράψετε τη δομή δεδομένων συμβολοσειρά (str) στην Python και να αναφέρετε τους τελεστές επεξεργασίας της.

Απάντηση:

Περιγραφή (σελ. 127): η συμβολοσειρά (αλφαριθμητικό, τύπος str) είναι ακολουθία χαρακτήρων με σταθερό μέγεθος και μη μεταβαλλόμενα περιεχόμενα — δεν μπορούμε να προσθέσουμε, να αφαιρέσουμε ή να τροποποιήσουμε χαρακτήρες (immutable). Η αρίθμηση των χαρακτήρων ξεκινά από το 0 (word = 'PYTHON': word[0] = 'P', word[3] = 'H'). Ορίζεται με μονά ή διπλά εισαγωγικά.
Τελεστές και συναρτήσεις επεξεργασίας: [i] προσπέλαση χαρακτήρα με δείκτη· len(word) μήκος (πλήθος χαρακτήρων)· + συνένωση (word[5]+word[0] → 'NP')· * επανάληψη (message*3, σελ. 37)· in / not in υπαρξιακός τελεστής για χαρακτήρα ή υποσυμβολοσειρά ('Py' in 'Python' → True)· συγκριτικοί <, <=, >, >=, ==, != με λεξικογραφική διάταξη ('antonis' > 'antonia', '1000' < '2')· τελεστής διαμέρισης : word[a:b] (τμήμα από a ως b−1, word[:7], word[8:])· μετατροπές str() (τιμή → συμβολοσειρά) και int() ('496' → 496)· διάσχιση με for char in word. Επίσης μέθοδοι όπως upper() (σελ. 109).

Σύνοψη: (ενδεικτική) Ακολουθία χαρακτήρων, σταθερού μεγέθους, immutable, δείκτες από 0, τύπος str· τελεστές: [i], len, +, *, in/not in, συγκριτικοί (λεξικογραφικά), διαμέριση a:b, str/int, for char in.

Κριτήρια αξιολόγησης:

Ορισμός με «immutable, από 0» + τουλάχιστον έξι τελεστές/συναρτήσεις.

Ερώτηση 2 — Η δομή Λίστα και οι τελεστές της

Ερώτηση: Να περιγράψετε τη δομή δεδομένων Λίστα στην Python και να αναφέρετε τους τελεστές επεξεργασίας της.

Απάντηση:

Περιγραφή (σελ. 130-131): η λίστα είναι διατεταγμένη ακολουθία αντικειμένων, όχι απαραίτητα του ίδιου τύπου, και η βασική δομή της Python. Είναι δυναμική και τροποποιήσιμη (mutable): προσθέτουμε, αφαιρούμε ή αλλάζουμε στοιχεία· δεν έχει σταθερό μέγεθος. Κάθε στοιχείο έχει μοναδικό αύξοντα αριθμό (θέση) από το 0, προσπέλαση L[i]. Ορίζεται με αγκύλες: L = [3, 5, 8, 13, 21, 34], mix = [6, 3.14159, True, 'Guido'].
Τελεστές (κοινοί με τις ακολουθιακές δομές): [i] προσπέλαση/ανάθεση (L[0] = ...)· + συνένωση λιστών (Λίστα + [στοιχείο] — δημιουργεί νέα λίστα) και += για προσθήκη στο τέλος· in / not in ύπαρξη στοιχείου· len(L) πλήθος· list(string) μετατροπή σε λίστα· τελεστής διαμέρισης : (L[a:b], L[:] = αντίγραφο)· range(A, M, B) παράγει λίστες αριθμών. Μέθοδοι: L.append(x) (στο τέλος), L.insert(i, x) (στη θέση i), L.pop([i]) (αφαίρεση και επιστροφή). Διάσχιση με for item in L (ή for index in range(len(L))).

Σύνοψη: (ενδεικτική) Διατεταγμένη, δυναμική, mutable ακολουθία αντικειμένων (και διαφορετικών τύπων), δείκτες από 0· τελεστές: [i], +, +=, in/not in, len, list(), διαμέριση, range· μέθοδοι append/insert/pop· for item in L.

Κριτήρια αξιολόγησης:

Ορισμός με «mutable, δυναμική» + τελεστές + τρεις μέθοδοι.

Ερώτηση 3 — Δομές που επιτρέπουν τροποποίηση (mutables)

Ερώτηση: Να αναφέρετε τις δομές δεδομένων οι οποίες επιτρέπουν τροποποίηση των δεδομένων τους (mutables).

Απάντηση:

Τροποποιήσιμες (mutable) δομές της Python είναι η λίστα και το λεξικό (σύνοψη, σελ. 152).
Λίστα: δυναμική δομή — προσθήκη (append, insert, +=), αφαίρεση (pop) και αλλαγή στοιχείων με ανάθεση L[i] = … (σελ. 130). Λεξικό: προσθήκη/ενημέρωση ζευγών με Λεξικό[κλειδί] = τιμή και διαγραφή με del (σελ. 147-148). Με βάση τις λίστες υλοποιούνται και η στοίβα και η ουρά, που είναι επίσης μεταβαλλόμενες δομές.
Σημείωση: το κείμενο της σύνοψης του βιβλίου (σελ. 152) γράφει κατά λάθος «immutables» για τις λίστες και τα λεξικά — από την ανάλυση των ενοτήτων 8.2 και 8.6 είναι σαφές ότι είναι οι mutable δομές.

Σύνοψη: Λίστα και λεξικό (και οι δομές που υλοποιούνται με λίστα: στοίβα, ουρά).

Κριτήρια αξιολόγησης:

Οι δύο δομές + ένα παράδειγμα τροποποίησης η καθεμία.

Ερώτηση 4 — Δομές που δεν επιτρέπουν τροποποίηση (immutables)

Ερώτηση: Να αναφέρετε τις δομές δεδομένων οι οποίες δεν επιτρέπουν τροποποίηση των δεδομένων τους (immutables).

Απάντηση:

Μη τροποποιήσιμες (immutable) δομές είναι οι συμβολοσειρές (str) και οι πλειάδες (tuples).
Συμβολοσειρές: σταθερό μέγεθος, δεν μπορούμε να προσθέσουμε, να αφαιρέσουμε ή να τροποποιήσουμε χαρακτήρες (σελ. 127) — κάθε «αλλαγή» (π.χ. συνένωση με +) δημιουργεί νέα συμβολοσειρά. Πλειάδες: ακολουθίες όπως οι λίστες, αλλά δεν μπορούν να τροποποιηθούν μετά τη δημιουργία τους (σελ. 146)· ορίζονται με παρενθέσεις, rec = ('Edsger', 'Dijkstra', 1940, 2006).

Σύνοψη: Συμβολοσειρές (str) και πλειάδες (tuples).

Κριτήρια αξιολόγησης:

Οι δύο δομές + τι σημαίνει immutable.

Ερώτηση 5 — Πότε χρησιμοποιούμε το Λεξικό

Ερώτηση: Πότε χρησιμοποιούμε τη δομή δεδομένων του Λεξικού;

Απάντηση:

Χρησιμοποιούμε λεξικό όταν θέλουμε να αποθηκεύουμε ζεύγη κλειδιού–τιμής και να βρίσκουμε πολύ γρήγορα την τιμή από το κλειδί — όπως σε έναν τηλεφωνικό κατάλογο, όπου βρίσκουμε τα στοιχεία κάποιου μόνο από το όνομά του (σελ. 147): version['python'] = 3.4, dictionary['Giga'] → 9.
Κάθε κλειδί είναι μοναδικό (εμφανίζεται το πολύ μία φορά) — επομένως το λεξικό ταιριάζει όταν τα δεδομένα ταυτοποιούνται από ένα κλειδί (όνομα, κωδικός, λέξη) αντί από αύξοντα αριθμό θέσης όπως στη λίστα, και όταν το σύνολο των κλειδιών αλλάζει δυναμικά (νέα κλειδιά δημιουργούνται με απλή ανάθεση, διαγράφονται με del, ελέγχονται με in). Χαρακτηριστική εφαρμογή: μετρητές συχνότητας (πόσες φορές εμφανίζεται κάθε γράμμα — δραστηριότητα 6), αντιστοιχίσεις μονάδων ('Kilo': 3, 'Mega': 6), κατάλογοι.

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

Κριτήρια αξιολόγησης:

Κλειδί-τιμή + μοναδικότητα + παράδειγμα χρήσης.

Ερώτηση 6 — Μια εφαρμογή των Πλειάδων

Ερώτηση: Να αναφέρετε μια εφαρμογή των Πλειάδων.

Απάντηση:

Μια γνωστή εφαρμογή των πλειάδων είναι η αμοιβαία αλλαγή των τιμών δύο μεταβλητών χωρίς βοηθητική μεταβλητή — η αντιμετάθεση (swap) (σελ. 146): a, b = b, a (a = 496, b = 28 → a = 28, b = 496). Στο δεξί μέλος σχηματίζεται η πλειάδα (b, a) και οι τιμές της εκχωρούνται στα a, b. Η ίδια εντολή χρησιμοποιείται στους αλγορίθμους ταξινόμησης (κεφ. 5).
Άλλη εφαρμογή: η αναπαράσταση οντοτήτων του πραγματικού κόσμου με τις ιδιότητές τους (όνομα, επώνυμο, έτη) ως εγγραφές σταθερής δομής — rec = ('Edsger', 'Dijkstra', 1940, 2006)· επίσης η divmod(10, 3) επιστρέφει πλειάδα (3, 1) (σελ. 39).

Σύνοψη: (ενδεικτική) Η αντιμετάθεση τιμών δύο μεταβλητών χωρίς βοηθητική μεταβλητή: a, b = b, a· επίσης η αναπαράσταση οντοτήτων/εγγραφών με σταθερές ιδιότητες.

Κριτήρια αξιολόγησης:

Τουλάχιστον μία εφαρμογή με παράδειγμα κώδικα.

Ερώτηση 7 — Βασικές λειτουργίες Στοίβας και Ουράς

Ερώτηση: Ποιες είναι οι βασικές λειτουργίες σε μια Στοίβα και ποιες σε μια Ουρά;

Απάντηση:

Στοίβα (σελ. 142-143): ① δημιουργία κενής στοίβας (createStack), ② έλεγχος αν είναι κενή (isEmpty — απαραίτητος πριν από απώθηση), ③ ώθηση (push) στοιχείου στην κορυφή, ④ απώθηση (pop) στοιχείου από την κορυφή. Λειτουργία LIFO — εισαγωγές και εξαγωγές από το ίδιο άκρο.
Ουρά (σελ. 145): ① εισαγωγή (enqueue) στοιχείου στο πίσω μέρος, ② εξαγωγή (dequeue) στοιχείου από το εμπρός μέρος — οι δύο βασικές· επίσης δημιουργία κενής ουράς (createQueue) και έλεγχος κενής (isEmpty). Λειτουργία FIFO — εξυπηρέτηση με τη σειρά άφιξης.
Υλοποίηση με λίστα: push → append, pop → pop() · enqueue → append, dequeue → pop(0).

Σύνοψη: (ενδεικτική) Στοίβα: δημιουργία, έλεγχος κενής, ώθηση (push), απώθηση (pop) — LIFO από το ίδιο άκρο. Ουρά: εισαγωγή (enqueue) πίσω, εξαγωγή (dequeue) εμπρός (+ δημιουργία, έλεγχος κενής) — FIFO.

Κριτήρια αξιολόγησης:

Οι λειτουργίες κάθε δομής + LIFO/FIFO + άκρα.

Ερώτηση 8 — Εφαρμογές της Στοίβας

Ερώτηση: Να αναφέρετε εφαρμογές της Στοίβας.

Απάντηση:

Από το βιβλίο (σελ. 140-143): ① το ιστορικό ιστοσελίδων του φυλλομετρητή — η λειτουργία Πίσω (Back) ανακτά τις σελίδες με αντίστροφη σειρά επίσκεψης· ② ο σωρός με τα πιάτα που περιμένουν πλύσιμο (το τελευταίο πλένεται πρώτο)· ③ η αντιστροφή μιας ακολουθίας — αριθμών (εφαρμογή σελ. 143) ή λέξης (δραστηριότητα 3)· ④ γενικότερα, χρησιμοποιείται σε πολλά πεδία της Πληροφορικής: θεωρία αλγορίθμων, ανάπτυξη μεταγλωττιστών, τεχνητή νοημοσύνη.
Άλλες γνωστές εφαρμογές: η αναίρεση (Undo) στους επεξεργαστές κειμένου, ο έλεγχος ισορροπίας παρενθέσεων, η διαχείριση των κλήσεων συναρτήσεων (η επιστροφή στο σημείο κλήσης — κεφ. 7).

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

Κριτήρια αξιολόγησης:

Τουλάχιστον τρεις εφαρμογές από το βιβλίο.

Ερώτηση 9 — Εφαρμογές της Ουράς

Ερώτηση: Να αναφέρετε εφαρμογές της Ουράς.

Απάντηση:

Η ουρά χρησιμοποιείται για τη μοντελοποίηση και προσομοίωση πραγματικών φαινομένων εξυπηρέτησης ανθρώπων, αντικειμένων ή προγραμμάτων (σελ. 144): ① οι ουρές στις τράπεζες και τα σούπερ-μάρκετ· ② η ουρά των προγραμμάτων που περιμένουν να εξυπηρετηθούν από τον επεξεργαστή του υπολογιστή· ③ η ουρά των αιτήσεων προς τον διακομιστή ιστού (web server) ενός δικτυακού τόπου.
Τα φαινόμενα αυτά μελετώνται από τη Θεωρία Ουρών και την Επιχειρησιακή Έρευνα. Άλλα παραδείγματα: ουρά εκτύπωσης (print spooler), αναμονή σε τηλεφωνικό κέντρο, buffer πληκτρολογίου — παντού όπου ισχύει «πρώτος ήρθε, πρώτος εξυπηρετείται» (FIFO).

Σύνοψη: (ενδεικτική) Ουρές τραπεζών/σούπερ-μάρκετ, προγράμματα προς τον επεξεργαστή, αιτήσεις σε web server (προσομοίωση εξυπηρέτησης, Θεωρία Ουρών)· επίσης ουρά εκτύπωσης κ.ά.

Κριτήρια αξιολόγησης:

Οι τρεις εφαρμογές του βιβλίου + FIFO.

Ερώτηση 10 — Διαφορά Δέντρου από Γράφο

Ερώτηση: Σε τι διαφέρει ένα Δέντρο από ένα Γράφο;

Απάντηση:

Γράφος = δομή από κορυφές (κόμβους) και ακμές μεταξύ τους (σελ. 148)· μπορεί να είναι κατευθυνόμενος ή μη, να έχει κύκλους (κυκλικά μονοπάτια, π.χ. B→D→C→D→B) και κορυφές χωρίς μονοπάτι προς άλλες (π.χ. καμία ακμή δεν καταλήγει στην Α).
Δέντρο = ειδική περίπτωση γράφου στον οποίο υπάρχει μονοπάτι μεταξύ δύο οποιωνδήποτε κορυφών και δεν περιέχει κυκλικές διαδρομές (σελ. 149). Έχει ιεραρχική δομή: μία ρίζα (επίπεδο 0, χωρίς πρόγονο), κάθε κόμβος έχει ακριβώς έναν πρόγονο και έναν ή περισσότερους απογόνους (παιδιά), οι κόμβοι χωρίς παιδιά είναι φύλλα· ορίζονται βαθμός (πλήθος παιδιών / μέγιστος), επίπεδο (απόσταση από τη ρίζα) και ύψος (μέγιστη απόσταση).
Άρα η διαφορά: κάθε δέντρο είναι γράφος, αλλά ο γράφος είναι γενικότερη δομή — μπορεί να έχει κύκλους και μη συνδεδεμένες κορυφές, δεν έχει ρίζα ούτε ιεραρχία επιπέδων. Παραδείγματα: γράφος → παγκόσμιος ιστός, δίκτυο πόλεων· δέντρο → γενεαλογικό δέντρο, οργανόγραμμα επιχείρησης.

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

Κριτήρια αξιολόγησης:

Ορισμός δέντρου ως ειδικού γράφου (συνδεδεμένος, ακυκλικός) + ιεραρχικά στοιχεία.

Προηγούμενο Στοιχείο

Επιστροφή στην Ενότητα

Επόμενο Στοιχείο