בגרות במדעי המחשב מבני נתונים ומסלול 899271 - קיץ 2026
4–5 יח"ל · שאלון 899271 · 12 שאלות · 3 שעות · פתרון מלא לכל סעיף
בחינת הבגרות במדעי המחשב, מבני נתונים ומסלול, קיץ 2026, כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה ופתרון מלא: הרעיון, הקוד או המעקב, ובדיקה קצרה. כל קוד מופיע ב-Java וב-C#. נסו לפתור לבד, ואז פתחו את הפתרון.
הוראות הבחינה (כמו בשאלון)
א. משך הבחינה: שלוש שעות.
ב. מבנה השאלון ומפתח ההערכה: בשאלון זה שני פרקים.
פרק ראשון – 25×2 – 50 נקודות
פרק שני – 25×2 – 50 נקודות
סך הכול – 100 נקודות
ג. חומר עזר מותר בשימוש: כל חומר עזר, חוץ ממחשבון שיש בו אפשרות תכנוּת.
ד. הוראות מיוחדות:
(1) רשמו על הכריכה החיצונית של המחברת את שם המסלול שלמדתם.
המסלול הוא אחד משלושת המסלולים האלה: אלגוריתמים, מודלים חישוביים, תכנוּת מונחה עצמים.
(2) את כל התוכניות שיש לכתוב בשפת מחשב בפרקים הראשון והשני כתבו בשפה אחת בלבד – Java או C# .
הערה: לא יוּרדוּ נקודות אם תכתבו בתוכניות אות גדולה במקום אות קטנה או להפך.
יש לכתוב במחברת הבחינה בלבד. יש לרשום "טיוטה" בראש כל עמוד המשמש טיוטה.
כתיבת טיוטה בדפים שאינם במחברת הבחינה עלולה לגרום לפסילת הבחינה.
השאלות בשאלון זה מנוסחות בלשון רבים, אף על פי כן על כל תלמידה וכל תלמיד להשיב עליהן באופן אישי.
בהצלחה!
השאלות
בשאלון זה שני פרקים. יש לענות על שאלות משני הפרקים, לפי ההוראות בכל פרק.
הערה: בכל שאלה שנדרשת בה קליטה, אין צורך לבדוק את תקינות הקלט.
לפותרים בשפת Java: בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner input = new Scanner (System.in);
שימו לב: בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
הערה: חוקי המענה בקיץ תשפ"ו (2026) שונו לפי הודעת משרד החינוך על ההנחיות החדשות למענה על שאלות הבחינה (ההנחיה אינה מודפסת בשאלון): יש לענות על 4 שאלות מתוך 6 השאלות במבחן (בפרק שני מענה ממסלול אחד בלבד). לכל שאלה – 27 נקודות (ניתן לצבור עד 100 נקודות. תלמיד שצבר מעל 100 נקודות יקבל 100). סך הכול: 100 נקודות. בפרק א יש שאלה אחת בלבד בכל נושא: תור, רשימה ועץ בינרי.
פרק ראשון
ענו על שתיים מן השאלות 1–3 (לכל שאלה – 25 נקודות).
שאלה 1 · איחוד הזמנות בתור (25 נקודות)
נתונה המחלקה Order – הזמנה של לקוח, ולה שתי תכונות:
הניחו שיש פעולות get/Get ו־ set/Set לתכונות המחלקה, ופעולה בונה המקבלת ערכים בעבור תכונות המחלקה.
בחברת המשלוחים "ברק" נבנה תור – qOrder מטיפוס Order , השומר את ההזמנות השונות של הלקוחות ביום מסוים, שחברת המשלוחים צריכה לספק.
הערות:
בסוף היום, כדי לייעל את המשלוחים, מבצעים בתור חדש איחוד הזמנות לפי מזהה לקוח (id), כך שלכל לקוח נשמרת בתור הזמנה אחת בלבד, עם סך כל המוצרים שהוא הזמין בכל ההזמנות (count). כך למשל, אם יש בתור qOrder 3 הזמנות של אותו הלקוח: הזמנה של 20 מוצרים, הזמנה של 15 מוצרים והזמנה של 30 מוצרים, לאחר האיחוד יופיע הלקוח רק פעם אחת בתור החדש – עם הזמנה של 65 מוצרים.
ממשו את הפעולה שלפניכם:
Java – public static Queue<Order> uniteOrders (Queue<Order> qOrder)
C# – public static Queue<Order> UniteOrders (Queue<Order> qOrder)
הפעולה מקבלת תור שיש בו הזמנות – qOrder ובו אותו לקוח יכול להופיע יותר מפעם אחת, ומחזירה תור חדש ובו יש איחוד הזמנות כפי שהוסבר לעיל.
הערות:
מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם.
"לקוח רגיל" הוא לקוח שהזמין פחות מ־ 10 מוצרים סך הכול ביום מסוים, ו"לקוח מועדף" הוא לקוח שהזמין 10 מוצרים ומעלה סך הכול ביום מסוים.
ממשו את הפעולה שלפניכם:
Java – public static Queue<Integer> preferredClients (Queue<Order> qOrder)
C# – public static Queue<int> PreferredClients (Queue<Order> qOrder)
הפעולה מקבלת תור הזמנות של יום מסוים – qOrder מטיפוס Order (תור "לא מאוחד", שבו אותו לקוח יכול להופיע כמה פעמים), ומחזירה תור מטיפוס שלם. בתחילת התור המוחזר יופיעו מספרי הזהות (id) של כל מי שהוא "לקוח מועדף", ואחריהם יופיעו מספרי הזהות (id) של כל מי שהוא "לקוח רגיל" (ללא חשיבות לסדר הלקוחות בכל קבוצה).
אפשר להשתמש בפעולה שכתבתם בסעיף א.
הערות:
מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א(1)
בכל סבב מוציאים הזמנה ראשונה, סוכמים את כל ההזמנות של אותו id ומעבירים את השאר לתור עזר שמחליף את qOrder; מכניסים לתוצאה new Order(id, total).
מה נדרש: לבנות תור חדש שבו כל לקוח (id) מופיע פעם אחת בלבד, עם סכום הכמויות (count) של כל ההזמנות שלו – בעזרת תורים בלבד.
רעיון: כל עוד qOrder אינו ריק:
first – זה לקוח שעוד לא טופל. מתחילים סכום total בכמות שלה.temp.qOrder = temp.מותר לשנות את התור שהתקבל (בסוף הוא מתרוקן), ומשתמשים רק בתורים ובפעולות insert/remove/isEmpty – בלי מערך ובלי רשימה.
פתרון: הקוד המלא – בלשונית Java / C#.
בדיקה: על התור (id,count): (7,20), (4,3), (7,15), (9,8), (7,30), (4,6) (משמאל – ראש התור).
| סבב | ההזמנה שהוצאה | total | temp בסוף הסבב | נוסף לתוצאה |
|---|---|---|---|---|
| 1 | (7,20) | 20+15+30 = 65 | (4,3), (9,8), (4,6) | (7,65) |
| 2 | (4,3) | 3+6 = 9 | (9,8) | (4,9) |
| 3 | (9,8) | 8 | ריק | (9,8) |
הפלט בפועל: [(7,65), (4,9), (9,8)] – לקוח 7 מופיע פעם אחת עם 65 מוצרים, כמו בדוגמה בשאלה. נבדקו גם תור ריק, הזמנה אחת, כל ההזמנות של אותו לקוח וכל הלקוחות שונים.
טעות נפוצה: ליצור את temp פעם אחת מחוץ ללולאה ולא להחליף איתו את qOrder – אז אחרי הסבב הראשון qOrder ריק וכל שאר הלקוחות "נעלמים". טעות נוספת: להשוות בין עצמי Order (o == first) במקום בין מספרי הזהות.
public static Queue<Order> uniteOrders(Queue<Order> qOrder) {
Queue<Order> result = new Queue<Order>();
while (!qOrder.isEmpty()) {
Order first = qOrder.remove(); // הזמנה של לקוח חדש
int total = first.getCount();
Queue<Order> temp = new Queue<Order>();
while (!qOrder.isEmpty()) { // מעבר על שאר ההזמנות
Order o = qOrder.remove();
if (o.getId() == first.getId())
total += o.getCount(); // אותו לקוח – מצרפים
else
temp.insert(o); // לקוח אחר – שומרים לסבב הבא
}
qOrder = temp;
result.insert(new Order(first.getId(), total));
}
return result;
}סעיף א(2)
O(n²) – לכל לקוח מעבר על כל ההזמנות שנותרו: (n−1)+(n−2)+…+1 במקרה הגרוע.
מה נדרש: סיבוכיות זמן הריצה של uniteOrders, כתלות ב־n – מספר ההזמנות בתור.
רעיון: כל פעולה על תור (insert, remove, isEmpty) היא O(1). נספור כמה פעמים מתבצעת הלולאה הפנימית.
פתרון:
(באופן כללי, אם יש k לקוחות שונים, יש k סבבים וכל סבב עובר על לכל היותר n הזמנות – O(k·n), ובמקרה הגרוע k = n.)
בדיקה: בדוגמה מסעיף א(1) (n = 6, שלושה לקוחות) היו 3 סבבים: הלולאה הפנימית עברה על 5, 2 ו־0 הזמנות.
סעיף ב(1)
מאחדים עם uniteOrders, מועדפים (count ≥ 10) נכנסים מיד לתוצאה, רגילים לתור עזר שמועבר לסוף התוצאה.
מה נדרש: תור של מספרי זהות: קודם כל הלקוחות המועדפים (סך הכול ≥ 10), אחריהם כל הרגילים (סך הכול < 10), וכל לקוח פעם אחת.
רעיון: הסיווג תלוי בסך ההזמנות של הלקוח, ולכן קודם מאחדים את התור בעזרת uniteOrders מסעיף א – עכשיו כל לקוח מופיע פעם אחת עם הסכום שלו. עוברים פעם אחת על התור המאוחד: מועדף – נכנס מיד לתור התוצאה; רגיל – נכנס לתור עזר regular. בסוף מעבירים את כל regular לסוף תור התוצאה, וכך הרגילים באים אחרי המועדפים.
פתרון: הקוד המלא – בלשונית Java / C#. (הקוד משתמש בפעולה uniteOrders / UniteOrders מסעיף א.)
בדיקה: על התור: (7,20), (4,3), (7,15), (9,8), (7,30), (4,6), (5,4), (5,6), (8,9).
אחרי האיחוד: (7,65), (4,9), (9,8), (5,10), (8,9).
| הזמנה מאוחדת | סך הכול | סוג | לאן נכנסה |
|---|---|---|---|
| (7,65) | 65 | מועדף | result |
| (4,9) | 9 | רגיל | regular |
| (9,8) | 8 | רגיל | regular |
| (5,10) | 10 | מועדף | result |
| (8,9) | 9 | רגיל | regular |
הפלט בפועל: [7, 5, 4, 9, 8] – קודם המועדפים 7 ו־5, אחריהם הרגילים 4, 9, 8.
טעות נפוצה: לסווג לפי כל הזמנה בנפרד ולא לפי הסכום. לקוח 5 הזמין 4 ו־6 מוצרים – כל הזמנה לבדה קטנה מ־10, אבל סך הכול 10, ולכן הוא "לקוח מועדף". טעות נוספת: לכתוב > 10 במקום >= 10 ("10 מוצרים ומעלה").
public static Queue<Integer> preferredClients(Queue<Order> qOrder) {
Queue<Order> united = uniteOrders(qOrder); // כל לקוח מופיע פעם אחת עם סך הכול
Queue<Integer> result = new Queue<Integer>();
Queue<Integer> regular = new Queue<Integer>();
while (!united.isEmpty()) {
Order o = united.remove();
if (o.getCount() >= 10)
result.insert(o.getId()); // לקוח מועדף
else
regular.insert(o.getId()); // לקוח רגיל
}
while (!regular.isEmpty()) // הלקוחות הרגילים – אחרי המועדפים
result.insert(regular.remove());
return result;
}סעיף ב(2)
O(n²) – בגלל הקריאה ל־uniteOrders; שאר המעברים O(n).
מה נדרש: סיבוכיות זמן הריצה של preferredClients, כתלות ב־n – מספר ההזמנות בתור.
פתרון:
סך הכול O(n²) + O(n) + O(n) = O(n²) – החלק היקר הוא איחוד ההזמנות.
בדיקה: במקרה הגרוע (כל הלקוחות שונים) uniteOrders לבדה מבצעת n(n−1)/2 מעברים בלולאה הפנימית, ושני המעברים הנוספים מוסיפים רק כ־2n פעולות.
שאלה 2 · חישוב ביטוי משתי שרשרות חוליות (25 נקודות)
נתונות שתי הפניות לשרשרות של חוליות:
numHead – הפניה לשרשרת חוליות של מספרים מטיפוס שלם.
charHead – הפניה לשרשרת חוליות מטיפוס תו (char), שבה מיוצגות פעולות החשבון חיבור וחיסור ('+', '−').
הערה: כמות החוליות בשרשרת המספרים גדולה ב־ 1 מכמות החוליות בשרשרת התווים.
שילוב בין שתי השרשרות מייצג סדרת פעולות חשבון, כמפורט לפניכם:
התו במיקום 1 בשרשרת התווים מתאר את הפעולה שבאה לפני המספר שבמיקום 2 בשרשרת המספרים, התו במיקום 2 מתאר את הפעולה שבאה לפני המספר שבמיקום 3, התו במיקום 3 מתאר את הפעולה שבאה לפני המספר שבמיקום 4, וכן הלאה עד סוף שתי השרשרות.
שימו לב: אין פעולת חשבון לפני המספר הראשון בשרשרת המספרים.
דוגמה: שתי השרשרות שלפניכם מייצגות את סדרת פעולות החשבון: 3 + 5 − 2 − 3 + 7 .
ממשו את הפעולה שלפניכם:
Java – public static int eval (Node<Integer> numHead, Node<Character> charHead, int len)
C# – public static int Eval (Node<int> numHead, Node<char> charHead, int len)
len הוא כמות המספרים שנרצה לחשב מתוך שרשרת המספרים (אין פעולת חשבון לפני המספר הראשון ולכן כמות התווים היא len–1 בהתאם).
הפעולה תחזיר את תוצאת החישוב של len מספרים ברצף, החל מתחילת שרשרת המספרים ותחילת שרשרת התווים.
הניחו ש־ len גדול מ־ 0 . אין לשנות את השרשרות שהתקבלו.
הערה: אם len גדול מכמות החוליות בשרשרת המספרים, הפעולה תחזיר את תוצאת החישוב של כל המספרים בשרשרת.
דוגמה: בעבור שתי השרשרות בדוגמה שלעיל ו־ len = 1 , הפעולה תחזיר 3 , כיוון שהוא המספר הראשון בשרשרת המספרים (היות שהוא המספר הראשון והיחיד, אין שום פעולת חשבון שצריך לבצע).
דוגמה נוספת: בעבור אותן שתי שרשרות ו־ len = 3 , הפעולה תחזיר 6 (3 + 5 − 2 = 6).
דוגמה נוספת: בעבור אותן שתי שרשרות ו־ len = 8 , הפעולה תחזיר 10 (3 + 5 − 2 − 3 + 7 = 10).
הסבר: מספר החוליות בשרשרת המספרים קטן מ־ 8 , ולכן הפעולה מחזירה את תוצאת החישוב של כל המספרים בשרשרת.
ממשו את הפעולה שלפניכם:
Java – public static boolean match (Node<Integer> numHead, Node<Character> charHead, int len, int val)
C# – public static bool Match (Node<int> numHead, Node<char> charHead, int len, int val)
הפעולה תחזיר true אם קיימת חוליה במיקום כלשהו בשרשרת המספרים וחוליה במיקום זהה בשרשרת התווים, שמהם והלאה יש len מספרים ברצף שתוצאת החישוב שלהם היא val (כלומר אם מתחילים את החישוב מן החוליה השנייה בשרשרת המספרים, גם פעולת החשבון הראשונה תהיה החוליה השנייה בשרשרת התווים). אחרת הפעולה תחזיר false .
אפשר להשתמש בפעולה שכתבתם בסעיף א. הניחו ש־ len גדול מ־ 0 . אין לשנות את השרשרות שהתקבלו.
שימו לב: אין פעולת חשבון לפני המספר הראשון בחישוב (מספר התווים הנדרש הוא len–1).
הערה: אם מחוליה כלשהי יש פחות מ־ len מספרים עד סוף השרשרת – החישוב מתבצע עד סוף השרשרת.
דוגמה: בעבור שתי השרשרות המוצגות בדוגמה שלעיל, len = 3 ו־ val = 0 , הפעולה תחזיר true , כי החל מן החוליה השנייה בשרשרת המספרים ומן החוליה השנייה בשרשרת התווים יש 3 מספרים ברצף שתוצאת החישוב שלהם היא 0 (5 − 2 − 3 = 0).
דוגמה נוספת: בעבור שתי השרשרות המוצגות בדוגמה שלעיל, len = 3 ו־ val = 10 , הפעולה תחזיר true , כי החל מן החוליה הרביעית בשרשרת המספרים ומן החוליה הרביעית בשרשרת התווים ועד סוף שרשרת המספרים תוצאת החישוב היא 10 (3 + 7 = 10).
◂ פתרון מלא לשאלה 2
סעיף א
result = הערך הראשון; כל עוד count < len וגם pNum != null: לפי התו מוסיפים/מחסרים את pNum ומקדמים את שני המצביעים.
מה נדרש: לחשב את הביטוי שמתקבל מ־len המספרים הראשונים ומ־len−1 התווים הראשונים (או עד סוף שרשרת המספרים, אם היא קצרה יותר).
רעיון: מתחילים את התוצאה בערך של החוליה הראשונה (לפניה אין פעולה). אחר כך מקדמים שני מצביעים במקביל: pNum על המספר הבא ו־pChar על התו שלפניו. בכל צעד: אם התו '+' – מוסיפים את המספר, אחרת מחסרים. ממשיכים כל עוד חושבו פחות מ־len מספרים וגם יש עוד מספר בשרשרת (pNum != null). מכיוון שמספר התווים קטן ב־1 ממספר המספרים, כשיש עוד מספר תמיד יש גם תו מתאים. הפעולה רק קוראת מהשרשרות ולא משנה אותן.
פתרון: הקוד המלא – בלשונית Java / C#.
בדיקה: על השרשרות מהדוגמה (3, 5, 2, 3, 7 ו־ +, −, −, +), עם len = 8:
| count | התו (pChar) | המספר (pNum) | result |
|---|---|---|---|
| 1 | – | 3 (ראשון) | 3 |
| 2 | + | 5 | 8 |
| 3 | − | 2 | 6 |
| 4 | − | 3 | 3 |
| 5 | + | 7 | 10 |
| – | – | null – עצירה | 10 |
התוצאות: len = 1 ← 3, len = 3 ← 6, len = 8 ← 10 – בדיוק כמו בדוגמאות שבשאלה (וגם len = 4 ← 3, len = 5 ← 10).
טעות נפוצה: להתחיל את הלולאה מהחוליה הראשונה עם התו הראשון – אז הפעולה הראשונה "נדבקת" למספר הראשון והחישוב זז בחוליה אחת. טעות נוספת: לשכוח את התנאי pNum != null ולקבל חריגה כאשר len גדול מאורך השרשרת.
public static int eval(Node<Integer> numHead, Node<Character> charHead, int len) {
int result = numHead.getValue(); // המספר הראשון – בלי פעולה לפניו
Node<Integer> pNum = numHead.getNext();
Node<Character> pChar = charHead;
int count = 1; // כמה מספרים כבר חושבו
while (count < len && pNum != null) {
if (pChar.getValue() == '+')
result = result + pNum.getValue();
else
result = result - pNum.getValue();
pNum = pNum.getNext();
pChar = pChar.getNext();
count++;
}
return result;
}סעיף ב
לכל מיקום k: אם eval(המספר ה־k, התו ה־k, len) == val מחזירים true; pChar מתקדם רק אם אינו null; בסוף false.
מה נדרש: לבדוק אם יש מיקום התחלה k כך שהחישוב של len מספרים החל מהמספר ה־k, עם התווים החל מהתו ה־k, נותן val.
רעיון: הפעולה eval מסעיף א מחשבת ביטוי החל מ"ראש" כלשהו – ואפשר להעביר לה חוליה מאמצע השרשרת. לכן עוברים עם שני מצביעים במקביל: pNum על המספר ה־k ו־pChar על התו ה־k, ולכל k קוראים ל־eval(pNum, pChar, len). אם התוצאה שווה ל־val – מחזירים true מיד. בסוף – false.
פרט חשוב: לחוליה האחרונה בשרשרת המספרים אין תו באותו מיקום (יש תו אחד פחות), ולכן מקדמים את pChar רק אם הוא לא null. כשמתחילים מהמספר האחרון, eval מחזירה את המספר עצמו ולא ניגשת לתו כלל. כך מטופל גם המקרה שבהערה (פחות מ־len מספרים עד הסוף) – eval כבר עוצרת בסוף השרשרת.
פתרון: הקוד המלא – בלשונית Java / C#. (הקוד משתמש בפעולה eval / Eval מסעיף א.)
בדיקה: על השרשרות מהדוגמה עם len = 3, ערכי eval לכל מיקום התחלה:
| k | החישוב | תוצאה |
|---|---|---|
| 1 | 3 + 5 − 2 | 6 |
| 2 | 5 − 2 − 3 | 0 |
| 3 | 2 − 3 + 7 | 6 |
| 4 | 3 + 7 | 10 |
| 5 | 7 | 7 |
לכן val = 0 ← true (k = 2) ו־val = 10 ← true (k = 4), כמו בדוגמאות; val = 100 ← false. נבדקו גם len = 2, val = −1 ← true (2 − 3) ו־len = 2, val = 4 ← false, וגם שרשרת של מספר אחד בלי תווים.
טעות נפוצה: לקדם את pChar בלי לבדוק null – כשעוברים מהמספר הלפני־אחרון לאחרון pChar כבר null, והקריאה ל־getNext עליו זורקת חריגה.
public static boolean match(Node<Integer> numHead, Node<Character> charHead, int len, int val) {
Node<Integer> pNum = numHead;
Node<Character> pChar = charHead; // התו באותו מיקום כמו pNum
while (pNum != null) {
if (eval(pNum, pChar, len) == val)
return true;
pNum = pNum.getNext();
if (pChar != null) // לחוליה האחרונה במספרים אין תו מתאים
pChar = pChar.getNext();
}
return false;
}שאלה 3 · מעקב אחרי פעולות רקורסיביות על עץ בינרי (25 נקודות)
שימו לב: לשאלה זו שני נוסחים: בשפת Java בעמודים 6–7 ובשפת C# בעמודים 8–9.
לפותרים בשפת Java
נתונה הפעולה foo שלפניכם:
public static int foo (BinNode<Integer> tree) {
if (tree.getLeft() == null && tree.getRight() == null)
return 0;
if (tree.getLeft() == null)
return foo (tree.getRight()) + 1;
if (tree.getRight() == null)
return foo (tree.getLeft()) - 1;
return foo (tree.getLeft()) + foo (tree.getRight());
}בצעו מעקב אחרי הפעולה foo והעץ שלפניכם, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.
בצעו מעקב אחרי הפעולה foo והעץ שלפניכם, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.
בעבור עץ שיש לו 6 צמתים, מהו המספר הכי גבוה שהפעולה foo יכולה להחזיר? הציגו את העץ.
בעבור עץ שיש לו 6 צמתים, מהו המספר הכי נמוך שהפעולה foo יכולה להחזיר? הציגו את העץ.
כתבו בקצרה מה הפעולה foo מחזירה בעבור עץ כלשהו שאינו ריק.
נתונה הפעולה goo שלפניכם:
public static boolean goo (BinNode<Integer> tree) {
if (tree == null)
return true;
if (foo (tree) != 0)
return false;
return goo (tree.getLeft()) && goo (tree.getRight());
}בצעו מעקב אחרי הפעולה goo והעץ שלפניכם, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.
בסעיף זה אין צורך להציג מעקב אחרי הפעולה foo .
הציגו עץ שיש לו מעל 3 צמתים שבעבורו הפעולה goo תחזיר תוצאה הפוכה מן התוצאה שהתקבלה בתת־סעיף ב(1).
◂ פתרון מלא לשאלה 3
סעיף א(1)
2
מה נדרש: מעקב אחרי foo על העץ 5 → 9 → 7 (ל־7 שני בנים: 0 משמאל ו־3 מימין).
רעיון: foo בודקת לכל צומת איזה סוג הוא: עלה ← 0; יש רק בן ימני ← foo(ימני) + 1; יש רק בן שמאלי ← foo(שמאלי) − 1; שני בנים ← סכום שני הבנים. הקריאות יורדות עד העלים, והערכים חוזרים למעלה.
פתרון (מעקב):
| קריאה | מצב הצומת | חישוב | ערך מוחזר |
|---|---|---|---|
| foo(5) | רק בן ימני (9) | foo(9) + 1 | 2 |
| foo(9) | רק בן ימני (7) | foo(7) + 1 | 1 |
| foo(7) | שני בנים | foo(0) + foo(3) | 0 |
| foo(0) | עלה | – | 0 |
| foo(3) | עלה | – | 0 |
חזרה מהרקורסיה: foo(0) = 0, foo(3) = 0 ← foo(7) = 0 + 0 = 0 ← foo(9) = 0 + 1 = 1 ← foo(5) = 1 + 1 = 2.
הפעולה מחזירה 2.
בדיקה: הקוד הנתון מדפיס על העץ 2.
(הערה: בנוסח C# שבשאלון הסימן בשורה return Foo (tree.GetLeft()) - 1; מודפס כקו מפריד '–'. זהו סימן המינוס; בקוד שמוצג כאן הוא נכתב כ־'-' הרגיל.)
סעיף א(2)
0
מה נדרש: מעקב אחרי foo על העץ: 5 ← בן ימני 1; ל־1 בן שמאלי 0 ובן ימני 7; ל־0 רק בן שמאלי 2; ל־2 רק בן שמאלי 4; ל־7 רק בן ימני 3.
פתרון (מעקב):
| קריאה | מצב הצומת | חישוב | ערך מוחזר |
|---|---|---|---|
| foo(5) | רק בן ימני (1) | foo(1) + 1 | 0 |
| foo(1) | שני בנים | foo(0) + foo(7) | −1 |
| foo(0) | רק בן שמאלי (2) | foo(2) − 1 | −2 |
| foo(2) | רק בן שמאלי (4) | foo(4) − 1 | −1 |
| foo(4) | עלה | – | 0 |
| foo(7) | רק בן ימני (3) | foo(3) + 1 | 1 |
| foo(3) | עלה | – | 0 |
חזרה מהרקורסיה: foo(4) = 0 ← foo(2) = −1 ← foo(0) = −2; foo(3) = 0 ← foo(7) = 1; foo(1) = −2 + 1 = −1 ← foo(5) = −1 + 1 = 0.
הפעולה מחזירה 0.
בדיקה: הקוד הנתון מדפיס על העץ 0, וערכי הביניים זהים לטבלה.
סעיף א(3)
5 – שרשרת של 6 צמתים שלכל אחד (חוץ מהאחרון) רק בן ימני.
מה נדרש: הערך המקסימלי של foo בעץ בן 6 צמתים, ועץ שמשיג אותו.
רעיון: מהמעקב רואים ש־foo מוסיפה +1 על כל צומת שיש לו רק בן ימני, −1 על כל צומת שיש לו רק בן שמאלי, ו־0 על עלה ועל צומת עם שני בנים (ראו סעיף 5). בכל עץ יש לפחות עלה אחד, ולכן לכל היותר 5 מתוך 6 הצמתים יכולים לתרום +1.
פתרון: המספר הגבוה ביותר הוא 5. העץ: "שרשרת ימנית" – כל צומת (חוץ מהאחרון) הוא בעל בן ימני בלבד (הערכים בצמתים לא משנים):
a
\
b
\
c
\
d
\
e
\
ffoo(f) = 0, foo(e) = 1, foo(d) = 2, foo(c) = 3, foo(b) = 4, foo(a) = 5.
בדיקה: על כל צורות העצים בני 6 צמתים הערך הגבוה ביותר של foo הוא 5, ועל השרשרת הימנית מתקבל 5.
סעיף א(4)
−5 – שרשרת של 6 צמתים שלכל אחד (חוץ מהאחרון) רק בן שמאלי.
מה נדרש: הערך המינימלי של foo בעץ בן 6 צמתים, ועץ שמשיג אותו.
רעיון: כמו בסעיף הקודם, רק הפוך: כל צומת עם בן שמאלי בלבד תורם −1, ולפחות צומת אחד (עלה) תורם 0.
פתרון: המספר הנמוך ביותר הוא −5. העץ: "שרשרת שמאלית" – כל צומת (חוץ מהאחרון) הוא בעל בן שמאלי בלבד:
a
/
b
/
c
/
d
/
e
/
ffoo(f) = 0, foo(e) = −1, foo(d) = −2, foo(c) = −3, foo(b) = −4, foo(a) = −5.
בדיקה: על כל העצים בני 6 צמתים הערך הנמוך ביותר הוא −5, ועל השרשרת השמאלית מתקבל −5.
סעיף א(5)
מספר הצמתים שיש להם בן ימני בלבד פחות מספר הצמתים שיש להם בן שמאלי בלבד.
מה נדרש: לתאר במשפט מה foo מחזירה.
רעיון: לפי ארבעת המקרים בקוד: עלה תורם 0; צומת עם בן ימני בלבד מוסיף 1 לתוצאה של תת־העץ שלו; צומת עם בן שמאלי בלבד מוריד 1; צומת עם שני בנים רק מחבר את התוצאות של שני תתי־העצים. לכן כל צומת בעץ תורם בדיוק פעם אחת: +1, −1 או 0.
פתרון: foo מחזירה את מספר הצמתים בעץ שיש להם בן ימני בלבד, פחות מספר הצמתים שיש להם בן שמאלי בלבד.
בדיקה: בעץ של סעיף (1) יש 2 צמתים עם בן ימני בלבד (5, 9) ואין צמתים עם בן שמאלי בלבד ← 2 − 0 = 2 ✓. בעץ של סעיף (2) יש 2 צמתים עם בן ימני בלבד (5, 7) ו־2 עם בן שמאלי בלבד (0, 2) ← 2 − 2 = 0 ✓. על כל צורות העצים הקטנות foo שווה תמיד להפרש הזה.
טעות נפוצה: לכתוב ש־foo "סופרת צמתים" או "מחשבת גובה" – הערך יכול להיות שלילי, ולצמתים עם שני בנים ולעלים אין השפעה. שימו לב גם שעל עץ ריק (null) הפעולה נכשלת, ולכן השאלה מדברת על עץ שאינו ריק.
סעיף ב(1)
false (foo(5) = 0, אבל foo(1) = −1)
מה נדרש: מעקב אחרי goo על העץ מסעיף א(2).
רעיון: goo מחזירה true לעץ ריק. לעץ לא ריק היא דורשת ש־foo של הצומת הנוכחי תהיה 0, ואז ממשיכה רקורסיבית לבן השמאלי ולבן הימני (עם && – אם השמאלי מחזיר false, הימני לא נבדק כלל). כלומר goo מחזירה true רק אם foo שווה 0 בכל תת־עץ.
פתרון (מעקב): (ערכי foo נלקחים מסעיף א(2))
| קריאה | בדיקה | תוצאה |
|---|---|---|
| goo(5) | foo(5) = 0 ← ממשיכים: goo(שמאלי של 5) && goo(1) | – |
| goo(null) | הבן השמאלי של 5 ריק | true |
| goo(1) | foo(1) = −1 ≠ 0 | false |
| goo(5) | true && false | false |
הפעולה מחזירה false.
בדיקה: הקוד הנתון מדפיס על העץ false.
סעיף ב(2)
כל עץ עם יותר מ־3 צמתים שבו לכל צומת 0 או 2 בנים, למשל 5 ← (1, 7), 7 ← (3, 4); goo מחזירה true.
מה נדרש: בסעיף ב(1) התקבל false, ולכן צריך עץ עם יותר מ־3 צמתים שבעבורו goo מחזירה true.
רעיון: goo מחזירה true רק אם foo = 0 בכל תת־עץ. אם לצומת v יש בן אחד בלבד, למשל ימני, אז foo(v) = foo(ימני) + 1, ולכן foo(v) ו־foo(ימני) לא יכולים להיות שניהם 0 – goo תחזיר false. מכאן ש־goo מחזירה true בדיוק כאשר לכל צומת יש 0 או 2 בנים. מספיק לבנות עץ כזה עם יותר מ־3 צמתים.
פתרון: עץ בן 5 צמתים (הערכים לא משנים):
5
/ \
1 7
/ \
3 4foo של כל העלים (1, 3, 4) הוא 0; foo(7) = 0 + 0 = 0; foo(5) = 0 + 0 = 0. לכן goo(5) ← goo(1) = true ו־goo(7) = true ← goo מחזירה true, ההפך מסעיף ב(1).
(גם עץ מלא בן 7 צמתים – שורש, שני בנים וארבעה נכדים – מתאים.)
בדיקה: goo מחזירה על העץ הזה true. בנוסף, על כל צורות העצים עד 7 צמתים goo החזירה true בדיוק כשלכל צומת 0 או 2 בנים.
טעות נפוצה: להציג עץ עם 3 צמתים בלבד (שורש ושני עלים) – השאלה דורשת מעל 3 צמתים.
פרק שני (50 נקודות) – אלגוריתמים
בפרק זה שאלות בשלושה מסלולים:
אלגוריתמים, עמודים 10–14.
מודלים חישוביים, עמודים 15–17.
תכנות מונחה עצמים (שפת Java ושפת C#), עמודים 18–27.
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 4 · טענות על גרפים וגרף "DFS שרשרתי" (25 נקודות)
לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם שבע טענות (1)–(7). בחרו בחמש מהן, וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא לא נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) נתון גרף G שאינו מכוון. אם בגרף יש קשת בין שני הקודקודים x , y , הרכיבים הקשירים של x ושל y זהים.
(2) נתון גרף G מכוון. אם בגרף יש קשת מקודקוד y לקודקוד x וקשת מקודקוד x לקודקוד y , הרכיבים הקשירים היטב של x ושל y זהים.
(3) בגרף מכוון שיש בו מעגל, יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ־ 0.
(4) אם בגרף ממושקל קשיר לא מכוון יש לכל קשת משקל שונה, אז המסלול הקצר (הקל) בין כל שני קודקודים בגרף הוא מסלול יחיד (כלומר אין יותר ממסלול קצר אחד בין קודקוד לקודקוד).
(5) בגרף מכוון שבו המשקל של כל קשת הוא משקל שונה יש עץ פורש מינימלי יחיד.
(6) לא קיים גרף מכוון ממושקל שבו האלגוריתם של דייקסטרה מקודקוד y אל קודקוד x ייתן את אותו מסלול קצר (קל) שהאלגוריתם BFS נותן.
(7) אפשר לעשות מיון טופולוגי בעבור כל גרף מכוון.
עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר.
דוגמה לעץ פורש "שרשרת":
גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת בגרף מתקבל עץ פורש "שרשרת".
לפניכם שבעה גרפים G₁–G₇ . בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף "DFS שרשרתי" או לא. אם כתבתם שלא – הציגו סריקת DFS שבעבורה מתקבל גרף שאינו עץ פורש "שרשרת".
◂ פתרון מלא לשאלה 4
סעיף א
(1) נכונה; (2) נכונה; (3) נכונה (בגרף בלי לולאות עצמיות); (4) לא נכונה; (5) לא נכונה (כפי שהיא מודפסת – בגרף מכוון; לגרף לא מכוון קשיר היא הייתה נכונה); (6) לא נכונה; (7) לא נכונה. (מספיק לענות על חמש מהן, למשל 1, 2, 4, 6, 7.)
מה נדרש: לבחור 5 מתוך 7 טענות, לקבוע אם כל אחת נכונה, ולנמק (טענה נכונה) או להביא דוגמה נגדית עם 4 קודקודים לפחות (טענה לא נכונה).
רעיון: כאן מוצגות כל שבע הטענות. מומלץ לבחור טענות שהתשובה עליהן חד־משמעית, למשל (1), (2), (4), (6), (7).
פתרון:
(1) נכונה. רכיב קשיר הוא קבוצה מקסימלית של קודקודים שיש מסלול בין כל שניים מהם. הקשת x–y היא מסלול בין x ל־y, ולכן x ו־y שייכים לאותו רכיב קשיר. כל קודקוד z שמחובר במסלול ל־x מחובר גם ל־y (דרך x והקשת), ולהפך – ולכן הרכיבים זהים.
(2) נכונה. רכיב קשיר היטב הוא קבוצה מקסימלית שבה יש מסלול מכוון מכל קודקוד לכל קודקוד. בזכות שתי הקשתות יש מסלול x→y וגם y→x, לכן x ו־y באותו רכיב קשיר היטב. אם z מגיע ל־x וגם x מגיע ל־z, אז z מגיע ל־y (z→…→x→y) ו־y מגיע ל־z (y→x→…→z). לכן הרכיבים זהים.
(3) נכונה (כמקובל, בגרף בלי לולאה עצמית – קשת מקודקוד לעצמו). מעגל מכוון עובר בלפחות שני קודקודים שונים v₁→v₂→…→vₖ→v₁ (k ≥ 2). לכל קודקוד על המעגל נכנסת קשת מהקודקוד שלפניו במעגל, ולכן לכל k ≥ 2 הקודקודים האלה דרגת הכניסה גדולה מ־0.
(אם מתירים לולאה עצמית, הטענה אינה נכונה: גרף עם ארבעה קודקודים A, B, C, D וקשת יחידה A→A – יש מעגל, ורק ל־A דרגת כניסה גדולה מ־0. לכן עדיף לא לבחור טענה זו.)
(4) לא נכונה. דוגמה נגדית – גרף לא מכוון עם הקשתות:
| קשת | A–B | B–C | A–C | C–D |
|---|---|---|---|---|
| משקל | 1 | 2 | 3 | 4 |
כל המשקלים שונים, אבל בין A ל־C יש שני מסלולים קלים במשקל 3: הקשת A–C (משקל 3) והמסלול A–B–C (משקל 1+2=3).
(5) לא נכונה. עץ פורש מינימלי מוגדר לגרף לא מכוון וקשיר. בגרף מכוון ייתכן שאין עץ פורש כלל. דוגמה נגדית: גרף מכוון עם הקודקודים A, B, C, D והקשתות A→B (משקל 1), C→D (משקל 2). המשקלים שונים, אבל אין בגרף אף עץ פורש (גם אם מתעלמים מכיוון הקשתות, הגרף אינו קשיר) – ולכן אין עץ פורש מינימלי יחיד.
(קריאה אחרת: אם הכוונה הייתה לגרף לא מכוון וקשיר, הטענה נכונה – כשכל המשקלים שונים יש עפ"מ יחיד: אילו היו שני עפ"מים שונים T₁, T₂, ניקח את הקשת הקלה ביותר e שנמצאת רק באחד מהם, נניח ב־T₁; הוספתה ל־T₂ יוצרת מעגל, ובמעגל יש קשת e′ שאינה ב־T₁, ומשקלה גדול ממשקל e; החלפת e′ ב־e נותנת עץ פורש קל מ־T₂ – סתירה. בגלל אי־הבהירות עדיף לא לבחור טענה זו.)
(6) לא נכונה. דוגמה נגדית: גרף מכוון y→A→B→x שבו משקל כל קשת 1. גם BFS מ־y וגם דייקסטרה מ־y נותנים את המסלול היחיד y→A→B→x. (באופן כללי – כשכל המשקלים שווים, דייקסטרה ו־BFS מוצאים מסלולים קצרים זהים באורכם.)
(7) לא נכונה. מיון טופולוגי אפשרי רק בגרף מכוון חסר מעגלים (DAG). דוגמה נגדית: A→B→C→D→A. לכל קודקוד דרגת כניסה 1, אין קודקוד שיכול להיות ראשון במיון: כל קודקוד חייב להופיע אחרי הקודקוד שלפניו במעגל – סתירה.
בדיקה: משקלי שני המסלולים בטענה (4) – [3, 3]; דייקסטרה ו־BFS בטענה (6) מחזירים שניהם y, A, B, x; בטענה (7) דרגות הכניסה הן 1 לכל קודקוד.
טעות נפוצה: בטענה (4) לבלבל עם עץ פורש מינימלי – משקלים שונים מבטיחים עץ פורש מינימלי יחיד (בגרף לא מכוון), אבל לא מסלול קצר יחיד.
סעיף ב
G₃ (מעגל) ו־G₇ (גרף מלא K₄) הם "DFS שרשרתיים". G₁, G₂, G₄, G₅, G₆ אינם (ראו סריקות נגדיות בפתרון).
מה נדרש: לקבוע לארבעה גרפים אם כל סריקת DFS (מכל צומת התחלה ובכל סדר בחירת שכנים) נותנת עץ שבו לכל צומת בן אחד לכל היותר; ואם לא – להציג סריקה שבה לצומת כלשהו יש שני בנים.
רעיון: עץ DFS הוא שרשרת אם ורק אם הסריקה אף פעם לא "חוזרת אחורה" לצומת שכבר יש לו בן ומוצאת ממנו שכן חדש. מספיק למצוא סריקה אחת שבה חוזרים (backtrack) לצומת ומשם יוצאים לבן שני.
פתרון: (רשימת הקשתות כפי שבאיור)
| גרף | קשתות | DFS שרשרתי? | סריקה נגדית (קשתות העץ לפי סדר הגילוי) |
|---|---|---|---|
| G₁ | A–B, B–C, B–D, B–E, B–F | לא | מ־A: A→B, B→C, (חזרה ל־B) B→D, B→E, B→F. ל־B יש ארבעה בנים |
| G₂ | A–B, B–C, C–D, D–E | לא | מ־B: B→A, (חזרה ל־B) B→C, C→D, D→E. ל־B שני בנים (A ו־C) |
| G₃ | A–B, B–C, C–D, D–E, E–F, F–A | כן | – |
| G₄ | A–B, B–C, B–E, C–D, D–E | לא | מ־B: B→A, (חזרה ל־B) B→C, C→D, D→E. ל־B שני בנים |
| G₅ | A–B, B–C, A–D, B–D | לא | מ־A: A→B, B→C, (חזרה ל־B) B→D. ל־B שני בנים |
| G₆ | A–B, B–C, A–D, C–F, B–E, E–F, E–D | לא | מ־A: A→B, B→E, E→D, (חזרה ל־E) E→F, F→C. ל־E שני בנים |
| G₇ | כל 6 הקשתות בין A, B, C, D | כן | – |
נימוק ל־G₃ (מעגל של 6 צמתים): מכל צומת יש שני שכנים. DFS יוצא לאחד מהם, וממנו תמיד יש בדיוק שכן אחד שלא ביקרנו בו (הצומת הבא במעגל), עד שמגיעים לצומת האחרון שכל שכניו כבר ביקורים. כלומר הסריקה עוברת על המעגל בכיוון אחד בלי לחזור אחורה – מתקבלת שרשרת, מכל צומת ובכל בחירה.
נימוק ל־G₇ (גרף מלא): כל צומת מחובר לכל הצמתים. בכל שלב של DFS לצומת הנוכחי יש קשת לכל צומת שעוד לא ביקרנו בו, ולכן הסריקה ממשיכה תמיד מהצומת האחרון שהתגלה ואינה חוזרת אחורה עד שכל הצמתים התגלו – מתקבלת שרשרת.
בדיקה: בכל סריקות ה־DFS האפשריות (כל צומת התחלה וכל סדר בחירת שכנים) בשבעת הגרפים: רק ב־G₃ וב־G₇ כל העצים הם שרשרות; בשאר נמצאו הסריקות שבטבלה.
טעות נפוצה: לחשוב ש־G₂ (מסלול) הוא "DFS שרשרתי" כי הוא עצמו שרשרת. סריקה מצומת אמצעי (למשל B או C) נותנת לשורש שני בנים.
שאלה 5 · גרף דו־צדדי ואלגוריתם Path (BFS מתחלף) (25 נקודות)
לפניכם גרף לא מכוון דו־צדדי G = (A, B, E) .
| צמתים בצד A | A = {A1, A2, A3} |
| צמתים בצד B | B = {B1, B2, B3} |
| קשתות בין A ל־ B | E = {(A1 – B1), (A1 – B2), (A2 – B1), (A2 – B2), (A2 – B3), (A3 – B1), (A3 – B2)} |
הצומת M מוגדר "שכן" של הצומת U , אם יש קשת ביניהם.
לפניכם טבלת שכנויות המציגה את השכנים של כל צומת בגרף G . הצמתים השכנים של A1 ושל B1 נתונים בטבלה.
השלימו את הטבלה.
| U | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
| M | B1 , B2 | A1 , A2 , A3 |
נתונה רשימה של חלק מן הקשתות בגרף G : L = {(A1 – B1), (A2 – B2)} .
"צומת תפוס" הוא צומת שמופיע ברשימה L (הצמתים A1 , A2 , B1 , B2 מופיעים ולכן הם "צמתים תפוסים").
"צומת חופשי" הוא צומת שאינו מופיע ברשימה L (הצמתים A3 , B3 אינם מופיעים ולכן הם "צמתים חופשיים").
נתון האלגוריתם Path (G, L) .
שלב אתחול נתונים באלגוריתם:
שימו לב: במהלך ריצת האלגוריתם ייכנסו לתור צמתים נוספים השייכים לצד A או לצד B .
| visited: | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
| לא | לא | כן | לא | לא | לא |
| parent: | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
שלב הרצת האלגוריתם:
בעבור כל צומת שכן – M של הצומת U :
אם עדיין לא ביקרנו בצומת M (לא = visited[M]), וגם אחד מן התנאים שלהלן מתקיימים:
– U בצד A והקשת (U–M) אינה נמצאת ברשימה L
– U בצד B והקשת (U–M) נמצאת ברשימה L
אז:
א. נכניס את M לתור.
ב. נכתוב את הערך כן בתא M במערך visited .
ג. נעדכן שהצומת U הוא ההורה של M במערך parent .
עקבו בטבלת מעקב אחרי ריצת האלגוריתם Path על הגרף הנתון G , עם הרשימה L .
המעקב צריך לכלול בכל איטרציה את הפריטים שלהלן:
| התור | U | visited A1 | A2 | A3 | B1 | B2 | B3 | parent A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ←[ ] | |||||||||||||
| ←[ ] |
כתבו את רשימת הצמתים שהאלגוריתם מחזיר.
◂ פתרון מלא לשאלה 5
סעיף א
A2: B1, B2, B3 ; A3: B1, B2 ; B2: A1, A2, A3 ; B3: A2
מה נדרש: להשלים לכל צומת את רשימת שכניו.
רעיון: עוברים על רשימת הקשתות E. כל קשת (X – Y) מוסיפה את Y לשכני X ואת X לשכני Y.
פתרון:
| U | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
| M | B1 , B2 | B1 , B2 , B3 | B1 , B2 | A1 , A2 , A3 | A1 , A2 , A3 | A2 |
בדיקה: סכום הדרגות 2+3+2+3+3+1 = 14 = 2·7, פעמיים מספר הקשתות (7), כנדרש.
סעיף ב
הוצאות מהתור לפי הסדר: A3, B1, B2, A1, A2, B3. ב־B3 (צד B, חופשי) האלגוריתם עוצר. parent בסוף: A1←B1, A2←B2, B1←A3, B2←A3, B3←A2.
מה נדרש: להריץ את Path צעד אחר צעד ולרשום אחרי כל איטרציה את התור, את U ואת שני המערכים.
רעיון: זו סריקת BFS מ־A3 עם הגבלה: מצד A מותר ללכת רק בקשת שאינה ב־L, ומצד B רק בקשת שנמצאת ב־L (מסלול "מתחלף"). השכנים נבדקים לפי סדר הטבלה מסעיף א (A1, A2, A3 / B1, B2, B3). התור כתוב משמאל (ראש התור) לימין (סוף התור).
פתרון:
| התור (אחרי האיטרציה) | U | visited A1 | A2 | A3 | B1 | B2 | B3 | parent A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [A3] (אתחול) | לא | לא | כן | לא | לא | לא | |||||||
| [B1, B2] | A3 | לא | לא | כן | כן | כן | לא | A3 | A3 | ||||
| [B2, A1] | B1 | כן | לא | כן | כן | כן | לא | B1 | A3 | A3 | |||
| [A1, A2] | B2 | כן | כן | כן | כן | כן | לא | B1 | B2 | A3 | A3 | ||
| [A2] | A1 | כן | כן | כן | כן | כן | לא | B1 | B2 | A3 | A3 | ||
| [B3] | A2 | כן | כן | כן | כן | כן | כן | B1 | B2 | A3 | A3 | A2 | |
| [ ] | B3 | כן | כן | כן | כן | כן | כן | B1 | B2 | A3 | A3 | A2 |
בשורה האחרונה U = B3 הוא צומת חופשי בצד B, ולכן האלגוריתם עוצר (התור ריק כבר, אבל העצירה היא בגלל B3).
בדיקה: מעקב אחרי Path בדיוק כמתואר נותן את אותה טבלה.
סעיף ג
B3 , A2 , B2 , A3
מה נדרש: הרשימה שמוחזרת כשמגיעים לצומת חופשי בצד B.
רעיון: מתחילים ב־U = B3 ועולים במערך parent עד צומת שאין לו הורה.
פתרון: B3 ⇐ parent[B3] = A2 ⇐ parent[A2] = B2 ⇐ parent[B2] = A3 ⇐ parent[A3] ריק (עצירה).
הרשימה: B3 , A2 , B2 , A3.
הערה: זהו מסלול "מתחלף" בין שני צמתים חופשיים: A3–B2 (לא ב־L), B2–A2 (ב־L), A2–B3 (לא ב־L). אם מחליפים ב־L את הקשתות של המסלול, מתקבלת רשימה גדולה יותר של קשתות זרות: {(A1–B1), (A3–B2), (A2–B3)}.
בדיקה: התוצאה: ['B3', 'A2', 'B2', 'A3'].
שאלה 6 · גרף "כוכב סגור" (25 נקודות)
גרף "כוכב סגור" – Gₙ הוא גרף לא מכוון שמורכב ממעגל של n קודקודים (מ־ 1 עד n), המכונים "קודקודי המעגל", ומקודקוד נוסף – 0 , המכונה "קודקוד מרכז", שנמצא במרכז המעגל ומחובר לכל אחד מ"קודקודי המעגל" (כך שסך הכול יש n + 1 קודקודים בגרף). מספר "קודקודי המעגל" בגרף גדול מ־ 2 (כלומר n > 2).
דוגמה: הגרף שלפניכם הוא גרף "כוכב סגור" – G₆ , כי הקודקודים 1 עד 6 יוצרים מעגל, והקודקוד הנוסף, 0 , נמצא במרכז ומחובר לכל אחד מהם.
"קשתות המעגל" הן הקשתות המחברות את "קודקודי המעגל" זה לזה (למשל בדוגמה לעיל, הקשת שמחברת את הקודקודים 1 ו־ 2 זה לזה, הקשת שמחברת את הקודקודים 2 ו־ 3 זה לזה וכן הלאה).
"קשתות מרכזיות" הן הקשתות המחברות את "קודקוד מרכז" לכל אחד מ"קודקודי המעגל" (למשל בדוגמה לעיל, הקשת שמחברת את קודקוד 0 לקודקוד 1 , הקשת שמחברת את קודקוד 0 לקודקוד 2 וכן הלאה).
נתון גרף "כוכב סגור" – Gₙ .
(1) מה הן דרגות "קודקודי המעגל" בגרף, ומהי דרגת "קודקוד מרכז"? נמקו את תשובתכם.
כמה "קשתות מעגל" יש בגרף, וכמה "קשתות מרכזיות" יש בגרף? נמקו את תשובתכם.
האם הגרף הוא דו־צדדי? נמקו את תשובתכם.
נתון גרף ממושקל שהוא "כוכב סגור" – Gₙ , שבו לכל "קשתות המעגל" משקל 2 , ולכל "הקשתות המרכזיות" משקל 1 .
כמה עפ"מים (עצים פורשים מינימליים) שונים יש בגרף? נמקו את תשובתכם.
נתון גרף ממושקל שהוא "כוכב סגור" – Gₙ , שבו לכל "קשתות המעגל" משקל b (גדול מ־ 0), ולכל "הקשתות המרכזיות" משקל m (גדול מ־ 0).
(1) הציבו ערכים ל־ b ו־ m , שעבורם כל מסלול קצר (קל) בין שני "קודקודי מעגל" יעבור דרך "קודקוד מרכז". נמקו את תשובתכם.
נתון כי b = 10 . מהו הערך הגדול ביותר של m שבעבורו כל מסלול קצר (קל) בין שני "קודקודי מעגל" עדיין יעבור דרך "קודקוד מרכז"? נמקו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א(1)
דרגת כל קודקוד מעגל 3; דרגת קודקוד המרכז n.
מה נדרש: דרגות הקודקודים ב־Gₙ.
רעיון: סופרים את הקשתות שנוגעות בכל קודקוד.
פתרון: כל "קודקוד מעגל" i נוגע בשתי קשתות מעגל (אל הקודקוד שלפניו ואל הקודקוד שאחריו במעגל) ובקשת מרכזית אחת (אל 0) ⇐ דרגה 3. "קודקוד המרכז" מחובר בקשת אחת לכל אחד מ־n קודקודי המעגל ⇐ דרגה n.
בדיקה: ב־G₆ שבאיור: לקודקוד 1 שכנים 6, 2, 0 (דרגה 3), ולקודקוד 0 שישה שכנים. כך גם לכל 3 ≤ n ≤ 7.
סעיף א(2)
n קשתות מעגל ו־n קשתות מרכזיות (סך הכול 2n).
מה נדרש: מספר הקשתות מכל סוג.
פתרון: מעגל של n קודקודים מכיל n קשתות (1–2, 2–3, …, (n−1)–n, n–1) ⇐ n קשתות מעגל. קודקוד המרכז מחובר לכל אחד מ־n קודקודי המעגל ⇐ n קשתות מרכזיות (בהתאם לדרגתו n מסעיף 1).
בדיקה: לפי משפט סכום הדרגות: n·3 + n = 4n = 2·(מספר הקשתות) ⇐ 2n קשתות = n + n. ב־G₆: 6 + 6 = 12 קשתות.
סעיף א(3)
לא. למשל 0, 1, 2 יוצרים משולש – מעגל באורך אי־זוגי.
מה נדרש: לקבוע אם אפשר לחלק את הקודקודים לשני צדדים כך שכל קשת עוברת בין הצדדים.
רעיון: גרף הוא דו־צדדי אם ורק אם אין בו מעגל באורך אי־זוגי.
פתרון: הגרף אינו דו־צדדי לכל n > 2. הקודקודים 0, 1, 2 יוצרים מעגל באורך 3: 0–1 (קשת מרכזית), 1–2 (קשת מעגל), 2–0 (קשת מרכזית). אם 0 בצד אחד, אז 1 ו־2 חייבים להיות שניהם בצד השני – אבל יש ביניהם קשת. סתירה.
בדיקה: צביעה בשני צבעים נכשלת לכל 3 ≤ n ≤ 7.
סעיף ב
עפ"מ אחד בלבד – העץ שמורכב מכל n הקשתות המרכזיות (משקלו n).
מה נדרש: מספר העצים הפורשים המינימליים.
רעיון: לכל עץ פורש על n + 1 קודקודים יש בדיוק n קשתות, ומשקל כל קשת הוא לפחות 1.
פתרון: לכן משקל כל עץ פורש הוא לפחות n·1 = n. n הקשתות המרכזיות (כולן במשקל 1) יוצרות עץ פורש (כוכב: 0 מחובר לכל הקודקודים, אין מעגל) – משקלו בדיוק n, ולכן הוא עפ"מ. כל עץ פורש אחר מכיל לפחות קשת מעגל אחת (משקל 2), ולכן משקלו לפחות n + 1 > n. כלומר יש עפ"מ אחד בלבד.
(גם בקרוסקל: קודם נבחרות כל n הקשתות במשקל 1, הן כבר מחברות את כל הקודקודים, וכל קשת מעגל תיצור מעגל.)
בדיקה: לכל 3 ≤ n ≤ 7 יש עפ"מ יחיד במשקל n.
טעות נפוצה: לחשוב שיש כמה עפ"מים כי יש הרבה קשתות במשקל שווה – כאן כל הקשתות במשקל 1 נבחרות, ואין בחירה.
סעיף ג(1)
למשל b = 3 , m = 1 (כל בחירה עם 2m < b מתאימה).
מה נדרש: משקלים שבהם כל מסלול קל ביותר בין שני קודקודי מעגל עובר ב־0.
רעיון: בין שני קודקודי מעגל, המסלול דרך המרכז i–0–j שוקל תמיד 2m. מסלול שלא עובר במרכז נע רק על המעגל ומשתמש לפחות בקשת מעגל אחת, ולכן שוקל לפחות b. (מסלול שעובר במרכז ומשתמש גם בקשתות מעגל כבד יותר מ־2m.)
פתרון: אם 2m < b, כל מסלול שאינו עובר במרכז שוקל ≥ b > 2m, ולכן המסלול הקל היחיד הוא i–0–j. דוגמה: b = 3 , m = 1: בין שני שכנים במעגל – הקשת הישירה 3, דרך המרכז 1+1 = 2; בין קודקודים רחוקים יותר – על המעגל ≥ 6, דרך המרכז 2.
בדיקה: בכל המסלולים בין כל זוג קודקודי מעגל (3 ≤ n ≤ 7) עם b = 3 , m = 1 – כל המסלולים הקלים ביותר עוברים ב־0.
סעיף ג(2)
צריך 2m < 10, כלומר m < 5. במשקלים שלמים – m = 4 (ב־m = 5 יש גם מסלול קל שאינו עובר במרכז).
מה נדרש: הערך הגדול ביותר של m כאשר b = 10.
רעיון: לפי סעיף (1), התנאי הוא שהמסלול דרך המרכז (2m) יהיה קל ממש מהקשת הישירה בין שני קודקודים שכנים במעגל (b = 10).
פתרון: צריך 2m < 10 ⇐ m < 5. אם המשקלים שלמים, הערך הגדול ביותר הוא m = 4: אז דרך המרכז 8 < 10.
ב־m = 5: בין שני שכנים במעגל יש שני מסלולים קלים במשקל 10 – דרך המרכז (5+5) והקשת הישירה (10). הקשת הישירה אינה עוברת במרכז, ולכן לא כל מסלול קל עובר במרכז. ב־m > 5 הקשת הישירה קלה יותר.
(אם m יכול להיות לא שלם, כל m < 5 מתאים ואין "גדול ביותר"; התשובה המקובלת היא m = 4 למשקלים שלמים, או "m קטן מ־5".)
בדיקה: עם b = 10 ו־m = 1..9: התנאי מתקיים רק ל־m = 1, 2, 3, 4; גם m = 4.9 מתאים, ו־m = 5 לא.
טעות נפוצה: לענות m = 5 – במצב של שוויון יש מסלול קל נוסף שאינו עובר במרכז.
פרק שני (50 נקודות) – מודלים חישוביים
בפרק זה שאלות בשלושה מסלולים:
אלגוריתמים, עמודים 10–14.
מודלים חישוביים, עמודים 15–17.
תכנות מונחה עצמים (שפת Java ושפת C#), עמודים 18–27.
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 7 · רגולריות של שפות ואוטומט סופי דטרמיניסטי (25 נקודות)
לפניכם שני סעיפים א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם שלוש שפות L₁ – L₃ מעל הא"ב {a, b, c} :
L₁ = {aⁿ bᵏ cⁿ | 0 < n < 1000 < k}
L₂ = {aⁿ bᵏ cⁿ | 0 < k < 1000 < n}
L₃ = {aⁿ bᵏ cⁿ | 0 < k < 1000 < n < 2000}
בנוגע לכל אחת מן השפות L₁ – L₃ , כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).
לפניכם שלוש שפות L₄ – L₆ מעל הא"ב {a, b, c} :
L₄ = L₂ ∩ R(L₂)
L₅ = L₁ ∪ L₂
L₆ = L̅₁ ∪ L̅₃
בנוגע לכל אחת מן השפות L₄ – L₆ , כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).
לפניכם השפה L מעל הא"ב {a, b, c} :
> L = {aⁿ bᵐ aᵏ w | n, m, k > 0}
>
> w היא מילה מעל הא"ב {b, c} המאופיינת באופן שלהלן:
> - אם n + k מתחלק ב־ 3 בלי שארית, w היא מילה ריקה.
> - אם n + k מתחלק ב־ 3 עם שארית 1 , w היא מילה שאינה מכילה את האות b כלל.
> - אם n + k מתחלק ב־ 3 עם שארית 2 , w היא מילה שאינה מכילה את האות c כלל.
דוגמה למילה השייכת לשפה L : a bb aaa ccc (aⁿ = a , bᵐ = bb , aᵏ = aaa , w = ccc)
הסבר: k = 3 , n = 1 . n + k מתחלק ב־ 3 עם שארית 1 , ו־ w היא מילה שאינה מכילה את האות b .
בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L .
◂ פתרון מלא לשאלה 7
סעיף א(1)
L₁ – רגולרית; L₂ – לא רגולרית; L₃ – רגולרית (סופית).
מה נדרש: לקבוע רגולריות של שלוש שפות ולנמק במילים.
רעיון: אוטומט סופי יכול "לזכור" רק כמות חסומה של מידע. השאלה בכל שפה היא: האם צריך להשוות שתי כמויות לא חסומות?
פתרון:
בדיקה: בדיקת עקביות – L₃ ⊆ L₂ , ו־L₃ סופית; תת־שפה סופית של שפה לא רגולרית יכולה להיות רגולרית, ואין סתירה.
טעות נפוצה: לחשוב ש־L₁ אינה רגולרית "כי יש aⁿ…cⁿ". המפתח הוא אם n חסום.
סעיף א(2)
L₄ = ∅ – רגולרית; L₅ – לא רגולרית; L₆ = Σ* (כל המילים) – רגולרית.
מה נדרש: לקבוע רגולריות של L₄, L₅, L₆ (R(L) = השפה ההפוכה, L̅ = המשלים).
פתרון:
בדיקה: לכל אחת מהשפות זוהתה צורה פשוטה (∅, Σ*) או הוכחה דרך חיתוך עם שפה רגולרית.
טעות נפוצה: לומר ש־L₅ רגולרית "כי L₁ רגולרית", או ש־L₄ אינה רגולרית "כי L₂ אינה רגולרית" – איחוד/חיתוך של שפה לא רגולרית יכולים לצאת רגולריים או לא; צריך לבדוק את השפה שמתקבלת.
סעיף ב
12 מצבים: S (התחלה), A0–A2, B0–B2, C0–C2, D, E; מקבלים: C0, C1, C2, D, E (טבלת המעברים בפתרון).
מה נדרש: אוטומט סופי דטרמיניסטי (לא חייב להיות מלא – מעבר שחסר פירושו דחייה) ל־L.
רעיון: המילה מתפרקת באופן יחיד: רצף a ראשון (n), רצף b (m), רצף a שני (k), ושארית w שאין בה a. צריך לזכור רק את (n + k) mod 3 – שלוש אפשרויות – ואת השלב שבו אנחנו נמצאים.
כשהשארית 0 אין מעבר ב־b או ב־c מ־C0 (w חייבת להיות ריקה).
פתרון: מצב התחלה: S. מצבים מקבלים: C0, C1, C2, D, E.
| מצב | a | b | c |
|---|---|---|---|
| → S | A1 | – | – |
| A0 | A1 | B0 | – |
| A1 | A2 | B1 | – |
| A2 | A0 | B2 | – |
| B0 | C1 | B0 | – |
| B1 | C2 | B1 | – |
| B2 | C0 | B2 | – |
| (C0) מקבל | C1 | – | – |
| (C1) מקבל | C2 | – | D |
| (C2) מקבל | C0 | E | – |
| (D) מקבל | – | – | D |
| (E) מקבל | – | E | – |
("–" = אין מעבר, המילה נדחית.)
שימו לב: מ־Bᵣ, ה־a הראשון של הרצף השני כבר מוסיף 1 לסכום, ולכן Bᵣ עובר ב־a ל־C₍ᵣ₊₁₎ mod 3.
בדיקה: המילה מהדוגמה abbaaaccc: S→A1→B1→B1→C2→C0→C1→D→D→D – מתקבלת. aba (n+k=2, w ריקה) – מסתיימת ב־C2, מתקבלת. abaac (n+k=3, w=c) – מ־C0 אין מעבר ב־c, נדחית. aabab (n+k=3, w=b) – נדחית.
שאלה 8 · אוטומט מחסנית דטרמיניסטי – השלמת מעברים (25 נקודות)
נתונה השפה L מעל הא"ב {a, b, c} :
L = {aⁿ bᵐ cᵏ |
}
דוגמה למילה בשפה L בעבור n זוגי: aaaa bb ccc (n=4 , m=2 , k=3) .
הסבר: n%2 = 0 , ובהתאם לכך גם m%2 = 0 , ומתקיים 4 = (2 / 2) + 3 וגם n, m, k > 0 .
דוגמה למילה בשפה L בעבור n אי־זוגי: aaa bbb cccc (n=3 , m=3 , k=4) .
הסבר: n%2 = 1 , ובהתאם לכך מתקיים 3 ≤ 3 + 4 − 2 .
לפניכם חמש מילים. בעבור כל אחת מהן, ציינו אם המילה שייכת לשפה L . נמקו את תשובתכם.
abcc, acccc, aabbc, aabbbb, aaabbc .
כתבו את המילה הקצרה ביותר בשפה L בעבור n זוגי, ואת אחת מן המילים הקצרות ביותר בעבור n אי־זוגי (יש יותר מאפשרות אחת).
לפניכם אוטומט מחסנית דטרמיניסטי המקבל את השפה L . באוטומט קיימים כל המצבים, המעברים וסימני הקלט הנדרשים. אולם מלבד המעברים בין q₀ ל־ q₁ , חסרות במעברים האות שבראש המחסנית והפעולה על המחסנית (מעברים אלה ממוספרים מ־ 1 עד 21). נוסף על כך, המצבים המקבלים באוטומט לא סומנו.
בעבור כל מעבר ממוספר, ציינו את מספרו והשלימו את הסימון החסר: האות שבראש המחסנית והפעולה שעל המחסנית (דחוף/push או שלוף/pop או ללא שינוי). נוסף על כך, כתבו מה הם המצבים המקבלים באוטומט (אין צורך להעתיק את האוטומט למחברתכם).
◂ פתרון מלא לשאלה 8
סעיף א
abcc – שייכת; acccc – שייכת; aabbc – שייכת; aabbbb – לא שייכת; aaabbc – לא שייכת.
מה נדרש: לבדוק חמש מילים מול הגדרת L.
רעיון: מחשבים n, m, k, בודקים את זוגיות n ומפעילים את התנאי המתאים.
פתרון:
| מילה | n | m | k | n זוגי? | בדיקה | שייכת? |
|---|---|---|---|---|---|---|
| abcc | 1 | 1 | 2 | לא | 1 ≤ 1 + 2 − 2 = 1 ✓ | כן |
| acccc | 1 | 0 | 4 | לא | 1 ≤ 0 + 4 − 2 = 2 ✓ | כן |
| aabbc | 2 | 2 | 1 | כן | m זוגי, 2 = 2/2 + 1 ✓, n,m,k > 0 ✓ | כן |
| aabbbb | 2 | 4 | 0 | כן | k = 0 – לא מתקיים k > 0 | לא |
| aaabbc | 3 | 2 | 1 | לא | 3 ≤ 2 + 1 − 2 = 1 ✗ | לא |
הערה ל־acccc: התנאי n,m,k > 0 מופיע רק בשורה של n זוגי; בשורה של n אי־זוגי התנאי היחיד הוא n ≤ m + k − 2, ולכן m = 0 מותר (וגם האוטומט שבסעיף ג מאפשר זאת – המעבר q₁ → q₅ ב־c).
בדיקה: לפי הגדרת השפה: abcc ✓, acccc ✓, aabbc ✓, aabbbb ✗, aaabbc ✗ – וכך גם האוטומט מסעיף ג.
סעיף ב
n זוגי: aabbc . n אי־זוגי: למשל abbc (גם abbb , abcc , accc).
מה נדרש: המילים הקצרות ביותר בכל אחד מהמקרים.
פתרון:
בדיקה: בין המילים עד אורך 7: הקצרה ביותר עם n זוגי – aabbc בלבד; עם n אי־זוגי אין מילה באורך < 4, ובאורך 4 בדיוק: abbb, abbc, abcc, accc.
סעיף ג
(1) b,A/ללא שינוי (2) b,A/שלוף (3) b,A/ללא שינוי (4) c,A/שלוף (5) c,A/שלוף (6) c,S/שלוף (7) c,S/שלוף (8)–(12) ללא שינוי בראש A וגם בראש S (13) b,A/שלוף (14) c,A/שלוף (15) c,A/שלוף (16) b,S/ללא שינוי (17)–(21) ראש S/ללא שינוי. מצבים מקבלים: q₉ , q₁₀ , q₁₁ .
מה נדרש: להשלים לכל מעבר ממוספר את ראש המחסנית והפעולה, ולציין את המצבים המקבלים.
רעיון: המעברים בין q₀ ל־q₁ כבר נתונים: ה־a הראשון דוחף S, וכל a נוסף דוחף A. אחרי n אותיות a המחסנית היא S A…A (ראש המחסנית מימין) – בדיוק n סימנים, והאוטומט ב־q₀ אם n זוגי וב־q₁ אם n אי־זוגי. (כש־n = 1 ראש המחסנית הוא S; כש־n ≥ 3 הוא A.)
ענף n זוגי (q₀ → q₂, q₃, q₆, q₉): צריך n = m/2 + k , כלומר: כל זוג b שולף סימן אחד, וכל c שולף סימן אחד, והסימן האחרון (S) נשלף בדיוק ב־c האחרון.
ענף n אי־זוגי (q₁ → q₄, q₅, q₇, q₈, q₁₀, q₁₁): צריך m + k ≥ n + 2. במחסנית n סימנים: n − 1 פעמים A ו־S בתחתית.
פתרון: (ראש המחסנית / פעולה)
| מעבר | מ־ → אל | אות | ראש המחסנית / פעולה |
|---|---|---|---|
| (1) | q₀ → q₂ | b | A / ללא שינוי |
| (2) | q₂ → q₃ | b | A / שלוף |
| (3) | q₃ → q₂ | b | A / ללא שינוי |
| (4) | q₃ → q₆ | c | A / שלוף |
| (5) | q₆ → q₆ | c | A / שלוף |
| (6) | q₃ → q₉ | c | S / שלוף |
| (7) | q₆ → q₉ | c | S / שלוף |
| (8) | q₁ → q₄ | b | A / ללא שינוי ; S / ללא שינוי |
| (9) | q₁ → q₅ | c | A / ללא שינוי ; S / ללא שינוי |
| (10) | q₄ → q₇ | b | A / ללא שינוי ; S / ללא שינוי |
| (11) | q₄ → q₈ | c | A / ללא שינוי ; S / ללא שינוי |
| (12) | q₅ → q₈ | c | A / ללא שינוי ; S / ללא שינוי |
| (13) | q₇ → q₇ | b | A / שלוף |
| (14) | q₇ → q₈ | c | A / שלוף |
| (15) | q₈ → q₈ | c | A / שלוף |
| (16) | q₇ → q₁₀ | b | S / ללא שינוי |
| (17) | q₇ → q₁₁ | c | S / ללא שינוי |
| (18) | q₈ → q₁₁ | c | S / ללא שינוי |
| (19) | q₁₀ → q₁₀ | b | S / ללא שינוי |
| (20) | q₁₀ → q₁₁ | c | S / ללא שינוי |
| (21) | q₁₁ → q₁₁ | c | S / ללא שינוי |
מצבים מקבלים: q₉ , q₁₀ , q₁₁ .
האוטומט דטרמיניסטי: מכל מצב, לכל זוג (אות קלט, ראש מחסנית) יש לכל היותר מעבר אחד.
בדיקה:
טעות נפוצה: לשכוח ש־n = 1 משאיר את S בראש המחסנית ב־q₁ – אם רושמים במעברים (8)–(12) רק "A", המילים abbc, accc וכו' נדחות.
שאלה 9 · מכונת טיורינג – מעקב ותיאור (25 נקודות)
לפניכם מכונת טיורינג המקבלת מילים מעל הא"ב {a, b} (מקרא: R – ימין, L – שמאל).
בסעיף א שלפניכם תתבקשו לבצע מעקב אחר פעולת המכונה. במעקב יש להראות בכל שלב את הסרט, מעל איזה תא ממוקם הראש הקורא, ובאיזה מצב q₀–q₅ נמצאים.
להלן דוגמה לאופן שבו יש לבצע מעקב בעבור המכונה הנתונה והמילה bb.
עקבו אחרי פעולת המכונה בעבור המילה a . יש להציג את המעקב.
עקבו אחרי פעולת המכונה בעבור המילה aba . יש להציג את המעקב.
הציגו את הסרט המתקבל בגמר הפעולה בעבור המילה baba . אין צורך להציג את המעקב.
האם קיימת מילה המכילה גם את a וגם את b שאינה משתנה לאחר הרצת המכונה עליה? אם כן – כתבו דוגמה למילה כזו. אם לא – נמקו את תשובתכם.
כתבו בקצרה מה המכונה עושה.
◂ פתרון מלא לשאלה 9
סעיף א(1)
3 שלבים (0–2): q₀ על a → q₁ (a נמחק) → q₅ ; המילה מתקבלת והסרט ריק.
מה נדרש: מעקב מלא על המילה a.
רעיון: מריצים את המעברים אחד אחד. מעברי המכונה: q₀: b/b,R → q₀ ; a/Δ,R → q₁ ; Δ/Δ,L → q₅ . q₁: Δ/Δ,R → q₅ ; b/Δ,L → q₃ ; a/Δ,L → q₂ . q₂: Δ/a,R → q₄ . q₃: Δ/b,R → q₄ . q₄: Δ/Δ,R → q₁ . q₅ – מצב מקבל.
בטבלה: תא 0 הוא הסמן ⊣, הראש הקורא מסומן ב־[ ].
פתרון:
| שלב | מצב | תא 0 | תא 1 | תא 2 | תא 3 | |
|---|---|---|---|---|---|---|
| 0 | q₀ | ⊣ | [a] | Δ | Δ | ... |
| 1 | q₁ | ⊣ | Δ | [Δ] | Δ | ... |
| 2 | q₅ | ⊣ | Δ | Δ | [Δ] | ... |
שלב 0→1: ב־q₀ קוראים a ⇐ כותבים Δ, זזים ימינה, q₁. שלב 1→2: ב־q₁ קוראים Δ ⇐ כותבים Δ, זזים ימינה, q₅ – המכונה עוצרת במצב מקבל. המילה מתקבלת, והסרט ריק.
בדיקה: המעקב עובר בדיוק בשלושת השלבים האלה.
סעיף א(2)
9 שלבים (0–8), מסתיים ב־q₅ ; המילה מתקבלת והסרט בסוף: ⊣ b a Δ …
מה נדרש: מעקב מלא על aba.
פתרון:
| שלב | מצב | תא 0 | תא 1 | תא 2 | תא 3 | תא 4 | |
|---|---|---|---|---|---|---|---|
| 0 | q₀ | ⊣ | [a] | b | a | Δ | ... |
| 1 | q₁ | ⊣ | Δ | [b] | a | Δ | ... |
| 2 | q₃ | ⊣ | [Δ] | Δ | a | Δ | ... |
| 3 | q₄ | ⊣ | b | [Δ] | a | Δ | ... |
| 4 | q₁ | ⊣ | b | Δ | [a] | Δ | ... |
| 5 | q₂ | ⊣ | b | [Δ] | Δ | Δ | ... |
| 6 | q₄ | ⊣ | b | a | [Δ] | Δ | ... |
| 7 | q₁ | ⊣ | b | a | Δ | [Δ] | ... |
| 8 | q₅ | ⊣ | b | a | Δ | Δ | [Δ] (תא 5) |
הסבר: בשלב 0 ה־a הראשון נמחק. ב־q₁ נקרא b: הוא נמחק (שלב 1→2), הראש חוזר שמאלה לתא הריק ו־q₃ כותב שם b (2→3) – כלומר ה־b "זז" תא אחד שמאלה. q₄ ממשיך ימינה (3→4). אותו דבר עם ה־a (4→5→6): הוא נמחק ונכתב תא אחד שמאלה. ב־q₁ נקרא Δ (סוף המילה) ⇐ q₅. המילה מתקבלת, ועל הסרט נשאר ba.
בדיקה: המעקב עובר באותם 9 שלבים, ובסוף: מתקבלת, תוכן הסרט ba.
סעיף א(3)
⊣ b b a Δ Δ … (על הסרט: bba)
מה נדרש: תוכן הסרט בסוף הריצה על baba.
רעיון: כפי שראינו בסעיף (2), המכונה מדלגת על ה־b עד ה־a הראשון, מוחקת אותו, ומזיזה כל אות שאחריו תא אחד שמאלה.
פתרון: ב־baba ה־a הראשון בתא 2. הוא נמחק, ו־"ba" שאחריו זזים שמאלה. הסרט בסוף:
| תא 0 | תא 1 | תא 2 | תא 3 | תא 4 | |
|---|---|---|---|---|---|
| ⊣ | b | b | a | Δ | ... |
כלומר על הסרט bba, והמכונה עוצרת ב־q₅ (מקבלת).
בדיקה: עבור baba: מתקבלת, תוכן הסרט bba.
סעיף ב(1)
לא. בכל מילה שיש בה a המכונה מוחקת את ה־a הראשון, ולכן המילה מתקצרת באות אחת.
מה נדרש: לקבוע אם יש מילה עם a וגם b שהמכונה לא משנה.
רעיון: לבדוק מה המכונה עושה כשיש במילה a.
פתרון: לא קיימת. המכונה עוברת ב־q₀ על כל ה־b שבהתחלה. במילה שיש בה a, היא מגיעה ל־a הראשון ומוחקת אותו (a/Δ,R). אחר כך כל אות שאחריו מועתקת תא אחד שמאלה (q₁→q₂/q₃→q₄→q₁), והתא שלה מתרוקן. בסוף נשארת על הסרט המילה בלי ה־a הראשון – אורכה קטן באחד מהמילה המקורית, ולכן היא שונה ממנה. (המכונה לא משאירה מילה זהה רק כשאין בה a כלל, כמו bb.)
בדיקה: אף מילה שמכילה a ו־b לא נשארת ללא שינוי.
סעיף ב(2)
המכונה מוחקת מהמילה את המופע הראשון של a (ומצמצמת את הרווח); אם אין a – המילה לא משתנה. היא מקבלת כל מילה.
מה נדרש: תיאור קצר של פעולת המכונה.
פתרון: המכונה מוחקת את ה־a הראשון במילה: היא מדלגת על ה־b שבהתחלה, מוחקת את ה־a הראשון, ומזיזה את כל האותיות שאחריו תא אחד שמאלה (כך שלא נשאר "חור"). אם אין במילה a – המילה נשארת כמו שהיא. המכונה עוצרת תמיד ב־q₅, כלומר מקבלת כל מילה מעל {a, b}.
בדיקה: a → ריקה, aba → ba, baba → bba, bb → bb. פלט המכונה הוא בדיוק "מחיקת ה־a הראשון" לכל מילה.
פרק שני – תכנות מונחה עצמים
שימו לב: השאלות 10–12 הן גם בעבור הפותרים בשפת Java וגם בעבור הפותרים בשפת C# .
לכל שאלה נוסח בשפת Java ונוסח בשפת C# .
יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).
שאלה 10 · ירושה והכלה – אקדמיה למוזיקה (Orchestra)
לשאלה זו שני נוסחים: בשפת Java בעמוד 18 ובשפת C# בעמוד 19.
לפותרים בשפת Java
באקדמיה למוזיקה "שיר חדש" פותחה מערכת ממוחשבת ובה המחלקות האלה:
Instrum – כלי נגינה, Bow – כלי קשת , Wind – כלי נשיפה, Perc – כלי הקשה, Musician – נגן בתזמורת,
Orchestra – תזמורת.
להלן פירוט תכונות המחלקות:
למחלקה Instrum (כלי נגינה) שתי תכונות: name – שם הכלי (מטיפוס מחרוזת), material – החומר שממנו עשוי הכלי (מטיפוס מחרוזת).
למחלקה Bow (כלי קשת) שלוש תכונות: name – שם הכלי (מטיפוס מחרוזת), material – החומר שממנו עשוי הכלי (מטיפוס מחרוזת), bowLength – אורך הקשת (מטיפוס שלם).
למחלקה Wind (כלי נשיפה) שלוש תכונות: name – שם הכלי (מטיפוס מחרוזת), material – החומר שממנו עשוי הכלי (מטיפוס מחרוזת), numberOfValves – מספר השסתומים בכלי (מטיפוס שלם).
למחלקה Perc (כלי הקשה) שלוש תכונות: name – שם הכלי (מטיפוס מחרוזת), material – החומר שממנו עשוי הכלי (מטיפוס מחרוזת), hasSticks – האם יש שימוש במקלות הקשה (מטיפוס בוליאני. אם יש שימוש במקלות – true , ואם לא – false).
למחלקה Musician (נגן בתזמורת) שתי תכונות: name – שם הנגן (מטיפוס מחרוזת), instrum – כלי הנגינה שלו (מטיפוס Instrum). כל נגן מנגן על כלי אחד בלבד.
למחלקה Orchestra (תזמורת) שתי תכונות: arrM – מערך של נגנים (מטיפוס Musician), count – כמות הנגנים השמורים במערך (מטיפוס שלם).
הנגנים מופיעים ברצף מתחילת המערך ללא null ביניהם, אך ייתכן שהמערך אינו מלא עד הסוף.
סרטטו תרשים הייררכייה בין כל המחלקות.
כתבו את כותרות המחלקות ואת התכונות שלהן. הניחו שבכל מחלקה הוגדרו פעולות get ו־ set ופעולות בונות.
כתבו במחלקה Orchestra פעולה ששמה withSticks , המחזירה את מספר הנגנים בתזמורת המנגנים בכלי הקשה שיש בהם שימוש במקלות.
מערך arrM "מסודר" הוא מערך שבו מופיעים קודם נגני כלי הקשת, אחר כך נגני כלי הנשיפה, ואחר כך נגני כלי ההקשה.
כתבו במחלקה Orchestra פעולה ששמה insert , המקבלת נגן – musician שאינו מופיע במערך arrM .
הניחו שלפני תחילת הפעולה המערך "מסודר", ושיש בתזמורת לפחות נגן אחד בכל סוג של כלי.
אם אין מקום לנגן נוסף במערך, הפעולה תחזיר false . אחרת, הפעולה תכניס את הנגן למערך במקום המתאים באופן שבו המערך ימשיך להיות "מסודר" (והנגנים יופיעו ברצף בתחילת המערך), ותחזיר true .
הערה: אפשר לשנות את סדר הנגנים, ובלבד שהמערך יהיה "מסודר" בסוף הפעולה.
◂ פתרון מלא לשאלה 10
סעיף א(1)
Bow, Wind, Perc יורשות מ־Instrum; Musician מכילה Instrum; Orchestra מכילה (מערך של) Musician.
מה נדרש – תרשים הייררכייה של שש המחלקות: מי יורשת ממי ומי מכילה את מי.
רעיון – שואלים על כל זוג מחלקות שתי שאלות:
פתרון
בדיקה – כל שש המחלקות מופיעות בתרשים. התכונות המשותפות name ו־material יוגדרו רק במחלקת הבסיס Instrum, וכל מחלקה יורשת מוסיפה רק את התכונה המיוחדת לה.
טעות נפוצה: לסמן ירושה בין Musician ל־Instrum. נגן אינו "סוג של" כלי נגינה; יש לו כלי נגינה, ולכן זו הכלה.
סעיף א(2)
Instrum(name, material); Bow extends Instrum(bowLength); Wind extends Instrum(numberOfValves); Perc extends Instrum(hasSticks); Musician(name, instrum: Instrum); Orchestra(arrM: Musician[], count)
מה נדרש – כותרות שש המחלקות והתכונות שלהן (בלי פעולות; פעולות get/set ופעולות בונות מניחים שקיימות).
רעיון – בכותרת של מחלקה יורשת מציינים את מחלקת הבסיס (extends ב־Java, : ב־C#). התכונות name ו־material מוגדרות רק ב־Instrum, והמחלקות היורשות מקבלות אותן בירושה. כל תכונה מוגדרת private (כימוס). לגישה אליהן משתמשים בפעולות get/set.
פתרון (הקוד המלא – בלשונית Java/C#)
| מחלקה | כותרת (Java) | תכונות |
|---|---|---|
| Instrum | public class Instrum | String name, String material |
| Bow | public class Bow extends Instrum | int bowLength |
| Wind | public class Wind extends Instrum | int numberOfValves |
| Perc | public class Perc extends Instrum | boolean hasSticks |
| Musician | public class Musician | String name, Instrum instrum |
| Orchestra | public class Orchestra | Musician[] arrM, int count |
ב־C#: public class Bow : Instrum וכן הלאה, והטיפוסים string ו־bool.
בדיקה – הכותרות והתכונות (Java ו־C#) תקינות.
טעות נפוצה: להגדיר שוב את name ו־material במחלקות Bow, Wind, Perc. הן כבר מתקבלות בירושה מ־Instrum.
public class Instrum {
private String name; // שם הכלי
private String material; // החומר שממנו עשוי הכלי
}
public class Bow extends Instrum {
private int bowLength; // אורך הקשת
}
public class Wind extends Instrum {
private int numberOfValves; // מספר השסתומים
}
public class Perc extends Instrum {
private boolean hasSticks; // האם יש שימוש במקלות
}
public class Musician {
private String name; // שם הנגן
private Instrum instrum; // כלי הנגינה של הנגן
}
public class Orchestra {
private Musician[] arrM; // מערך הנגנים
private int count; // כמות הנגנים השמורים במערך
}סעיף ב
סופרים נגנים i<count שהכלי שלהם instanceof Perc ו־((Perc)ins).getHasSticks() הוא true.
מה נדרש – פעולה במחלקה Orchestra שמחזירה כמה נגנים מנגנים בכלי הקשה (Perc) שיש בו שימוש במקלות.
רעיון – עוברים על הנגנים שבמערך, רק עד count (אחרי count יש null). לכל נגן לוקחים את הכלי שלו ובודקים:
instanceof ב־Java, is ב־C#.getHasSticks() / GetHasSticks()).סופרים את הנגנים שעומדים בשני התנאים.
פתרון
public int withSticks() {
int sum = 0;
for (int i = 0; i < this.count; i++) {
Instrum ins = this.arrM[i].getInstrum();
if (ins instanceof Perc && ((Perc) ins).getHasSticks())
sum++;
}
return sum;
}בדיקה – תזמורת עם 6 נגנים: b1, b2 (קשת), w1 (נשיפה), p1 (תוף, עם מקלות), p2 (משולש, עם מקלות), p3 (בונגו, בלי מקלות). הפעולה החזירה 2 (ב־Java וב־C#). אחרי שנוסף נגן הקשה עם מקלות היא החזירה 3.
טעות נפוצה: לקרוא ל־getHasSticks() על הפניה מטיפוס Instrum בלי המרה ל־Perc גורם לשגיאת הידור, כי ב־Instrum אין פעולה כזו. המרה בלי בדיקת instanceof מראש גורמת לשגיאת ריצה כשהכלי הוא Bow או Wind. גם לולאה עד arrM.length במקום עד count מגיעה ל־null ונכשלת.
public int withSticks() {
int sum = 0;
for (int i = 0; i < this.count; i++) {
Instrum ins = this.arrM[i].getInstrum();
if (ins instanceof Perc && ((Perc) ins).getHasSticks())
sum++;
}
return sum;
}סעיף ג
אם המערך מלא – false. אחרת pos = count להקשה, אחרי נגן הקשת האחרון לקשת, לפני נגן ההקשה הראשון לנשיפה; הזזה ימינה מ־pos, הצבה, count++ ו־true.
מה נדרש – להכניס נגן חדש למערך "מסודר" (קשת ← נשיפה ← הקשה) כך שהמערך יישאר "מסודר" ורציף. אם המערך מלא, מחזירים false.
רעיון
count == arrM.length, אין מקום ומחזירים false.pos = count.(ההנחה שיש לפחות נגן אחד מכל סוג מבטיחה שהחיפוש תמיד מוצא מקום. התנאי pos < count נוסף ליתר ביטחון.)
פתרון
public boolean insert(Musician musician) {
if (this.count == this.arrM.length) // אין מקום במערך
return false;
Instrum ins = musician.getInstrum();
int pos = this.count; // נגן כלי הקשה – בסוף הרצף
if (ins instanceof Bow) { // נגן כלי קשת – אחרי כל נגני הקשת
pos = 0;
while (pos < this.count && this.arrM[pos].getInstrum() instanceof Bow)
pos++;
}
else if (ins instanceof Wind) { // נגן כלי נשיפה – לפני נגן ההקשה הראשון
pos = 0;
while (pos < this.count && !(this.arrM[pos].getInstrum() instanceof Perc))
pos++;
}
for (int i = this.count; i > pos; i--) // הזזת הנגנים מ-pos ימינה במקום אחד
this.arrM[i] = this.arrM[i - 1];
this.arrM[pos] = musician;
this.count++;
return true;
}בדיקה – מערך בגודל 9: b1 b2 w1 p1 p2 p3 (count=6). הפלט ב־Java וב־C#:
| פעולה | מוחזר | המערך אחרי הפעולה |
|---|---|---|
| הכנסת w2 (נשיפה) | true | b1 b2 w1 w2 p1 p2 p3 (count=7) |
| הכנסת b3 (קשת) | true | b1 b2 b3 w1 w2 p1 p2 p3 (count=8) |
| הכנסת p4 (הקשה) | true | b1 b2 b3 w1 w2 p1 p2 p3 p4 (count=9) |
| הכנסת b4 (קשת) | false | המערך מלא – לא השתנה |
הערה: אפשר גם בלי הזזה של כל הנגנים, כי מותר לשנות את הסדר בתוך כל סוג. למשל, כשמכניסים נגן נשיפה, מעבירים את נגן ההקשה הראשון לסוף הרצף ושמים את הנגן החדש במקומו.
טעות נפוצה: להזיז את הנגנים משמאל לימין (for i = pos ...). כך כל התאים נדרסים באותו ערך.
public boolean insert(Musician musician) {
if (this.count == this.arrM.length) // אין מקום במערך
return false;
Instrum ins = musician.getInstrum();
int pos = this.count; // נגן כלי הקשה – בסוף הרצף
if (ins instanceof Bow) { // נגן כלי קשת – אחרי כל נגני הקשת
pos = 0;
while (pos < this.count && this.arrM[pos].getInstrum() instanceof Bow)
pos++;
}
else if (ins instanceof Wind) { // נגן כלי נשיפה – לפני נגן ההקשה הראשון
pos = 0;
while (pos < this.count && !(this.arrM[pos].getInstrum() instanceof Perc))
pos++;
}
for (int i = this.count; i > pos; i--) // הזזת הנגנים מ-pos ימינה במקום אחד
this.arrM[i] = this.arrM[i - 1];
this.arrM[pos] = musician;
this.count++;
return true;
}שאלה 11 · פעולות בונות, תכונת מחלקה (static), תרשימי הייררכייה והשלמת מחלקת־על
לשאלה זו שני נוסחים: בשפת Java בעמודים 20–21 ובשפת C# בעמודים 22–23.
לפותרים בשפת Java
לפניכם שלושה סעיפים א–ג שאין קשר ביניהם. ענו על שלושת הסעיפים.
לפניכם המחלקה Father ללא מימוש הפעולות הבונות, והמחלקה Son ללא מימוש הפעולות הבונות ופעולת toString .
public class Father {
private static int st = 0;
protected int num;
public Father () {…}
public Father (int num) {…}
public String toString() {return "st=" + st + ", num=" + num;}
}
------------------------------------------------------------------
public class Son extends Father {
private char ch;
public Son (int num, char ch){…}
public Son (int num) {…}
public String toString() {... }
}לפניכם קטע קוד והפלט שהתקבל בעקבות הרצת קטע הקוד:
הקוד
Father x1 = new Father ();
System.out.println (x1); //1
Father x2 = new Father (3);
System.out.println (x2); //2
Father x3 = new Son (5, 'A');
System.out.println (x3); //3
Father x4 = new Son (7);
System.out.println (x4); //4הפלט
st=1, num=9 //1
st=1, num=3 //2
st=2, num=5, ch=A //3
st=2, num=7, ch=Z //4ממשו את הפעולות הבונות במחלקה Father ובמחלקה Son , ואת הפעולה toString במחלקה Son , בהתאם לעקרונות תכנות מונחה עצמים, כך שיתקבל הפלט הנתון.
אין להוסיף פעולות נוספות למחלקות. תשובה הכוללת פעולות נוספות במחלקות, לא תזוכה בנקודות.
נתונות המחלקות A, B, C, D והפעולה main במחלקה Tester , שרצה באופן תקין.
public class Tester {
public static void main(String[] args) {
C c1 = new B();
A a1 = new C();
A a2 = new B();
C c2 = new D();
}
}לפניכם שישה תרשימי הייררכייה 1–6 (החץ מסמן יחס ירושה). בנוגע לכל אחד מהם, ציינו אם ייתכן או לא ייתכן שהוא מתאר את יחס ההייררכייה בין המחלקות A, B, C, D . אם ציינתם שלא ייתכן, נמקו מדוע.
בסוף הפעולה main נוספו שורות הקוד שלהלן, שרצות באופן תקין:
A a3 = new B();
D d1 = (D)a3;בעקבות זאת, האם תשתנה תשובתכם בתת־סעיף ב(1)? נמקו את תשובתכם.
נתונה המחלקה BBB , היורשת ממחלקה AAA :
public class BBB extends AAA {
private char ch;
public BBB (int num, char ch) {
super (num);
this.ch = ch;
}
public BBB (char ch) {this.ch = ch; }
public int gg (int val) {return super.gg(val) + num; }
public int mm () {return AAA.c + 2; }
public boolean nn () {return this.mm (10); }
}כתבו במחלקה AAA את תכונות המחלקה (כולל הרשאות הגישה) ואת הכותרות של הפעולות הנדרשות כדי שהמחלקה BBB תהיה תקינה, בהתאם לעקרונות תכנות מונחה עצמים.
אין צורך לממש את הפעולות שאת הכותרות שלהן הוספתם במחלקה AAA . אין לשנות את הקוד של המחלקה BBB.
◂ פתרון מלא לשאלה 11
סעיף א
Father(): st++, num=9 · Father(int num): num=num · Son(int num, char ch): super(); num=num; ch=ch · Son(int num): super(num); ch='Z' · toString: super.toString() + ", ch=" + ch
מה נדרש – לממש את הפעולות הבונות של Father ושל Son ואת toString של Son כך שיתקבל הפלט הנתון.
רעיון – מסיקים מהפלט, שורה אחר שורה:
new Father() הדפיס st=1, num=9 ⇐ הבונה בלי פרמטרים מגדילה את st ב־1 ומציבה num=9.new Father(3) הדפיס st=1 (לא השתנה), num=3 ⇐ הבונה עם פרמטר רק מציבה את num ולא נוגעת ב־st.new Son(5,'A') הדפיס st=2 ⇐ st גדל, ורק Father() מגדילה אותו. ל־Son אין גישה ל־st כי היא private ב־Father, ולכן הבונה של Son חייבת לזמן את Father() (super() / : base()). אחר כך היא מציבה num=5 (מותר, כי num היא protected) ו־ch='A'.new Son(7) הדפיס st=2 (לא השתנה), ch=Z ⇐ הבונה מזמנת את Father(int) (super(num) / : base(num)), שלא מגדילה את st, ומציבה ch='Z'.super.toString() / base.ToString()) ומוסיפה ", ch=" + ch. כך לא משכפלים קוד, וגם אין צורך בגישה ל־st, שהיא private.פתרון
public class Father {
private static int st = 0;
protected int num;
public Father() {
st++;
this.num = 9;
}
public Father(int num) {
this.num = num;
}
public String toString() { return "st=" + st + ", num=" + num; }
}
public class Son extends Father {
private char ch;
public Son(int num, char ch) {
super(); // הפעולה הבונה היחידה שמגדילה את st
this.num = num; // num מוגדרת protected ולכן נגישה במחלקה היורשת
this.ch = ch;
}
public Son(int num) {
super(num); // לא מגדילה את st
this.ch = 'Z';
}
public String toString() {
return super.toString() + ", ch=" + this.ch;
}
}בדיקה – קטע הקוד מהשאלה (Java ו־C#) מדפיס בדיוק:
st=1, num=9
st=1, num=3
st=2, num=5, ch=A
st=2, num=7, ch=Zst היא תכונת מחלקה (static), אחת לכל העצמים. כל שורה מודפסת מיד אחרי יצירת העצם, ולכן מוצג הערך של st באותו רגע.
טעות נפוצה: לממש את Son(int num) כ־this(num, 'Z'). כך מופעלת Son(int, char), שמפעילה את Father(), ו־st גדל ל־3. מתקבל st=3, num=7, ch=Z במקום st=2.
public class Father {
private static int st = 0;
protected int num;
public Father() {
st++;
this.num = 9;
}
public Father(int num) {
this.num = num;
}
public String toString() { return "st=" + st + ", num=" + num; }
}
public class Son extends Father {
private char ch;
public Son(int num, char ch) {
super(); // הפעולה הבונה היחידה שמגדילה את st
this.num = num; // num מוגדרת protected ולכן נגישה במחלקה היורשת
this.ch = ch;
}
public Son(int num) {
super(num); // לא מגדילה את st
this.ch = 'Z';
}
public String toString() {
return super.toString() + ", ch=" + this.ch;
}
}סעיף ב(1)
1 – לא ייתכן; 2 – ייתכן; 3 – לא ייתכן; 4 – ייתכן; 5 – לא ייתכן; 6 – ייתכן.
מה נדרש – לקבוע לכל אחד מששת התרשימים אם הוא מתאים לקוד שרץ באופן תקין.
רעיון – השמה X ref = new Y(); עוברת הידור רק אם Y היא X או תת־מחלקה של X (ישירה או עקיפה). מכל שורה ב־main מקבלים דרישה:
C c1 = new B(); ⇐ B יורשת (ישירות או בעקיפין) מ־C.A a1 = new C(); ⇐ C יורשת מ־A.A a2 = new B(); ⇐ B יורשת מ־A (נובע משתי הקודמות).C c2 = new D(); ⇐ D יורשת מ־C.פתרון
| תרשים | מבנה (בן → אב) | ייתכן? | נימוק |
|---|---|---|---|
| 1 | B→C, D→B, A→B | לא ייתכן | C היא מחלקת־על של A, ולא תת־מחלקה שלה ⇐ A a1 = new C(); שגיאת הידור. |
| 2 | C→A, B→C, D→C | ייתכן | B ו־D יורשות מ־C, ו־C יורשת מ־A. כל הדרישות מתקיימות. |
| 3 | B→D, C→D, A→C | לא ייתכן | B אינה יורשת מ־C (שתיהן "אחיות" תחת D) ⇐ C c1 = new B(); שגיאת הידור. גם A a1 = new C(); ו־C c2 = new D(); שגויות. |
| 4 | C→A, B→C, D→B | ייתכן | B יורשת מ־C, C מ־A, ו־D יורשת מ־C בעקיפין (דרך B). |
| 5 | A→B, C→A, D→C | לא ייתכן | B היא השורש ואינה יורשת מ־C ⇐ C c1 = new B(); שגיאת הידור (וגם A a2 = new B();). |
| 6 | C→A, D→C, B→D | ייתכן | B יורשת מ־C בעקיפין (דרך D), C מ־A, ו־D מ־C. |
בדיקה – בנינו את מחלקות A–D לפי כל אחד מהתרשימים והידרנו את Tester (ב־Java וב־C#). בתרשימים 1, 3, 5 הייתה שגיאת הידור, ובתרשימים 2, 4, 6 התוכנית רצה תקין.
סעיף ב(2)
כן. ההמרה (D)a3 של עצם B מצליחה רק אם B יורשת מ־D, ולכן רק תרשים 6 נשאר אפשרי (ב־2 וב־4 תהיה שגיאת ריצה).
מה נדרש – לבדוק אילו מהתרשימים שנמצאו אפשריים ב־ב(1) (2, 4, 6) נשארים אפשריים אחרי השורות החדשות.
רעיון – a3 מפנה לעצם מטיפוס B. ההמרה (D)a3 עוברת הידור בכל שלושת התרשימים, כי D היא תת־מחלקה של A. אבל בזמן ריצה היא מצליחה רק אם העצם (B) הוא באמת D, כלומר רק אם B יורשת (ישירות או בעקיפין) מ־D. אחרת נזרקת חריגה: ClassCastException ב־Java, InvalidCastException ב־C#.
פתרון – כן, התשובה משתנה: רק תרשים 6 נשאר אפשרי.
בדיקה – עם השורות הנוספות (Java ו־C#): בתרשימים 2 ו־4 מתקבלת שגיאת ריצה (ClassCastException / InvalidCastException), ובתרשים 6 התוכנית רצה תקין.
טעות נפוצה: לחשוב שאם ההמרה עוברת הידור היא תקינה. המהדר בודק רק שההמרה אפשרית לפי טיפוס ההפניה (A ⇐ D). את סוג העצם בפועל בודקים רק בזמן ריצה.
סעיף ג
protected int num; protected static int c; public AAA(); public AAA(int num); public int gg(int val) (ב־C#: public virtual int GG(int val)); public boolean mm(int x) (ב־C#: public bool MM(int x))
מה נדרש – לכתוב את התכונות ואת כותרות הפעולות של AAA שבלעדיהן BBB לא תעבור הידור.
רעיון – עוברים על BBB שורה אחר שורה ושואלים מה היא צריכה מ־AAA:
| שורה ב־BBB | מה נדרש ב־AAA |
|---|---|
super(num) / : base(num) | פעולה בונה AAA(int num) |
BBB(char ch) – אין קריאה מפורשת ל־super/base | מופעלת אוטומטית הבונה בלי פרמטרים ⇐ AAA() |
... + num בתוך gg | תכונה int num שנגישה למחלקה היורשת ⇐ protected (עם private תהיה שגיאת הידור) |
super.gg(val) + num שמוחזר כ־int | public int gg(int val). ב־C# BBB כותבת override, ולכן ב־AAA: public virtual int GG(int val) (ב־C# הרשאת הגישה בדריסה חייבת להיות זהה, ולכן protected virtual תגרום לשגיאת הידור) |
AAA.c + 2 שמוחזר כ־int | תכונת מחלקה (static) מטיפוס שלם ⇐ protected static int c |
this.mm(10) שמוחזר כ־boolean | ב־BBB יש רק mm() בלי פרמטרים, ולכן ב־AAA צריכה להיות העמסה: public boolean mm(int x) (ב־C#: public bool MM(int x)) |
פתרון (גופי הפעולות כאן ריקים או מחזירים ערך זמני, רק כדי שהקוד יעבור הידור; בבחינה מספיקות הכותרות)
public class AAA {
protected int num;
protected static int c;
public AAA() { }
public AAA(int num) { }
public int gg(int val) { return 0; }
public boolean mm(int x) { return false; }
}בדיקה – AAA יחד עם BBB ללא שינוי תקינות ב־Java וב־C#. בדקנו גם שכל רכיב נחוץ: בלי AAA(), עם private int num, עם c שאינה static או שהיא private, בלי mm(int) או בלי gg(int) (וב־C# בלי virtual) – בכל אחד מהמקרים התקבלה שגיאת הידור.
טעות נפוצה: לחשוב ש־this.mm(10) מתייחס ל־mm() של BBB. ל־mm של BBB אין פרמטרים, ולכן נדרשת ב־AAA פעולה נוספת בשם mm שמקבלת מספר ומחזירה boolean (העמסה).
public class AAA {
protected int num;
protected static int c;
public AAA() { }
public AAA(int num) { }
public int gg(int val) { return 0; }
public boolean mm(int x) { return false; }
}שאלה 12 · פולימורפיזם, העמסה ודריסה – מעקב והדפסה
לשאלה זו שני נוסחים: בשפת Java בעמודים 24–25 ובשפת C# בעמודים 26–27.
לפותרים בשפת Java
לפניכם המחלקות A, B, C :
public class A {
public int num;
public A() {
this.num = 1;
}
public A(int num) {
this.num = num;
}
public int func (int val) {
return val * 2;
}
public int func (B other) {
return this.num - other.num;
}
}public class B extends A {
public B() {
super(2);
}
public B(int val) {
super(val);
this.num = this.num + func (val);
}
public int func (A other) {
return this.num + (other.num * 10);
}
public int func (B other) {
return this.num + other.num;
}
}public class C extends B {
public C(int val) {
this.num = this.num - val;
}
public int func (B other) {
return this.num * other.num;
}
public int func (C c) {
return this.num * 4;
}
}לפניכם קטע קוד שרץ ללא שגיאות:
A a = new A();
A ab = new B();
A ac = new C(0);
B b = new B(1);
B bc = new C(1);
C c = new C(1);הציגו את העצמים שנוצרו (סוג העצם, סוג ההפניה, וערך התכונה num).
לפניכם המשך קטע הקוד (ממוספר) שרץ ללא שגיאות.
ציינו את מספר שורת ההדפסה, וכתבו מה הקוד מדפיס.
1. System.out.println (a.func (b));
2. System.out.println (a.func (c));
3. System.out.println (ab.func ((B)ab));
4. System.out.println (((B)ab).func (ab));
5. System.out.println (ab.func (10));
6. System.out.println (a.func (a.func (2)));
7. System.out.println (ac.func (c));
8. System.out.println (c.func (ac));
9. System.out.println (c.func (a));
10. System.out.println (((C)bc).func ((C)bc));◂ פתרון מלא לשאלה 12
סעיף א
a: A/A num=1 · ab: הפניה A, עצם B, num=2 · ac: הפניה A, עצם C, num=2 · b: B/B num=3 · bc: הפניה B, עצם C, num=1 · c: C/C num=1
מה נדרש – לכל אחד מששת העצמים: סוג העצם (המחלקה שאחרי new), סוג ההפניה (הטיפוס שבהצהרה) וערך num.
רעיון – עוקבים אחרי שרשרת הפעולות הבונות. אם הבונה של מחלקה יורשת לא מזמנת במפורש בונה של מחלקת הבסיס, מופעלת אוטומטית הבונה בלי פרמטרים של מחלקת הבסיס.
new A() ⇐ num = 1.new B() ⇐ super(2) / base(2) ⇐ A(2) ⇐ num = 2.new B(1) ⇐ A(1) מציבה num = 1. אחר כך num = num + func(1): הארגומנט מטיפוס int, ולכן נבחרת func(int val) של A, שמחזירה 1·2 = 2 ⇐ num = 3.new C(0) ⇐ אין קריאה מפורשת, ולכן מופעלת B() ⇐ num = 2. אחר כך num = 2 − 0 = 2.new C(1) ⇐ B() ⇐ num = 2. אחר כך num = 2 − 1 = 1.פתרון
| הפניה | סוג ההפניה | סוג העצם | num |
|---|---|---|---|
| a | A | A | 1 |
| ab | A | B | 2 |
| ac | A | C | 2 |
| b | B | B | 3 |
| bc | B | C | 1 |
| c | C | C | 1 |
בדיקה – מדפיסים לכל עצם את המחלקה שלו ואת num. התקבלו בדיוק הערכים שבטבלה.
טעות נפוצה: לחשוב ש־new C(0) מציבה num = 1 דרך A(). הבונה של C מזמנת את B(), ו־B() מזמנת את A(2), ולכן num = 2.
הערה על הקוד: בנוסח Java המודפס מופיע בשורות this.num – other.num ו־this.num – val מקף ארוך (–). זהו סימן החיסור, ובקוד שלמעלה הוא נכתב כ־-.
סעיף ב
1: -2 · 2: 0 · 3: 4 · 4: 22 · 5: 20 · 6: 8 · 7: 2 · 8: 21 · 9: 11 · 10: 4
מה נדרש – מה מודפס בכל אחת מעשר השורות.
רעיון – שני שלבים בכל קריאה:
מצב העצמים (מסעיף א): a=A(1), ab=B(2), ac=C(2), b=B(3), bc=C(1), c=C(1).
פתרון
| שורה | הפניה.פעולה(טיפוס ארגומנט) | חתימה שנבחרה | מתבצעת בפועל | חישוב | פלט |
|---|---|---|---|---|---|
| 1 | a:A . func(B) | func(B) | A.func(B) | 1 − 3 | -2 |
| 2 | a:A . func(C) | func(B) (C הוא B) | A.func(B) | 1 − 1 | 0 |
| 3 | ab:A . func(B) | func(B) | B.func(B) (דריסה) | 2 + 2 | 4 |
| 4 | (B)ab:B . func(A) | func(A) | B.func(A) | 2 + 2·10 | 22 |
| 5 | ab:A . func(int) | func(int) | A.func(int) | 10·2 | 20 |
| 6 | a.func(a.func(2)) | func(int) פעמיים | A.func(int) | 2·2=4, 4·2 | 8 |
| 7 | ac:A . func(C) | func(B) (ל־A אין func(C)) | C.func(B) (דריסה) | 2·1 | 2 |
| 8 | c:C . func(A) | func(A) (היחידה שמקבלת A) | B.func(A) (בירושה) | 1 + 2·10 | 21 |
| 9 | c:C . func(A) | func(A) | B.func(A) | 1 + 1·10 | 11 |
| 10 | (C)bc:C . func(C) | func(C) (המתאימה ביותר) | C.func(C) | 1·4 | 4 |
הפלט:
-2
0
4
22
20
8
2
21
11
4בדיקה – הפלט ב־Java וב־C# זהה (-2, 0, 4, 22, 20, 8, 2, 21, 11, 4).
הבדל בין הנוסחים: ב־C#, Func(B) מוגדרת virtual ב־A ו־override ב־B וב־C, ולכן היא נדרסת כמו ב־Java. לעומתה, Func(A) של B ו־Func(C) של C הן העמסות חדשות. בשורות 8–10 המהדר של C# בוחר קודם מבין הפעולות שהוגדרו (לא כ־override) במחלקה של טיפוס ההפניה:
Func(C).Func(C) לא מתאימה לארגומנט מטיפוס A, ולכן נבחרת Func(A) של B.התוצאות זהות ל־Java.
טעות נפוצה: בשורה 7 לחשוב שתתבצע func(C) של C, כי הארגומנט והעצם הם מטיפוס C. טיפוס ההפניה ac הוא A, ול־A יש רק func(int) ו־func(B). לכן נבחרת func(B), ובזמן ריצה מתבצעת הגרסה הדורסת של C. באופן דומה, בשורה 4 הארגומנט ab מוצהר כ־A, ולכן נבחרת func(A) ולא func(B).
טבלת התשובות
| שאלה | סעיף | תשובה |
|---|---|---|
| 1 | א(1) | בכל סבב מוציאים הזמנה ראשונה, סוכמים את כל ההזמנות של אותו id ומעבירים את השאר לתור עזר שמחליף את qOrder; מכניסים לתוצאה new Order(id, total). |
| א(2) | O(n²) – לכל לקוח מעבר על כל ההזמנות שנותרו: (n−1)+(n−2)+…+1 במקרה הגרוע. | |
| ב(1) | מאחדים עם uniteOrders, מועדפים (count ≥ 10) נכנסים מיד לתוצאה, רגילים לתור עזר שמועבר לסוף התוצאה. | |
| ב(2) | O(n²) – בגלל הקריאה ל־uniteOrders; שאר המעברים O(n). | |
| 2 | א | result = הערך הראשון; כל עוד count < len וגם pNum != null: לפי התו מוסיפים/מחסרים את pNum ומקדמים את שני המצביעים. |
| ב | לכל מיקום k: אם eval(המספר ה־k, התו ה־k, len) == val מחזירים true; pChar מתקדם רק אם אינו null; בסוף false. | |
| 3 | א(1) | 2 |
| א(2) | 0 | |
| א(3) | 5 – שרשרת של 6 צמתים שלכל אחד (חוץ מהאחרון) רק בן ימני. | |
| א(4) | −5 – שרשרת של 6 צמתים שלכל אחד (חוץ מהאחרון) רק בן שמאלי. | |
| א(5) | מספר הצמתים שיש להם בן ימני בלבד פחות מספר הצמתים שיש להם בן שמאלי בלבד. | |
| ב(1) | false (foo(5) = 0, אבל foo(1) = −1) | |
| ב(2) | כל עץ עם יותר מ־3 צמתים שבו לכל צומת 0 או 2 בנים, למשל 5 ← (1, 7), 7 ← (3, 4); goo מחזירה true. | |
| 4 | א | (1) נכונה; (2) נכונה; (3) נכונה (בגרף בלי לולאות עצמיות); (4) לא נכונה; (5) לא נכונה (כפי שהיא מודפסת – בגרף מכוון; לגרף לא מכוון קשיר היא הייתה נכונה); (6) לא נכונה; (7) לא נכונה. (מספיק לענות על חמש מהן, למשל 1, 2, 4, 6, 7.) |
| ב | G₃ (מעגל) ו־G₇ (גרף מלא K₄) הם "DFS שרשרתיים". G₁, G₂, G₄, G₅, G₆ אינם (ראו סריקות נגדיות בפתרון). | |
| 5 | א | A2: B1, B2, B3 ; A3: B1, B2 ; B2: A1, A2, A3 ; B3: A2 |
| ב | הוצאות מהתור לפי הסדר: A3, B1, B2, A1, A2, B3. ב־B3 (צד B, חופשי) האלגוריתם עוצר. parent בסוף: A1←B1, A2←B2, B1←A3, B2←A3, B3←A2. | |
| ג | B3 , A2 , B2 , A3 | |
| 6 | א(1) | דרגת כל קודקוד מעגל 3; דרגת קודקוד המרכז n. |
| א(2) | n קשתות מעגל ו־n קשתות מרכזיות (סך הכול 2n). | |
| א(3) | לא. למשל 0, 1, 2 יוצרים משולש – מעגל באורך אי־זוגי. | |
| ב | עפ"מ אחד בלבד – העץ שמורכב מכל n הקשתות המרכזיות (משקלו n). | |
| ג(1) | למשל b = 3 , m = 1 (כל בחירה עם 2m < b מתאימה). | |
| ג(2) | צריך 2m < 10, כלומר m < 5. במשקלים שלמים – m = 4 (ב־m = 5 יש גם מסלול קל שאינו עובר במרכז). | |
| 7 | א(1) | L₁ – רגולרית; L₂ – לא רגולרית; L₃ – רגולרית (סופית). |
| א(2) | L₄ = ∅ – רגולרית; L₅ – לא רגולרית; L₆ = Σ* (כל המילים) – רגולרית. | |
| ב | 12 מצבים: S (התחלה), A0–A2, B0–B2, C0–C2, D, E; מקבלים: C0, C1, C2, D, E (טבלת המעברים בפתרון). | |
| 8 | א | abcc – שייכת; acccc – שייכת; aabbc – שייכת; aabbbb – לא שייכת; aaabbc – לא שייכת. |
| ב | n זוגי: aabbc . n אי־זוגי: למשל abbc (גם abbb , abcc , accc). | |
| ג | (1) b,A/ללא שינוי (2) b,A/שלוף (3) b,A/ללא שינוי (4) c,A/שלוף (5) c,A/שלוף (6) c,S/שלוף (7) c,S/שלוף (8)–(12) ללא שינוי בראש A וגם בראש S (13) b,A/שלוף (14) c,A/שלוף (15) c,A/שלוף (16) b,S/ללא שינוי (17)–(21) ראש S/ללא שינוי. מצבים מקבלים: q₉ , q₁₀ , q₁₁ . | |
| 9 | א(1) | 3 שלבים (0–2): q₀ על a → q₁ (a נמחק) → q₅ ; המילה מתקבלת והסרט ריק. |
| א(2) | 9 שלבים (0–8), מסתיים ב־q₅ ; המילה מתקבלת והסרט בסוף: ⊣ b a Δ … | |
| א(3) | ⊣ b b a Δ Δ … (על הסרט: bba) | |
| ב(1) | לא. בכל מילה שיש בה a המכונה מוחקת את ה־a הראשון, ולכן המילה מתקצרת באות אחת. | |
| ב(2) | המכונה מוחקת מהמילה את המופע הראשון של a (ומצמצמת את הרווח); אם אין a – המילה לא משתנה. היא מקבלת כל מילה. | |
| 10 | א(1) | Bow, Wind, Perc יורשות מ־Instrum; Musician מכילה Instrum; Orchestra מכילה (מערך של) Musician. |
| א(2) | Instrum(name, material); Bow extends Instrum(bowLength); Wind extends Instrum(numberOfValves); Perc extends Instrum(hasSticks); Musician(name, instrum: Instrum); Orchestra(arrM: Musician[], count) | |
| ב | סופרים נגנים i<count שהכלי שלהם instanceof Perc ו־((Perc)ins).getHasSticks() הוא true. | |
| ג | אם המערך מלא – false. אחרת pos = count להקשה, אחרי נגן הקשת האחרון לקשת, לפני נגן ההקשה הראשון לנשיפה; הזזה ימינה מ־pos, הצבה, count++ ו־true. | |
| 11 | א | Father(): st++, num=9 · Father(int num): num=num · Son(int num, char ch): super(); num=num; ch=ch · Son(int num): super(num); ch='Z' · toString: super.toString() + ", ch=" + ch |
| ב(1) | 1 – לא ייתכן; 2 – ייתכן; 3 – לא ייתכן; 4 – ייתכן; 5 – לא ייתכן; 6 – ייתכן. | |
| ב(2) | כן. ההמרה (D)a3 של עצם B מצליחה רק אם B יורשת מ־D, ולכן רק תרשים 6 נשאר אפשרי (ב־2 וב־4 תהיה שגיאת ריצה). | |
| ג | protected int num; protected static int c; public AAA(); public AAA(int num); public int gg(int val) (ב־C#: public virtual int GG(int val)); public boolean mm(int x) (ב־C#: public bool MM(int x)) | |
| 12 | א | a: A/A num=1 · ab: הפניה A, עצם B, num=2 · ac: הפניה A, עצם C, num=2 · b: B/B num=3 · bc: הפניה B, עצם C, num=1 · c: C/C num=1 |
| ב | 1: -2 · 2: 0 · 3: 4 · 4: 22 · 5: 20 · 6: 8 · 7: 2 · 8: 21 · 9: 11 · 10: 4 |