B.4 · סוגי נתונים מופשטים (רק HL)

מיקוד HL נתמך. מטרה הראשונה 2027; החזרות PDF רשמיות 403; בקשה שנרכשה ישנה היא ההערכה הסופית 2026. הדגם, ההערכה והדרישות המעשיות הנותרות שומרות על החזקות המוקלטות שלהן.

תנאי הכנה: קרא את הכמויות והיחידות הנ stated, השתמש באריתמטיקה ובתנאי המודל למטה. כל שיעור מפתח את השיטה שלו לפני העברה עצמאית.

אלו הם דוגמאות הוראה מקוריות או בדיוניות במפורש, לא מדידות אמיתיות או בדיקות למידה שנבדקו והושלמו.

מה would explain this observation?

• סימולציית תור דורשת את הפריט המתמתיך הישן ביותר ראשונה. ערמה נותנת את הפריט האחרון ראשונה, ולכן קריאת הפעולה חשובה.
• התחל בחזית. ציין את הכמותות או התכונות שת срав, ואז החלט איזה עדות יכולה להבדיל בין שתי הסברות.

בנה את המודל

• סוג נתונים מופשט (ADT) מגדיר ערכים ותפעולות ללא תלות ביישום ספציפי. אגרת (stack) היא "אחרון נכנס, ראשון יוצא"; תור (queue) הוא "ראשון נכנס, ראשון יוצא". ממשק קבוצה דורש התנהגות מוגדרת לתפעולים על מבנה ריק או לא חוקי.
• שורה (Stack): סוג נתונים مجردי של אחרון-נכנס-ראשון-יוצא; תור (Queue): סוג נתונים مجردי של ראשון-נכנס-ראשון-יוצא.

בחר עדויות שיכולות לבחון אותו

• בחר את המבנה המתאים לדפוס הגישה הנדרש. המורכבות תלויה ביישום ובנחות: הסרת הפריט הראשון מארגון זז שונה מהזזת מצביע ראש בתור.
• מעקב ידני אחר רצף תפעוליות, ולאחר מכן השוואה של התוכנה למצבים צפויים. בדיקת מצבי ריק, יחיד-פריטי ופעולות חוזרות. ציון התנהגות גלישה (overflow) כאשר הקיבולת קבועה.

עבוד מכמויות ידועות

• ציין את הערכים הידועים ואת יחידות המידה שלהם. בחר בקשר מכיוון שההנחות שלו מתאימות למקרה זה, ולאחר מכן סדר מחדש לפני ההצבה.
• ידוע: הוספת A, B ו-C לתור, ולאחר מכן ביצוע פעולת הסרה פעמיים. A ו-B יוצאים; C נותר. לאחר הוספת D ישנם שני פריטים בממתנה, C ולאחריו D. באגרה, אותה סדרת הכנסות הייתה מוצאת C ולאחריו B.

דוגמה:

תור מתחיל ריק, מקבל 7 פריטים ומסיר 4. מצא את המספר שנותר. השתמש באותה רצף: כמות ידועה → מודל → קשר → הצבה → יחידה ופרשנות.

בדוק את המסקנה ואת הגבולות שלה

• ADT אינו מייצוג זיכרון ספציפי. תור אינו מסדר לפי עדיפות אלא אם כן החוזה שלו מגדיר תור עדיפות.
• חזור לתצפית המקורית. הסבר מה התוצאה תומכת, אילו תנאים היא מניחה, ודרך אחת לבדוק הסבר מתחרה.

אזהרה:

כל תור מסדר אוטומטית פריטים לפי עדיפות. טענה זו שגויה: ADT אינו מייצוג זיכרון ספציפי. תור אינו מסדר לפי עדיפות אלא אם כן החוזה שלו מגדיר תור עדיפות.

מפת מושגים:

סוגי נתונים מופשטים: חוזה תפעול: בחר את המבנה המתאים לדפוס הגישה הנדרש. המורכבות תלויה ביישום ובנחות: הסרת הפריט הראשון מארגון זז שונה מהזזת מצביע ראש בתור.

מעקב וגבול ניתנים לביצוע

from collections import deque
queue = deque()
queue.extend(["A", "B"])
print(queue.popleft())
queue.append("C")
print(queue.popleft())
print(list(queue))
queue.clear()
print(queue.popleft() if queue else "EMPTY")

תוצאה צפויה:

A
B
['C']
EMPTY

הסרה משמאל ממיישמת FIFO. הגנת ריקות מפורשת מגדירה את תוצאת הגבול; deque.popleft ללא זאת תגרום IndexError. סטאק במקום זאת מסיר מימין.