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

כתבו פעולה המקבלת מחסנית של מספרים שלמים וחיוביים `st` וספרה `k`. הפעולה תבדוק אם מחסנית היא "מחסנית תקינה" עבור ספרה זו. אם כן – הפעולה תחזיר ערך `true`, ואם לא – הפעולה תחזיר ערך `false`.
כותרת הפעולה:
public static boolean isProperK(Stack<Integer> st, int k)public static bool IsProperK(Stack<int> st, int k)כתבו פעולה המקבלת מחסנית של מספרים שלמים `st` וספרה `k`. הפעולה תבדוק אם המחסנית היא "מחסנית תקינה עבור k". אם כן – הפעולה לא תבצע דבר, ואם לא – הפעולה תשנה את סדר המספרים במחסנית כך שהיא תהיה "תקינה עבור k".
אפשר להניח שבמחסנית יש לפחות מספר אחד אשר מתחיל ב-`k`.
כותרת הפעולה:
public static void fixIt(Stack<Integer> st, int k)public static void FixIt(Stack<int> st, int k)מהי סיבוכיות הפעולות שכתבתם בסעיפים א'–ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
סופרים את רצפי המספרים שמתחילים ב-k; המחסנית תקינה אם ורק אם יש בדיוק רצף אחד (המחסנית משוחזרת).
נתון: מחסנית `st` של מספרים שלמים וחיוביים וספרה `k`.
מבוקש: להחזיר true אם יש לפחות מספר אחד שמתחיל ב-`k`, וכל המספרים שמתחילים ב-`k` צמודים זה לזה (רצף אחד).
הרעיון: שני התנאים יחד שקולים לתנאי אחד: מספר הרצפים של מספרים שמתחילים ב-`k` שווה בדיוק 1. אם אין אף מספר כזה – יש 0 רצפים; אם המספרים מפוזרים – יש 2 רצפים או יותר.
1. פעולת עזר `firstDigit` מחזירה את הספרה הראשונה של מספר: מחלקים ב-10 כל עוד המספר גדול מ-9 (למשל ).
2. מוציאים את איברי המחסנית אחד-אחד ומעבירים אותם למחסנית עזר `temp` (כדי לשחזר בסוף).
3. לכל איבר בודקים אם הוא מתחיל ב-`k` (`curK`). אם הוא מתחיל ב-`k` והאיבר שלפניו לא התחיל ב-`k` – כאן מתחיל רצף חדש, ומגדילים את `groups` ב-1.
4. מחזירים את האיברים מ-`temp` ל-`st` – המחסנית חוזרת למצבה המקורי.
5. מחזירים `groups == 1`.
בדיקה עם הדוגמה (מראש המחסנית): .
•עבור : הרצף – רצף אחד, true. כך גם (הרצף ) ו- (רק ).
•עבור : הרצפים ואחר כך ואחר כך – שלושה רצפים, false.
•עבור : אין אף מספר שמתחיל ב-7 – אפס רצפים, false.
// הספרה השמאלית (הראשונה) של מספר שלם וחיובי
public static int firstDigit(int x)
{
while (x > 9)
x = x / 10;
return x;
}
public static boolean isProperK(Stack<Integer> st, int k)
{
Stack<Integer> temp = new Stack<Integer>();
int groups = 0; // מספר הרצפים של מספרים שמתחילים ב-k
boolean prevK = false; // האם המספר הקודם התחיל ב-k
while (!st.isEmpty())
{
int x = st.pop();
temp.push(x);
boolean curK = (firstDigit(x) == k);
if (curK && !prevK) // מתחיל רצף חדש
groups++;
prevK = curK;
}
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return groups == 1;
}// הספרה השמאלית (הראשונה) של מספר שלם וחיובי
public static int FirstDigit(int x)
{
while (x > 9)
x = x / 10;
return x;
}
public static bool IsProperK(Stack<int> st, int k)
{
Stack<int> temp = new Stack<int>();
int groups = 0; // מספר הרצפים של מספרים שמתחילים ב-k
bool prevK = false; // האם המספר הקודם התחיל ב-k
while (!st.IsEmpty())
{
int x = st.Pop();
temp.Push(x);
bool curK = (FirstDigit(x) == k);
if (curK && !prevK) // מתחיל רצף חדש
groups++;
prevK = curK;
}
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return groups == 1;
}תשובה: סופרים את מספר הרצפים של מספרים שמתחילים ב-`k` (מעבר אחד על המחסנית ושחזורה); המחסנית תקינה אם ורק אם יש בדיוק רצף אחד.
סעיף ב
אם לא תקינה: מפרידים לשתי מחסניות עזר ומחזירים קודם את השאר ואז את המתחילים ב-k – הם ברצף אחד בראש המחסנית.
נתון: מחסנית `st` וספרה `k`; מותר להניח שיש לפחות מספר אחד שמתחיל ב-`k`.
מבוקש: אם המחסנית אינה תקינה עבור `k` – לסדר אותה מחדש כך שכל המספרים שמתחילים ב-`k` יהיו ברצף אחד.
הרעיון: מספיק לאסוף את כל המספרים שמתחילים ב-`k` למקום אחד. נעביר אותם לראש המחסנית, ואת כל השאר נשאיר מתחתם.
1. בודקים בעזרת `isProperK` מסעיף א' (שמשחזרת את המחסנית). אם התשובה true – יוצאים בלי לשנות דבר.
2. מרוקנים את `st`: כל מספר שמתחיל ב-`k` עובר למחסנית `withK`, וכל מספר אחר למחסנית `others`.
3. מחזירים ל-`st` קודם את איברי `others` – הם יהיו בתחתית, ובסדרם היחסי המקורי (כל העברה בין מחסניות הופכת סדר, ושתי העברות מחזירות אותו).
4. אחריהם מחזירים את איברי `withK` – הם יושבים יחד בראש המחסנית, כלומר ברצף אחד, ולכן המחסנית תקינה עבור `k` (יש לפחות מספר אחד כזה לפי ההנחה).
דוגמה: עבור המחסנית שבשאלה ו- מתקבלת (מהראש): – ארבעת המספרים שמתחילים ב-3 צמודים.
public static void fixIt(Stack<Integer> st, int k)
{
if (isProperK(st, k))
return; // המחסנית כבר תקינה - לא עושים דבר
Stack<Integer> withK = new Stack<Integer>();
Stack<Integer> others = new Stack<Integer>();
while (!st.isEmpty())
{
int x = st.pop();
if (firstDigit(x) == k)
withK.push(x);
else
others.push(x);
}
while (!others.isEmpty()) // קודם השאר (יהיו בתחתית)
st.push(others.pop());
while (!withK.isEmpty()) // ואז כל המתחילים ב-k ברצף אחד בראש
st.push(withK.pop());
}public static void FixIt(Stack<int> st, int k)
{
if (IsProperK(st, k))
return; // המחסנית כבר תקינה - לא עושים דבר
Stack<int> withK = new Stack<int>();
Stack<int> others = new Stack<int>();
while (!st.IsEmpty())
{
int x = st.Pop();
if (FirstDigit(x) == k)
withK.Push(x);
else
others.Push(x);
}
while (!others.IsEmpty()) // קודם השאר (יהיו בתחתית)
st.Push(others.Pop());
while (!withK.IsEmpty()) // ואז כל המתחילים ב-k ברצף אחד בראש
st.Push(withK.Pop());
}תשובה: אם המחסנית אינה תקינה – מפרידים לשתי מחסניות עזר (מתחילים ב-`k` / השאר), מחזירים קודם את השאר ואחריהם את המתחילים ב-`k`, וכך הם ברצף אחד בראש המחסנית.
סעיף ג
לשתי הפעולות
נסמן ב- את מספר האיברים במחסנית, ונזכור שכל מספר מוגבל בגודלו (`int`), ולכן מציאת הספרה הראשונה שלו היא לכל היותר 10 חלוקות – .
1. סעיף א': כל איבר מוצא פעם אחת ומוחזר פעם אחת; לכל איבר מספר קבוע של פעולות. סך הכול .
2. סעיף ב': זימון אחד של `isProperK` – ; אחריו כל איבר עובר למחסנית עזר ובחזרה – עוד . סך הכול .
תשובה: שתי הפעולות בסיבוכיות – מספר קבוע של מעברים על המחסנית.
שאלה 2 · מספר גדול כשרשרת ספרות
באוניברסיטה מפתחים מערכת למעקב אחר כוכבים חדשים שמתגלים מדי יום. מספר הכוכבים הוא גדול מאוד, לכן הוחלט לייצג את המספר באמצעות שרשרת חוליות של ספרות. סדר החוליות הוא לפי סדר הופעת הספרות במספר, כך שספרת האחדות היא החוליה האחרונה בשרשרת.
לדוגמה:
•השרשרת מייצגת את המספר 258.
•השרשרת מייצגת את המספר 120,945.
המחלקה StarCount אחראית על ספירת הכוכבים ביקום.
public class StarCount
{
private Node<Integer> number;
}public class StarCount
{
private Node<int> number;
}הערך ההתחלתי של מספר הכוכבים ביקום הוזן באופן ידני ובגלל טעויות הקלדה בחלק מהחוליות בשרשרת `number` הופיעו מספרים שאינם חד-ספרתיים.
כתבו פעולה פנימית המתקנת את שרשרת החוליות `number` כך שכל החוליות יכילו ספרה אחת.
חוליה המכילה מספר דו-ספרתי תפוצל לשתי חוליות, חוליה מכילה מספר תלת-ספרתי תפוצל לשלוש חוליות וכן הלאה.
השרשרת:
תהפוך לשרשרת:
כותרת הפעולה:
public void fixNumber()public void FixNumber()בכל יום מתגלים כוכבים חדשים על ידי טלסקופים הפזורים במקומות שונים בכדור הארץ.
כדי לשמור על הנתונים מעודכנים, נדרש לאפשר ביצוע של פעולות חשבון על המספרים המיוצגים על ידי שרשרת החוליות.
הפעולה הבסיסית ביותר הנדרשת היא `addOne` - פעולה המגדילה ב-1 את מספר הכוכבים.
ממשו את הפעולה הפנימית addOne המגדילה את מספר הכוכבים ב-1.
מהי סיבוכיות הפעולה `addOne` שכתבתם בסעיף ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
כל חוליה עם ערך גדול מ-9 מפוצלת: ספרותיה נכנסות אחריה (מהאחדות והלאה, כל אחת מיד אחרי החוליה), ובחוליה נשארת הספרה השמאלית.
נתון: שרשרת `number` שבחלק מחוליותיה יש מספר רב-ספרתי.
מבוקש: לפצל כל חוליה כזו לחוליות של ספרה אחת, בסדר הספרות במספר, בלי לשנות את שאר השרשרת.
הרעיון: עוברים על החוליות המקוריות. בחוליה עם ערך "מקלפים" את ספרת האחדות ומכניסים אותה בחוליה חדשה מיד אחרי החוליה הנוכחית, ומחלקים את ב-10. כל ספרה חדשה נכנסת לפני הספרות שכבר קולפו, ולכן בסוף הן מסודרות נכון. כשנשארת ספרה אחת – שמים אותה בחוליה עצמה.
1. שומרים מראש את `rest` – החוליה המקורית הבאה – כדי לא לעבור על החוליות החדשות שוב.
2. עבור : מכניסים 4 אחרי החוליה (), ; מכניסים 7 אחרי החוליה (), ; שמים 1 בחוליה: .
3. ממשיכים ל-`rest`.
בדיקה עם הדוגמה: הופכת ל-.
public void fixNumber()
{
Node<Integer> pos = this.number;
while (pos != null)
{
Node<Integer> rest = pos.getNext(); // החוליה המקורית הבאה
int val = pos.getValue();
while (val > 9) // מפצלים את הספרות מימין לשמאל
{
pos.setNext(new Node<Integer>(val % 10, pos.getNext()));
val = val / 10;
}
pos.setValue(val); // בחוליה עצמה נשארת הספרה השמאלית
pos = rest;
}
}public void FixNumber()
{
Node<int> pos = this.number;
while (pos != null)
{
Node<int> rest = pos.GetNext(); // החוליה המקורית הבאה
int val = pos.GetValue();
while (val > 9) // מפצלים את הספרות מימין לשמאל
{
pos.SetNext(new Node<int>(val % 10, pos.GetNext()));
val = val / 10;
}
pos.SetValue(val); // בחוליה עצמה נשארת הספרה השמאלית
pos = rest;
}
}תשובה: לכל חוליה עם ערך גדול מ-9 מכניסים אחריה את ספרותיה מהאחדות כלפי מעלה (כל אחת מיד אחרי החוליה), ובחוליה עצמה משאירים את הספרה השמאלית.
סעיף ב
הספרה האחרונה שאינה 9 גדלה ב-1 וכל הספרות שאחריה מתאפסות; אם כל הספרות 9 – חוליה 1 חדשה בראש וכל השאר 0.
נתון: שרשרת `number` של ספרות בודדות (הספרה המשמעותית ביותר ראשונה, האחדות אחרונה).
מבוקש: להגדיל את המספר ב-1 ישירות על השרשרת.
הרעיון: כמו בחיבור במחברת: מוסיפים 1 לספרת האחדות; ספרה 9 הופכת ל-0 ומעבירה "1 בדמיון" לספרה שמשמאלה. לכן:
•כל רצף ה-9 שבסוף המספר הופך ל-0;
•הספרה האחרונה שאינה 9 גדלה ב-1;
•אם כל הספרות הן 9 (למשל 99), כולן הופכות ל-0 ומוסיפים חוליה חדשה עם 1 בתחילת השרשרת (100).
השלבים:
1. עוברים על השרשרת וזוכרים ב-`lastNotNine` את החוליה האחרונה שערכה שונה מ-9.
2. אם נמצאה – מגדילים את ערכה ב-1; אחרת – יוצרים חוליה חדשה עם 1 בראש השרשרת.
3. כל החוליות שאחריה (כולן 9) מקבלות 0.
בדיקה עם הדוגמאות: הופכת ל-; הופכת ל-; הופכת ל-.
public void addOne()
{
Node<Integer> lastNotNine = null;
Node<Integer> pos = this.number;
while (pos != null) // מציאת הספרה האחרונה שאינה 9
{
if (pos.getValue() != 9)
lastNotNine = pos;
pos = pos.getNext();
}
if (lastNotNine == null) // כל הספרות הן 9
{
this.number = new Node<Integer>(1, this.number);
pos = this.number.getNext();
}
else
{
lastNotNine.setValue(lastNotNine.getValue() + 1);
pos = lastNotNine.getNext();
}
while (pos != null) // כל ה-9 שאחריה הופכים ל-0
{
pos.setValue(0);
pos = pos.getNext();
}
}public void AddOne()
{
Node<int> lastNotNine = null;
Node<int> pos = this.number;
while (pos != null) // מציאת הספרה האחרונה שאינה 9
{
if (pos.GetValue() != 9)
lastNotNine = pos;
pos = pos.GetNext();
}
if (lastNotNine == null) // כל הספרות הן 9
{
this.number = new Node<int>(1, this.number);
pos = this.number.GetNext();
}
else
{
lastNotNine.SetValue(lastNotNine.GetValue() + 1);
pos = lastNotNine.GetNext();
}
while (pos != null) // כל ה-9 שאחריה הופכים ל-0
{
pos.SetValue(0);
pos = pos.GetNext();
}
}תשובה: מוצאים את הספרה האחרונה שאינה 9, מגדילים אותה ב-1 ומאפסים את כל הספרות שאחריה; אם כל הספרות 9 – מוסיפים חוליה 1 בראש ומאפסים את כל השאר.
סעיף ג
נסמן ב- את מספר החוליות (הספרות) בשרשרת.
1. הלולאה הראשונה עוברת על כל השרשרת פעם אחת – .
2. הלולאה השנייה עוברת רק על החוליות שאחרי `lastNotNine` – לכל היותר חוליות, .
3. יצירת חוליה חדשה בראש השרשרת (אם צריך) – .
תשובה: – לכל היותר שני מעברים על שרשרת הספרות.
שאלה 3 · שחזור היררכיית ירושה מקטע קוד
נתון פרויקט שבו הוגדרו מחלקות `V, W, X, Y, Z`.
הפעולה `stam()` (ב-C#: `Stam()`) מומשה בשתי מחלקות.
במחלקה נוספת באותו פרויקט, בשם `Tester`, נכתב קטע הקוד הבא בפעולה `main`, והוא תקין:
V v1 = new V(9);
V v2 = new Y("9");
V v3 = new Z(new V(6));
W w1 = new W(z1, v2);
Y y1 = new Y("5");
Z z1 = new W(4, 1.1, 'Z', true);
Z z2 = new Z();
Z z3 = new X();
z2.stam(); // "Good" תקין ומדפיס
z3.stam(); // "Good" תקין ומדפיס
w1.stam(); // "Bad" תקין ומדפיסV v1 = new V(9);
V v2 = new Y("9");
V v3 = new Z(new V(6));
W w1 = new W(z1, v2);
Y y1 = new Y("5");
Z z1 = new W(4, 1.1, 'Z', true);
Z z2 = new Z();
Z z3 = new X();
z2.Stam(); // "Good" תקין ומדפיס
z3.Stam(); // "Good" תקין ומדפיס
w1.Stam(); // "Bad" תקין ומדפיסחמש הפקודות האלה גורמות לשגיאות:
X x1 = new W(); // שגיאת קומפילציה
v1.stam(); // שגיאת קומפילציה
y1.stam(); // שגיאת קומפילציה
((Z)y1).stam(); // שגיאת קומפילציה
((Z)v2).stam(); // שגיאת זמן ריצהX x1 = new W(); // שגיאת קומפילציה
v1.Stam(); // שגיאת קומפילציה
y1.Stam(); // שגיאת קומפילציה
((Z)y1).Stam(); // שגיאת קומפילציה
((Z)v2).Stam(); // שגיאת זמן ריצהשרטטו תרשים היררכיה UML המתאר עץ ירושה אפשרי עבור מחלקות הפרויקט.
ציינו באילו מחלקות מומשה הפעולה `stam()`.
כתבו את כותרות כל המחלקות וכותרות הפעולות הבונות (הבנאים) הנדרשות.
◂ פתרון מלא לשאלה 3
סעיף א
V בשורש; Y ו-Z יורשות מ-V; W ו-X יורשות מ-Z.
נתון: קטע קוד תקין וחמש פקודות שגויות.
מבוקש: עץ ירושה אפשרי של המחלקות `V, W, X, Y, Z`.
נסיק את הקשרים מכל שורה. השמה `A a = new B(...)` תקינה רק אם `B` היא `A` או יורשת ממנה.
1. `V v2 = new Y("9")` – לכן Y יורשת מ-V.
2. `V v3 = new Z(new V(6))` – לכן Z יורשת מ-V.
3. `Z z1 = new W(4, 1.1, 'Z', true)` – לכן W יורשת מ-Z.
4. `Z z3 = new X()` – לכן X יורשת מ-Z.
5. בדיקה מול השגיאות: `((Z)y1)` היא שגיאת קומפילציה – אכן Y ו-Z הן "אחיות" (שתיהן יורשות מ-V ואין ביניהן קשר ירושה), ולכן אי אפשר להמיר Y ל-Z. `((Z)v2)` עוברת קומפילציה (המרה כלפי מטה מ-V ל-Z מותרת), אבל בזמן ריצה `v2` הוא עצם מסוג Y – שגיאת זמן ריצה. `X x1 = new W()` – W אינה X (שתיהן אחיות תחת Z), וגם אין ל-W בנאי ריק.
6. X לא יכולה לרשת מ-W: אז `z3.stam()` הייתה מדפיסה "Bad" (של W), ולא "Good".
העץ: V בשורש; ל-V שני בנים – Y ו-Z; ל-Z שני בנים – W ו-X.
(הערה: בקוד שבשאלה `w1` נוצר בעזרת `z1` לפני ש-`z1` הוגדר; כדי שהקוד יהיה תקין, ההגדרה של `z1` צריכה להופיע לפני השורה של `w1`. אין לכך השפעה על עץ הירושה.)
תשובה: Y ו-Z יורשות מ-V; W ו-X יורשות מ-Z.
סעיף ב
Z ו-W
מבוקש: באילו שתי מחלקות מומשה `stam()`.
1. `v1.stam()` ו-`y1.stam()` הן שגיאות קומפילציה – לכן ב-V אין `stam()` (וגם לא ב-Y, שיורשת רק מ-V).
2. `z2.stam()` תקין ומדפיס "Good", כש-`z2` הוא עצם מסוג Z – לכן Z מממשת את `stam()` ומדפיסה "Good".
3. `w1.stam()` מדפיס "Bad" – לכן W דורסת את `stam()` ומדפיסה "Bad".
4. `z3.stam()` (עצם מסוג X) מדפיס "Good" – X לא מממשת את הפעולה, ומשתמשת בזו שירשה מ-Z. זה מתאים לכך שהפעולה מומשה בשתי מחלקות בלבד.
תשובה: במחלקות Z ו-W.
סעיף ג
V(int); Y extends V: Y(String); Z extends V: Z(), Z(V); W extends Z: W(Z, V), W(int, double, char, boolean); X extends Z: X().
מבוקש: כותרות המחלקות (עם הירושה מסעיף א') וכותרות הבנאים שהקוד משתמש בהם.
נעבור על כל `new` בקוד התקין:
1. `new V(9)`, `new V(6)` – בנאי `V(int)`.
2. `new Y("9")`, `new Y("5")` – בנאי `Y(String)`.
3. `new Z(new V(6))` – בנאי `Z(V)`; `new Z()` – בנאי ריק `Z()`.
4. `new W(z1, v2)` – הפרמטרים מטיפוס Z ו-V – בנאי `W(Z, V)`; `new W(4, 1.1, 'Z', true)` – בנאי `W(int, double, char, boolean)`.
5. `new X()` – בנאי ריק `X()`.
הערה: ל-V יש רק בנאי שמקבל `int`, ולכן הבנאים של Y ו-Z חייבים לזמן במפורש את בנאי מחלקת הבסיס עם מספר שלם (`super(...)` / `: base(...)`). הבנאים של W ו-X יכולים להסתמך על הבנאי הריק של Z.
public class V
{
public V(int num) { ... }
}
public class Y extends V
{
public Y(String str) { super(...); ... }
}
public class Z extends V
{
public Z() { super(...); ... }
public Z(V v) { super(...); ... }
}
public class W extends Z
{
public W(Z z, V v) { ... }
public W(int a, double b, char c, boolean d) { ... }
}
public class X extends Z
{
public X() { ... }
}public class V
{
public V(int num) { ... }
}
public class Y : V
{
public Y(string str) : base(...) { ... }
}
public class Z : V
{
public Z() : base(...) { ... }
public Z(V v) : base(...) { ... }
}
public class W : Z
{
public W(Z z, V v) { ... }
public W(int a, double b, char c, bool d) { ... }
}
public class X : Z
{
public X() { ... }
}תשובה: `V(int)`; `Y extends V` עם `Y(String)`; `Z extends V` עם `Z()` ו-`Z(V)`; `W extends Z` עם `W(Z, V)` ו-`W(int, double, char, boolean)`; `X extends Z` עם `X()`.
שאלה 4 · ניהול מסעדה בתור וברשימה מקושרת
במערכת לניהול מסעדה יש כמה מחלקות:
לקוח Client המאופיין בשם (`String name`) ומספר סועדים (`int diners`),
שולחן Table המאופיין במספר שולחן (`int num`), מספר מקומות בשולחן (`int places`) ומספר מקומות פנויים (`int free`).
מספר המקומות בשולחן (גודל השולחן) הוא אחד משלוש אפשרויות: 2 (שולחנות קטנים), 4 (שולחנות בינוניים) ו-8 (שולחנות גדולים).
בשתי המחלקות קיימות הפעולות הבונות המקבלות את ערכי התכונות ופעולות `get/set` (ב-C#: `Get/Set`) לכל תכונה.
המחלקה `Restaurant` מאופיינת בתור של לקוחות וברשימה מקושרת של שולחנות.
class Restaurant{
private Queue<Client> clients;
private Node<Table> tables;
….
}class Restaurant{
private Queue<Client> clients;
private Node<Table> tables;
….
}כתבו במחלקה `Restaurant` את הפעולה הבונה המקבלת את מספר השולחנות הקטנים, את מספר השולחנות הבינוניים ואת מספר השולחנות הגדולים שיש במסעדה.
הפעולה הבונה מייצרת מסעדה חדשה עם תור הלקוחות ריק, ובה שולחנות בכמות שהועברה כפרמטר. סדר הכנסת השולחנות לרשימה הוא לבחירתכם.
כותרת הפעולה:
public Restaurant(int small, int medium, int large)public Restaurant(int small, int medium, int large)כתבו פעולה במחלקה `Restaurant` המקבלת מספר סועדים ומחזירה את מספר השולחן שיש בו מספיק מקומות הפנויים. אם אין שולחן כזה, הפעולה תחזיר ערך (-1).
כותרת הפעולה:
public int findAvailableTable(int numOfDiners)public int FindAvailableTable(int numOfDiners)כתבו פעולה במחלקה `Restaurant` המטפלת בהושבת לקוח בשולחן. הפעולה תושיב לקוח אחד מתוך הלקוחות הממתינים בתור, בשולחן שבו יש מספיק מקומות פנויים, תוך שמירה על סדר התור – לקוח מתאים שהגיע קודם, יטופל קודם.
אם יימצא שולחן מתאים, יש להוציא את הלקוח מהתור, לעדכן את מספר מקומות הפנויים בשולחן ולהחזיר `true`. אם הפעולה לא תצליח להושיב אף לקוח מהלקוחות בתור, הפעולה תחזיר `false`.
כותרת הפעולה:
public boolean seatNextClient()public bool SeatNextClient()◂ פתרון מלא לשאלה 4
סעיף א
תור לקוחות ריק ורשימה של כל השולחנות, ממוספרים מ-1 (קטנים, בינוניים, גדולים), כל שולחן עם free = places.
נתון: מספר השולחנות מכל גודל: `small` (2 מקומות), `medium` (4 מקומות), `large` (8 מקומות).
מבוקש: בנאי שיוצר תור לקוחות ריק ורשימה של כל השולחנות; כל שולחן ריק, כלומר מספר המקומות הפנויים בו שווה למספר המקומות.
הרעיון: נמספר את השולחנות (כאשר הוא מספר השולחנות הכולל), ונסדר אותם ברשימה מהקטן לגדול: קודם הקטנים, אחריהם הבינוניים ואחריהם הגדולים (סדר זה גם עוזר בסעיף ב' – השולחן הראשון שמתאים הוא הקטן ביותר שמתאים). מנחים שהבנאי של `Table` מקבל את התכונות בסדר שבו הן מתוארות: `Table(num, places, free)`.
1. יוצרים תור לקוחות ריק.
2. הכנסה בראש רשימה היא , ולכן בונים את הרשימה מהסוף להתחלה: עוברים על המספרים מ- עד 1, ומכניסים כל שולחן לראש הרשימה. כך בסוף שולחן 1 יהיה ראשון.
3. גודל השולחן לפי מספרו: מספרים עד `small` – 2 מקומות; עד `small + medium` – 4 מקומות; השאר – 8 מקומות.
4. כל שולחן נוצר עם `free = places` (השולחן ריק).
למשל `new Restaurant(2, 1, 1)` יוצר את הרשימה: שולחן 1 (2 מקומות), שולחן 2 (2), שולחן 3 (4), שולחן 4 (8).
public Restaurant(int small, int medium, int large)
{
this.clients = new Queue<Client>();
this.tables = null;
int total = small + medium + large;
for (int num = total; num >= 1; num--) // בונים את הרשימה מהסוף להתחלה
{
int places;
if (num <= small)
places = 2;
else if (num <= small + medium)
places = 4;
else
places = 8;
this.tables = new Node<Table>(new Table(num, places, places), this.tables);
}
}public Restaurant(int small, int medium, int large)
{
this.clients = new Queue<Client>();
this.tables = null;
int total = small + medium + large;
for (int num = total; num >= 1; num--) // בונים את הרשימה מהסוף להתחלה
{
int places;
if (num <= small)
places = 2;
else if (num <= small + medium)
places = 4;
else
places = 8;
this.tables = new Node<Table>(new Table(num, places, places), this.tables);
}
}תשובה: תור לקוחות ריק, ורשימה של שולחנות ממוספרים מ-1, קטנים ואז בינוניים ואז גדולים, וכולם פנויים לגמרי.
סעיף ב
מספר השולחן הראשון ברשימה שבו free ≥ numOfDiners, אחרת -1.
נתון: מספר סועדים `numOfDiners`.
מבוקש: מספר של שולחן שיש בו לפחות `numOfDiners` מקומות פנויים, או אם אין כזה.
הרעיון: חיפוש סדרתי ברשימת השולחנות.
1. עוברים על הרשימה מתחילתה.
2. לכל שולחן בודקים אם `getFree() >= numOfDiners`. אם כן – מחזירים מיד את מספרו.
3. אם הגענו לסוף הרשימה בלי למצוא – מחזירים .
מכיוון שהרשימה מסודרת מהשולחנות הקטנים לגדולים (סעיף א'), השולחן הראשון שנמצא הוא גם מהקטנים שמתאימים, וכך לא "מבזבזים" שולחן גדול על קבוצה קטנה.
public int findAvailableTable(int numOfDiners)
{
Node<Table> pos = this.tables;
while (pos != null)
{
if (pos.getValue().getFree() >= numOfDiners)
return pos.getValue().getNum();
pos = pos.getNext();
}
return -1;
}public int FindAvailableTable(int numOfDiners)
{
Node<Table> pos = this.tables;
while (pos != null)
{
if (pos.GetValue().GetFree() >= numOfDiners)
return pos.GetValue().GetNum();
pos = pos.GetNext();
}
return -1;
}תשובה: מעבר על רשימת השולחנות והחזרת מספר השולחן הראשון שבו מספר המקומות הפנויים לפחות `numOfDiners`; אחרת .
סעיף ג
הלקוח הראשון בתור שיש לו שולחן מושב ויוצא מהתור (עדכון free), שאר התור נשמר בסדרו; true אם הושב לקוח, אחרת false.
נתון: תור הלקוחות הממתינים ורשימת השולחנות.
מבוקש: להושיב את הלקוח הראשון בתור שיש עבורו שולחן מתאים: להוציא אותו מהתור, לעדכן את המקומות הפנויים בשולחן ולהחזיר true. סדר שאר הלקוחות בתור לא משתנה. אם אף לקוח לא הושב – false.
הרעיון: בתור אי אפשר להוציא איבר מהאמצע, ולכן מעבירים את כל הלקוחות לתור עזר, ומדלגים (לא מעבירים) רק על הלקוח שהושב.
1. מוציאים לקוחות מהתור לפי הסדר. דגל `seated` אומר אם כבר הושבנו לקוח.
2. כל עוד לא הושבנו אף לקוח, לכל לקוח `c` בודקים בעזרת `findAvailableTable` מסעיף ב' אם יש שולחן עם `c.getDiners()` מקומות פנויים לפחות.
3. אם יש – מוצאים את השולחן ברשימה לפי מספרו, מקטינים את מספר המקומות הפנויים בו במספר הסועדים, ומדליקים את `seated`. הלקוח לא מוכנס לתור העזר – כך הוא יוצא מהתור.
4. כל לקוח אחר (שאין לו שולחן, או שמגיע אחרי שכבר הושבנו לקוח) מוכנס לתור העזר.
5. מחזירים את כל הלקוחות מתור העזר לתור המקורי – תור שומר על סדר (FIFO), ולכן סדר הלקוחות נשמר.
6. מחזירים את `seated`.
דוגמה: במסעדה עם שולחנות 1, 2 (2 מקומות), 3 (4 מקומות), 4 (8 מקומות), ובתור הלקוחות A (9 סועדים), B (3), C (4), D (8): ל-A אין שולחן; B מושב בשולחן 3 (נשאר מקום פנוי אחד), והתור הופך ל-A, C, D. זימון נוסף מושיב את C בשולחן 4 (נשארים 4 מקומות פנויים), והתור A, D. זימון שלישי מחזיר false – ל-A ול-D אין שולחן מתאים.
public boolean seatNextClient()
{
Queue<Client> temp = new Queue<Client>();
boolean seated = false;
while (!this.clients.isEmpty())
{
Client c = this.clients.remove();
if (!seated && this.findAvailableTable(c.getDiners()) != -1)
{
int num = this.findAvailableTable(c.getDiners());
Node<Table> pos = this.tables; // מציאת השולחן לפי מספרו
while (pos.getValue().getNum() != num)
pos = pos.getNext();
Table t = pos.getValue();
t.setFree(t.getFree() - c.getDiners()); // עדכון המקומות הפנויים
seated = true; // הלקוח לא חוזר לתור
}
else
temp.insert(c);
}
while (!temp.isEmpty()) // החזרת שאר הלקוחות באותו סדר
this.clients.insert(temp.remove());
return seated;
}public bool SeatNextClient()
{
Queue<Client> temp = new Queue<Client>();
bool seated = false;
while (!this.clients.IsEmpty())
{
Client c = this.clients.Remove();
if (!seated && this.FindAvailableTable(c.GetDiners()) != -1)
{
int num = this.FindAvailableTable(c.GetDiners());
Node<Table> pos = this.tables; // מציאת השולחן לפי מספרו
while (pos.GetValue().GetNum() != num)
pos = pos.GetNext();
Table t = pos.GetValue();
t.SetFree(t.GetFree() - c.GetDiners()); // עדכון המקומות הפנויים
seated = true; // הלקוח לא חוזר לתור
}
else
temp.Insert(c);
}
while (!temp.IsEmpty()) // החזרת שאר הלקוחות באותו סדר
this.clients.Insert(temp.Remove());
return seated;
}תשובה: מעבר אחד על התור בעזרת תור עזר: הלקוח הראשון שנמצא לו שולחן מושב (עדכון `free` של השולחן) ולא חוזר לתור; כל השאר חוזרים לתור באותו סדר; מחזירים true אם הושב לקוח, אחרת false.
שאלה 5 · ממשקים, ירושה ותקינות קטעי קוד
חברת סטארטאפ מפתחת מערכת לניהול שירותי רשת. המערכת כוללת ממשקים ומחלקות המייצגים סוגים שונים של שירותים ויכולותיהם. לפניכם תרשים היררכיה המתאר את הקשר בין מחלקות וממשקים:

נתונים 12 קטעי קוד. ציינו עבור כל אחד מהם אם הוא תקין או שגוי. אם הקוד שגוי, יש לפרט ולנמק מדוע ולציין מה סוג השגיאה – שגיאת קומפילציה או שגיאת זמן ריצה. אין קשר בין הקטעים!
// 1
IConnectable c1 = new WebService();
c1.connect("api.com");
c1.send("hello");
// 2
IDataStream d1 = new StreamingService();
d1.connect("stream.com");
// 3
StreamingService s1 = new StreamingService();
s1.connect("video.com");
s1.request("play video");
s1.optimizeStream();
// 4
INetworkService n1 = new StreamingService();
n1.send("start stream");
n1.configureBuffer(1024);
// 5
WebService w1 = new StreamingService();
w1.receive();
w1.logRequest("get status");
// 6
IConnectable c2 = new StreamingService();
c2.disconnect();
c2.send("ping");
// 7
IConnectable c3 = new DatabaseService();
c3.connect("db.com");
c3.runQuery("SELECT * FROM users;");
((DatabaseService) c3).backupDatabase();
System.out.println(((DatabaseService) c3).receive());
// 8
INetworkService n2 = new DatabaseService();
n2.connect("db2.com");
// 9
IConnectable c4 = new WebService();
((DatabaseService) c4).runQuery("DROP TABLE posts;");
// 10
StreamingService s2 = new WebService();
// 11
INetworkService n3 = new WebService();
// 12
IConnectable[] connections = new IConnectable[2];
connections[0] = new WebService();
connections[1] = new DatabaseService();
((StreamingService) connections[0]).optimizeStream();// 1
IConnectable c1 = new WebService();
c1.Connect("api.com");
c1.Send("hello");
// 2
IDataStream d1 = new StreamingService();
d1.Connect("stream.com");
// 3
StreamingService s1 = new StreamingService();
s1.Connect("video.com");
s1.Request("play video");
s1.OptimizeStream();
// 4
INetworkService n1 = new StreamingService();
n1.Send("start stream");
n1.ConfigureBuffer(1024);
// 5
WebService w1 = new StreamingService();
w1.Receive();
w1.LogRequest("get status");
// 6
IConnectable c2 = new StreamingService();
c2.Disconnect();
c2.Send("ping");
// 7
IConnectable c3 = new DatabaseService();
c3.Connect("db.com");
c3.RunQuery("SELECT * FROM users;");
((DatabaseService) c3).BackupDatabase();
Console.WriteLine(((DatabaseService) c3).Receive());
// 8
INetworkService n2 = new DatabaseService();
n2.Connect("db2.com");
// 9
IConnectable c4 = new WebService();
((DatabaseService) c4).RunQuery("DROP TABLE posts;");
// 10
StreamingService s2 = new WebService();
// 11
INetworkService n3 = new WebService();
// 12
IConnectable[] connections = new IConnectable[2];
connections[0] = new WebService();
connections[1] = new DatabaseService();
((StreamingService) connections[0]).OptimizeStream();◂ פתרון מלא לשאלה 5
פתרון
תקינים: 3, 5. שגיאת קומפילציה: 1, 2, 4, 6, 7, 8, 9, 10, 11, 12.
נתון: תרשים ההיררכיה ו-12 קטעי קוד בלתי תלויים.
מבוקש: לכל קטע – תקין או שגוי, ואם שגוי – למה, ואם זו שגיאת קומפילציה או שגיאת זמן ריצה.
שלב 1 – קריאת התרשים. חץ רציף = ירושה, חץ מקווקו = מימוש ממשק:
•`INetworkService` (בתרשים כתוב `INetworkSevice`) הוא ממשק שיורש משני הממשקים `IConnectable` ו-`IDataStream`, ומוסיף את `request`.
•`DatabaseService` מממשת את `IConnectable` ואת `IDataStream`, ומוסיפה `runQuery`, `backUpDataBase`.
•`WebService` מממשת רק את `IDataStream` (אין לה `connect`/`disconnect`), ומוסיפה `logRequest`, `setTimeOut`.
•`StreamingService` יורשת מ-`WebService` ומממשת את `INetworkService` – כלומר היא גם `IConnectable` וגם `IDataStream`, ויש לה את כל הפעולות, וגם `configureBuffer`, `optimizeStream`.
1. השמה `T x = new S()` עוברת קומפילציה רק אם S היא T (יורשת ממנה או מממשת אותה).
2. הקומפיילר מאפשר לזמן דרך משתנה רק פעולות שקיימות בטיפוס המוצהר של המשתנה.
3. המרה מפורשת `(S) x` לטיפוס "למטה" בהיררכיה עוברת קומפילציה, אבל אם העצם בפועל אינו S – נזרקת שגיאה בזמן ריצה (`ClassCastException` ב-Java, `InvalidCastException` ב-C#).
תשובה: תקינים: 3, 5. שגיאות קומפילציה: 1, 2, 4, 6, 7, 8, 9, 10, 11, 12 (בקטעים 9 ו-12 ההשמה של `WebService` למשתנה `IConnectable` כבר אינה חוקית; ההמרה שאחריה הייתה נכשלת בזמן ריצה).
שאלה 6 · החלפת חלקי רשימת תווים בלי חוליות
נתונה המחלקה `CharList` שלפניכם המייצגת רשימת תווים:
public class CharList {
private Node<Character> head;
public CharList(){
this.head = null;
}
public CharList(Node<Character> chain){
this.head = chain;
}
}public class CharList {
private Node<char> head;
public CharList(){
this.head = null;
}
public CharList(Node<char> chain){
this.head = chain;
}
}כותרת הפעולה:
public Node<Character> firstAfterChain(Node<Character> chain,
char letter)public Node<char> FirstAfterChain(Node<char> chain, char letter)כתבו פעולה המקבלת תו `letter`. הפעולה תחזיר את הפנייה לחוליה האחרונה המכילה את התו `letter`. אם התו לא מופיע ברשימה, הפעולה תחזיר `null`. כותרת הפעולה:
public Node<Character> last (char letter)public Node<char> Last (char letter)כתבו פעולה המקבלת תו `letter` המופיע לפחות פעמיים במקומות כלשהם ברשימה, אך לא בתחילתה ולא בסופה.
הפעולה תחליף בין תת-השרשרת הנמצאת לפני המופע הראשון של `letter` לבין תת-השרשרת הנמצאת אחרי המופע האחרון של התו `letter`.
לדוגמה, עבור הרשימה שלפניכם והתו `%`:
`k → a → % → b → b → % → b → % → e → r → r`
אחרי זימון הפעולה הרשימה תיראה כך:
`e → r → r → % → b → b → % → b → % → k → a`
כותרת הפעולה:
public void swap(char letter)public void Swap(char letter)מהי סיבוכיות זמן הריצה של הפעולה `swap`? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
חיפוש המופע הראשון (firstAfterChain עם null) ואז קפיצות ממופע למופע עד שמתקבל null; מוחזר המופע האחרון שנמצא.
נתון: הפעולה `firstAfterChain(chain, letter)` שמחזירה את המופע הראשון של `letter` אחרי החוליה `chain`.
מבוקש: הפניה למופע האחרון של `letter` ברשימה, או `null`.
הרעיון: "קופצים" ממופע למופע: כל זימון של `firstAfterChain` עם המופע הנוכחי מחזיר את המופע הבא. כשהזימון מחזיר `null` – המופע הנוכחי הוא האחרון.
1. כדי למצוא את המופע הראשון מזמנים את `firstAfterChain` עם `chain = null`, ומפרשים זאת כ"חיפוש מתחילת הרשימה" (אין חוליה שלפניה מתחילים).
2. כל עוד נמצא מופע (`found != null`): שומרים אותו ב-`lastFound`, ומחפשים את המופע הבא אחריו.
3. בסוף מחזירים את `lastFound`. אם התו לא הופיע כלל – הלולאה לא מתבצעת, ומוחזר `null`.
public Node<Character> last(char letter)
{
Node<Character> lastFound = null;
Node<Character> found = firstAfterChain(null, letter); // המופע הראשון
while (found != null)
{
lastFound = found;
found = firstAfterChain(found, letter); // המופע הבא
}
return lastFound;
}public Node<char> Last(char letter)
{
Node<char> lastFound = null;
Node<char> found = FirstAfterChain(null, letter); // המופע הראשון
while (found != null)
{
lastFound = found;
found = FirstAfterChain(found, letter); // המופע הבא
}
return lastFound;
}תשובה: מתחילים מ-`firstAfterChain(null, letter)` וקוראים שוב ושוב ל-`firstAfterChain` מהמופע האחרון שנמצא, עד שמתקבל `null`; מחזירים את המופע האחרון שנמצא.
סעיף ב
חיבור מחדש של שלוש הפניות: זנב הרשימה → המופע הראשון, המופע האחרון → הראש הישן, החוליה שלפני המופע הראשון → null; הראש החדש – החוליה שאחרי המופע האחרון.
נתון: תו `letter` שמופיע לפחות פעמיים ברשימה, ולא בחוליה הראשונה ולא באחרונה.
מבוקש: להחליף את מקומם של החלק שלפני המופע הראשון ושל החלק שאחרי המופע האחרון – רק בשינוי הפניות, בלי חוליות חדשות ובלי מבני עזר.
הרעיון: הרשימה מורכבת משלושה חלקים: (מתחילת הרשימה עד לפני המופע הראשון), (מהמופע הראשון עד המופע האחרון, כולל), ו- (אחרי המופע האחרון עד הסוף). מבוקש לקבל , אחריו , אחריו . מכיוון ש-`letter` אינו בתחילת הרשימה ולא בסופה, ו- אינם ריקים.
1. `first` – המופע הראשון (`firstAfterChain(null, letter)`), `lst` – המופע האחרון (`last` מסעיף א').
2. `prevFirst` – החוליה האחרונה של : מתקדמים מראש הרשימה עד שהחוליה הבאה היא `first`.
3. `newHead = lst.getNext()` – החוליה הראשונה של ; `tail` – החוליה האחרונה של (ושל כל הרשימה).
4. מחברים מחדש שלוש הפניות:
•`tail.setNext(first)` – סוף מצביע לתחילת ;
•`lst.setNext(head)` – סוף מצביע לתחילת ;
•`prevFirst.setNext(null)` – סוף הוא עכשיו סוף הרשימה.
5. `head = newHead` – הרשימה מתחילה ב-.
בדיקה עם הדוגמה: = `k a`, = `% b b % b %`, = `e r r`. אחרי החיבור: `e r r % b b % b % k a`, כמו בדוגמה.
public void swap(char letter)
{
Node<Character> first = firstAfterChain(null, letter); // המופע הראשון
Node<Character> lst = last(letter); // המופע האחרון
Node<Character> prevFirst = this.head; // החוליה שלפני המופע הראשון
while (prevFirst.getNext() != first)
prevFirst = prevFirst.getNext();
Node<Character> newHead = lst.getNext(); // תחילת החלק שאחרי המופע האחרון
Node<Character> tail = newHead; // החוליה האחרונה ברשימה
while (tail.getNext() != null)
tail = tail.getNext();
tail.setNext(first); // החלק האחרון -> החלק האמצעי
lst.setNext(this.head); // החלק האמצעי -> החלק הראשון
prevFirst.setNext(null); // החלק הראשון מסיים את הרשימה
this.head = newHead;
}public void Swap(char letter)
{
Node<char> first = FirstAfterChain(null, letter); // המופע הראשון
Node<char> lst = Last(letter); // המופע האחרון
Node<char> prevFirst = this.head; // החוליה שלפני המופע הראשון
while (prevFirst.GetNext() != first)
prevFirst = prevFirst.GetNext();
Node<char> newHead = lst.GetNext(); // תחילת החלק שאחרי המופע האחרון
Node<char> tail = newHead; // החוליה האחרונה ברשימה
while (tail.GetNext() != null)
tail = tail.GetNext();
tail.SetNext(first); // החלק האחרון -> החלק האמצעי
lst.SetNext(this.head); // החלק האמצעי -> החלק הראשון
prevFirst.SetNext(null); // החלק הראשון מסיים את הרשימה
this.head = newHead;
}תשובה: מוצאים את סוף החלק הראשון (`prevFirst`), את המופע האחרון ואת זנב הרשימה, ומחברים: זנב → מופע ראשון, מופע אחרון → ראש ישן, `prevFirst` → `null`; הראש החדש הוא החוליה שאחרי המופע האחרון.
סעיף ד
נסמן ב- את מספר החוליות ברשימה.
1. `firstAfterChain(null, letter)` – לכל היותר מעבר אחד על הרשימה, .
2. `last(letter)` – כל זימון של `firstAfterChain` מתחיל מהמופע הקודם וממשיך קדימה, ולכן כל הזימונים יחד עוברים על הרשימה פעם אחת בלבד – .
3. מציאת `prevFirst` ומציאת `tail` – כל אחת לכל היותר מעבר על הרשימה, .
4. שינוי ההפניות – .
תשובה: – מספר קבוע של מעברים על הרשימה.
שאלה 7 · מעקב רקורסיה על עץ בינארי
נתונה הפעולה `why` המקבלת הפניה לשורש עץ בינארי של מספרים שלמים:
public static int why(BinNode<Integer> t){
if(!t.hasLeft()&&!t.hasRight()) return t.getValue();
if(t.hasLeft()) return why(t.getLeft());
return why(t.getRight());
}public static int Why(BinNode<int> t){
if(!t.HasLeft()&&!t.HasRight()) return t.GetValue();
if(t.HasLeft()) return Why(t.GetLeft());
return Why(t.GetRight());
}ציירו עץ בעל שישה צמתים שעבורו הפעולה תחזיר ערך ארבע. כל ערכי הצמתים שונים זה מזה.
כתבו את הפעולה `why` בצורה הלא רקורסיבית.
נתונה הפעולה what המקבלת מספר שלם וחיובי `n`. הפעולה משתמשת בפעולה `why`.
public static BinNode<Integer> what (int n){
if (n == 0)
return null;
else
{
if (n % 2 == 0)
return new BinNode<Integer>(what(n-1), n, null);
else
{
BinNode<Integer> tree = what(n-1);
if(tree!=null)
{
int val = why(tree);
tree.setRight(new BinNode<Integer>(n + val));
}
return tree;
}
}
}public static BinNode<int> What (int n){
if (n == 0)
return null;
else
{
if (n % 2 == 0)
return new BinNode<int>(What(n-1), n, null);
else
{
BinNode<int> tree = What(n-1);
if(tree!=null)
{
int val = Why(tree);
tree.SetRight(new BinNode<int>(n + val));
}
return tree;
}
}
}עקבו אחרי זימון הפעולה `what (7)` ורשמו מה תחזיר הפעולה.
◂ פתרון מלא לשאלה 7
סעיף א
למשל: 10 בשורש, בנים 7 (שמאל) ו-12; ל-7 בנים 4 (שמאל) ו-9; ל-12 בן שמאלי 11. why: 10→7→4.
נתון: הפעולה `why`.
מבוקש: עץ בן שישה צמתים עם ערכים שונים, שעבורו `why` מחזירה 4.
מה עושה `why`: בכל צומת – אם הוא עלה, מחזירה את ערכו; אחרת יורדת שמאלה אם יש בן שמאלי, ורק אם אין – ימינה. כלומר היא מחזירה את ערך העלה שמגיעים אליו כשהולכים מהשורש ומעדיפים תמיד את הבן השמאלי.
לכן מספיק לבנות עץ שבו המסלול "שמאלה כשאפשר" מסתיים בעלה 4. דוגמה (אחת מני רבות):
•השורש 10; בנו השמאלי 7 ובנו הימני 12;
•הבנים של 7: משמאל 4 (עלה), מימין 9 (עלה);
•ל-12 בן שמאלי 11 (עלה).
מעקב: 10 (יש בן שמאלי) → 7 (יש בן שמאלי) → 4 (עלה) – מוחזר 4. בעץ שישה צמתים: 10, 7, 12, 4, 9, 11, וכל הערכים שונים.
תשובה: למשל עץ שבשורשו 10, בנים 7 (שמאלי) ו-12 (ימני), ל-7 בנים 4 (שמאלי) ו-9, ול-12 בן שמאלי 11; `why` הולכת 10 → 7 → 4 ומחזירה 4.
סעיף ב
לולאה: כל עוד t אינו עלה – t עובר לבן השמאלי אם יש, אחרת לימני; מחזירים t.getValue().
הרעיון: הרקורסיה ב-`why` היא "רקורסיית זנב" – כל זימון רק עובר לבן אחד, ואין עבודה אחרי החזרה. לכן אפשר להחליף אותה בלולאה שמזיזה את `t` במורד העץ:
1. תנאי העצירה של הרקורסיה (צומת שהוא עלה) הופך לתנאי היציאה מהלולאה: ממשיכים כל עוד ל-`t` יש בן כלשהו.
2. בכל סיבוב: אם יש בן שמאלי – עוברים אליו, אחרת עוברים לבן הימני.
3. בסוף הלולאה `t` הוא עלה, ומחזירים את ערכו.
public static int why(BinNode<Integer> t)
{
while (t.hasLeft() || t.hasRight()) // כל עוד t אינו עלה
{
if (t.hasLeft())
t = t.getLeft();
else
t = t.getRight();
}
return t.getValue();
}public static int Why(BinNode<int> t)
{
while (t.HasLeft() || t.HasRight()) // כל עוד t אינו עלה
{
if (t.HasLeft())
t = t.GetLeft();
else
t = t.GetRight();
}
return t.GetValue();
}תשובה: לולאה שיורדת מהשורש – שמאלה אם יש בן שמאלי, אחרת ימינה – עד שמגיעים לעלה, ומחזירה את ערכו.
סעיף ג
שורש 6; ילדים 4 (שמאל) ו-12 (ימין); ל-4 ילדים 2 (שמאל) ו-10 (ימין); ל-2 ילד ימני 5.
מבוקש: מעקב אחרי `what(7)` והעץ שמוחזר.
מה עושה `what(n)`: עבור מחזירה עץ ריק. עבור זוגי – יוצרת צומת חדש עם הערך , שבנו השמאלי הוא העץ `what(n-1)` ואין לו בן ימני. עבור אי-זוגי – לוקחת את העץ `what(n-1)`, ואם אינו ריק – מחשבת `val = why(tree)` (העלה שמגיעים אליו כשמעדיפים שמאלה) ומציבה בבן הימני של השורש צומת חדש עם הערך .
`what(7)` מזמנת את `what(6)`, וזו את `what(5)` וכן הלאה עד `what(0)`. נעקוב לפי סדר החזרה מהזימונים (מ-0 עד 7):
שימו לב: ב-`why`, בצומת 2 אין בן שמאלי, ולכן יורדים ימינה ל-5.
העץ שמוחזר מ-`what(7)`: השורש 6; בנו השמאלי 4 ובנו הימני 12; לצומת 4 בן שמאלי 2 ובן ימני 10; לצומת 2 אין בן שמאלי (מסומן "—"), ובנו הימני 5.
תשובה: `what(7)` מחזירה עץ: שורש 6, ילדים 4 (שמאל) ו-12 (ימין); ל-4 ילדים 2 (שמאל) ו-10 (ימין); ל-2 ילד ימני 5.
שאלה 8 · ירושה, בנאים והעמסת פעולות
בפרויקט מוגדרות שש מחלקות: A, B, C, D, E ו-Test. כל אחת בקובץ נפרד.
להלן מתוארות המחלקות עם החתימות של הפעולות שיש בהן. המימוש עצמו אינו חשוב.
public class A
{
protected int x;
protected int y;
public A(){
x = 0;
y = 1;
}
public A(int a){
this(a, a);
}
public A(int a,int b){
y = a*b;
}
public void func(D d){} // 1
public void func(B b){} // 2
} //end of class A
public class B extends A
{
protected int z;
public B(int b){
super(b+1);
x = b;
z = b*2;
}
public void func(A a){} // 3
public void func(B b){} // 4
} //end of class B
public class C extends A
{
protected int t;
public void func(A a){}// 5
public void func(B b){}// 6
} //end of class C
public class D extends B
{
public D(int d){
super(d+2);
}
public void func(A a){}// 7
public void func(B b){}// 8
} //end of class D
public class E extends C
{
protected int w;
public E (int num){
super();
x = num;
w = x + y;
}
public void func(A a){}// 9
} //end of class E
public class Test {
public static void main (String []args)
{
A ab =new B(2);
A ae =new E(3);
B bd =new D(2);
C cc =new C();
D dd =new D(4);
// ****** //
}
} //end of class Testpublic class A
{
protected int x;
protected int y;
public A() {
x = 0;
y = 1;
}
public A(int a) : this(a, a){
}
public A(int a, int b){
y = a * b;
}
public virtual void Func(D d){
} // 1
public virtual void Func(B b){
} // 2
} //end of class A
public class B : A
{
protected int z;
public B(int b) : base(b + 1){
x = b;
z = b * 2;
}
public virtual void Func(A a){
} // 3
public override void Func(B b){
} // 4
} //end of class B
public class C : A
{
protected int t;
public virtual void Func(A a){
} // 5
public override void Func(B b){
} // 6
} //end of class C
public class D : B
{
public D(int d): base(d+2){
}
public override void Func(A a) {
} //7
public override void Func(B b) {
} //8
} //end of class D
public class E :C
{
protected int w;
public E(int num):base(){
x = num;
w = x + y;
}
public override void Func(A a){
} // 9
} //end of class E
public class Test {
public static void Main (string []args)
{
A ab =new B(2);
A ae =new E(3);
B bd =new D(2);
C cc =new C();
D dd =new D(4);
// ****** //
}
} //end of class Testשרטטו את עץ הירושה למחלקות המוגדרות בפרויקט.
לפניכם טבלה ובה כל האובייקטים שהוגדרו בשיטה `main` במחלקה `Test` לעיל. כל אובייקט בשורה נפרדת. בעמודות של הטבלה רשומים השמות של התכונות שיש במחלקות שמהן נוצרו האובייקטים.
עליכם למלא את הטבלה ולכתוב בכל תא מהו הערך של התכונה שבעמודה באובייקט שבשורה.
שימו לב שלא תמיד כל התאים יתמלאו. בתא שלא קיימת התכונה במחלקה, כתבו "אין".
להדגמה, מילאנו את הערכים המתאימים בחלק מהתאים. עליכם להשלים את כל שאר התאים ולהעתיק את הטבלה המלאה לחוברת הבחינה.
בכל אחד מסעיפים הבאים השורה (*) תוחלף בשורת קוד משורות הקוד 1–8. כתבו, עבור כל אחד מהסעיפים, אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (קומפילציה או זמן ריצה).
אם הקוד תקין, כתבו מהי מספר הפעולה `func` שתופעל.
1. ab.func(bd);
2. ((E)ae).func (ab);
3. ((B)dd).func (bd);
4. ((A)bd).func (ae);
5. ((E)cc).func (bd);
6. bd.func(ae);
7. cc.func(cc);
8. ((D)ab).func(dd);1. ab.Func(bd);
2. ((E)ae).Func (ab);
3. ((B)dd).Func (bd);
4. ((A)bd).Func (ae);
5. ((E)cc).Func (bd);
6. bd.Func(ae);
7. cc.Func(cc);
8. ((D)ab).Func(dd);◂ פתרון מלא לשאלה 8
סעיף א
A בשורש; B ו-C יורשות מ-A; D יורשת מ-B; E יורשת מ-C.
מבוקש: עץ הירושה לפי הכותרות (`extends` ב-Java, `:` ב-C#).
1. `B extends A`, `C extends A` – ל-A שני בנים: B ו-C.
2. `D extends B` – D יורשת מ-B.
3. `E extends C` – E יורשת מ-C.
תשובה: A בשורש; B ו-C יורשות מ-A; D יורשת מ-B; E יורשת מ-C.
סעיף ב
ab: 2, 9, 4, אין, אין; ae: 3, 1, אין, 0, 4; bd: 4, 25, 8, אין, אין; cc: 0, 1, אין, 0, אין; dd: 6, 49, 12, אין, אין (לפי x, y, z, t, w).
מבוקש: ערכי התכונות של כל עצם אחרי הבנייה.
כללים: תכונה שלא הוצב בה ערך מקבלת 0 (ברירת המחדל של `int`). בנאי של מחלקה יורשת מפעיל קודם את בנאי מחלקת הבסיס ורק אחר כך את גופו. תכונה שלא מוגדרת במחלקה או באחת ממחלקות הבסיס שלה – "אין". התכונות לפי מחלקה: A – x, y; B – x, y, z; C – x, y, t; D – כמו B; E – x, y, t, w.
1. `new B(2)`: `B(2)` מזמן `A(3)`, שמזמן `A(3, 3)`: (ו-x נשאר 0). חזרה לגוף של B: , . אין t ו-w.
2. `new E(3)`: `super()` של E מפעיל את בנאי ברירת המחדל של C, שמפעיל את `A()`: , ; ב-C לא הוצב ערך ב-t, ולכן . בגוף E: , . אין z.
3. `new D(2)`: `D(2)` מזמן `B(4)`, שמזמן `A(5)` ← `A(5, 5)`: ; בגוף B: , . אין t ו-w.
4. `new C()`: בנאי ברירת המחדל מפעיל את `A()`: , , . אין z ו-w.
5. `new D(4)`: `D(4)` מזמן `B(6)`, שמזמן `A(7)` ← `A(7, 7)`: ; בגוף B: , . אין t ו-w.
תשובה: ab: x=2, y=9, z=4; ae: x=3, y=1, t=0, w=4; bd: x=4, y=25, z=8; cc: x=0, y=1, t=0; dd: x=6, y=49, z=12 (בשאר התאים – "אין").
סעיף ג
1) 4; 2) 9; 3) 8 (ב-C#: 7); 4) שגיאת קומפילציה; 5) שגיאת זמן ריצה; 6) 7; 7) 5; 8) שגיאת זמן ריצה.
מבוקש: לכל שורה – תקינה או לא, ואם תקינה – מספר הפעולה שתופעל.
1. בזמן קומפילציה – לפי הטיפוס המוצהר של העצם (אחרי ההמרה, אם יש) ולפי הטיפוס המוצהר של הפרמטר, נבחרת החתימה: מבין הפעולות `func` שמוכרות בטיפוס המוצהר, אלה שהפרמטר מתאים להן, והספציפית ביותר. אם אין חתימה מתאימה – שגיאת קומפילציה.
2. בזמן ריצה – החתימה שנבחרה מופעלת לפי הטיפוס בפועל של העצם: אם המחלקה בפועל (או מחלקה בדרך אליה) דורסת את החתימה – מופעלת הגרסה הדורסת. המרה `(X)` לעצם שאינו X בפועל נכשלת בזמן ריצה.
הטיפוסים בפועל: ab – B; ae – E; bd – D; cc – C; dd – D.
ב-C# – הבדל בשורה 3. ב-C# בחירת החתימה נעשית אחרת: פעולות המסומנות `override` אינן נחשבות "מוגדרות" במחלקה הדורסת, ואם במחלקה הנגזרת ביותר יש פעולה מתאימה – לא מתחשבים כלל בפעולות של מחלקות הבסיס, גם אם הן ספציפיות יותר.
•בשורה 3 הטיפוס המוצהר הוא B. ב-B מוגדרת חדשה (virtual) רק `Func(A)` (`Func(B)` של B היא `override` של A). `Func(A)` מתאימה לפרמטר מסוג B, ולכן היא נבחרת ו-`Func(B)` של A לא נבחנת. בזמן ריצה dd הוא D, ו-D דורסת את `Func(A)` – מופעלת פעולה 7.
•בשאר השורות התוצאה זהה ל-Java: בשורות 1, 2, 6, 7 יש רק חתימה אחת מתאימה ברמה הנגזרת ביותר (1 – `Func(B)` של A; 2 – `Func(A)` של C; 6 – `Func(A)` של B; 7 – `Func(A)` של C), שורה 4 – אין חתימה מתאימה, ובשורות 5 ו-8 ההמרה נכשלת בזמן ריצה (`InvalidCastException`).
תשובה (Java): 1. תקין – 4; 2. תקין – 9; 3. תקין – 8; 4. שגיאת קומפילציה; 5. שגיאת זמן ריצה; 6. תקין – 7; 7. תקין – 5; 8. שגיאת זמן ריצה.
ב-C#: אותן תשובות, פרט לשורה 3: תקין – 7.
שאלה 9 · מעקב רקורסיה על שרשרת ותור
נתונות הפעולות `f1, f2` (ב-C#: `F1, F2`):
public static boolean f1(Node<Integer> n, Queue<Integer> q){
if (q.isEmpty())return true;
if (n == null) return false;
if (n.getValue() != q.remove())return false;
return f1(n.getNext(), q);
}
public static Queue<Integer>f2(Node<Integer> n1,
Node<Integer> n2) {
if (n2 == null) {
return new Queue<Integer>();
}
if (!n2.hasNext()) {
Queue<Integer> q = new Queue<Integer>();
q.insert(n1.getValue());
return q;
}
Queue<Integer>q = f2(n1.getNext(),n2.getNext().getNext());
q.insert(n1.getValue());
return q;
}public static bool F1(Node<int> n, Queue<int> q){
if (q.IsEmpty())return true;
if (n == null) return false;
if (n.GetValue() != q.Remove())return false;
return F1(n.GetNext(), q);
}
public static Queue<int>F2(Node<int> n1,
Node<int> n2) {
if (n2 == null) {
return new Queue<int>();
}
if (!n2.HasNext()) {
Queue<int> single = new Queue<int>();
single.Insert(n1.GetValue());
return single;
}
Queue<int>q = F2(n1.GetNext(),n2.GetNext().GetNext());
q.Insert(n1.GetValue());
return q;
}נתונה שרשרת חוליות .
תנו דוגמה לתור `q` הכולל לפחות ארבעה איברים כך שתוצאת זימון `f1(n, q)` תהיה `true`.
מהי מטרת הפעולה `f1` באופן כללי? יש להסביר מה מבצעת הפעולה ולא כיצד פועל האלגוריתם.
נתונה שרשרת חוליות .
מה תהיה תוצאת הזימון `f2(n, n)`? יש להראות מעקב אחרי ביצוע הפעולה!
נתונה שרשרת חוליות .
מה תהיה תוצאת הזימון `f2(n,n)`?
מהי מטרת הפעולה `f2` באופן כללי? יש להסביר מה מבצעת הפעולה ולא כיצד פועל האלגוריתם.
◂ פתרון מלא לשאלה 9
סעיף א
למשל התור [9, 8, 7, 6] (9 בראש).
נתון: השרשרת .
מבוקש: תור עם לפחות ארבעה איברים שעבורו `f1(n, q)` מחזירה true.
מה עושה `f1`: בכל צעד מוציאה את האיבר שבראש התור ומשווה אותו לערך החוליה הנוכחית. אם הם שונים – false. אם התור התרוקן – true (כל האיברים התאימו). אם השרשרת נגמרה לפני התור – false. כלומר, התשובה true כשאיברי התור, מהראש לזנב, שווים לערכים הראשונים של השרשרת, לפי הסדר.
לכן נבחר את ארבעת הערכים הראשונים של השרשרת: התור (ראש התור משמאל) .
מעקב: , , , , התור ריק – מוחזר true.
תשובה: למשל התור (9 בראש התור).
סעיף ב
בודקת אם איברי התור (מהראש) שווים לערכים הראשונים בשרשרת לפי הסדר – התור הוא התחלת השרשרת.
1. כל זימון משווה את ראש התור לחוליה הנוכחית, ומתקדם בשרשרת ובתור יחד.
2. אם התור מתרוקן – כל איבריו התאימו לחוליות הראשונות – true.
3. אם יש אי-התאמה, או שהשרשרת קצרה מהתור – false.
תשובה: `f1` בודקת אם איברי התור (מהראש לזנב) זהים לערכים הראשונים בשרשרת לפי הסדר – כלומר אם התור הוא "רישא" (התחלה) של השרשרת; אם כן – true, אחרת false (התור מתרוקן בתהליך).
סעיף ג
התור [3, 2, 1] (3 בראש).
מה עושה `f2(n1, n2)`: `n1` מתקדם בכל זימון חוליה אחת, ו-`n2` מתקדם שתי חוליות. כש-`n2` מגיע ל-`null` מוחזר תור ריק; כש-`n2` הוא החוליה האחרונה מוחזר תור עם הערך של `n1`. בחזרה מהרקורסיה כל זימון מכניס את הערך של `n1` שלו לסוף התור – כך הערכים נכנסים בסדר הפוך.
מעקב על `f2(n, n)` עבור (ראש התור משמאל):
החזרה מתבצעת מלמטה למעלה: התור הריק מזימון 4, הכנסת 3, אחר כך 2, אחר כך 1.
תשובה: התור (3 בראש התור).
סעיף ד
התור [4, 3, 2, 1] (4 בראש).
מעקב על `f2(n, n)` עבור (ראש התור משמאל):
תשובה: התור (4 בראש התור).
סעיף ה
מחזירה תור עם החצי הראשון של ערכי השרשרת (מעוגל כלפי מעלה) בסדר הפוך.
1. `n2` מתקדם פי שניים מהר מ-`n1`, ולכן כש-`n2` מגיע לסוף השרשרת, `n1` נמצא באמצע: בשרשרת של חוליות מבוצעים זימונים שמכניסים ערך.
2. הערכים מוכנסים בחזרה מהרקורסיה, מהעמוק לרדוד, כלומר מהחוליה האמצעית אחורה עד הראשונה.
3. בדיקה: – (3 ערכים); – (4 ערכים).
תשובה: `f2(n, n)` מחזירה תור שמכיל את החצי הראשון של ערכי השרשרת (עבור אורך אי-זוגי – כולל האיבר האמצעי, כלומר ערכים) בסדר הפוך: האיבר האמצעי בראש התור והראשון בשרשרת בסופו.