מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2025 מועד א'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2025 מועד א', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- C# (עמוד 2)
מבחן ב- JAVA (עמוד 12)
בכל מבחן 12 שאלות.
שאלות 1–5: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 6–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 11–12: יש לענות על שאלה אחת בלבד. ערך השאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קיבוץ איברים זהים בתור לרצפים
כתבו פעולה המקבלת תור של מספרים שלמים ומחזירה תור חדש המכיל את כל האיברים שבתור המקורי כך שהאיברים הזהים יהיו ברצף. סדר הרצפים בתור החדש אינו חשוב.
עבור התור q הזה:
הפעולה תחזיר את התור (אחת התשובות האפשריות):
כותרת הפעולה:
public static Queue<Integer> orderQ(Queue<Integer> q)public static Queue<int> OrderQ(Queue<int> st)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
בכל סבב לוקחים את האיבר שבראש התור, מעבירים את כל המופעים שלו לתור התוצאה ואת השאר לתור עזר; חוזרים עד שלא נשארו איברים. התור המקורי נשמר.
נתון: תור q של מספרים שלמים (ראש התור משמאל, כמו בציור החיצים).
מבוקש: תור חדש שבו כל האיברים השווים זה לזה עומדים ברצף, למשל עבור – התור .
הרעיון: בונים את התור החדש "רצף אחרי רצף":
1. קודם מעתיקים את q לתור עבודה `rest` (ומחזירים את האיברים ל-q, כדי לא להרוס את התור המקורי).
2. כל עוד `rest` אינו ריק: מסתכלים על האיבר שבראשו, `x`. עוברים על כל `rest`: כל איבר ששווה ל-`x` מוכנס לתור התוצאה `result`, וכל איבר אחר מוכנס לתור העזר `temp`.
3. אחרי המעבר כל המופעים של `x` נמצאים ברצף אחד בסוף `result`, ובתור העזר נשארו רק ערכים אחרים. מחזירים אותם מ-`temp` ל-`rest` וחוזרים לשלב 2.
4. כשהתור `rest` מתרוקן – כל ערך קיבל רצף משלו, ומחזירים את `result`.
בדוגמה: בסבב הראשון ונאספים שני ה-3; בסבב השני ונאספים שלושה 10; אחר כך שלושה 2 ולבסוף 7. מתקבל בדיוק התור (הרצפים בסדר ההופעה הראשונה של כל ערך).
public static Queue<Integer> orderQ(Queue<Integer> q)
{
Queue<Integer> result = new Queue<Integer>();
Queue<Integer> rest = new Queue<Integer>();
Queue<Integer> temp = new Queue<Integer>();
while (!q.isEmpty()) // העתקת q ל-rest
{
int x = q.remove();
rest.insert(x);
temp.insert(x);
}
while (!temp.isEmpty()) // שחזור q
q.insert(temp.remove());
while (!rest.isEmpty())
{
int x = rest.head(); // הערך של הרצף הבא
while (!rest.isEmpty())
{
int y = rest.remove();
if (y == x)
result.insert(y); // מצטרף לרצף
else
temp.insert(y); // נשאר לסבבים הבאים
}
while (!temp.isEmpty())
rest.insert(temp.remove());
}
return result;
}public static Queue<int> OrderQ(Queue<int> st)
{
Queue<int> result = new Queue<int>();
Queue<int> rest = new Queue<int>();
Queue<int> temp = new Queue<int>();
while (!st.IsEmpty()) // העתקת st ל-rest
{
int x = st.Remove();
rest.Insert(x);
temp.Insert(x);
}
while (!temp.IsEmpty()) // שחזור st
st.Insert(temp.Remove());
while (!rest.IsEmpty())
{
int x = rest.Head(); // הערך של הרצף הבא
while (!rest.IsEmpty())
{
int y = rest.Remove();
if (y == x)
result.Insert(y); // מצטרף לרצף
else
temp.Insert(y); // נשאר לסבבים הבאים
}
while (!temp.IsEmpty())
rest.Insert(temp.Remove());
}
return result;
}תשובה: בכל סבב מעבירים לתור התוצאה את כל המופעים של הערך שבראש התור, ואת שאר האיברים שומרים לסבב הבא; התור המקורי משוחזר.
סעיף ב
נסמן ב- את מספר האיברים בתור וב- את מספר הערכים השונים בו.
1. ההעתקה של q ל-`rest` והשחזור – .
2. בכל סבב של הלולאה החיצונית עוברים על כל האיברים שנשארו ב-`rest` (לכל היותר ) ומחזירים מ-`temp` לכל היותר – כלומר לסבב.
3. יש סבב אחד לכל ערך שונה, כלומר סבבים. במקרה הגרוע כל הערכים שונים (), ואז מספר הפעולות הוא בערך .
תשובה: במקרה הגרוע (באופן כללי ).
שאלה 2 · המרחק הגדול בין איברים זהים במחסנית

נתונה מחסנית של מספרים שלמים. כל איבר במחסנית מופיע פעמיים בדיוק. המרחק בין שני איברים במחסנית הוא כמות האיברים הנמצאים ביניהם.
כתבו פעולה המחזירה את המרחק הגדול ביותר בין שני איברים זהים במחסנית.
לדוגמה:
עבור המחסנית הבאה הפעולה תחזיר 5 (המרחק בין שני איברים שערכם 9).
כותרת הפעולה:
public static int maxDistance(Stack<Integer> st)public static int MaxDistance(Stack<int> st)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
מעתיקים את המחסנית למערך (ומשחזרים אותה), ולכל זוג מקומות עם ערכים שווים מחשבים ; מחזירים את המקסימום. בדוגמה: 5.
נתון: מחסנית st שבה כל ערך מופיע בדיוק פעמיים.
מבוקש: המרחק הגדול ביותר בין שני המופעים של ערך כלשהו. אם שני המופעים נמצאים במקומות , ביניהם יש איברים.
הרעיון: במחסנית אי אפשר לגשת ישירות למקום מסוים, ולכן:
1. מוציאים את כל האיברים למחסנית עזר `temp` וסופרים אותם ().
2. יוצרים מערך בגודל , מוציאים את האיברים מ-`temp` למערך ובאותו צעד מחזירים אותם ל-st – כך המחסנית משוחזרת בדיוק כפי שהייתה.
3. עוברים על כל זוג מקומות במערך. אם `arr[i] == arr[j]` – זהו זוג זהה, והמרחק שלו . שומרים את הגדול ביותר.
המרחקים אינם תלויים בכיוון המערך (מלמעלה או מלמטה), ולכן אין חשיבות לכך שהמערך מסודר מתחתית המחסנית לראשה.
בדוגמה (מראש המחסנית): . המרחקים: בין ה-7: 1, בין ה-10: 3, בין ה-9: 5 (האיברים ), בין ה-3: 3, בין ה-2: 0, בין ה-6: 0. המקסימום הוא 5.
public static int maxDistance(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
int n = 0;
while (!st.isEmpty()) // ספירת האיברים
{
temp.push(st.pop());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור st
{
arr[i] = temp.pop();
st.push(arr[i]);
}
int max = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j] && j - i - 1 > max)
max = j - i - 1;
return max;
}public static int MaxDistance(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
int n = 0;
while (!st.IsEmpty()) // ספירת האיברים
{
temp.Push(st.Pop());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור st
{
arr[i] = temp.Pop();
st.Push(arr[i]);
}
int max = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j] && j - i - 1 > max)
max = j - i - 1;
return max;
}תשובה: המרחק הגדול ביותר מתקבל ממעבר על כל הזוגות במערך עזר; עבור המחסנית בדוגמה מוחזר 5.
סעיף ב
נסמן ב- את מספר האיברים במחסנית.
1. הוצאת האיברים, ההעתקה למערך והשחזור – שלוש לולאות של צעדים, .
2. הלולאה הכפולה בודקת את כל הזוגות : בדיקות, כל אחת .
תשובה: – הלולאה הכפולה על הזוגות קובעת את הסיבוכיות.
שאלה 3 · בדיקת שרשרת מושלמת לפי מספר מופעים
שרשרת נקראת "שרשרת מושלמת" אם כל ערך חיובי שבה מופיע מספר זוגי של פעמים וכל ערך שלילי שבה מופיע מספר אי-זוגי של פעמים.
כתבו פעולה המקבלת הפניה לחוליה הראשונה בשרשרת של מספרים שלמים. הפעולה תבדוק אם השרשרת היא "שרשרת מושלמת". אם כן – הפעולה תחזיר ערך true, אם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean perfectList(Node<Integer> chain)public static bool PerfectList(Node<int> chain)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
לכל חוליה סופרים כמה פעמים הערך שלה מופיע בשרשרת; ערך חיובי עם מספר מופעים אי-זוגי או ערך שלילי עם מספר מופעים זוגי – false; אחרת true.
נתון: שרשרת חוליות של מספרים שלמים, `chain` מפנה לחוליה הראשונה.
מבוקש: true אם כל ערך חיובי מופיע מספר זוגי של פעמים וכל ערך שלילי מופיע מספר אי-זוגי של פעמים. על הערך 0 אין דרישה (הוא לא חיובי ולא שלילי).
1. עוברים עם מצביע `p` על כל חוליות השרשרת.
2. עבור הערך `x` של החוליה הנוכחית סופרים במעבר נוסף (מצביע `r` מתחילת השרשרת) כמה פעמים `x` מופיע בכל השרשרת.
3. אם `x` חיובי ומספר המופעים אי-זוגי – השרשרת אינה מושלמת, מחזירים false. אם `x` שלילי ומספר המופעים זוגי – גם כן false.
4. אם עברנו על כל החוליות ולא נמצאה הפרה – מחזירים true. שרשרת ריקה מושלמת (אין בה ערך שמפר את התנאי).
ערך שמופיע כמה פעמים נבדק כמה פעמים – זה לא משנה את התוצאה, רק חוזר על אותה בדיקה. השרשרת לא משתנה, כי רק קוראים ממנה.
למשל, השרשרת מושלמת (5 ו-2 מופיעים פעמיים, פעם אחת), ואילו אינה מושלמת ( מופיע פעמיים).
public static boolean perfectList(Node<Integer> chain)
{
Node<Integer> p = chain;
while (p != null)
{
int x = p.getValue();
int count = 0; // מספר המופעים של x
Node<Integer> r = chain;
while (r != null)
{
if (r.getValue() == x)
count++;
r = r.getNext();
}
if (x > 0 && count % 2 != 0) // חיובי - מספר אי-זוגי של פעמים
return false;
if (x < 0 && count % 2 == 0) // שלילי - מספר זוגי של פעמים
return false;
p = p.getNext();
}
return true;
}public static bool PerfectList(Node<int> chain)
{
Node<int> p = chain;
while (p != null)
{
int x = p.GetValue();
int count = 0; // מספר המופעים של x
Node<int> r = chain;
while (r != null)
{
if (r.GetValue() == x)
count++;
r = r.GetNext();
}
if (x > 0 && count % 2 != 0) // חיובי - מספר אי-זוגי של פעמים
return false;
if (x < 0 && count % 2 == 0) // שלילי - מספר זוגי של פעמים
return false;
p = p.GetNext();
}
return true;
}תשובה: לכל חוליה סופרים את מספר המופעים של ערכה; מופר התנאי (חיובי–אי-זוגי או שלילי–זוגי) – false, אחרת true.
סעיף ב
נסמן ב- את מספר החוליות בשרשרת.
1. הלולאה החיצונית עוברת על חוליות.
2. עבור כל חוליה הלולאה הפנימית עוברת שוב על כל החוליות כדי לספור מופעים, .
3. סך הכול במקרה הגרוע (שרשרת מושלמת, שבה אין יציאה מוקדמת) צעדים.
תשובה: .
שאלה 4 · ירושה, בנאים, העמסה ודריסה של פעולות
נתונות שתי מחלקות A ו-B:
public class A
{
protected int num;
public A() { }
public A (int num){ this.num = num; }
public int func(int k){ return k + this.num;}
}
public class B extends A {
private int x;
public boolean test() { return this.x > this.num; }
}public class A
{
protected int num;
public A() { }
public A (int num){ this.num = num; }
public int Func(int k){ return k + this.num;}
}
public class B : A {
private int x;
public bool Test() { return this.x > this.num; }
}לפניכם שלושה היגדים. קבעו לכל אחד מהם אם הוא נכון או אינו נכון, ונמקו את קביעתכם.
1. המחלקה A לא תעבור קומפילציה כי התכונה num אינה מקבלת ערך בבנאי הראשון.
2. המחלקה B לא תעבור קומפילציה כי אין לה שום בנאי.
3. המחלקה B לא תעבור קומפילציה כי בפעולה test יש שימוש בתכונה num והיא לא הוגדרה במחלקה זו.
לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה A. אם הוספת הפעולה תגרום לשגיאה יש להסביר אותה.
1. public int func () { return 1; }
2. public int func (double k){ return (int) k; }
3. public double func (int k){ return 1.0*k; }
4. public int func (int p){ return p; }
5. public void func(int k, int p){ System.out.print(k*p); }1. public int Func () { return 1; }
2. public int Func (double k){ return (int) k; }
3. public double Func (int k){ return 1.0*k; }
4. public int Func (int p){ return p; }
5. public void Func (int k, int p){ Console.WriteLine(k*p); }לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה B. אם הוספת הפעולה תגרום לשגיאה יש להסביר אותה.
1. public int func () { return 1; }
2. public int func (double k){ return (int) k; }
3. public double func (int k){ return 1.0*k; }
4. public int func (int p){ return p; }
5. public void func(int k, int p){ System.out.print(k*p); }כותרת הפעולה Func במחלקה A השתנתה:
public virtual int Func(int k)לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה B. אם הוספת הפעולה תגרום לשגיאה יש להסביר אותה.
1. public overload int Func () { return 1; }
2. public overload int Func (double k){ return (int) k; }
3. public overload double Func (int k){ return 1.0*k; }
4. public overload int Func (int p){ return p; }
5. public overload void Func (int k, int p){
Console.WriteLine(k*p); }◂ פתרון מלא לשאלה 4
סעיף א
1 – לא נכון; 2 – לא נכון; 3 – לא נכון.
1. לא נכון. תכונה של עצם שלא קיבלה ערך בבנאי מקבלת ערך ברירת מחדל – עבור `int` הערך הוא 0. בנאי ריק הוא חוקי לגמרי, והמחלקה A עוברת קומפילציה.
2. לא נכון. כשלא כותבים במחלקה אף בנאי, המהדר מוסיף לה בנאי ברירת מחדל ללא פרמטרים. הבנאי הזה קורא לבנאי ללא פרמטרים של מחלקת הבסיס – `A()` – והוא קיים ב-A. לכן B עוברת קומפילציה (אפשר לכתוב `new B()`).
3. לא נכון. B יורשת מ-A, והתכונה `num` מוגדרת ב-A כ-`protected`. תכונה מוגנת נגישה במחלקות היורשות, ולכן `this.num` בפעולה `test` (ב-C#: `Test`) חוקי.
תשובה: שלושת ההיגדים אינם נכונים – שתי המחלקות עוברות קומפילציה.
סעיף ב
1 – אפשר; 2 – אפשר; 3 – שגיאה; 4 – שגיאה; 5 – אפשר.
במחלקה A כבר מוגדרת הפעולה `int func(int k)` (ב-C#: `Func`). במחלקה אחת מותר להגדיר כמה פעולות באותו שם (העמסה) רק אם רשימת הפרמטרים שלהן שונה – במספר הפרמטרים או בטיפוסים שלהם. טיפוס הערך המוחזר ושמות הפרמטרים אינם חלק מהחתימה.
1. `func()` – אפשר. אין פרמטרים, החתימה שונה מ-`func(int)` – העמסה.
2. `func(double k)` – אפשר. פרמטר מטיפוס `double`, החתימה שונה – העמסה.
3. `double func(int k)` – שגיאה. החתימה `func(int)` כבר קיימת במחלקה. ההבדל הוא רק בטיפוס המוחזר, ואי אפשר להעמיס פעולות לפי הטיפוס המוחזר בלבד (המהדר לא יידע איזו פעולה לזמן בקריאה `func(5)`).
4. `int func(int p)` – שגיאה. זו בדיוק אותה חתימה `func(int)`; שינוי שם הפרמטר מ-k ל-p לא יוצר פעולה חדשה, ולכן זו הגדרה כפולה של אותה פעולה.
5. `void func(int k, int p)` – אפשר. שני פרמטרים – חתימה שונה, העמסה.
תשובה: אפשר להגדיר במחלקה A את פעולות 1, 2, 5; פעולות 3 ו-4 גורמות לשגיאה (חתימה `func(int)` שכבר קיימת).
סעיף ג
Java: 1, 2, 4, 5 – אפשר (4 דורסת); 3 – שגיאה. C# (עם override): רק 4 אפשרית; 1, 2, 5 – אין פעולה וירטואלית מתאימה לדרוס; 3 – טיפוס מוחזר שונה.
Java. B יורשת מ-A את `int func(int k)`. במחלקה היורשת מותר להוסיף פעולות בחתימה אחרת (העמסה), ומותר להגדיר פעולה באותה חתימה בדיוק – זו דריסה – אבל אז הטיפוס המוחזר חייב להיות זהה (או תואם) לזה של הפעולה הנדרסת.
1. `int func()` – אפשר. חתימה חדשה, העמסה.
2. `int func(double k)` – אפשר. חתימה חדשה, העמסה.
3. `double func(int k)` – שגיאה. החתימה `func(int)` זהה לזו של הפעולה שנורשה מ-A, ולכן זו ניסיון דריסה – אבל הטיפוס המוחזר `double` אינו תואם ל-`int` (שגיאה: func(int) in B cannot override func(int) in A).
4. `int func(int p)` – אפשר. אותה חתימה ואותו טיפוס מוחזר – דריסה חוקית של הפעולה של A (שם הפרמטר לא משנה).
5. `void func(int k, int p)` – אפשר. שני פרמטרים, העמסה.
C#. המילה `overload` אינה מילה שמורה ב-C# (ואינה מגדיר גישה), ולכן כפי שהן מודפסות אף אחת מחמש השורות לא תעבור הידור – שגיאת תחביר. ככל הנראה הכוונה ל-`override`, ובפרט לכך שהפעולה ב-A הוגדרה עכשיו `virtual`. עם `override`, מותר לדרוס רק פעולה וירטואלית שקיימת במחלקת הבסיס באותה חתימה ובאותו טיפוס מוחזר:
1. `override int Func()` – שגיאה. ב-A אין פעולה `Func()` ללא פרמטרים – אין מה לדרוס.
2. `override int Func(double k)` – שגיאה. ב-A אין `Func(double)` – אין מה לדרוס.
3. `override double Func(int k)` – שגיאה. יש פעולה וירטואלית `Func(int)`, אבל הטיפוס המוחזר בדריסה חייב להיות `int` כמו ב-A.
4. `override int Func(int p)` – אפשר. אותה חתימה ואותו טיפוס מוחזר, והפעולה ב-A וירטואלית – דריסה חוקית.
5. `override void Func(int k, int p)` – שגיאה. ב-A אין פעולה עם שני פרמטרים לדרוס. (בלי המילה `override` היו 1, 2, 5 העמסות חוקיות.)
תשובה: ב-Java – פעולות 1, 2, 4, 5 אפשריות (4 היא דריסה), 3 שגיאה בגלל טיפוס מוחזר שונה. ב-C# (`override`) – רק פעולה 4 אפשרית; 1, 2, 5 – אין פעולה וירטואלית מתאימה לדרוס, 3 – טיפוס מוחזר שונה.
שאלה 5 · מעקב אחר פעולה המסירה כפילויות מתור
נתונה הפעולה הבאה:
public static void what(Queue<Integer> q)
{
int num1, num2;
boolean found;
Queue<Integer> temp1 = new Queue<Integer>();
Queue<Integer> temp2 = new Queue<Integer>();
while(!q.isEmpty())
{
num1 = q.remove();
found = false;
while(!q.isEmpty())
{
num2 = q.remove();
if(num1 == num2)
found = true;
temp1.insert(num2);
}
while(!temp1.isEmpty())
q.insert(temp1.remove());
if(!found)
temp2.insert(num1);
}
while(!temp2.isEmpty())
q.insert(temp2.remove());
}public static void What(Queue<int> q)
{
int num1, num2;
bool found;
Queue<int> temp1 = new Queue<int>();
Queue<int> temp2 = new Queue<int>();
while(!q.IsEmpty())
{
num1 = q.Remove();
found = false;
while(!q.IsEmpty())
{
num2 = q.Remove();
if(num1 == num2)
found = true;
temp1.Insert(num2);
}
while(!temp1.IsEmpty())
q.Insert(temp1.Remove());
if(!found)
temp2.Insert(num1);
}
while(!temp2.IsEmpty())
q.Insert(temp2.Remove());
}נתון תור q הבא:
מה יהיה התוכן של התור q אחרי זימון הפעולה what(q) עבור התור q?
תנו דוגמה לתור q המכיל לפחות חמישה ערכים כך שתוכן התור לא ישתנה אחרי זימון הפעולה what(q). אם לא ניתן ליצור תור כזה, יש להסביר מדוע.
תנו דוגמה לתור q המכיל לפחות חמישה ערכים כך שאחרי זימון הפעולה what(q) התור יהיה ריק. אם לא ניתן ליצור תור כזה, יש להסביר מדוע.
מה מבצעת הפעולה what(q) עבור תור של מספרים שלמים q?
◂ פתרון מלא לשאלה 5
סעיף א
(מראש התור)
נתון: התור (מראש התור לסופו) .
מה קורה בכל סבב של הלולאה החיצונית: מוציאים מראש התור את `num1`; מוציאים את כל שאר האיברים, בודקים אם אחד מהם שווה ל-`num1` (אז `found = true`), ומחזירים אותם לתור באותו סדר (דרך `temp1`). אם `num1` לא הופיע שוב בהמשך התור – הוא נשמר ב-`temp2`, ואחרת הוא נזרק. בסוף מעבירים את `temp2` ל-q.
הלולאה מסתיימת כש-q ריק, ואז כל איברי `temp2` מועברים ל-q.
תשובה: התור q יהיה (מראש התור) .
סעיף ב
למשל – כל הערכים שונים.
איבר נזרק רק אם יש אחריו בתור איבר ששווה לו. לכן אם כל הערכים בתור שונים זה מזה, אף איבר לא נזרק: כל `num1` מקבל `found = false` ועובר ל-`temp2`, והאיברים חוזרים ל-q באותו סדר.
למשל q = : בכל סבב `found` נשאר false, ו-`temp2` = , כלומר q לא משתנה.
תשובה: כל תור שבו כל הערכים שונים, למשל .
סעיף ג
לא ניתן – האיבר האחרון בתור תמיד נשמר.
לא ניתן ליצור תור כזה.
הסבר: האיבר האחרון של התור מטופל בסבב האחרון של הלולאה החיצונית. כשהוא מוצא כ-`num1`, התור q כבר ריק, הלולאה הפנימית לא מתבצעת כלל, ולכן `found` נשאר false. כתוצאה מכך האיבר האחרון תמיד נכנס ל-`temp2` וחוזר ל-q. באופן כללי: המופע האחרון של כל ערך תמיד נשמר.
למשל עבור נזרקים ארבעת ה-4 הראשונים, והתור שמתקבל הוא – לא ריק.
תשובה: לא ניתן – בתור לא ריק המופע האחרון של כל ערך (ובפרט האיבר האחרון) נשאר תמיד בתור.
סעיף ד
מוחקת כפילויות: מכל ערך נשאר רק המופע האחרון שלו, והסדר היחסי נשמר.
כל איבר שיש אחריו בתור איבר שווה לו נזרק, וכל איבר שאין אחריו איבר שווה נשמר, והאיברים שנשמרים חוזרים לתור בסדר המקורי שלהם.
תשובה: הפעולה מוחקת מהתור את הערכים הכפולים – מכל ערך נשאר מופע אחד בלבד (המופע האחרון שלו), והסדר היחסי של האיברים שנשארו נשמר.
שאלה 6 · תור מושלם N ותור סופר מושלם
התור הבא הוא תור מושלם של 5 אבל לא תור מושלם של 7 (כי מספר 6 אינו מופיע בתור).
כתבו פעולה `boolean isPerfectN(Queue<Integer> q, int n)` (ב-C#: `bool IsPerfectN(Queue<int> q, int n)`) המקבלת תור של מספרים שלמים q ומספר שלם וחיובי n. הפעולה תבדוק אם תור הוא "תור מושלם של n". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כתבו פעולה `void doItSuper(Queue<Integer> q, int n)` (ב-C#: `void DoItSuper(Queue<int> q, int n)`) המקבלת תור של מספרים שלמים q ומספר שלם וחיובי n. הפעולה מורידה מתור ערכים מיותרים ומוסיפה בסוף התור ערכים חסרים, כך שיתקבל תור "סופר מושלם n".
אם לפני זימון הפעולה התור q היה
אז אחרי ביצוע זימון הפעולה doItSuper(q, 9) התור q יהיה:
מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א–ב? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
מערך בוליאני exists בגודל n+1: מסמנים כל ערך בתחום 1..n שמופיע בתור (והתור משוחזר); אם כל התאים 1..n מסומנים – true.
נתון: תור q ומספר חיובי n.
מבוקש: true אם כל אחד מהמספרים מופיע בתור (מותר שיופיעו גם מספרים אחרים או כפולים).
הרעיון: מערך סימון.
1. יוצרים מערך בוליאני `exists` בגודל (תא 0 לא בשימוש). `exists[x]` יהיה true אם המספר x נמצא בתור.
2. מוציאים את כל איברי q לתור עזר `temp`. כל איבר x בתחום מסומן ב-`exists[x] = true`; איברים מחוץ לתחום פשוט מדלגים עליהם (אחרת הייתה חריגה מגבולות המערך).
3. מחזירים את האיברים מ-`temp` ל-q – התור נשמר כפי שהיה.
4. עוברים על התאים : אם אחד מהם false – מספר חסר, מחזירים false. אחרת מחזירים true.
בדוגמה (): עבור מסומנים 1–5 והתשובה true; עבור התא 6 נשאר false והתשובה false.
public static boolean isPerfectN(Queue<Integer> q, int n)
{
boolean[] exists = new boolean[n + 1];
Queue<Integer> temp = new Queue<Integer>();
while (!q.isEmpty())
{
int x = q.remove();
temp.insert(x);
if (x >= 1 && x <= n)
exists[x] = true; // x נמצא בתור
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
for (int i = 1; i <= n; i++)
if (!exists[i])
return false; // המספר i חסר
return true;
}public static bool IsPerfectN(Queue<int> q, int n)
{
bool[] exists = new bool[n + 1];
Queue<int> temp = new Queue<int>();
while (!q.IsEmpty())
{
int x = q.Remove();
temp.Insert(x);
if (x >= 1 && x <= n)
exists[x] = true; // x נמצא בתור
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
for (int i = 1; i <= n; i++)
if (!exists[i])
return false; // המספר i חסר
return true;
}תשובה: מסמנים במערך בוליאני את הערכים 1..n שנמצאים בתור, ומחזירים true רק אם כולם סומנו.
סעיף ב
עוברים על התור פעם אחת: משאירים כל ערך בתחום 1..n (גם מופעים חוזרים, כמו בדוגמה) וזורקים ערכים מחוץ לתחום, ומסמנים במערך; אחר כך מוסיפים בסוף, בסדר עולה, כל ערך 1..n שלא סומן. בדוגמה: 4, 5, 3, 2, 4, 1, 7, 6, 8, 9.
נתון: תור q ומספר חיובי n.
מבוקש: לשנות את q כך שיכיל את כל המספרים בין 1 ל-n, ולא יכיל אף מספר אחר. לפי הדוגמה, האיברים שנשארים שומרים על הסדר שלהם, ערך שמופיע פעמיים בתחום נשאר פעמיים (ה-4 בדוגמה), והחסרים נוספים בסוף בסדר עולה.
ערכים "מיותרים" הם הערכים שמחוץ לתחום (בדוגמה: 15). הם היחידים שמפריעים לתנאי "ורק אותם".
1. מערך בוליאני `exists` בגודל שומר אילו ערכים מהתחום נמצאים בתור.
2. מעבירים את כל איברי q לתור עזר `temp` (כדי לעבור על כל האיברים המקוריים בדיוק פעם אחת).
3. מוציאים מ-`temp` איבר x: אם – מסמנים `exists[x] = true` ומחזירים אותו ל-q. אחרת הוא מיותר ולא מוחזר.
4. בסוף, עבור , כל ערך שלא סומן חסר – מוסיפים אותו לסוף q.
בדוגמה (): עוברים – נשמרים; 15 – מחוץ לתחום, נזרק; – נשמרים. התור כעת . חסרים 6, 8, 9 – מוסיפים אותם, ומתקבל , בדיוק כמו בדוגמה.
public static void doItSuper(Queue<Integer> q, int n)
{
boolean[] exists = new boolean[n + 1];
Queue<Integer> temp = new Queue<Integer>();
while (!q.isEmpty())
temp.insert(q.remove());
while (!temp.isEmpty())
{
int x = temp.remove();
if (x >= 1 && x <= n) // ערך בתחום - נשאר בתור
{
exists[x] = true;
q.insert(x);
} // אחרת - ערך מיותר
}
for (int i = 1; i <= n; i++) // הוספת הערכים החסרים
if (!exists[i])
q.insert(i);
}public static void DoItSuper(Queue<int> q, int n)
{
bool[] exists = new bool[n + 1];
Queue<int> temp = new Queue<int>();
while (!q.IsEmpty())
temp.Insert(q.Remove());
while (!temp.IsEmpty())
{
int x = temp.Remove();
if (x >= 1 && x <= n) // ערך בתחום - נשאר בתור
{
exists[x] = true;
q.Insert(x);
} // אחרת - ערך מיותר
}
for (int i = 1; i <= n; i++) // הוספת הערכים החסרים
if (!exists[i])
q.Insert(i);
}תשובה: משאירים בתור את כל הערכים שבתחום 1..n, זורקים את הערכים שמחוץ לתחום, ומוסיפים בסוף את הערכים החסרים; בדוגמה מתקבל .
סעיף ג
שתיהן , כאשר m מספר האיברים בתור.
נסמן ב- את מספר האיברים בתור וב- את הפרמטר.
1. isPerfectN: יצירת המערך – ; מעבר על התור ושחזורו – פעולות ; בדיקת התאים – . סך הכול .
2. doItSuper: יצירת המערך – ; העברה ל-`temp` ומעבר עליו – פעולות; הוספת החסרים – לולאה של צעדים. סך הכול .
הסימון במערך מאפשר לבדוק "האם הערך כבר נמצא" ב-, ולכן אין לולאה כפולה.
תשובה: שתי הפעולות – לינאריות.
שאלה 7 · זוג בעל סכום נתון וסכום מרבי במחסנית
כתבו פעולה המקבלת מחסנית מספרים שלמים s ומספר שלם num. הפעולה תבדוק אם קיים במחסנית זוג איברים שהסכום שלהם שווה ל-num. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean existSum(Stack<Integer> s, int num)public static bool ExistSum(Stack<int> s, int num)כתבו פעולה המקבלת מחסנית של מספרים שלמים s ומחזירה את הסכום הגדול ביותר של שני איברי המחסנית. אפשר להניח שבמחסנית יש לפחות שני איברים.
כותרת הפעולה:
public static int maxSum(Stack<Integer> s)public static int MaxSum(Stack<int> s)מהן סיבוכיות הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
מעתיקים את המחסנית למערך (ומשחזרים), ובודקים כל זוג מקומות אם .
נתון: מחסנית s ומספר num.
מבוקש: true אם יש שני איברים (בשני מקומות שונים במחסנית) שסכומם num.
1. מוציאים את האיברים למחסנית עזר וסופרים אותם ().
2. מעבירים אותם למערך, ובאותו צעד מחזירים אותם ל-s – המחסנית משוחזרת.
3. עוברים על כל הזוגות ; ברגע שנמצא זוג עם `arr[i] + arr[j] == num` – מחזירים true. אם אין זוג כזה – false.
הדרישה מבטיחה ששני האיברים בזוג הם במקומות שונים (איבר לא מזווג עם עצמו). למשל במחסנית : עבור num = 6 התשובה true ( או ), ועבור num = 16 התשובה false (8 מופיע פעם אחת בלבד).
public static boolean existSum(Stack<Integer> s, int num)
{
Stack<Integer> temp = new Stack<Integer>();
int n = 0;
while (!s.isEmpty())
{
temp.push(s.pop());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור s
{
arr[i] = temp.pop();
s.push(arr[i]);
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] + arr[j] == num)
return true;
return false;
}public static bool ExistSum(Stack<int> s, int num)
{
Stack<int> temp = new Stack<int>();
int n = 0;
while (!s.IsEmpty())
{
temp.Push(s.Pop());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור s
{
arr[i] = temp.Pop();
s.Push(arr[i]);
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] + arr[j] == num)
return true;
return false;
}תשובה: בודקים את כל זוגות האיברים (דרך מערך עזר, המחסנית משוחזרת); אם סכום של זוג כלשהו שווה ל-num – true, אחרת false.
סעיף ב
הסכום של שני האיברים הגדולים ביותר: מעבר אחד עם max1 ≥ max2, והמחסנית משוחזרת.
הרעיון: הסכום הגדול ביותר של שני איברים הוא סכום שני האיברים הגדולים ביותר במחסנית (אם מחליפים אחד מהם באיבר אחר, הסכום רק קטן או נשאר). לכן מספיק למצוא אותם במעבר אחד:
1. מוציאים את שני האיברים הראשונים: `max1` הגדול מביניהם ו-`max2` הקטן.
2. לכל איבר x נוסף: אם – `max1` הקודם יורד להיות `max2`, ו-x נעשה `max1`. אחרת, אם – x מחליף את `max2`.
3. כל איבר שמוצא נדחף למחסנית עזר, ובסוף מחזירים את כולם ל-s (המחסנית משוחזרת).
4. מחזירים .
הפתרון עובד גם עם מספרים שליליים ועם ערכים כפולים (למשל במחסנית הסכום הוא ), כי ההתחלה היא משני איברים אמיתיים ולא מ-0. במחסנית מתקבל .
public static int maxSum(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
int max1 = s.pop();
int max2 = s.pop();
temp.push(max1);
temp.push(max2);
if (max2 > max1) // max1 - הגדול, max2 - השני בגודלו
{
int t = max1;
max1 = max2;
max2 = t;
}
while (!s.isEmpty())
{
int x = s.pop();
temp.push(x);
if (x > max1)
{
max2 = max1;
max1 = x;
}
else if (x > max2)
max2 = x;
}
while (!temp.isEmpty()) // שחזור המחסנית
s.push(temp.pop());
return max1 + max2;
}public static int MaxSum(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
int max1 = s.Pop();
int max2 = s.Pop();
temp.Push(max1);
temp.Push(max2);
if (max2 > max1) // max1 - הגדול, max2 - השני בגודלו
{
int t = max1;
max1 = max2;
max2 = t;
}
while (!s.IsEmpty())
{
int x = s.Pop();
temp.Push(x);
if (x > max1)
{
max2 = max1;
max1 = x;
}
else if (x > max2)
max2 = x;
}
while (!temp.IsEmpty()) // שחזור המחסנית
s.Push(temp.Pop());
return max1 + max2;
}תשובה: מוצאים במעבר אחד את שני האיברים הגדולים ביותר ומחזירים את סכומם; המחסנית משוחזרת.
סעיף ג
existSum – ; maxSum – .
נסמן ב- את מספר האיברים במחסנית.
1. existSum: ההעתקה למערך והשחזור – . הלולאה הכפולה בודקת במקרה הגרוע את כל הזוגות. סך הכול .
2. maxSum: מעבר אחד על המחסנית ( איברים, לכל איבר) ועוד מעבר שחזור. סך הכול .
תשובה: existSum – , maxSum – .
שאלה 8 · פעולות על קבוצת מספרים דרך ממשק בלבד
קבוצת מספרים – SetOfNumbers – היא אוסף של מספרים, כאשר כל מספר יכול להופיע בקבוצה פעם אחת בלבד. אין חשיבות לסדר המספרים בקבוצה.
לפניכם ממשק חלקי של המחלקה SetOfNumbers המייצגת קבוצת מספרים שלמים.
כתבו במחלקה SetOfNumbers פעולה פנימית המחזירה את מספר האיברים בקבוצה.
יש לשמור על הקבוצה אחרי ביצוע הפעולה.
כותרת הפעולה:
public int sizeOfSet()public int SizeOfSet()כתבו במחלקה SetOfNumbers פעולה פנימית המחזירה את המספר הקטן ביותר בקבוצה ומוחקת אותו מהקבוצה.
הנחה: הקבוצה לא ריקה.
כותרת הפעולה:
public int removeMin()public int RemoveMin()כתבו פעולה חיצונית המקבלת שתי קבוצות sn1 ו-sn2. הפעולה תחזיר true אם כל האיברים בקבוצה sn1 גדולים מכל האיברים בקבוצה sn2, אם לא – הפעולה תחזיר false.
יש לשמור על הקבוצה אחרי ביצוע הפעולה.
הנחה: הקבוצות לא ריקות.
כותרת הפעולה:
public static boolean bigger(SetOfNumbers sn1,SetOfNumbers sn2)public static bool Bigger(SetOfNumbers sn1,SetOfNumbers sn2)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א'–ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
מוציאים את כל האיברים לקבוצת עזר וסופרים, ואחר כך מחזירים אותם לקבוצה.
הרעיון: המימוש של הקבוצה לא ידוע, ולכן הדרך היחידה "לעבור" על האיברים היא להוציא אותם אחד אחד ב-`removeRandom`.
1. כל עוד הקבוצה (`this`) לא ריקה – מוציאים איבר, מוסיפים אותו לקבוצת עזר `temp` ומגדילים מונה.
2. כשהקבוצה מתרוקנת, המונה שווה למספר האיברים.
3. מחזירים את כל האיברים מ-`temp` לקבוצה. האיברים שונים זה מזה, ולכן `addToSet` מוסיפה כל אחד מהם, והקבוצה חוזרת להיות כפי שהייתה (הסדר אינו חשוב בקבוצה).
public int sizeOfSet()
{
SetOfNumbers temp = new SetOfNumbers();
int count = 0;
while (!this.isEmpty())
{
temp.addToSet(this.removeRandom());
count++;
}
while (!temp.isEmpty()) // שחזור הקבוצה
this.addToSet(temp.removeRandom());
return count;
}public int SizeOfSet()
{
SetOfNumbers temp = new SetOfNumbers();
int count = 0;
while (!this.IsEmpty())
{
temp.AddToSet(this.RemoveRandom());
count++;
}
while (!temp.IsEmpty()) // שחזור הקבוצה
this.AddToSet(temp.RemoveRandom());
return count;
}תשובה: סופרים את האיברים תוך העברתם לקבוצת עזר, ומחזירים אותם לקבוצה.
סעיף ב
מוציאים את כל האיברים ומחפשים את הקטן ביותר; כל השאר מועברים לקבוצת עזר ומוחזרים, והמינימום לא מוחזר לקבוצה.
1. מוציאים איבר ראשון – הוא המינימום הזמני `min` (הקבוצה לא ריקה).
2. מוציאים את שאר האיברים. אם איבר x קטן מ-`min` – ה-`min` הקודם כבר אינו המינימום, ולכן הוא עובר לקבוצת העזר, ו-x נעשה `min`. אחרת x עובר לקבוצת העזר.
3. בסוף בקבוצת העזר נמצאים כל האיברים חוץ מהמינימום. מחזירים אותם לקבוצה ומחזירים את `min` – כך הוא נמחק מהקבוצה.
public int removeMin()
{
SetOfNumbers temp = new SetOfNumbers();
int min = this.removeRandom();
while (!this.isEmpty())
{
int x = this.removeRandom();
if (x < min)
{
temp.addToSet(min); // המינימום הקודם חוזר לקבוצה
min = x;
}
else
temp.addToSet(x);
}
while (!temp.isEmpty()) // כל האיברים חוץ מהמינימום
this.addToSet(temp.removeRandom());
return min;
}public int RemoveMin()
{
SetOfNumbers temp = new SetOfNumbers();
int min = this.RemoveRandom();
while (!this.IsEmpty())
{
int x = this.RemoveRandom();
if (x < min)
{
temp.AddToSet(min); // המינימום הקודם חוזר לקבוצה
min = x;
}
else
temp.AddToSet(x);
}
while (!temp.IsEmpty()) // כל האיברים חוץ מהמינימום
this.AddToSet(temp.RemoveRandom());
return min;
}תשובה: מוצאים את המינימום תוך ריקון הקבוצה לקבוצת עזר, מחזירים לקבוצה את כל האיברים מלבדו, ומחזירים אותו.
סעיף ג
כל איברי sn1 גדולים מכל איברי sn2 אם ורק אם min(sn1) > max(sn2); מחשבים את שניהם (בעזרת removeMin והחזרה, ומעבר עם קבוצת עזר) ומשחזרים את הקבוצות.
הרעיון: כל איבר של sn1 גדול מכל איבר של sn2 בדיוק כאשר האיבר הקטן ביותר ב-sn1 גדול מהאיבר הגדול ביותר ב-sn2. לכן:
1. המינימום של sn1: משתמשים בפעולה `removeMin` מסעיף ב', ומיד מחזירים את הערך לקבוצה ב-`addToSet` – sn1 נשמרת.
2. המקסימום של sn2: מוציאים את כל איבריה לקבוצת עזר תוך שמירת הגדול ביותר, ואחר כך מחזירים את כולם ל-sn2.
3. מחזירים `min1 > max2`.
למשל עבור sn1 = {7, 10, 12, 15} ו-sn2 = {−1, 3, 6}: ולכן true; אם נוסיף ל-sn2 את 7, אז לא מתקיים, והתשובה false.
public static boolean bigger(SetOfNumbers sn1, SetOfNumbers sn2)
{
int min1 = sn1.removeMin(); // הקטן ביותר ב-sn1
sn1.addToSet(min1); // מחזירים אותו - sn1 נשמרת
SetOfNumbers temp = new SetOfNumbers();
int max2 = sn2.removeRandom();
temp.addToSet(max2);
while (!sn2.isEmpty()) // הגדול ביותר ב-sn2
{
int x = sn2.removeRandom();
temp.addToSet(x);
if (x > max2)
max2 = x;
}
while (!temp.isEmpty()) // שחזור sn2
sn2.addToSet(temp.removeRandom());
return min1 > max2;
}public static bool Bigger(SetOfNumbers sn1, SetOfNumbers sn2)
{
int min1 = sn1.RemoveMin(); // הקטן ביותר ב-sn1
sn1.AddToSet(min1); // מחזירים אותו - sn1 נשמרת
SetOfNumbers temp = new SetOfNumbers();
int max2 = sn2.RemoveRandom();
temp.AddToSet(max2);
while (!sn2.IsEmpty()) // הגדול ביותר ב-sn2
{
int x = sn2.RemoveRandom();
temp.AddToSet(x);
if (x > max2)
max2 = x;
}
while (!temp.IsEmpty()) // שחזור sn2
sn2.AddToSet(temp.RemoveRandom());
return min1 > max2;
}תשובה: מחזירים true אם ורק אם המינימום של sn1 גדול מהמקסימום של sn2; שתי הקבוצות משוחזרות.
סעיף ד
sizeOfSet – ; removeMin – ; bigger – .
כל פעולות הממשק הן . נסמן ב- את מספר האיברים בקבוצה.
1. sizeOfSet: כל איבר מוצא פעם אחת ומוחזר פעם אחת – פעולות , כלומר .
2. removeMin: כל איבר מוצא פעם אחת, ו- איברים מוחזרים – .
3. bigger: `removeMin` על sn1 – , ועוד הוספה אחת; מעבר על sn2 ושחזורה – . סך הכול , כאשר מספרי האיברים בקבוצות.
תשובה: כל שלוש הפעולות לינאריות: , , .
שאלה 9 · מסלול משורש לעלה עם סכום ואורך נתונים
נתונה הפעולה what. הפעולה מקבלת הפניה לשורש עץ בינרי של מספרים שלמים חיוביים bt ושני מספרים שלמים חיוביים num ו-count.
public static boolean what(BinNode<Integer> bt,
int num, int count)
{
if(bt == null) return false;
if(num < 1 || count < 1) return false;
if(bt.getLeft()==null && bt.getRight()==null)
{
return bt.getValue() == num && count == 1;
}
return what(bt.getLeft(), num - bt.getValue(), count -1) ||
what(bt.getRight(), num - bt.getValue(), count -1);
}public static bool What(BinNode<int> bt,
int num, int count)
{
if(bt == null) return false;
if(num < 1 || count < 1) return false;
if(bt.GetLeft()==null && bt.GetRight()==null)
{
return bt.GetValue() == num && count == 1;
}
return What(bt.GetLeft(), num - bt.GetValue(), count -1) ||
What(bt.GetRight(), num - bt.GetValue(), count -1);
}נתון העץ הבינרי bt הבא:

מה תהיה תוצאת זימון הפעולה what(bt, 16, 4)?
תנו דוגמה לערכים של num ו-count כך שהזימון what(bt, num, count) יחזיר תוצאה שונה מזו שהתקבלה בסעיף א'.
האם קיים ערך count>0 שעבורו הזימון what(bt, num, count) יחזיר ערך false לכל num>0? הסבירו את תשובתכם.
תנו דוגמה לעץ בינרי של מספרים שלמים חיוביים bt שעבורו כל אחד משלושת הזימונים הבאים יחזיר ערך true:
what(bt, 2, 2)
what(bt, 3, 3)
what(bt, 4, 4)מה מבצעת הפעולה what באופן כללי?
◂ פתרון מלא לשאלה 9
סעיף א
false
מבנה העץ: השורש 7. בנו השמאלי 1, ולו בן שמאלי 1 (עלה) ובן ימני 7, שלו בן ימני 6 (עלה). בנו הימני של השורש 5, ולו רק בן ימני 2; ל-2 בן שמאלי 2 (שלו בן שמאלי 6, עלה) ובן ימני 3 (עלה).
מה עושה כל זימון: בצומת שאינו עלה מחסירים את ערך הצומת מ-num ומורידים 1 מ-count, וממשיכים לשני הבנים (ה-`||` עוצר ברגע שצד אחד מחזיר true). בעלה בודקים אם הערך שווה ל-num ו-count שווה 1.
בדיקה כוללת: המסלולים משורש לעלה הם (סכום 9, 3 צמתים), (סכום 21, 4 צמתים), (סכום 22, 5 צמתים), (סכום 17, 4 צמתים). אף מסלול אינו בעל סכום 16 ו-4 צמתים.
תשובה: הזימון what(bt, 16, 4) מחזיר false.
סעיף ב
למשל num = 9, count = 3 (המסלול 7→1→1); גם (17, 4), (21, 4), (22, 5).
צריך זימון שמחזיר true, כלומר מסלול משורש לעלה שבו בדיוק count צמתים וסכום ערכיהם num.
המסלול כולל 3 צמתים וסכומו . מעקב קצר: (7, 9, 3) → (1, 2, 2) → העלה 1 עם (1, 1): ו-count = 1, ולכן true, וה-true עולה עד השורש.
תשובה: למשל what(bt, 9, 3) מחזיר true. (גם (17, 4), (21, 4) או (22, 5) מתאימים.)
סעיף ג
כן, למשל count = 1 (או 2, או כל count ≥ 6) – אין בעץ מסלול משורש לעלה עם מספר כזה של צמתים.
הפעולה מחזירה true רק אם יש מסלול משורש לעלה שבו בדיוק count צמתים (ובנוסף הסכום שווה ל-num). לכן אם אין בעץ מסלול משורש לעלה באורך count, התשובה false לכל num.
אורכי המסלולים משורש לעלה בעץ (במספר צמתים): 3, 4, 5, 4. לכן:
1. count = 1: השורש אינו עלה, ולכן הפעולה עוברת לבנים עם count = 0, ושם `count < 1` מחזיר false. התוצאה false לכל num.
2. count = 2: אין עלה בעומק 2 (שני הבנים של השורש אינם עלים), ולכן false.
3. count ≥ 6: המסלול הארוך ביותר כולל 5 צמתים, ולכן false.
תשובה: כן. למשל count = 1 (וגם 2 או כל count ≥ 6): אין מסלול משורש לעלה עם מספר כזה של צמתים, ולכן what מחזירה false לכל num > 0.
סעיף ד
עץ שכל ערכיו 1 ויש בו עלים בעומק 2, 3 ו-4 צמתים, למשל: שורש 1; בן שמאלי – עלה 1; בן ימני 1, ולו בן שמאלי עלה 1 ובן ימני 1 שלו בן עלה 1.
הרעיון: כדי ש-what(bt, k, k) יחזיר true צריך מסלול משורש לעלה עם צמתים שסכומם . מכיוון שהערכים חיוביים שלמים (לפחות 1), סכום של צמתים הוא לפחות , ושווה ל- רק אם כל הצמתים במסלול הם 1. לכן בונים עץ שכל ערכיו 1, עם עלים בעומקים של 2, 3 ו-4 צמתים:
1. השורש: 1.
2. הבן השמאלי של השורש: עלה 1 – מסלול של 2 צמתים, סכום 2.
3. הבן הימני של השורש: 1. לו בן שמאלי – עלה 1 (מסלול של 3 צמתים, סכום 3), ובן ימני 1.
4. לבן הימני הזה יש בן אחד – עלה 1 – מסלול של 4 צמתים, סכום 4.
בדיקה: what(bt, 2, 2) – (1, 2, 2) → העלה השמאלי עם (1, 1) → true. what(bt, 3, 3) – (1, 3, 3) → העלה השמאלי עם (2, 2): → false; הבן הימני (2, 2) → העלה שלו עם (1, 1) → true. what(bt, 4, 4) – באותו אופן מגיעים לעלה התחתון עם (1, 1) → true.
תשובה: עץ שכל ערכיו 1 ויש בו עלים במסלולים של 2, 3 ו-4 צמתים מהשורש (כמו בעץ שבציור).
סעיף ה
מחזירה true אם יש בעץ מסלול משורש לעלה בן count צמתים בדיוק שסכום ערכיו num; אחרת false.
בכל צעד רקורסיבי מחסירים מ-num את ערך הצומת ומקטינים את count ב-1, ובעלה בודקים שהערך שנותר שווה לערך העלה ושנשאר צומת אחד. כלומר, לאורך המסלול מחסירים את כל הערכים ואת מספר הצמתים, ובודקים שבעלה "נגמרו" שניהם בדיוק. התנאי `num < 1 || count < 1` רק עוצר מוקדם מסלול שכבר אינו יכול להצליח (הערכים חיוביים).
תשובה: הפעולה מחזירה true אם בעץ קיים מסלול מהשורש לעלה שבו בדיוק count צמתים וסכום ערכי הצמתים בו שווה ל-num; אחרת היא מחזירה false.
שאלה 10 · מעקב אחר עצמים, ירושה והפניות
בבית האבות "גיל הזהב" הוחלט לצרף לכל דייר איש קשר שדרכו משפחות הדיירים יוכלו לקבל מידע עדכני על מצבו הבריאותי של הדייר ועל תוכניות הבידור והאירועים בבית האבות. איש הקשר הוא דייר בבית האבות שהתנדב לתפקיד זה. לשם כך פותחו שלוש המחלקות הבאות: Person, Contact, Test.
המחלקה Person מתארת דייר:
public class Person {
private String fName; // שם פרטי
private String lName; // שם משפחה
private int age; // גיל
public Person(){
this.fName = "unknown";
this.lName = "unknown";
this.age = 120;
}
public Person(String fName, String lName, int age) {
this.fName = fName;
this.lName = lName;
this.age = age;
}
public Person(Person other){
this.fName = other.fName;
this.lName = other.lName;
this.age = other.age;
}
public void addAge(int num) {
if(this.age + num < 120)
this.age += num;
}
public String toString(){
return this.fName+" "+this.lName + " "+this.age;
}
}public class Person {
private string fName; // שם פרטי
private string lName; // שם משפחה
private int age; // גיל
public Person(){
this.fName = "unknown";
this.lName = "unknown";
this.age = 120;
}
public Person(string fName, string lName, int age) {
this.fName = fName;
this.lName = lName;
this.age = age;
}
public Person(Person other){
this.fName = other.fName;
this.lName = other.lName;
this.age = other.age;
}
public void AddAge(int num) {
if(this.age + num < 120)
this.age += num;
}
public override string ToString(){
return this.fName+" "+this.lName + " "+this.age;
}
}המחלקה Contact מתארת איש קשר:
public class Contact extends Person {
private String tel; // טלפון של איש קשר
private Person contact; // איש קשר
public Contact(String fName, String lName, int age){
super(fName,lName,age);
this.tel = "NO";
this.contact = new Person();
}
public Contact(Person person){
super(person);
this.tel = "NO";
this.contact = null;
}
public Contact(Person person1, Person person2, String tel){
super(person1);
this.tel = tel;
this.contact = new Person(person2);
}
public Contact(String fName, String lName, int age,
Person person,String tel){
super(fName,lName,age);
this.tel = tel;
this.contact = person;
}
public void setContact(Person person, String tel){
this.contact = person;
this.tel = tel;
}
public String toString(){
if(this.contact == null) return super.toString();
return super.toString() + " --> "+ this.contact +
" tel: "+this.tel;
}
}public class Contact : Person {
private string tel; // טלפון של איש קשר
private Person contact; // איש קשר
public Contact(string fName, string lName, int age):
base(fName,lName,age){
this.tel = "NO";
this.contact = new Person();
}
public Contact(Person person): base(person){
this.tel = "NO";
this.contact = null;
}
public Contact(Person person1, Person person2, string tel):
base(person1){
this.tel = tel;
this.contact = new Person(person2);
}
public Contact(string fName, string lName, int age,
Person person, String tel):
base(fName,lName,age){
this.tel = tel;
this.contact = person;
}
public void SetContact(Person person, string tel){
this.contact = person;
this.tel = tel;
}
public override string ToString(){
if(this.contact == null) return base.ToString();
return base.ToString() + " --> "+ this.contact +
" tel: "+this.tel;
}
}נתונה הפעולה הראשית main אשר נמצאת במחלקה Test. עקבו אחרי הביצוע של הפעולה main ורשמו מה יהיו ערכי התכונות של כל עצם שנוצר במהלך הביצוע.
public static void main(String[] args){
Person[] p = new Person[6];
p[0] = new Person("Avi","Barak",60);
p[1] = new Person("Benny","Coehn",70);
p[2] = new Person(p[1]);
p[3] = p[1];
p[4] = new Person();
p[5] = new Person("David","Ezra",65);
p[3].addAge(30);
for(int i = 0; i< p.length; i++)
System.out.println(i+") "+p[i]);
Person[] c = new Person[6];
c[0] = new Contact(p[0],p[5], "123");
c[1] = new Contact(p[1]);
c[2] = new Contact (p[5],p[2], "456");
c[3] = new Contact("Eric","Far",65,c[0],"789");
c[4] = new Contact( "Fiona","Gold",40);
c[5] = (Person)c[3];
((Contact)c[1]).setContact(c[5],"999");
for(int i = 0; i< c.length; i++)
System.out.println(i+") "+ c[i]);
}public static void Main(string[] args){
Person[] p = new Person[6];
p[0] = new Person("Avi","Barak",60);
p[1] = new Person("Benny","Coehn",70);
p[2] = new Person(p[1]);
p[3] = p[1];
p[4] = new Person();
p[5] = new Person("David","Ezra",65);
p[3].AddAge(30);
for(int i = 0; i< p.Length; i++)
Console.WriteLine(i+") "+p[i]);
Person[] c = new Person[6];
c[0] = new Contact(p[0],p[5], "123");
c[1] = new Contact(p[1]);
c[2] = new Contact (p[5],p[2], "456");
c[3] = new Contact("Eric","Far",65,c[0],"789");
c[4] = new Contact( "Fiona","Gold",40);
c[5] = (Person)c[3];
((Contact)c[1]).SetContact(c[5],"999");
for(int i = 0; i< L.length; i++)
Console.WriteLine(i+") "+ c[i]);
}מהו הפלט של הפעולה main?
◂ פתרון מלא לשאלה 10
סעיף א
p[1] ו-p[3] הם אותו עצם (Benny Coehn 100); p[2] עותק (Benny Coehn 70). c[5] ו-c[3] אותו עצם; c[3].contact = c[0]; c[1].contact = c[3], tel = "999". פירוט מלא בטבלאות.
שלב 1 – המערך p. כל `new` יוצר עצם חדש; השמה של הפניה (`p[3] = p[1]`) אינה יוצרת עצם.
1. `p[0]` – עצם חדש: Avi, Barak, 60.
2. `p[1]` – עצם חדש: Benny, Coehn, 70.
3. `p[2] = new Person(p[1])` – עצם חדש, עותק של p[1] באותו רגע: Benny, Coehn, 70.
4. `p[3] = p[1]` – אין עצם חדש: p[3] ו-p[1] מפנים לאותו עצם.
5. `p[4] = new Person()` – בנאי ברירת המחדל: unknown, unknown, 120.
6. `p[5]` – עצם חדש: David, Ezra, 65.
7. `p[3].addAge(30)`: , ולכן הגיל של העצם המשותף ל-p[1] ול-p[3] נעשה 100. העותק p[2] לא משתנה (70).
שלב 2 – המערך c (כל העצמים מטיפוס Contact, ולכל אחד גם תכונות Person):
1. `c[0] = new Contact(p[0], p[5], "123")` – הבנאי השלישי: `super(person1)` מעתיק את Avi Barak 60; tel = "123"; contact = עצם Person חדש, עותק של p[5]: David Ezra 65.
2. `c[1] = new Contact(p[1])` – הבנאי השני: עותק של Benny Coehn 100; tel = "NO"; contact = null.
3. `c[2] = new Contact(p[5], p[2], "456")` – David Ezra 65; tel = "456"; contact = עצם Person חדש, עותק של p[2]: Benny Coehn 70.
4. `c[3] = new Contact("Eric", "Far", 65, c[0], "789")` – הבנאי הרביעי: Eric Far 65; tel = "789"; contact = הפניה לעצם c[0] עצמו (לא עותק).
5. `c[4] = new Contact("Fiona", "Gold", 40)` – הבנאי הראשון: Fiona Gold 40; tel = "NO"; contact = עצם Person חדש מבנאי ברירת המחדל: unknown unknown 120.
6. `c[5] = (Person)c[3]` – אין עצם חדש: c[5] מפנה לאותו עצם כמו c[3]. ההמרה לא משנה את העצם – הוא נשאר Contact.
7. `((Contact)c[1]).setContact(c[5], "999")` – בעצם c[1]: contact = c[5] (כלומר העצם c[3]), tel = "999".
הערה (C#): בלולאה האחרונה מודפס `L.length` – אין משתנה L; הכוונה ל-`c.Length` (שגיאת הדפסה).
תשובה: הערכים מפורטים בטבלאות: p[1] ו-p[3] הם עצם אחד (גיל 100) ו-p[2] עותק (גיל 70); c[3] ו-c[5] עצם אחד שאיש הקשר שלו הוא העצם c[0]; ל-c[1] נקבע איש קשר c[3] וטלפון "999".
סעיף ב
שתים-עשרה שורות; למשל `1) Benny Coehn 100 --> Eric Far 65 --> Avi Barak 60 --> David Ezra 65 tel: 123 tel: 789 tel: 999`.
הלולאה הראשונה מדפיסה את p לפי `toString` של Person (שם פרטי, שם משפחה, גיל):
0) Avi Barak 60
1) Benny Coehn 100
2) Benny Coehn 70
3) Benny Coehn 100
4) unknown unknown 120
5) David Ezra 65הלולאה השנייה מדפיסה את c. כל העצמים הם Contact, ולכן (קישור דינמי) מופעלת `toString` של Contact גם כשההפניה מטיפוס Person. אם contact אינו null, מודפס: פרטי העצם, ` --> `, ה-`toString` של איש הקשר, ` tel: ` והטלפון. כשאיש הקשר הוא בעצמו Contact – ההדפסה שלו רקורסיבית:
1. c[0]: `Avi Barak 60 --> David Ezra 65 tel: 123`.
2. c[3]: איש הקשר הוא c[0], ולכן `Eric Far 65 --> ` + (מחרוזת c[0]) + ` tel: 789`.
3. c[1]: איש הקשר הוא c[3], ולכן `Benny Coehn 100 --> ` + (מחרוזת c[3]) + ` tel: 999`.
4. c[5] הוא אותו עצם כמו c[3] – אותה שורה.
0) Avi Barak 60 --> David Ezra 65 tel: 123
1) Benny Coehn 100 --> Eric Far 65 --> Avi Barak 60 --> David Ezra 65 tel: 123 tel: 789 tel: 999
2) David Ezra 65 --> Benny Coehn 70 tel: 456
3) Eric Far 65 --> Avi Barak 60 --> David Ezra 65 tel: 123 tel: 789
4) Fiona Gold 40 --> unknown unknown 120 tel: NO
5) Eric Far 65 --> Avi Barak 60 --> David Ezra 65 tel: 123 tel: 789תשובה: הפלט הוא שתי קבוצות השורות שלמעלה (6 שורות עבור p ו-6 שורות עבור c).
שאלה 11 · מערכת תזכורות שבועית לתורים
המרכז הרפואי "כל הבריאות" מפעיל שירות של אישור תורים אוטומטי. המערכת מזכירה לכל אדם שקבע תור למכון כלשהו את פרטי התור ומקבלת ממנו אישור הגעה או ביטול התור. פרטי התור כוללים את שם המכון, תאריך התור, שעת התור. לכל לקוח מתקשרים פעם אחת בשבוע. על הלקוח לאשר את הגעתו באמצעות הקשה על הספרה 1, או לבטל את התור באמצעות הקשה על הספרה 2. אם אין מענה, הלקוח עובר לרשימת התזכורת של שבוע הבא. המערכת מחדשת את פרטי תזכורות התורים מדי שבוע.
המחלקה Reminder מייצגת תזכורת:
תכונות המחלקה:
private String cust; // שם הלקוח
private String tel; // טלפון הלקוח
private String inst; // שם המכון
private String date; // תאריך התור
private int hour; // שעת התור
private int status; // 2- ביטול, 1- אישור, 0- אין מענהprivate string cust; // שם הלקוח
private string tel; // טלפון הלקוח
private string inst; // שם המכון
private string date; // תאריך התור
private int hour; // שעת התור
private int status; // 2- ביטול, 1- אישור, 0- אין מענהבמחלקה הוגדרו פעולה בונה המקבלת את השם ומספר הטלפון של הלקוח, שם המכון, התאריך והשעה של התור. סטטוס התזכורת מאותחל ב-0 (אין מענה). במחלקה הוגדרו הפעולות set/get לכל התכונות. המחלקה DailyReminder מייצגת רשימת תזכורות ביום מסוים.
כתבו את כותרת המחלקה DailyReminder ואת התכונות שלה.
המחלקה WeeklyReminder מייצגת מערכת שבועית של תזכורות. במחלקה יש תכונה אחת – מערך של תזכורות בכל יום בשבוע (1–6). תא ה-0 מיועד לתזכורות שלא קיבלו מענה.
private DailyReminder [] arr = new DailyReminder[7];כתבו במחלקה WeeklyReminder פעולה המקבלת את הפרטים של הלקוח ושל התור ואת יום התזכורת dayReminder (1–6) ומוסיפה את התזכורת לרשימת התזכורות המתאימה.
כותרת הפעולה:
public void addReminder(String cust, String tel, String inst,
String date, int hour, int dayReminder)public void AddReminder(string cust, string tel, string inst,
string date, int hour, int dayReminder)כתבו במחלקה WeeklyReminder פעולה המקבלת את שם הלקוח cust, שם המכון inst, יום התזכורת dayReminder (1–6) וקוד אישור ההגעה answer (0/1/2).
אם ערך קוד האישור הוא 1 או 2, הפעולה תעדכן את הסטטוס בהתאם. אם אין מענה, הפעולה תעביר את התזכורת לרשימת תזכורות בתא 0 כדי לטפל בה בשבוע הבא. כותרת הפעולה:
public void updateReminder(String cust, String inst,
int dayReminder, int answer)public void UpdateReminder(string cust, string inst,
int dayReminder, int answer)כתבו במחלקה WeeklyReminder פעולה המקבלת מערך מכונים של המרכז הרפואי "כל הבריאות". הפעולה תדפיס עבור כל מכון את פרטי התורים שהתפנו עקב ביטול מצד המטופל.
◂ פתרון מלא לשאלה 11
סעיף א
public class DailyReminder עם התכונות int day (היום) ו-Node<Reminder> first (שרשרת התזכורות של היום).
הבחירה: את רשימת התזכורות של יום אחד נייצג כשרשרת חוליות `Node<Reminder>`. שרשרת מאפשרת לעבור על התזכורות בלי להרוס את האוסף, ולהוציא תזכורת מאמצע הרשימה (נצטרך זאת בסעיף ג', כשתזכורת שלא נענתה עוברת לתא 0). נוסיף גם את מספר היום, כדי שכל רשימה "תדע" לאיזה יום היא שייכת.
public class DailyReminder
{
private int day; // היום בשבוע (0 - תזכורות שלא נענו)
private Node<Reminder> first; // הפניה לחוליה הראשונה בשרשרת התזכורות של היוםpublic class DailyReminder
{
private int day; // היום בשבוע (0 - תזכורות שלא נענו)
private Node<Reminder> first; // הפניה לחוליה הראשונה בשרשרת התזכורות של היוםתשובה: `public class DailyReminder` עם התכונות `int day` – היום בשבוע (0 – תזכורות שלא נענו), ו-`Node<Reminder> first` – הפניה לחוליה הראשונה בשרשרת התזכורות של אותו יום.
סעיף ב
יוצרים עצם Reminder חדש מהפרטים ומוסיפים אותו לרשימה arr[dayReminder] (בעזרת פעולה add של DailyReminder).
נתון: פרטי הלקוח והתור, ויום התזכורת (1–6).
מבוקש: להוסיף תזכורת חדשה לרשימת התזכורות של אותו יום.
כדי שהפעולה תעבוד צריך שכל תא במערך יכיל עצם DailyReminder, ושב-DailyReminder תהיה פעולה המוסיפה תזכורת. לכן:
1. ב-DailyReminder: בנאי המקבל את היום ומתחיל שרשרת ריקה, פעולה `add` המוסיפה חוליה חדשה בתחילת השרשרת (הסדר בתוך יום אינו חשוב), ופעולת get לחוליה הראשונה.
2. ב-WeeklyReminder: בנאי שיוצר רשימה ריקה לכל אחד משבעת התאים (0–6).
3. `addReminder` יוצרת עצם Reminder חדש (הסטטוס שלו מאותחל ב-0 בבנאי) ומוסיפה אותו ל-`arr[dayReminder]`.
// במחלקה DailyReminder
public DailyReminder(int day)
{
this.day = day;
this.first = null;
}
public int getDay() { return this.day; }
public Node<Reminder> getFirst() { return this.first; }
public void add(Reminder r) // הוספה בתחילת השרשרת
{
Node<Reminder> node = new Node<Reminder>(r);
node.setNext(this.first);
this.first = node;
}
// במחלקה WeeklyReminder
public WeeklyReminder()
{
for (int i = 0; i < arr.length; i++)
arr[i] = new DailyReminder(i);
}
public void addReminder(String cust, String tel, String inst,
String date, int hour, int dayReminder)
{
Reminder r = new Reminder(cust, tel, inst, date, hour);
arr[dayReminder].add(r);
}// במחלקה DailyReminder
public DailyReminder(int day)
{
this.day = day;
this.first = null;
}
public int GetDay() { return this.day; }
public Node<Reminder> GetFirst() { return this.first; }
public void Add(Reminder r) // הוספה בתחילת השרשרת
{
Node<Reminder> node = new Node<Reminder>(r);
node.SetNext(this.first);
this.first = node;
}
// במחלקה WeeklyReminder
public WeeklyReminder()
{
for (int i = 0; i < arr.Length; i++)
arr[i] = new DailyReminder(i);
}
public void AddReminder(string cust, string tel, string inst,
string date, int hour, int dayReminder)
{
Reminder r = new Reminder(cust, tel, inst, date, hour);
arr[dayReminder].Add(r);
}תשובה: יוצרים Reminder חדש מהפרטים ומוסיפים אותו לשרשרת של `arr[dayReminder]`.
סעיף ג
answer 1 או 2: מוצאים ברשימה arr[dayReminder] את התזכורת לפי cust ו-inst ומעדכנים status = answer. answer 0: מוציאים את התזכורת מהרשימה ומוסיפים אותה ל-arr[0].
נתון: שם לקוח, שם מכון, יום ותשובת הלקוח (0 – אין מענה, 1 – אישור, 2 – ביטול).
מבוקש: לעדכן את התזכורת המתאימה – או להעביר אותה לתא 0.
הרעיון: תזכורת מזוהה לפי שם הלקוח ושם המכון ברשימה של היום הנתון. נוסיף ל-DailyReminder שתי פעולות עזר:
1. `find(cust, inst)` – עוברת על השרשרת ומחזירה את התזכורת המתאימה (או null אם אינה קיימת).
2. `remove(cust, inst)` – מוצאת את החוליה של התזכורת, מנתקת אותה מהשרשרת (אם זו החוליה הראשונה – מקדמים את `first`, אחרת מחברים את החוליה הקודמת לחוליה שאחריה) ומחזירה את התזכורת.
ב-`updateReminder`:
1. אם answer הוא 1 או 2 – מוצאים את התזכורת ומעדכנים את הסטטוס שלה לערך answer (1 – אישור, 2 – ביטול).
2. אחרת (0, אין מענה) – מוציאים את התזכורת מרשימת היום ומוסיפים אותה לרשימה `arr[0]`. הסטטוס שלה נשאר 0.
// במחלקה DailyReminder
public Reminder find(String cust, String inst)
{
Node<Reminder> p = this.first;
while (p != null)
{
Reminder r = p.getValue();
if (r.getCust().equals(cust) && r.getInst().equals(inst))
return r;
p = p.getNext();
}
return null;
}
public Reminder remove(String cust, String inst)
{
Node<Reminder> prev = null;
Node<Reminder> p = this.first;
while (p != null)
{
Reminder r = p.getValue();
if (r.getCust().equals(cust) && r.getInst().equals(inst))
{
if (prev == null)
this.first = p.getNext(); // מחיקת החוליה הראשונה
else
prev.setNext(p.getNext()); // עקיפת החוליה
return r;
}
prev = p;
p = p.getNext();
}
return null;
}
// במחלקה WeeklyReminder
public void updateReminder(String cust, String inst,
int dayReminder, int answer)
{
if (answer == 1 || answer == 2) // אישור או ביטול
{
Reminder r = arr[dayReminder].find(cust, inst);
if (r != null)
r.setStatus(answer);
}
else // אין מענה - לתא 0
{
Reminder r = arr[dayReminder].remove(cust, inst);
if (r != null)
arr[0].add(r);
}
}// במחלקה DailyReminder
public Reminder Find(string cust, string inst)
{
Node<Reminder> p = this.first;
while (p != null)
{
Reminder r = p.GetValue();
if (r.GetCust() == cust && r.GetInst() == inst)
return r;
p = p.GetNext();
}
return null;
}
public Reminder Remove(string cust, string inst)
{
Node<Reminder> prev = null;
Node<Reminder> p = this.first;
while (p != null)
{
Reminder r = p.GetValue();
if (r.GetCust() == cust && r.GetInst() == inst)
{
if (prev == null)
this.first = p.GetNext(); // מחיקת החוליה הראשונה
else
prev.SetNext(p.GetNext()); // עקיפת החוליה
return r;
}
prev = p;
p = p.GetNext();
}
return null;
}
// במחלקה WeeklyReminder
public void UpdateReminder(string cust, string inst,
int dayReminder, int answer)
{
if (answer == 1 || answer == 2) // אישור או ביטול
{
Reminder r = arr[dayReminder].Find(cust, inst);
if (r != null)
r.SetStatus(answer);
}
else // אין מענה - לתא 0
{
Reminder r = arr[dayReminder].Remove(cust, inst);
if (r != null)
arr[0].Add(r);
}
}תשובה: עבור 1 או 2 – מעדכנים את הסטטוס של התזכורת שנמצאה; עבור 0 – מוציאים את התזכורת מרשימת היום ומוסיפים אותה לרשימה בתא 0.
סעיף ד
לכל מכון במערך עוברים על הרשימות של הימים 1–6 ומדפיסים את התאריך והשעה של כל תזכורת של אותו מכון שהסטטוס שלה 2 (ביטול).
נתון: מערך של שמות מכונים.
מבוקש: לכל מכון – להדפיס את פרטי התורים שבוטלו (התפנו). תור שבוטל הוא תזכורת שהסטטוס שלה 2. "פרטי התור" שהתפנה הם התאריך והשעה שלו.
לא ניתנה כותרת, ולכן נבחר: `public void printCanceled(String[] insts)`.
1. לולאה על המכונים במערך. לכל מכון מדפיסים את שמו.
2. לולאה על הימים 1–6 (בתא 0 נמצאות רק תזכורות שלא נענו – סטטוס 0, ולכן אין בו ביטולים).
3. מעבר על שרשרת התזכורות של היום: תזכורת ששם המכון שלה שווה למכון הנוכחי והסטטוס שלה 2 – מדפיסים את התאריך והשעה.
public void printCanceled(String[] insts)
{
for (int i = 0; i < insts.length; i++)
{
System.out.println("Institute: " + insts[i]);
for (int d = 1; d <= 6; d++)
{
Node<Reminder> p = arr[d].getFirst();
while (p != null)
{
Reminder r = p.getValue();
if (r.getInst().equals(insts[i]) && r.getStatus() == 2)
System.out.println(" " + r.getDate() + " " + r.getHour());
p = p.getNext();
}
}
}
}public void PrintCanceled(string[] insts)
{
for (int i = 0; i < insts.Length; i++)
{
Console.WriteLine("Institute: " + insts[i]);
for (int d = 1; d <= 6; d++)
{
Node<Reminder> p = arr[d].GetFirst();
while (p != null)
{
Reminder r = p.GetValue();
if (r.GetInst() == insts[i] && r.GetStatus() == 2)
Console.WriteLine(" " + r.GetDate() + " " + r.GetHour());
p = p.GetNext();
}
}
}
}תשובה: לכל מכון עוברים על רשימות הימים 1–6 ומדפיסים את התאריך והשעה של כל תזכורת של המכון שהסטטוס שלה 2 (ביטול).
שאלה 12 · פעולות רקורסיביות על שרשרת והיפוך קטע
נתונה השרשרת הבאה:
נתונות שתי הפעולות הרקורסיביות הבאות:
public static int zero(Node<Integer> ch){
if(ch == null) return 0;
return 1 + zero(ch.getNext());
}
public static Node<Integer> one(Node<Integer> ch, int n){
if(ch == null) return null;
if(n == 1) return ch;
return one(ch.getNext(), n-1);
}public static int Zero(Node<int> ch){
if(ch == null) return 0;
return 1 + Zero(ch.GetNext());
}
public static Node<int> One(Node<int> ch, int n){
if(ch == null) return null;
if(n == 1) return ch;
return One(ch.GetNext(), n-1);
}
מה יהיה הפלט של הפקודה הבאה?
System.out.println(zero(ch1));Console.WriteLine(Zero(ch1));מה מבצעת הפעולה zero?
מה יהיה הפלט של הפקודה הבאה?
System.out.println(one(ch1, 3));Console.WriteLine (One(ch1, 3));מה מבצעת הפעולה one עבור ערך n שלם? יש להתייחס לאפשרויות שונות.
נתונה הפעולה הרקורסיבית two הבאה:
public static void two(Node<Integer> ch, int n, int m){
if(n < m)
{
Node<Integer> p1 = one(ch, n);
Node<Integer> p2 = one(ch, m);
int temp = p1.getValue();
p1.setValue(p2.getValue());
p2.setValue(temp);
two(ch, n+1, m-1);
}
}public static void Two(Node<int> ch, int n, int m){
if(n < m)
{
Node<int> p1 = One(ch, n);
Node<int> p2 = One(ch, m);
int temp = p1.GetValue();
p1.SetValue(p2.GetValue());
p2.SetValue(temp);
Two(ch, n+1, m-1);
}
}עקבו אחרי זימון הפעולה two(ch1, 2, 6) ורשמו איך תיראה השרשרת אחרי ביצוע הפעולה?
מה מבצעת הפעולה באופן כללי?

נתונה השרשרת הבאה:
איך תיראה השרשרת לאחר ביצוע קטע קוד הבא:
int s = zero(ch2);
for(int i = 1; i <= s/2; i++){
two(ch2, i, s - i + 1);
}int s = Zero(ch2);
for(int i = 1; i <= s/2; i++){
Two(ch2, i, s - i + 1);
}◂ פתרון מלא לשאלה 12
סעיף א
7; zero מחזירה את מספר החוליות בשרשרת.
השרשרת ch1: .
הפעולה מוסיפה 1 עבור כל חוליה ועוברת לחוליה הבאה, עד שמגיעים ל-null (שם מוחזר 0):
תשובה: יודפס 7. הפעולה zero מחזירה את מספר החוליות (האורך) של השרשרת.
סעיף ב
החוליה השלישית, שערכה 5 (יודפס 5). one מחזירה הפניה לחוליה ה-n; אם n גדול ממספר החוליות או n ≤ 0 – מוחזר null.
מעקב: one(10…, 3) → n ≠ 1, עוברים לחוליה הבאה: one(12…, 2) → one(5…, 1) → n = 1, מוחזרת החוליה שערכה 5.
הפעולה מחזירה הפניה לחוליה. בהדפסה של חוליה מופעלת הפעולה toString שלה, שמחזירה את הערך של החוליה, ולכן יודפס 5.
1. מספר החוליות: מוחזרת הפניה לחוליה ה-n בשרשרת (ספירה מ-1).
2. n גדול ממספר החוליות: מגיעים לסוף השרשרת לפני ש-n מגיע ל-1, ומוחזר null.
3. : n רק קטן ולעולם לא יהיה 1, ולכן עוברים על כל השרשרת עד null – מוחזר null.
4. שרשרת ריקה (ch == null): מוחזר null.
תשובה: יודפס 5 (ערך החוליה השלישית). one מחזירה את החוליה ה-n אם אורך השרשרת, ובכל מקרה אחר מחזירה null.
סעיף ג
הפעולה מחליפה בין הערכים של החוליה ה-n והחוליה ה-m, ואז ממשיכה עם ו-, עד ש-.
תשובה: אחרי הביצוע השרשרת היא .
סעיף ד
הופכת את סדר הערכים בקטע השרשרת שבין החוליה ה-n לחוליה ה-m (כולל).
בכל שלב מוחלפים הערכים בשני קצות הקטע, והקצוות מתקרבים זה לזה – בדיוק כמו היפוך של מערך משני הקצוות. כשהם נפגשים או חולפים זה על פני זה, הקטע כולו הפוך. (הפעולה מניחה ש- ו- אינו גדול ממספר החוליות, אחרת one מחזירה null ותהיה חריגה.)
תשובה: הפעולה הופכת את סדר הערכים בחוליות שבמקומות n עד m בשרשרת (כולל), ושאר החוליות לא משתנות.
סעיף ה
נתון: ch2 = , ולכן והלולאה רצה עבור (כי ).
לפי סעיף ד', הזימון two(ch2, i, 11 − i) הופך את הקטע שבין המקום i למקום . כלומר, בכל סבב הופכים קטע פנימי יותר:
למשל בסבב הקטע שבמקומות 2–9 הוא , ואחרי ההיפוך הוא .
אפשר לראות זאת גם כך: הערך שבמקום (מכל צד) נהפך מספר פעמים השווה למרחק שלו מהקצה. במקומות 1, 3, 5 (וגם 10, 8, 6) מספר ההיפוכים אי-זוגי, ולכן שם הערכים מוחלפים עם המקום הסימטרי; במקומות 2, 4 (וגם 9, 7) מספר ההיפוכים זוגי, ולכן שם הערכים חוזרים למקומם.
תשובה: השרשרת תהיה .