מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2026 מועד א'
הנדסת תוכנה · סמל 97105 · 9 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2026 מועד א', כל 9 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- C# (עמוד 2)
מבחן ב- JAVA (עמוד 12)
בכל מבחן תשע שאלות.
שאלות 3–1: יש לענות על שתי שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 6–4: יש לענות על שתי שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 9–7: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · בדיקת מחסנית עולה-יורדת
סדרת מספרים נקראת "עולה – יורדת" אם עד מספר מסוים המספרים הולכים וגדלים וממספר זה ואילך, הם הולכים וקטנים.
לדוגמה, הסדרה שלפניכם היא סדרה "עולה – יורדת":
4, 9, 13, 20, 45, 33, 18, 1

כתבו פעולה המקבלת מחסנית של מספרים שלמים. הפעולה תבדוק אם הערכים שבמחסנית מהווים סדרה "עולה – יורדת". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isUpDown(Stack<Integer> st)public static bool IsUpDown(Stack<int> st)מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
הפעולה isUpDown שלהלן: שולפת את האיברים מראש המחסנית, בודקת שהסדרה עולה ממש ואחר כך יורדת ממש (עם לפחות עלייה אחת ולפחות ירידה אחת), ומשחזרת את המחסנית בעזרת מחסנית עזר.
הרעיון: את הסדרה קוראים מראש המחסנית כלפי מטה (כמו בדוגמה: 4 בראש המחסנית, 1 בתחתית). נשלוף את האיברים אחד אחד ונשווה כל איבר לאיבר שנשלף לפניו. בסדרה "עולה – יורדת" יש קודם רק עליות ואחר כך רק ירידות. נחזיק שני דגלים:
•`up` - כבר הייתה עלייה;
•`down` - כבר התחילה ירידה.
ההגדרה מופרת אם:
•יש עלייה אחרי שכבר התחילה ירידה;
•הסדרה מתחילה בירידה (ירידה לפני שהייתה עלייה כלשהי);
•יש שני מספרים שווים זה אחר זה (הם לא "הולכים וגדלים" ולא "הולכים וקטנים").
לפי ההגדרה יש מספר מסוים (השיא) שעד אליו הסדרה עולה וממנו היא יורדת, ולכן נדרוש שתהיה לפחות עלייה אחת ולפחות ירידה אחת (מחסנית עם פחות משלושה איברים, סדרה עולה בלבד או יורדת בלבד - אינה "עולה – יורדת").
כדי לשמור על שלמות המחסנית, כל איבר שנשלף נדחף למחסנית עזר `temp`, ובסוף מחזירים את כל האיברים מ-`temp` ל-`st` - היפוך כפול מחזיר את הסדר המקורי. שימו לב שלא יוצאים מהלולאה באמצע (גם כשכבר ידוע שהתשובה false), כדי שהשחזור יתבצע תמיד על כל האיברים.
1. אם המחסנית ריקה - מחזירים false.
2. שולפים את האיבר העליון ל-`prev` ודוחפים אותו ל-`temp`.
3. כל עוד המחסנית אינה ריקה: שולפים איבר `x` ודוחפים אותו ל-`temp`, ומשווים ל-`prev`:
•`x > prev` (עלייה): אם `down` כבר true - הפרה; מסמנים `up = true`.
•`x < prev` (ירידה): אם `up` עדיין false - הפרה; מסמנים `down = true`.
•`x == prev` - הפרה.
ומעדכנים `prev = x`.
4. מחזירים את האיברים מ-`temp` ל-`st`.
5. מחזירים `ok && up && down`.
public static boolean isUpDown(Stack<Integer> st)
{
if (st.isEmpty())
return false;
Stack<Integer> temp = new Stack<Integer>(); // לשחזור המחסנית
boolean ok = true; // לא נמצאה הפרה של ההגדרה
boolean up = false; // הייתה לפחות עלייה אחת
boolean down = false; // הייתה לפחות ירידה אחת
int prev = st.pop();
temp.push(prev);
while (!st.isEmpty())
{
int x = st.pop();
temp.push(x);
if (x > prev) // עלייה
{
if (down) // עלייה אחרי שכבר התחילה ירידה
ok = false;
up = true;
}
else if (x < prev) // ירידה
{
if (!up) // ירידה לפני שהייתה עלייה
ok = false;
down = true;
}
else // שני מספרים שווים זה אחר זה
ok = false;
prev = x;
}
while (!temp.isEmpty()) // החזרת האיברים למחסנית
st.push(temp.pop());
return ok && up && down;
}public static bool IsUpDown(Stack<int> st)
{
if (st.IsEmpty())
return false;
Stack<int> temp = new Stack<int>(); // לשחזור המחסנית
bool ok = true; // לא נמצאה הפרה של ההגדרה
bool up = false; // הייתה לפחות עלייה אחת
bool down = false; // הייתה לפחות ירידה אחת
int prev = st.Pop();
temp.Push(prev);
while (!st.IsEmpty())
{
int x = st.Pop();
temp.Push(x);
if (x > prev) // עלייה
{
if (down) // עלייה אחרי שכבר התחילה ירידה
ok = false;
up = true;
}
else if (x < prev) // ירידה
{
if (!up) // ירידה לפני שהייתה עלייה
ok = false;
down = true;
}
else // שני מספרים שווים זה אחר זה
ok = false;
prev = x;
}
while (!temp.IsEmpty()) // החזרת האיברים למחסנית
st.Push(temp.Pop());
return ok && up && down;
}בדיקה על הדוגמה: הסדרה הנשלפת היא 4, 9, 13, 20, 45, 33, 18, 1. ארבעת המעברים הראשונים (4→9→13→20→45) הם עליות, ולכן `up = true` ו-`down` נשאר false. המעברים 45→33→18→1 הם ירידות, `down = true`, ואין אחריהן עלייה. לא נמצאה הפרה, ולכן מוחזר true, והמחסנית חוזרת למצבה המקורי.
דוגמאות נוספות: 1, 3, 2 → true; 3, 2, 1 → false (מתחילה בירידה); 1, 2, 3 → false (אין ירידה); 1, 5, 3, 4 → false (עלייה אחרי ירידה); 1, 2, 2, 1 → false (שני מספרים שווים).
תשובה: הפעולה isUpDown שלמעלה.
סעיף ב
, כאשר מספר האיברים במחסנית.
נסמן ב- את מספר האיברים במחסנית.
1. כל פעולות המחסנית (`push`, `pop`, `isEmpty`) מתבצעות ב-.
2. הלולאה הראשונה שולפת כל איבר פעם אחת, משווה אותו לקודמו ודוחפת אותו ל-`temp`: סיבובים של עבודה קבועה.
3. הלולאה השנייה מחזירה כל איבר פעם אחת: עוד סיבובים.
4. בסך הכול כ- פעולות קבועות - סיבוכיות לינארית.
תשובה: .
שאלה 2 · איבר במקום נתון ומיזוג שרשראות חוליות
כתבו פעולה המקבלת הפניה לחוליה הראשונה בשרשרת חוליות של מספרים שלמים ומספר שלם חיובי pos. הפעולה תחזיר איבר שנמצא במקום pos בשרשרת. אם אין מקום pos בשרשרת, הפעולה תחזיר ערך (-1).
יש להניח כי המיקום נספר החל מ-1, כאשר pos = 1 מתייחס לחוליה הראשונה.
public static int valueAt(Node<Integer> ch, int pos)public static int ValueAt(Node<int> ch, int pos)כתבו פעולה המקבלת שתי הפניות לחוליות הראשונות של שתי שרשראות של מספרים שלמים ch1 ו – ch2. הפעולה תיצור שרשרת חדשה לפי הכלל הבא:
•ראשית מכניסים את האיבר הראשון מהשרשרת ch1, ואחריו – את האיבר האחרון מהשרשרת ch2;
•מכניסים את האיבר השני מהשרשרת ch1, ואחריו את האיבר שלפני האחרון מהשרשרת ch2;
•וכך הלאה.
הפעולה תחזיר הפניה לחוליה הראשונה של השרשרת החדשה.
אפשר להניח שאורכן של שתי השרשראות שווה.
כותרת הפעולה:
public static Node<Integer> merge (Node<Integer>ch1,
Node<Integer>ch2)public static Node<int> Merge (Node<int>ch1, Node<int>ch2)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
הפעולה valueAt שלהלן: מתקדמת pos-1 צעדים מהחוליה הראשונה; אם השרשרת נגמרה לפני כן מחזירה -1, אחרת את ערך החוליה.
הרעיון: החוליה במקום pos נמצאת pos-1 צעדים אחרי החוליה הראשונה. נתקדם עם מצביע `p` ונספור את המקום ב-`i`. אם השרשרת נגמרת (`p == null`) לפני שהגענו למקום pos - אין מקום כזה בשרשרת, ומחזירים -1.
1. מתחילים ב-`p = ch`, `i = 1`.
2. כל עוד `p != null` וגם `i < pos`: מתקדמים `p = p.getNext()` ומגדילים את `i`.
3. אם בסוף `p == null` (השרשרת קצרה מ-pos, או ריקה) - מחזירים -1. (גם עבור pos קטן מ-1, שאינו מקום חוקי, מחזירים -1.)
4. אחרת `p` היא החוליה במקום pos - מחזירים את ערכה.
public static int valueAt(Node<Integer> ch, int pos)
{
int i = 1;
Node<Integer> p = ch;
while (p != null && i < pos) // מתקדמים עד המקום pos
{
p = p.getNext();
i++;
}
if (p == null || pos < 1) // אין מקום כזה בשרשרת
return -1;
return p.getValue();
}public static int ValueAt(Node<int> ch, int pos)
{
int i = 1;
Node<int> p = ch;
while (p != null && i < pos) // מתקדמים עד המקום pos
{
p = p.GetNext();
i++;
}
if (p == null || pos < 1) // אין מקום כזה בשרשרת
return -1;
return p.GetValue();
}דוגמה: עבור השרשרת 5 → 8 → 2 → 7: `valueAt(ch, 1)` מחזירה 5, `valueAt(ch, 3)` מחזירה 2, `valueAt(ch, 4)` מחזירה 7 ו-`valueAt(ch, 5)` מחזירה -1.
תשובה: הפעולה valueAt שלמעלה.
סעיף ב
הפעולה merge שלהלן: דוחפת את ערכי ch2 למחסנית (כך שהם יוצאים מהאחרון לראשון), ואז עוברת על ch1 ובונה שרשרת חדשה: ערך מ-ch1 ואחריו ערך שנשלף מהמחסנית.
הרעיון: את ch1 עוברים מההתחלה לסוף, ואילו את ch2 צריך לעבור מהסוף להתחלה - אבל בשרשרת חוליות אפשר להתקדם רק קדימה. לכן נעביר קודם את כל ערכי ch2 למחסנית: מחסנית הופכת את הסדר, והשליפה הראשונה תחזיר את האיבר האחרון של ch2, השנייה את האיבר שלפני האחרון, וכן הלאה.
אחר כך נעבור על ch1, ולכל איבר ניצור שתי חוליות חדשות - חוליה עם הערך מ-ch1 וחוליה עם הערך שנשלף מהמחסנית - ונחבר אותן לסוף השרשרת החדשה. כדי לחבר לסוף ב- נחזיק הפניה `last` לחוליה האחרונה של השרשרת החדשה. השרשראות המקוריות אינן משתנות ("תיצור שרשרת חדשה").
1. עוברים על ch2 ודוחפים כל ערך למחסנית `st`.
2. `first = null`, `last = null` - השרשרת החדשה ריקה.
3. לכל חוליה `p1` ב-ch1:
•יוצרים חוליה `a` עם הערך של `p1`, וחוליה `b` עם `st.pop()`, ומחברים `a → b`;
•אם השרשרת החדשה ריקה, `first = a`; אחרת `last.setNext(a)`;
•`last = b`.
4. מחזירים את `first` (אם השרשראות ריקות מוחזר null).
public static Node<Integer> merge(Node<Integer> ch1, Node<Integer> ch2)
{
// ערכי ch2 נכנסים למחסנית, כך שיוצאים ממנה מהאחרון לראשון
Stack<Integer> st = new Stack<Integer>();
for (Node<Integer> p = ch2; p != null; p = p.getNext())
st.push(p.getValue());
Node<Integer> first = null; // החוליה הראשונה של השרשרת החדשה
Node<Integer> last = null; // החוליה האחרונה של השרשרת החדשה
Node<Integer> p1 = ch1;
while (p1 != null)
{
Node<Integer> a = new Node<Integer>(p1.getValue()); // איבר מ-ch1
Node<Integer> b = new Node<Integer>(st.pop()); // איבר מסוף ch2
a.setNext(b);
if (first == null)
first = a;
else
last.setNext(a);
last = b;
p1 = p1.getNext();
}
return first;
}public static Node<int> Merge(Node<int> ch1, Node<int> ch2)
{
// ערכי ch2 נכנסים למחסנית, כך שיוצאים ממנה מהאחרון לראשון
Stack<int> st = new Stack<int>();
for (Node<int> p = ch2; p != null; p = p.GetNext())
st.Push(p.GetValue());
Node<int> first = null; // החוליה הראשונה של השרשרת החדשה
Node<int> last = null; // החוליה האחרונה של השרשרת החדשה
Node<int> p1 = ch1;
while (p1 != null)
{
Node<int> a = new Node<int>(p1.GetValue()); // איבר מ-ch1
Node<int> b = new Node<int>(st.Pop()); // איבר מסוף ch2
a.SetNext(b);
if (first == null)
first = a;
else
last.SetNext(a);
last = b;
p1 = p1.GetNext();
}
return first;
}דוגמה: עבור ch1 = 1 → 2 → 3 → 4 ו-ch2 = 5 → 6 → 7 → 8: במחסנית 8 בראש, אחריו 7, 6, 5. השרשרת החדשה: 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5.
תשובה: הפעולה merge שלמעלה.
סעיף ג
valueAt: (לכל היותר צעדים); merge: , כאשר אורך השרשרת.
נסמן ב- את אורך השרשרת (בסעיף ב' - אורך כל אחת משתי השרשראות).
1. valueAt: הלולאה מתקדמת חוליה אחת בכל סיבוב, לכל היותר סיבובים, ובכל סיבוב עבודה קבועה. במקרה הגרוע (pos בסוף השרשרת או מחוץ לה) - צעדים: .
2. merge: מעבר על ch2 עם דחיפה למחסנית - פעולות ; מעבר על ch1 - סיבובים, בכל אחד יצירת שתי חוליות, שליפה אחת מהמחסנית וחיבור לסוף בעזרת `last` - כולן . בסך הכול כ- פעולות קבועות: .
תשובה: בסעיף א' - ; בסעיף ב' - .
שאלה 3 · ממשקים, מימוש והמרות טיפוסים
בפרויקט פיתוח רכב אוטונומי הוגדרו שלושה ממשקים ושתי מחלקות:
public interface Steering {
void turnLeft();
void turnRight(int degrees);
}
public interface Navigation{ void setDestination(String dest); }
public interface Sensing { void activateLidar(); }
public class AutonomousCar implements Steering, Navigation,
Sensing {
private String modelName;
private double batteryLevel;
// ...
}
public class TestDrive {
public static void main(String[] args) {
AutonomousCar car1 = new AutonomousCar("Tesla Y", 98.5);
AutonomousCar car2 = new AutonomousCar("Waymo One");
// ( *****)
}
}public interface Steering {
void TurnLeft();
void TurnRight(int degrees);
}
public interface Navigation{ void SetDestination(string dest); }
public interface Sensing { void ActivateLidar(); }
public class AutonomousCar : Steering, Navigation, Sensing {
private string modelName;
private double batteryLevel;
// ...
}
public class TestDrive {
public static void Main(string[] args) {
AutonomousCar car1 = new AutonomousCar("Tesla Y", 98.5);
AutonomousCar car2 = new AutonomousCar("Waymo One");
// ( *****)
}
}השלימו את המחלקה AutonomousCar: כתבו כותרות לפעולות החסרות בה, כולל כל הפעולות הבונות (constructors) הנדרשות כדי שהקוד בפעולה main יהיה תקין, וכן את כל הפעולות הנדרשות למימוש הממשקים. אין צורך לממש את גוף הפעולות.
בכל אחד מסעיפים הבאים השורה (*) תוחלף בשורת קוד משורות הקוד 1–6 מהטבלה הבאה. עבור כל אחד מהסעיפים, כתבו אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין, יש לציין את סוג השגיאה (קומפילציה או זמן ריצה).
Steering s1 = car1;
s1.turnRight(45);Steering s1 = car1;
s1.TurnRight(45);Navigation n2 = new Navigation();
n2.setDestination("Tel Aviv");Navigation n2 = new Navigation();
n2.SetDestination("Tel Aviv");Navigation n3 = new AutonomousCar("Audi A8", 60.0);
Steering s3 = (AutonomousCar)n3;Navigation n3 = new AutonomousCar("Audi A8", 60.0);
Steering s3 = (AutonomousCar)n3;Navigation n4 = new AutonomousCar("Mercedes");
n4.activateLidar();Navigation n4 = new AutonomousCar("Mercedes");
n4.ActivateLidar();Steering s5 = new AutonomousCar("Ford");
Sensing sn5 = (Sensing) s5 ;
sn5.activateLidar();Steering s5 = new AutonomousCar("Ford");
Sensing sn5 = (Sensing) s5 ;
sn5.ActivateLidar();Sensing sn6 = new AutonomousCar("Nissan", 70.0);
((AutonomousCar) sn6).turnLeft();
((Navigation) sn6).setDestination("Haifa");Sensing sn6 = new AutonomousCar("Nissan", 70.0);
((AutonomousCar) sn6).TurnLeft();
((Navigation) sn6).SetDestination("Haifa");◂ פתרון מלא לשאלה 3
סעיף א
שתי פעולות בונות: AutonomousCar(String modelName, double batteryLevel) ו-AutonomousCar(String modelName); ומימוש הממשקים: void turnLeft(), void turnRight(int degrees), void setDestination(String dest), void activateLidar() - כולן public.
1. פעולות בונות - לפי main:
•`new AutonomousCar("Tesla Y", 98.5)` - פעולה בונה שמקבלת מחרוזת (שם הדגם) ומספר ממשי (רמת הסוללה);
•`new AutonomousCar("Waymo One")` - פעולה בונה שמקבלת מחרוזת בלבד.
מאחר שהמחלקה מגדירה פעולה בונה, אין פעולה בונה ברירת מחדל, ולכן צריך את שתיהן במפורש.
2. מימוש הממשקים - מחלקה (שאינה מופשטת) שמממשת ממשק חייבת לממש את כל הפעולות שלו, עם אותה חתימה ובהרשאה public (פעולות הממשק הן public):
•מ-Steering: `turnLeft()` ו-`turnRight(int degrees)`;
•מ-Navigation: `setDestination(String dest)`;
•מ-Sensing: `activateLidar()`.
public class AutonomousCar implements Steering, Navigation, Sensing {
private String modelName;
private double batteryLevel;
// פעולות בונות - נדרשות בגלל car1 ו-car2 בפעולה main
public AutonomousCar(String modelName, double batteryLevel) { ... }
public AutonomousCar(String modelName) { ... }
// מימוש הממשק Steering
public void turnLeft() { ... }
public void turnRight(int degrees) { ... }
// מימוש הממשק Navigation
public void setDestination(String dest) { ... }
// מימוש הממשק Sensing
public void activateLidar() { ... }
}public class AutonomousCar : Steering, Navigation, Sensing {
private string modelName;
private double batteryLevel;
// פעולות בונות - נדרשות בגלל car1 ו-car2 בפעולה Main
public AutonomousCar(string modelName, double batteryLevel) { ... }
public AutonomousCar(string modelName) { ... }
// מימוש הממשק Steering
public void TurnLeft() { ... }
public void TurnRight(int degrees) { ... }
// מימוש הממשק Navigation
public void SetDestination(string dest) { ... }
// מימוש הממשק Sensing
public void ActivateLidar() { ... }
}(הסימון `{ ... }` מציין את גוף הפעולה, שאין צורך לממש.)
תשובה: שתי הפעולות הבונות וארבע הפעולות של הממשקים, כמו בקוד שלמעלה.
סעיף ב
תקין.
1. `Steering s1 = car1;` - המחלקה AutonomousCar מממשת את Steering, ולכן עצם מטיפוס AutonomousCar הוא גם Steering. זו המרה כלפי מעלה (upcasting), והיא מתבצעת אוטומטית בלי המרה מפורשת.
2. `s1.turnRight(45);` - הפעולה turnRight(int) מוגדרת בממשק Steering, ולכן המהדר מאשר את הקריאה דרך הפניה מטיפוס Steering. בזמן ריצה מתבצע המימוש שבמחלקה AutonomousCar.
תשובה: הקוד תקין.
לא תקין - שגיאת קומפילציה: אי אפשר ליצור עצם מממשק (new Navigation()).
1. Navigation הוא ממשק (interface). לממשק אין פעולה בונה ואין מימוש לפעולות שלו, ולכן אי אפשר ליצור ממנו עצם בעזרת `new`.
2. המהדר מזהה זאת כבר בשורה הראשונה.
תשובה: לא תקין - שגיאת קומפילציה: `new Navigation()` - אי אפשר ליצור מופע של ממשק.
תקין.
1. `Navigation n3 = new AutonomousCar("Audi A8", 60.0);` - נוצר עצם AutonomousCar (בעזרת הפעולה הבונה עם שני הפרמטרים) ומוצב בהפניה מטיפוס Navigation - המרה כלפי מעלה, תקינה.
2. `(AutonomousCar)n3` - המרה מפורשת כלפי מטה מהממשק Navigation למחלקה AutonomousCar שמממשת אותו: המהדר מתיר אותה. בזמן ריצה n3 מפנה בפועל לעצם AutonomousCar, ולכן ההמרה מצליחה.
3. את התוצאה (מטיפוס AutonomousCar) מציבים בהפניה מטיפוס Steering - AutonomousCar מממשת את Steering, המרה כלפי מעלה תקינה.
תשובה: הקוד תקין.
לא תקין - שגיאת קומפילציה: בממשק Navigation אין פעולה activateLidar.
1. השורה הראשונה תקינה: עצם AutonomousCar (פעולה בונה עם פרמטר אחד) מוצב בהפניה מטיפוס Navigation.
2. בשורה השנייה הקריאה נעשית דרך הפניה מטיפוס Navigation. המהדר בודק את הקריאה לפי הטיפוס של ההפניה, ובממשק Navigation מוגדרת רק setDestination. אין בו activateLidar, ולכן הקריאה לא עוברת הידור - למרות שהעצם בפועל הוא AutonomousCar ויש לו את הפעולה.
(תיקון אפשרי: `((Sensing) n4).activateLidar();`.)
תשובה: לא תקין - שגיאת קומפילציה בשורה `n4.activateLidar();`.
תקין.
1. `Steering s5 = new AutonomousCar("Ford");` - המרה כלפי מעלה, תקינה.
2. `(Sensing) s5` - המרה מפורשת מממשק לממשק אחר. המהדר מתיר אותה, כי ייתכן שהעצם שההפניה מפנה אליו מממש את שני הממשקים. בזמן ריצה נבדק העצם בפועל: הוא AutonomousCar, שמממשת את Sensing - ההמרה מצליחה.
3. `sn5.activateLidar();` - הפעולה מוגדרת בממשק Sensing, ובזמן ריצה מתבצע המימוש שב-AutonomousCar.
תשובה: הקוד תקין.
תקין.
1. `Sensing sn6 = new AutonomousCar("Nissan", 70.0);` - המרה כלפי מעלה, תקינה.
2. `((AutonomousCar) sn6).turnLeft();` - המרה מפורשת כלפי מטה ל-AutonomousCar (העצם בפועל הוא AutonomousCar, ולכן היא מצליחה בזמן ריצה), ולמחלקה AutonomousCar יש turnLeft.
3. `((Navigation) sn6).setDestination("Haifa");` - המרה מממשק Sensing לממשק Navigation: מותרת בהידור, ובזמן ריצה מצליחה כי העצם מממש את Navigation. הפעולה setDestination מוגדרת ב-Navigation.
תשובה: הקוד תקין.
שאלה 4 · מספרים זרים ותור של מספרים זרים
שני מספרים שלמים וחיוביים num1 ו-num2 נקראים "זרים זה לזה" אם אין להם שום ספרה משותפת.
לדוגמה:
המספרים 81224 ו-973656 הם זרים, וגם המספרים 1000 ו-289 הם זרים.
המספרים 14 ו-21 הם לא זרים כי יש להם ספרה משותפת, 1.
כתבו פעולה המקבלת שני מספרים שלמים חיוביים. הפעולה תבדוק אם הם "זרים". אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean areStrangers(int num1, int num2)public static bool AreStrangers(int num1, int num2)כתבו פעולה המקבלת תור של מספרים שלמים חיוביים. הפעולה תבדוק אם כל הערכים בתור זרים זה לזה. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isStrangersQueue(Queue<Integer> q)public static bool IsStrangersQueue(Queue<int> q)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 4
סעיף א
הפעולה areStrangers שלהלן: מסמנת במערך בוליאני בגודל 10 את הספרות של num1, ואז בודקת אם ספרה כלשהי של num2 מסומנת.
הרעיון: יש רק 10 ספרות אפשריות (0-9). נבנה מערך בוליאני `digits` בגודל 10, ונסמן בו את כל הספרות שמופיעות ב-num1. אחר כך נעבור על הספרות של num2: אם אחת מהן כבר מסומנת - יש ספרה משותפת והמספרים אינם זרים.
את הספרות של מספר מפרקים בעזרת `% 10` (ספרת האחדות) ו-`/ 10` (הורדת ספרת האחדות), עד שהמספר מתאפס.
1. כל עוד `num1 > 0`: מסמנים `digits[num1 % 10] = true` ומחלקים את num1 ב-10.
2. כל עוד `num2 > 0`: אם `digits[num2 % 10]` מסומן - מחזירים false; אחרת מחלקים את num2 ב-10.
3. אם לא נמצאה ספרה משותפת - מחזירים true.
public static boolean areStrangers(int num1, int num2)
{
boolean[] digits = new boolean[10]; // digits[d] = true אם הספרה d מופיעה ב-num1
while (num1 > 0)
{
digits[num1 % 10] = true;
num1 = num1 / 10;
}
while (num2 > 0)
{
if (digits[num2 % 10]) // ספרה של num2 מופיעה גם ב-num1
return false;
num2 = num2 / 10;
}
return true;
}public static bool AreStrangers(int num1, int num2)
{
bool[] digits = new bool[10]; // digits[d] = true אם הספרה d מופיעה ב-num1
while (num1 > 0)
{
digits[num1 % 10] = true;
num1 = num1 / 10;
}
while (num2 > 0)
{
if (digits[num2 % 10]) // ספרה של num2 מופיעה גם ב-num1
return false;
num2 = num2 / 10;
}
return true;
}- 81224 ו-973656: הספרות של 81224 הן {1, 2, 4, 8}; הספרות של 973656 הן {3, 5, 6, 7, 9} - אין משותפת → true.
- 1000 ו-289: {0, 1} מול {2, 8, 9} → true.
- 14 ו-21: {1, 4}; בפירוק 21 הספרה הראשונה שנבדקת היא 1, והיא מסומנת → false.
תשובה: הפעולה areStrangers שלמעלה.
סעיף ב
הפעולה isStrangersQueue שלהלן: מעבר אחד על התור עם מערך used של ספרות שכבר הופיעו; אם ספרה של מספר כלשהו כבר הופיעה במספר אחר - false. התור משוחזר.
הרעיון: כל הערכים בתור זרים זה לזה אם כל זוג של שני ערכים שונים בתור (שני מקומות שונים בתור) הם זרים - כלומר אף ספרה אינה מופיעה בשני מספרים שונים. (ספרה שחוזרת בתוך אותו מספר, כמו 0 ב-1000, מותרת.)
אפשר היה לבדוק כל זוג בעזרת areStrangers, אבל זה דורש השוואות ומעברים חוזרים על התור. במקום זה נעבור על התור פעם אחת ונחזיק מערך `used` בגודל 10 של הספרות שכבר הופיעו במספרים הקודמים:
1. לכל מספר `x` שמוציאים מהתור (ומכניסים לתור עזר `temp`, לשחזור), מחשבים את קבוצת הספרות שלו במערך `cur`.
2. לכל ספרה `d` שמופיעה ב-x: אם `used[d]` כבר true - הספרה הופיעה במספר קודם, ולכן יש זוג לא זר: `ok = false`. אחרת מסמנים `used[d] = true`.
חשוב להשתמש ב-`cur` ולא לסמן ישר ב-`used` בזמן הפירוק - אחרת ספרה שחוזרת באותו מספר (כמו 0 ב-1000) הייתה נחשבת בטעות להתנגשות.
3. בסוף מחזירים את כל האיברים מ-`temp` ל-`q` (תור שומר על הסדר, ולכן התור חוזר בדיוק למצבו), ומחזירים `ok`.
תור ריק או תור עם איבר אחד - אין זוג שמפר את התנאי, ומוחזר true. אם אותו מספר מופיע פעמיים בתור - לשני המופעים ספרות משותפות, ומוחזר false.
public static boolean isStrangersQueue(Queue<Integer> q)
{
boolean[] used = new boolean[10]; // ספרות שכבר הופיעו במספרים קודמים
boolean ok = true;
Queue<Integer> temp = new Queue<Integer>();
while (!q.isEmpty())
{
int x = q.remove();
temp.insert(x);
boolean[] cur = new boolean[10]; // הספרות של המספר הנוכחי
int n = x;
while (n > 0)
{
cur[n % 10] = true;
n = n / 10;
}
for (int d = 0; d < 10; d++)
{
if (cur[d])
{
if (used[d]) // הספרה d כבר הופיעה במספר אחר
ok = false;
used[d] = true;
}
}
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return ok;
}public static bool IsStrangersQueue(Queue<int> q)
{
bool[] used = new bool[10]; // ספרות שכבר הופיעו במספרים קודמים
bool ok = true;
Queue<int> temp = new Queue<int>();
while (!q.IsEmpty())
{
int x = q.Remove();
temp.Insert(x);
bool[] cur = new bool[10]; // הספרות של המספר הנוכחי
int n = x;
while (n > 0)
{
cur[n % 10] = true;
n = n / 10;
}
for (int d = 0; d < 10; d++)
{
if (cur[d])
{
if (used[d]) // הספרה d כבר הופיעה במספר אחר
ok = false;
used[d] = true;
}
}
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return ok;
}•התור 1000, 289, 35, 7: הספרות {0,1}, {2,8,9}, {3,5}, {7} - אין חזרה בין מספרים → true.
•התור 81224, 973656, 1000: הספרה 1 מופיעה ב-81224 וגם ב-1000 → false.
תשובה: הפעולה isStrangersQueue שלמעלה.
סעיף ג
areStrangers: (מספר הספרות); isStrangersQueue: , כלומר כשמספר הספרות חסום.
1. areStrangers: נסמן ב-, את מספר הספרות של num1 ו-num2 (כ- של המספר). כל לולאה מבצעת סיבוב אחד לכל ספרה, ובכל סיבוב עבודה קבועה (גישה למערך בגודל קבוע 10). לכן . מאחר שמספר שלם (int) מכיל לכל היותר 10 ספרות, זה למעשה .
2. isStrangersQueue: נסמן ב- את מספר האיברים בתור וב- את מספר הספרות המרבי של מספר בתור. לכל איבר: הוצאה והכנסה לתור עזר - ; פירוק לספרות - ; לולאה על 10 ספרות - . בסך הכול למעבר, ועוד לשחזור התור. לכן , ומאחר ש- חסום (לכל היותר 10) - .
תשובה: בסעיף א' - (לינארי במספר הספרות); בסעיף ב' - , כלומר לינארי במספר האיברים בתור.
שאלה 5 · עץ ירושה, המרות טיפוסים ופולימורפיזם
חברת סטארט-אפ פיתחה פלטפורמה לשירותי רשת. הטבלה שלפניכם מייצגת את היררכיית היישומים (Applications) במערכת.
שרטטו את עץ הירושה הכולל של המחלקות (Class Diagrams).
נתון קטע קוד מתוך הפעולה הראשית (main):
Application a1 = new Application();
Application a2 = new FrontendApp();
Application a3 = new MobileApp();
WebService ws1 = new BackendService();
MobileApp ma1 = new DataQuery();לפניכם שמונה קטעי קוד. עבור כל אחד מהסעיפים יש לציין אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (שגיאת קומפילציה/הידור או שגיאת זמן ריצה).
WebService ws2 = new Application();WebService ws3 = a2;WebService ws4 = (WebService)a2;WebService ws5 = (WebService)a3;BackendService bs1 = (BackendService)ws1;MobileApp ma2 = (MobileApp)a1;Application a4 = (MobileApp)(new DataQuery());FrontendApp fa1 = (WebService)(new BackendService());לכל שירות במערכת יש עלות תפעול משלו (Cost). המטרה היא לחשב את סכום העלויות של כל היישומים שהם שירותי הרשת (WebService).
באילו מהמחלקות יש להגדיר את הפעולה `public double getCost()` (ב-C#: `public double GetCost()`) המחזירה את עלות התפעול? הסבירו את תשובתכם.
כתבו פעולה סטטית בשם sumWebServiceCost המקבלת מערך של יישומים ומחזירה את סכום העלויות של כל שירותי הרשת. כותרת הפעולה:
public static double sumWebServiceCost(Application[] arr)public static double SumWebServiceCost(Application[] arr)◂ פתרון מלא לשאלה 5
סעיף א
Object ← Application; Application ← WebService, MobileApp; WebService ← BackendService, FrontendApp; MobileApp ← DataQuery.
בונים את העץ מעמודת "יורשת מ-": כל מחלקה מצוירת מתחת למחלקת האב שלה, עם חץ ממנה אל האב.
1. בשורש - Object, ומתחתיו Application (מחלקת האב של כל היישומים).
2. מ-Application יורשות שתי מחלקות: WebService ו-MobileApp.
3. מ-WebService יורשות BackendService ו-FrontendApp.
4. מ-MobileApp יורשת DataQuery.
Object
^
|
Application
^ ^
| |
WebService MobileApp
^ ^ ^
| | |
BackendService FrontendApp DataQuery(החצים מצביעים מהמחלקה היורשת אל מחלקת האב.)
תשובה: העץ שלמעלה.
סעיף ב
לא תקין - שגיאת קומפילציה: אי אפשר להציב עצם מטיפוס Application (מחלקת האב) בהפניה מטיפוס WebService (מחלקה יורשת).
1. `new Application()` יוצר עצם מטיפוס Application - מחלקת האב של WebService.
2. הפניה מטיפוס WebService יכולה להפנות רק לעצם שהוא WebService (או יורש ממנו). Application אינו WebService, וההצבה היא כלפי מטה בלי המרה מפורשת.
3. המהדר דוחה את ההצבה (גם המרה מפורשת לא הייתה עוזרת - היא הייתה נכשלת בזמן ריצה).
תשובה: לא תקין - שגיאת קומפילציה.
לא תקין - שגיאת קומפילציה: a2 מוגדר מטיפוס Application, וההצבה ל-WebService היא כלפי מטה ודורשת המרה מפורשת.
1. בפועל a2 מפנה לעצם FrontendApp (שהוא כן WebService), אבל המהדר בודק לפי הטיפוס המוצהר של a2 - Application.
2. הצבה מטיפוס אב (Application) לטיפוס יורש (WebService) היא המרה כלפי מטה, והיא אינה מתבצעת אוטומטית - צריך המרה מפורשת (כמו בקטע 3).
תשובה: לא תקין - שגיאת קומפילציה.
תקין.
1. `(WebService)a2` - המרה מפורשת כלפי מטה מ-Application ל-WebService: המהדר מתיר אותה, כי WebService יורשת מ-Application.
2. בזמן ריצה a2 מפנה לעצם FrontendApp, ו-FrontendApp יורשת מ-WebService - ההמרה מצליחה.
תשובה: תקין.
לא תקין - שגיאת זמן ריצה: a3 מפנה לעצם MobileApp, שאינו WebService (ClassCastException ב-Java, InvalidCastException ב-C#).
1. בהידור: המרה מפורשת מ-Application ל-WebService מותרת (ייתכן ש-a3 מפנה ל-WebService), ולכן הקוד עובר הידור.
2. בזמן ריצה נבדק העצם בפועל: a3 מפנה לעצם MobileApp. MobileApp ו-WebService הן שתי מחלקות אחיות (שתיהן יורשות מ-Application), ו-MobileApp אינה WebService - ההמרה נכשלת.
תשובה: לא תקין - שגיאת זמן ריצה (ClassCastException / InvalidCastException).
תקין.
1. `(BackendService)ws1` - המרה מפורשת כלפי מטה מ-WebService ל-BackendService: מותרת בהידור.
2. בזמן ריצה ws1 מפנה לעצם BackendService - ההמרה מצליחה.
תשובה: תקין.
לא תקין - שגיאת זמן ריצה: a1 מפנה לעצם Application, שאינו MobileApp (ClassCastException / InvalidCastException).
1. בהידור: המרה מפורשת מ-Application ל-MobileApp (יורשת) מותרת.
2. בזמן ריצה a1 מפנה לעצם מטיפוס Application בדיוק - עצם של מחלקת האב אינו עצם של המחלקה היורשת, ולכן ההמרה נכשלת.
תשובה: לא תקין - שגיאת זמן ריצה.
תקין.
1. `new DataQuery()` - עצם DataQuery; `(MobileApp)` - המרה כלפי מעלה (DataQuery יורשת מ-MobileApp), תמיד תקינה.
2. הצבת MobileApp בהפניה מטיפוס Application - שוב המרה כלפי מעלה, אוטומטית.
תשובה: תקין.
לא תקין - שגיאת קומפילציה: תוצאת ההמרה היא מטיפוס WebService, ואי אפשר להציב אותה בהפניה מטיפוס FrontendApp בלי המרה מפורשת.
1. `(WebService)(new BackendService())` - המרה כלפי מעלה, תקינה; טיפוס הביטוי הוא WebService.
2. הצבת ביטוי מטיפוס WebService בהפניה מטיפוס FrontendApp היא הצבה כלפי מטה בלי המרה מפורשת - המהדר דוחה אותה. (וגם אילו נכתבה המרה ל-FrontendApp, היא הייתה נכשלת בזמן ריצה, כי BackendService ו-FrontendApp הן מחלקות אחיות.)
תשובה: לא תקין - שגיאת קומפילציה.
סעיף ג
במחלקה WebService (אפשר כפעולה מופשטת), ולדרוס אותה ב-BackendService וב-FrontendApp לפי העלות של כל סוג שירות.
1. עלות תפעול שייכת לשירותי רשת בלבד, ולכן אין להגדיר אותה ב-Application: אז גם ל-MobileApp ול-DataQuery, שאינם שירותי רשת, הייתה עלות.
2. מגדירים את `getCost()` במחלקה WebService. כך כל שירות רשת - WebService עצמו וכל היורשות ממנה (BackendService, FrontendApp) - מקבל את הפעולה בירושה, ואפשר לקרוא לה דרך הפניה מטיפוס WebService.
3. מאחר שלכל שירות עלות משלו, דורסים (override) את `getCost()` ב-BackendService וב-FrontendApp, כל אחת לפי חישוב העלות שלה. בזכות הפולימורפיזם, קריאה ל-`getCost()` דרך הפניה מטיפוס WebService תפעיל בזמן ריצה את הגרסה של המחלקה בפועל. (אם אין עצמים מטיפוס WebService עצמו, אפשר להגדיר אותה ב-WebService כפעולה מופשטת - abstract.) ב-C# מסמנים אותה ב-WebService כ-`virtual` (או `abstract`), ובמחלקות היורשות כ-`override`.
4. ב-MobileApp וב-DataQuery לא מגדירים את הפעולה.
תשובה: ב-WebService, עם דריסה ב-BackendService וב-FrontendApp.
הפעולה sumWebServiceCost שלהלן: לכל איבר במערך שהוא WebService (instanceof / is) מוסיפה לסכום את getCost() אחרי המרה ל-WebService.
הרעיון: המערך מטיפוס Application[], ולכן הוא יכול להכיל כל יישום. עוברים על כל האיברים, ולכל איבר בודקים אם הוא שירות רשת - `instanceof WebService` ב-Java (`is WebService` ב-C#). הבדיקה מחזירה true גם עבור BackendService ו-FrontendApp, כי הן יורשות מ-WebService, ו-false עבור MobileApp, DataQuery, Application ו-null.
כדי לקרוא ל-`getCost()` צריך להמיר את ההפניה ל-WebService - הפעולה מוגדרת ב-WebService ולא ב-Application, והמהדר בודק לפי הטיפוס המוצהר. בזמן ריצה תופעל הגרסה של המחלקה בפועל (דריסה).
1. `sum = 0`.
2. לכל `i` מ-0 עד אורך המערך פחות 1: אם `arr[i]` הוא WebService - `sum += ((WebService) arr[i]).getCost()`.
3. מחזירים את `sum`.
public static double sumWebServiceCost(Application[] arr)
{
double sum = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof WebService) // רק שירותי רשת
sum += ((WebService) arr[i]).getCost(); // getCost מוגדרת ב-WebService
}
return sum;
}public static double SumWebServiceCost(Application[] arr)
{
double sum = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is WebService) // רק שירותי רשת
sum += ((WebService) arr[i]).GetCost(); // GetCost מוגדרת ב-WebService
}
return sum;
}דוגמה: עבור המערך {Application, FrontendApp (עלות 30), MobileApp, BackendService (עלות 100), DataQuery} - נסכמים רק FrontendApp ו-BackendService, והפעולה מחזירה 130.
תשובה: הפעולה sumWebServiceCost שלמעלה.
שאלה 6 · הוספת חוליה ועדכון מונה הקטנים
נתונה המחלקה SpecNode:
public class SpecNode {
private int value;
private int numOfSmallers;
private SpecNode next;
public SpecNode (int val) {
this.value = val;
this. numOfSmallers = 0;
this.next = null;
}
}למחלקה הוגדר בנאי.
לכל תכונה במחלקה הוגדרו פעולות get/set (ב-C#: Get/Set).
בשרשרת חוליות מסוג SpecNode:
•value – מספר שלם.
•numOfSmallers – מספר החוליות המופיעות אחרי החוליה הנוכחית בשרשרת שערך ה-value שלהן קטן מערך ה-value של החוליה הנוכחית.
•next – מצביע לחוליה הבאה.
לדוגמה:
•ערך ה-value של החוליה הראשונה הוא 7, ואחריה יש ארבע חוליות שערכי ה-value שלהן קטן מ-7 ובגלל זה ערך התכונה numOfSmallers של החוליה הראשונה הוא 4.
•P מצביע על חוליה עם value=4, והתכונה numOfSmallers=2 מציינת כי יש שתי חוליות אחריה שערכי ה-value שלהן קטנים מ-4 (כלומר 1 ו-2).


כתבו פעולה חיצונית המכניסה חוליה חדשה לשרשרת במיקום pos ועם ערך val. הפעולה מקבלת הפניה לחוליה הראשונה של שרשרת חוליות מסוג SpecNode, מספר שלם val ומספר שלם חיובי pos. (המיקום הראשון בשרשרת הוא 1). אפשר להניח כי מיקום pos חוקי (אינו עולה על אורך רשימה+1).
לאחר ההוספה, יש לעדכן את כל ערכי numOfSmallers בהתאם.
כותרת הפעולה:
public static SpecNode addNum(SpecNode list, int val, int pos)public static SpecNode AddNum (SpecNode list, int val, int pos)לדוגמה:
אחרי זימון הפעולה addNum(list, 3, 5) השרשרת שתתקבל תהיה:
מהי סיבוכיות הפעולה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
הפעולה addNum שלהלן: בדרך למקום pos מגדילה ב-1 את numOfSmallers של כל חוליה שערכה גדול מ-val, מחברת את החוליה החדשה, וסופרת לה את החוליות שאחריה שערכן קטן מ-val. מחזירה את ראש השרשרת (חוליה חדשה אם pos = 1).
הרעיון: נבדוק על אילו חוליות משפיעה הוספת חוליה חדשה עם הערך val במקום pos:
1. חוליה שלפני המקום pos: החוליה החדשה נמצאת אחריה. אם הערך שלה גדול מ-val, נוספה אחריה חוליה קטנה ממנה, ולכן numOfSmallers שלה גדל ב-1. אם הערך שלה קטן מ-val או שווה לו - אין שינוי.
2. חוליה שאחרי המקום pos: החוליה החדשה נמצאת לפניה, ולכן היא לא נספרת אצלה - אין שינוי.
3. החוליה החדשה: numOfSmallers שלה הוא מספר החוליות שאחריה שערכן קטן מ-val. סופרים אותן במעבר על המשך השרשרת.
כך כל העדכונים נעשים במעבר אחד על השרשרת:
1. יוצרים חוליה חדשה `node` עם הערך val.
2. מתקדמים עם `cur` (ו-`prev` שמאחוריו) pos-1 צעדים. בכל צעד: אם `cur.getValue() > val` - מגדילים את numOfSmallers של `cur` ב-1.
3. מחברים: `node.setNext(cur)`; אם `prev == null` (pos = 1) החוליה החדשה היא ראש השרשרת, אחרת `prev.setNext(node)`.
4. ממשיכים מ-`cur` עד סוף השרשרת וסופרים ב-`count` את החוליות שערכן קטן מ-val; `node.setNumOfSmallers(count)`.
5. מחזירים את ראש השרשרת (ייתכן שהשתנה).
public static SpecNode addNum(SpecNode list, int val, int pos)
{
SpecNode node = new SpecNode(val);
SpecNode prev = null;
SpecNode cur = list;
int i = 1;
// מעבר על החוליות שלפני המקום pos: לכל חוליה שערכה גדול מ-val
// נוספה חוליה קטנה ממנה אחריה
while (i < pos)
{
if (cur.getValue() > val)
cur.setNumOfSmallers(cur.getNumOfSmallers() + 1);
prev = cur;
cur = cur.getNext();
i++;
}
// חיבור החוליה החדשה בין prev ל-cur
node.setNext(cur);
if (prev == null)
list = node; // הוספה בראש השרשרת
else
prev.setNext(node);
// ספירת החוליות שאחרי החוליה החדשה וערכן קטן מ-val
int count = 0;
while (cur != null)
{
if (cur.getValue() < val)
count++;
cur = cur.getNext();
}
node.setNumOfSmallers(count);
return list;
}public static SpecNode AddNum(SpecNode list, int val, int pos)
{
SpecNode node = new SpecNode(val);
SpecNode prev = null;
SpecNode cur = list;
int i = 1;
// מעבר על החוליות שלפני המקום pos: לכל חוליה שערכה גדול מ-val
// נוספה חוליה קטנה ממנה אחריה
while (i < pos)
{
if (cur.GetValue() > val)
cur.SetNumOfSmallers(cur.GetNumOfSmallers() + 1);
prev = cur;
cur = cur.GetNext();
i++;
}
// חיבור החוליה החדשה בין prev ל-cur
node.SetNext(cur);
if (prev == null)
list = node; // הוספה בראש השרשרת
else
prev.SetNext(node);
// ספירת החוליות שאחרי החוליה החדשה וערכן קטן מ-val
int count = 0;
while (cur != null)
{
if (cur.GetValue() < val)
count++;
cur = cur.GetNext();
}
node.SetNumOfSmallers(count);
return list;
}בדיקה על הדוגמה - addNum(list, 3, 5) על השרשרת 7(4) → 1(0) → 4(2) → 8(2) → 2(1) → 1(0) (בסוגריים numOfSmallers):
אחרי 4 צעדים `cur` מצביע על החוליה 2, והחוליה החדשה 3 מחוברת בין 8 ל-2. אחריה החוליות 2 ו-1 - שתיהן קטנות מ-3, ולכן `count = 2`. החוליות 2(1) ו-1(0) לא משתנות.
השרשרת המתקבלת: 7(5) → 1(0) → 4(3) → 8(3) → 3(2) → 2(1) → 1(0), בדיוק כמו באיור לסעיף.
תשובה: הפעולה addNum שלמעלה.
סעיף ב
, כאשר אורך השרשרת.
נסמן ב- את אורך השרשרת.
1. הלולאה הראשונה עוברת על pos-1 החוליות שלפני מקום ההוספה, ובכל חוליה עבודה קבועה (השוואה ואולי עדכון).
2. החיבור של החוליה החדשה - .
3. הלולאה השנייה עוברת על החוליות שמהמקום pos ועד הסוף, ובכל אחת עבודה קבועה.
4. יחד שתי הלולאות עוברות על כל חוליה בשרשרת בדיוק פעם אחת: צעדים.
תשובה: .
שאלה 7 · העמסה מול דריסה ומעקב פלט
נתון פרויקט שהוגדרו בו שלוש מחלקות Employee, Manager, Intern ומחלקה Driver, כך:
public class Employee {
private int seniority; // ותק
public Employee(int seniority) {
this.seniority = seniority;
}
public int getSeniority() {
return this.seniority;
}
public boolean check(Employee e) {
System.out.println("EmpCheck");
return this.seniority > e.seniority;
}
}
public class Manager extends Employee {
public Manager(int seniority) {
super(seniority);
}
public boolean check(Manager m) {
System.out.println("MgrCheck");
return this.getSeniority() == m.getSeniority();
}
}
public class Intern extends Employee {
private int mentorId;
public Intern(int seniority, int mentorId) {
super(seniority);
this.mentorId = mentorId;
}
public boolean check(Employee e) {
System.out.println("IntCheck");
if (!(e instanceof Intern)) {
return true;
}
Intern other = (Intern) e;
return this.mentorId == other.mentorId;
}
}
public class Driver
{
public static void main(String[] args)
{
Employee e1 = new Manager(15);
Manager m1 = new Manager(15);
Employee e2 = new Employee(10);
Employee i1 = new Intern(2, 800);
Intern i2 = new Intern(2, 900);
Intern i3 = new Intern(5, 800);
(1) System.out.println(e1.check(m1));
(2) System.out.println(m1.check(e1));
(3) System.out.println(m1.check(m1));
(4) System.out.println(i1.check(e2));
(5) System.out.println(i1.check(i2));
(6) System.out.println(i1.check(i3));
(7) System.out.println(e2.check(i1));
}
}public class Employee {
private int seniority; // ותק
public Employee(int seniority) {
this.seniority = seniority;
}
public int GetSeniority() {
return this.seniority;
}
public virtual bool Check(Employee e) {
Console.WriteLine("EmpCheck");
return this.seniority > e.seniority;
}
}
public class Manager : Employee {
public Manager(int seniority): base(seniority) {
}
public bool Check(Manager m) {
Console.WriteLine("MgrCheck");
return this.GetSeniority() == m.GetSeniority();
}
}
public class Intern : Employee {
private int mentorId;
public Intern(int seniority, int mentorId): base(seniority){
this.mentorId = mentorId;
}
public override bool Check(Employee e) {
Console.WriteLine("IntCheck");
if (!(e is Intern)) {
return true;
}
Intern other = (Intern) e;
return this.mentorId == other.mentorId;
}
}
public class Driver
{
public static void Main(string[] args)
{
Employee e1 = new Manager(15);
Manager m1 = new Manager(15);
Employee e2 = new Employee(10);
Employee i1 = new Intern(2, 800);
Intern i2 = new Intern(2, 900);
Intern i3 = new Intern(5, 800);
(1) Console.WriteLine(e1.Check(m1));
(2) Console.WriteLine(m1.Check(e1));
(3) Console.WriteLine(m1.Check(m1));
(4) Console.WriteLine(i1.Check(e2));
(5) Console.WriteLine(i1.Check(i2));
(6) Console.WriteLine(i1.Check(i3));
(7) Console.WriteLine(e2.Check(i1));
}
}עבור כל אחת מהפקודות 1–7 כתבו מה יהיה הפלט של הפקודה.
נתונה הפקודה: `System.out.println(i1.check(XXX))` (ב-C#: `Console.WriteLine(i1.Check(XXX))`) כאשר XXX הוא משתנה שהוגדר בפעולה הראשית main במחלקה Driver.
כתבו את כל המשתנים שאפשר לשים במקום XXX כדי שלאחר ביצוע הפקודה יודפס הפלט "IntCheck false".
◂ פתרון מלא לשאלה 7
סעיף א
(1) EmpCheck, false; (2) EmpCheck, false; (3) MgrCheck, true; (4) IntCheck, true; (5) IntCheck, false; (6) IntCheck, true; (7) EmpCheck, true. (ב-C# הערכים מודפסים True/False.)
1. בזמן הידור המהדר בוחר את חתימת הפעולה לפי הטיפוס המוצהר של ההפניה שעליה קוראים ולפי הטיפוס המוצהר של הארגומנט - מבין הפעולות שקיימות בטיפוס המוצהר, הגרסה המתאימה ביותר.
2. בזמן ריצה - אם החתימה שנבחרה נדרסה (override) במחלקה של העצם בפועל, מתבצעת הגרסה הדורסת.
3. ב-Manager הפעולה `check(Manager m)` מקבלת פרמטר מטיפוס אחר מזה של `check(Employee e)`, ולכן היא העמסה (overloading) ולא דריסה: למחלקה Manager יש שתי פעולות check - זו שירשה מ-Employee וזו החדשה. (ב-C# זה בולט: היא אינה מסומנת override.)
4. ב-Intern הפעולה `check(Employee e)` היא דריסה של הפעולה של Employee (ב-C#: virtual / override).
ערכי העצמים: e1 - Manager עם ותק 15; m1 - Manager עם ותק 15; e2 - Employee עם ותק 10; i1 - Intern (ותק 2, mentorId 800); i2 - Intern (2, 900); i3 - Intern (5, 800).
כל פקודה מדפיסה שתי שורות: קודם ההודעה שבתוך check, ואחר כך הערך שהפעולה מחזירה.
•(1) ההפניה e1 מוצהרת Employee, ובמחלקה Employee יש רק `check(Employee)`, ולכן זו החתימה שנבחרת (m1 הוא Employee). בזמן ריצה העצם הוא Manager, אבל Manager לא דורסת את `check(Employee)` - מתבצעת הגרסה של Employee.
•(2) ההפניה m1 מוצהרת Manager, אבל הארגומנט e1 מוצהר Employee, ולכן `check(Manager)` אינה מתאימה (אי אפשר להעביר Employee לפרמטר Manager בלי המרה). נבחרת `check(Employee)` שירשה Manager מ-Employee.
•(3) גם ההפניה וגם הארגומנט מוצהרים Manager: שתי הגרסאות מתאימות, ו-`check(Manager)` היא המתאימה ביותר.
•(4)-(6) i1 מוצהר Employee, ולכן נבחרת `check(Employee)`; בזמן ריצה העצם הוא Intern שדורס אותה, ולכן מודפס IntCheck. בפקודה (4) e2 אינו Intern ומוחזר true; ב-(5) ו-(6) משווים את mentorId.
•(7) e2 הוא עצם Employee - מתבצעת הגרסה של Employee: 10 > 2.
EmpCheck
false
EmpCheck
false
MgrCheck
true
IntCheck
true
IntCheck
false
IntCheck
true
EmpCheck
true(ב-C# הפקודה Console.WriteLine מדפיסה ערך בוליאני כ-True / False, באות גדולה.)
תשובה: (1) EmpCheck false; (2) EmpCheck false; (3) MgrCheck true; (4) IntCheck true; (5) IntCheck false; (6) IntCheck true; (7) EmpCheck true.
סעיף ב
רק i2.
נתון: i1 מוצהר Employee ובפועל Intern עם mentorId = 800. מבוקש: המשתנים XXX שעבורם מודפס IntCheck ואחריו false.
1. כל המשתנים ב-main (e1, m1, e2, i1, i2, i3) הם מטיפוס Employee או יורשים ממנו, ולכן הקריאה `i1.check(XXX)` עוברת הידור עם החתימה `check(Employee)`. בזמן ריצה מתבצעת הגרסה הדורסת של Intern, ולכן תמיד מודפס קודם IntCheck.
2. הערך המוחזר:
•אם XXX אינו Intern - מוחזר true. כך עבור e1, m1 (Manager) ו-e2 (Employee).
•אם XXX הוא Intern - מוחזר `800 == XXX.mentorId`.
3. העצמים מטיפוס Intern: i1 (mentorId 800 → true), i2 (900 → false), i3 (800 → true).
4. לכן false מתקבל רק עבור i2.
תשובה: המשתנה היחיד הוא i2.
שאלה 8 · רקורסיה בשרשרת ובעץ: הוספה לסוף ורמה
הפעולה first שלפניכם מקבלת הפניה ch לחוליה הראשונה של שרשרת החוליות של מספרים שלמים ומספר שלם x.
public static Node<Integer> first(Node<Integer> ch, int x){
if(ch == null)
return new Node<Integer>(x);
ch.setNext(first(ch.getNext(),x));
return ch;
}public static Node<int> First(Node<int> ch, int x){
if(ch == null)
return new Node<int>(x);
ch.SetNext(First(ch.GetNext(),x));
return ch;
}נתונה שרשרת החוליות: ch ->8→7→9→15→4
עקבו אחרי זימון הפעולה ch = first(ch, 3) ורשמו איך תיראה השרשרת אחרי ביצוע הפעולה.
מה מבצעת הפעולה first באופן כללי?
כתבו את הפעולה first בצורה הלא רקורסיבית.

הפעולה second שלפניכם מקבלת הפניה לשורש של עץ בינארי ומספר שלם וחיובי k.
public static Node<Integer> second(BinNode<Integer> bt, int k){
Node<Integer> list = third(bt, null, k);
return list;
}
public static Node<Integer> third(BinNode<Integer> bt,
Node<Integer> list, int k) {
if(bt!=null)
{
if(k>0)
{
list = third(bt.getLeft(), list, k-1);
list = third(bt.getRight(), list, k-1);
}
else
list = first(list, bt.getValue());
}
return list;
}public static Node<int> Second(BinNode<int> bt, int k){
Node<int> list = Third(bt, null, k);
return list;
}
public static Node<int> Third(BinNode<int> bt, Node<int> list,
int k) {
if(bt!=null)
{
if(k>0)
{
list = Third(bt.GetLeft(), list, k-1);
list = Third(bt.GetRight(), list, k-1);
}
else
list = First(list, bt.GetValue());
}
return list;
}עקבו אחרי זימון הפעולה second(bt,3) ורשמו מה תחזיר הפעולה עבור העץ שלפניכם:
מה מבצעת הפעולה second באופן כללי?
◂ פתרון מלא לשאלה 8
סעיף א
ch -> 8 → 7 → 9 → 15 → 4 → 3
הפעולה רקורסיבית: כל זימון מטפל בחוליה אחת ופונה לשאר השרשרת. נעקוב אחרי הזימונים (ירידה ברקורסיה) ואחר כך אחרי החזרות (עלייה).
בחזרה: זימון 5 מבצע `4.setNext(3)` ומחזיר את החוליה 4; זימון 4 מבצע `15.setNext(4)` (אותה הפניה כמו קודם) ומחזיר את 15; וכך הלאה עד זימון 1, שמחזיר את החוליה 8. כל החוליות הקיימות נשארות מחוברות כמו קודם, ובסוף נוספה החוליה 3.
תשובה: ch -> 8 → 7 → 9 → 15 → 4 → 3
מוסיפה חוליה חדשה עם הערך x לסוף השרשרת (אם השרשרת ריקה - יוצרת שרשרת של חוליה אחת) ומחזירה הפניה לחוליה הראשונה.
1. מקרה הבסיס: שרשרת ריקה (`ch == null`) - נוצרת חוליה חדשה עם x, והיא כל השרשרת.
2. צעד הרקורסיה: מוסיפים את x לסוף השרשרת שמתחילה בחוליה הבאה, ומחברים את התוצאה אחרי ch. ראש השרשרת לא משתנה, ולכן מוחזר ch.
3. לכן, באינדוקציה על אורך השרשרת, הפעולה מוסיפה את x כחוליה אחרונה ושומרת את סדר החוליות הקיימות.
תשובה: הפעולה מוסיפה חוליה עם הערך x לסוף השרשרת ומחזירה את ראש השרשרת.
סעיף ב
יוצרים חוליה חדשה; אם השרשרת ריקה מחזירים אותה; אחרת מתקדמים בלולאה עד החוליה האחרונה, מחברים אחריה את החדשה ומחזירים את ch.
הרעיון: במקום לרדת ברקורסיה עד סוף השרשרת, נתקדם בלולאה עד החוליה האחרונה (זו ש-`getNext()` שלה הוא null) ונחבר אחריה את החוליה החדשה.
1. יוצרים חוליה חדשה `node` עם הערך x.
2. אם `ch == null` - השרשרת ריקה, והחוליה החדשה היא השרשרת: מחזירים `node`.
3. אחרת מתקדמים עם `p` מ-ch כל עוד יש חוליה הבאה.
4. `p.setNext(node)` ומחזירים את `ch` (ראש השרשרת לא השתנה).
public static Node<Integer> first(Node<Integer> ch, int x)
{
Node<Integer> node = new Node<Integer>(x);
if (ch == null) // שרשרת ריקה: החוליה החדשה היא כל השרשרת
return node;
Node<Integer> p = ch;
while (p.getNext() != null) // התקדמות עד החוליה האחרונה
p = p.getNext();
p.setNext(node); // חיבור החוליה החדשה בסוף
return ch;
}public static Node<int> First(Node<int> ch, int x)
{
Node<int> node = new Node<int>(x);
if (ch == null) // שרשרת ריקה: החוליה החדשה היא כל השרשרת
return node;
Node<int> p = ch;
while (p.GetNext() != null) // התקדמות עד החוליה האחרונה
p = p.GetNext();
p.SetNext(node); // חיבור החוליה החדשה בסוף
return ch;
}בדיקה: עבור ch = 8 → 7 → 9 → 15 → 4 ו-x = 3, הלולאה עוצרת בחוליה 4, ומתקבל 8 → 7 → 9 → 15 → 4 → 3 - כמו בפעולה הרקורסיבית.
תשובה: הפעולה שלמעלה.
סעיף ג
שרשרת: 6 → 2 → 3
הרעיון של third: בכל ירידה לילד, k קטן ב-1. כשמגיעים לחוליה עם `k == 0` - היא נמצאת בדיוק 3 רמות מתחת לשורש, והערך שלה מתווסף לסוף השרשרת `list` בעזרת first. חוליה עם `k == 0` לא ממשיכה לרדת לילדיה. הסדר: קודם תת-העץ השמאלי ואחר כך הימני, ולכן החוליות נאספות משמאל לימין.
מבנה העץ: השורש 7; ילדיו 1 (שמאלי) ו-5 (ימני). לחוליה 1 ילדים 1 (שמאלי) ו-7 (ימני); לחוליה 7 זו ילד ימני 6. לחוליה 5 ילד ימני 2; לחוליה 2 ילדים 2 (שמאלי) ו-3 (ימני); לחוליה 2 השמאלית ילד שמאלי 6.
מעקב (רק הזימונים עם חוליה שאינה null):
החוליה 6 שבתחתית (ילד של 2 השמאלית) נמצאת ברמה 4, והרקורסיה לא מגיעה אליה, כי בחוליה 2 שמעליה כבר k = 0.
תשובה: הפעולה מחזירה הפניה לשרשרת 6 → 2 → 3.
מחזירה שרשרת חדשה עם הערכים של כל החוליות שברמה k של העץ (השורש ברמה 0), לפי הסדר משמאל לימין; אם אין חוליות ברמה k - מחזירה null.
1. third יורדת מהשורש ומקטינה את k ב-1 בכל ירידה, ולכן החוליות שבהן `k == 0` הן בדיוק החוליות שבעומק k מהשורש (השורש בעומק 0).
2. רק ערכי החוליות האלה מתווספים, כל אחד לסוף השרשרת (first).
3. הסריקה היא קודם תת-עץ שמאלי ואחר כך ימני, ולכן הערכים מופיעים בשרשרת לפי סדרם ברמה משמאל לימין.
4. second מתחילה את third עם שרשרת ריקה (null) ומחזירה את התוצאה; אם אין חוליות ברמה k מוחזר null.
לדוגמה, בעץ שבשאלה: k=1 → 1, 5; k=2 → 1, 7, 2; k=3 → 6, 2, 3.
תשובה: second מחזירה שרשרת של ערכי כל החוליות ברמה k של העץ, משמאל לימין.
שאלה 9 · מחלקות מושב וניהול כנס: רישום משתתפים
מערכת הניהול של תהליך הרישום לכנס מדעי כוללת את שתי המחלקות הבאות: המחלקה "מושב" (Session) והמחלקה "ניהול כנס" (ConferenceManager).
למחלקה "מושב" (Session) התכונות הבאות:
•שם המושב – nameSession
•תור שמות המשתתפים – participants
•קיבולת מקסימלית – maxCapacity
•מספר המשתתפים בפועל – numParticipants
•סימן אם המושב הוא "קריטי" – isCritical. המושב הוא קריטי, אם נשארו פחות מחמישה מקומות פנויים.
למחלקה "ניהול כנס" ConferenceManager שתי תכונות: שם הכנס ורשימת מושבים:
public class ConferenceManager {
private String nameConference;
private Node<Session> sessions;
}public class ConferenceManager {
private string nameConference;
private Node<Session> sessions;
}כתבו במחלקה Session פעולה בונה המקבלת את שם המושב ואת הקיבולת המקסימלית. הפעולה מאתחלת מושב ללא משתתפים:
public Session (String nameSession, int maxCapacity)public Session (string nameSession, int maxCapacity)ניתן להוסיף משתתף למושב רק אם יש מקום פנוי והמשתתף עדיין לא קיים ברשימת המשתתפים הרשומים במושב זה.
כתבו במחלקה Session פעולה המקבלת שם משתתף ומנסה לרשום אותו למושב. אם הרישום אפשרי, הפעולה תוסיף את שם המשתתף לסוף התור, תעדכן את התכונות הרלוונטיות ותחזיר ערך true. אם הרישום אינו אפשרי, הפעולה תדפיס הודעה מתאימה ותחזיר ערך false.
כותרת הפעולה:
public boolean registerParticipant(String name)public bool RegisterParticipant(string name)עקב ביקוש רב, הוחלט להחמיר את כללי הרישום למושבים "קריטיים": משתתף יכול להירשם למושב קריטי רק אם הוא אינו רשום בשום מושב קריטי אחר.
כתבו במחלקה ConferenceManager פעולה המקבלת שם משתתף ושם מושב. הפעולה תבדוק אם ניתן לרשום את המשתתף למושב. אם כן – הפעולה תבצע רישום ותחזיר ערך true. אם אין מושב רצוי או שהרישום אינו אפשרי, הפעולה תדפיס הודעה מתאימה ותחזיר ערך false.
כותרת הפעולה:
public boolean tryRegister(String nameSession, String name)public bool TryRegister(string nameSession, string name)◂ פתרון מלא לשאלה 9
סעיף א
הפעולה הבונה שלהלן: שומרת את השם והקיבולת, יוצרת תור משתתפים ריק, numParticipants = 0, ו-isCritical = (maxCapacity < 5).
מה צריך לאתחל: מושב חדש הוא מושב ללא משתתפים, ולכן:
1. `nameSession` ו-`maxCapacity` - מהפרמטרים.
2. `participants` - תור חדש וריק (בלי יצירת התור, הוספת משתתף בהמשך תיכשל).
3. `numParticipants = 0`.
4. `isCritical` - המושב קריטי אם נשארו בו פחות מחמישה מקומות פנויים. במושב ריק מספר המקומות הפנויים הוא maxCapacity, ולכן `isCritical = maxCapacity < 5`.
public class Session {
private String nameSession;
private Queue<String> participants;
private int maxCapacity;
private int numParticipants;
private boolean isCritical;
public Session(String nameSession, int maxCapacity)
{
this.nameSession = nameSession;
this.maxCapacity = maxCapacity;
this.participants = new Queue<String>(); // מושב ללא משתתפים
this.numParticipants = 0;
this.isCritical = maxCapacity < 5; // פחות מחמישה מקומות פנויים
}
...
}public class Session {
private string nameSession;
private Queue<string> participants;
private int maxCapacity;
private int numParticipants;
private bool isCritical;
public Session(string nameSession, int maxCapacity)
{
this.nameSession = nameSession;
this.maxCapacity = maxCapacity;
this.participants = new Queue<string>(); // מושב ללא משתתפים
this.numParticipants = 0;
this.isCritical = maxCapacity < 5; // פחות מחמישה מקומות פנויים
}
...
}תשובה: הפעולה הבונה שלמעלה.
סעיף ב
registerParticipant שלהלן: אם המושב מלא או שהשם כבר בתור (בדיקה בפעולת עזר isRegistered שמשחזרת את התור) - הודעה ו-false; אחרת מוסיפה לסוף התור, מגדילה את numParticipants, מעדכנת את isCritical ומחזירה true.
1. יש מקום פנוי: `numParticipants < maxCapacity`.
2. המשתתף עוד לא רשום: צריך לחפש את השם בתור `participants`. בתור אפשר לראות רק את הראש, ולכן נוציא את כל השמות לתור עזר, נבדוק כל שם, ונחזיר אותם לתור המקורי באותו סדר. את החיפוש נכתוב כפעולת עזר `isRegistered(name)` - נשתמש בה גם בסעיף ג'. השוואת מחרוזות נעשית ב-`equals` (ב-Java) או ב-`==` (ב-C#).
•מוסיפים את השם לסוף התור (`insert`);
•מגדילים את `numParticipants` ב-1;
•מעדכנים את `isCritical`: מספר המקומות הפנויים הוא `maxCapacity - numParticipants`, והמושב קריטי אם הוא קטן מ-5;
•מחזירים true.
אם אחד התנאים לא מתקיים - מדפיסים הודעה שמסבירה מה הבעיה ומחזירים false.
// הפעולה מחזירה true אם name רשום כבר בתור המשתתפים (התור משוחזר)
public boolean isRegistered(String name)
{
boolean found = false;
Queue<String> temp = new Queue<String>();
while (!participants.isEmpty())
{
String s = participants.remove();
if (s.equals(name))
found = true;
temp.insert(s);
}
while (!temp.isEmpty())
participants.insert(temp.remove());
return found;
}
public boolean registerParticipant(String name)
{
if (numParticipants >= maxCapacity)
{
System.out.println("The session " + nameSession + " is full");
return false;
}
if (isRegistered(name))
{
System.out.println(name + " is already registered to " + nameSession);
return false;
}
participants.insert(name); // הוספה לסוף התור
numParticipants++;
isCritical = (maxCapacity - numParticipants) < 5; // עדכון הסימון
return true;
} // הפעולה מחזירה true אם name רשום כבר בתור המשתתפים (התור משוחזר)
public bool IsRegistered(string name)
{
bool found = false;
Queue<string> temp = new Queue<string>();
while (!participants.IsEmpty())
{
string s = participants.Remove();
if (s == name)
found = true;
temp.Insert(s);
}
while (!temp.IsEmpty())
participants.Insert(temp.Remove());
return found;
}
public bool RegisterParticipant(string name)
{
if (numParticipants >= maxCapacity)
{
Console.WriteLine("The session " + nameSession + " is full");
return false;
}
if (IsRegistered(name))
{
Console.WriteLine(name + " is already registered to " + nameSession);
return false;
}
participants.Insert(name); // הוספה לסוף התור
numParticipants++;
isCritical = (maxCapacity - numParticipants) < 5; // עדכון הסימון
return true;
}דוגמה: במושב עם קיבולת 3: רישום a, b, c מצליח (true), ואחרי הרישום הראשון כבר נשארים 2 מקומות פנויים, כך שהמושב קריטי. ניסיון לרשום את a שוב, או משתתף רביעי - מדפיס הודעה ומחזיר false.
תשובה: הפעולות isRegistered ו-registerParticipant שלמעלה.
סעיף ג
tryRegister שלהלן: מוצאת את המושב לפי שמו (אם אין - הודעה ו-false); אם המושב קריטי - בודקת שהמשתתף לא רשום במושב קריטי אחר (אחרת הודעה ו-false); ואז מחזירה את התוצאה של registerParticipant.
1. מציאת המושב: עוברים על שרשרת המושבים `sessions` ומחפשים מושב ששמו (`getNameSession()`) שווה ל-nameSession. אם אין כזה - מדפיסים הודעה ומחזירים false.
2. הכלל החדש למושב קריטי: אם המושב שנמצא (`target`) קריטי (`getIsCritical()`), עוברים שוב על כל המושבים, ולכל מושב `s` אחר (`s != target`) שהוא קריטי בודקים אם המשתתף רשום בו (`s.isRegistered(name)` מסעיף ב'). אם כן - מדפיסים הודעה ומחזירים false. אם המושב המבוקש אינו קריטי, הכלל החדש לא חל עליו.
3. הרישום עצמו: קוראים ל-`target.registerParticipant(name)` (כנדרש), שבודקת את שני התנאים הרגילים - מקום פנוי ושהמשתתף עוד לא רשום למושב זה - ומבצעת את הרישום. מחזירים את מה שהיא מחזירה (true או false, וההודעה במקרה של כישלון מודפסת בתוכה).
public boolean tryRegister(String nameSession, String name)
{
// 1. חיפוש המושב המבוקש ברשימת המושבים
Session target = null;
for (Node<Session> p = sessions; p != null && target == null; p = p.getNext())
if (p.getValue().getNameSession().equals(nameSession))
target = p.getValue();
if (target == null)
{
System.out.println("No session named " + nameSession);
return false;
}
// 2. אם המושב קריטי - בדיקה שהמשתתף אינו רשום במושב קריטי אחר
if (target.getIsCritical())
{
for (Node<Session> p = sessions; p != null; p = p.getNext())
{
Session s = p.getValue();
if (s != target && s.getIsCritical() && s.isRegistered(name))
{
System.out.println(name + " is already registered to the critical session "
+ s.getNameSession());
return false;
}
}
}
// 3. רישום בפועל (בדיקת מקום פנוי ורישום כפול נעשית ב-registerParticipant)
return target.registerParticipant(name);
} public bool TryRegister(string nameSession, string name)
{
// 1. חיפוש המושב המבוקש ברשימת המושבים
Session target = null;
for (Node<Session> p = sessions; p != null && target == null; p = p.GetNext())
if (p.GetValue().GetNameSession() == nameSession)
target = p.GetValue();
if (target == null)
{
Console.WriteLine("No session named " + nameSession);
return false;
}
// 2. אם המושב קריטי - בדיקה שהמשתתף אינו רשום במושב קריטי אחר
if (target.GetIsCritical())
{
for (Node<Session> p = sessions; p != null; p = p.GetNext())
{
Session s = p.GetValue();
if (s != target && s.GetIsCritical() && s.IsRegistered(name))
{
Console.WriteLine(name + " is already registered to the critical session "
+ s.GetNameSession());
return false;
}
}
}
// 3. רישום בפועל (בדיקת מקום פנוי ורישום כפול נעשית ב-RegisterParticipant)
return target.RegisterParticipant(name);
}דוגמה: בכנס עם המושבים W (קיבולת 30, לא קריטי), C1 (קיבולת 3, קריטי) ו-C2 (קיבולת 4, קריטי):
•tryRegister("C1", "dana") → true.
•tryRegister("C2", "dana") → C2 קריטי, ו-dana רשומה במושב הקריטי C1: הודעה ו-false.
•tryRegister("W", "dana") → W אינו קריטי: true.
•tryRegister("X", "dana") → אין מושב X: הודעה ו-false.
תשובה: הפעולה tryRegister שלמעלה.