מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2022 מועד ב'
הנדסת תוכנה · סמל 97105 · 11 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2022 מועד ב', כל 11 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 14)
בכל מבחן 11 שאלות.
שאלות 1-4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 15 נקודות.
שאלות 5-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה 15 נקודות.
שאלות 9-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה 12 נקודות.
נקודה אחת תינתן על הערכה.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית שוות סכומים
מחסנית "שוות סכומים", היא מחסנית של מספרים שלמים המכילה מספר אי זוגי של איברים.
כך שכל שני איברים קיצוניים (ראשון + אחרון, שני + לפני אחרון וכו') שווים בסכומם לאיבר האמצעי מחסנית.
האיבר האמצעי במחסנית הוא 25. וכל זוג איברים קיצונים שווה ל- 25.
25=18+7 (האיבר הראשון והאיבר האחרון).
25=3+22 (האיבר השני והאיבר שלפני אחרון).
25=15+10
25=13+12
25=4+21

כתבו פעולה בשם equalSums המקבלת מחסנית של מספרים שלמים. הפעולה מחזירה true אם המחסנית היא מחסנית "שווה סכומים", ואם היא אינה "שוות סכומים", הפעולה תחזיר false.
(ב-C#: EqualSums)
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
סופרים את האיברים תוך העברה למחסנית עזר, מחזירים את המחסנית למצבה ומעתיקים למערך; אם מספר האיברים זוגי – false, אחרת בודקים ש-arr[i] + arr[n-1-i] שווה לאיבר האמצעי arr[n/2] לכל i < n/2.
1. במחסנית אפשר לגשת רק לאיבר העליון, אבל ההגדרה דורשת להשוות את האיבר ה-i מלמעלה לאיבר ה-i מלמטה. לכן נעתיק את איברי המחסנית למערך, ושם יש גישה ישירה לכל מקום.
2. קודם צריך לדעת כמה איברים יש (כדי ליצור מערך בגודל המתאים): מרוקנים את s למחסנית עזר temp וסופרים n.
3. מרוקנים את temp חזרה ל-s (כך המחסנית חוזרת למצבה המקורי – הפעולה לא הורסת את המחסנית שקיבלה), ובאותה לולאה כותבים כל איבר למערך arr. arr[0] הוא האיבר התחתון ו-arr[n-1] העליון; זה לא משנה, כי התנאי סימטרי.
4. אם n זוגי (כולל מחסנית ריקה, n = 0) אין איבר אמצעי, ולפי ההגדרה המחסנית אינה "שוות סכומים" – מחזירים false.
5. האיבר האמצעי הוא arr[n/2]. עוברים על הזוגות (i, n-1-i) עבור i = 0 עד n/2 - 1; אם יש זוג שסכומו שונה מהאמצעי – מחזירים false. אם כל הזוגות עברו – true. (מחסנית עם איבר אחד: אין זוגות לבדוק, והיא "שוות סכומים".)
public static boolean equalSums(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
int n = 0;
while (!s.isEmpty()) // מעבירים למחסנית עזר וסופרים
{
temp.push(s.pop());
n++;
}
int[] arr = new int[n];
int i = 0;
while (!temp.isEmpty()) // מחזירים את s למצבה ומעתיקים למערך
{
int x = temp.pop();
arr[i] = x;
i++;
s.push(x);
}
if (n % 2 == 0) // מספר זוגי של איברים (גם מחסנית ריקה)
return false;
int mid = arr[n / 2]; // האיבר האמצעי
for (i = 0; i < n / 2; i++)
if (arr[i] + arr[n - 1 - i] != mid)
return false;
return true;
}public static bool EqualSums(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
int n = 0;
while (!s.IsEmpty()) // מעבירים למחסנית עזר וסופרים
{
temp.Push(s.Pop());
n++;
}
int[] arr = new int[n];
int i = 0;
while (!temp.IsEmpty()) // מחזירים את s למצבה ומעתיקים למערך
{
int x = temp.Pop();
arr[i] = x;
i++;
s.Push(x);
}
if (n % 2 == 0) // מספר זוגי של איברים (גם מחסנית ריקה)
return false;
int mid = arr[n / 2]; // האיבר האמצעי
for (i = 0; i < n / 2; i++)
if (arr[i] + arr[n - 1 - i] != mid)
return false;
return true;
}בדיקה על הדוגמה: במחסנית 18, 3, 15, 13, 4, 25, 21, 12, 10, 22, 7 יש n = 11 איברים (אי-זוגי), האמצעי arr[5] = 25, והזוגות: 18+7, 3+22, 15+10, 13+12, 4+21 – כולם 25, ולכן הפעולה מחזירה true. עבור המחסנית 1, 5, 3 (האמצעי 5, אבל 1 + 3 = 4) הפעולה מחזירה false.
תשובה: הפעולה equalSums שלמעלה.
סעיף ב
O(n), כאשר n מספר האיברים במחסנית.
נסמן ב-n את מספר האיברים במחסנית.
1. הלולאה הראשונה מעבירה את כל n האיברים ל-temp: n פעולות pop ו-push, כל אחת O(1).
2. הלולאה השנייה מחזירה את n האיברים ל-s ומעתיקה אותם למערך: שוב n צעדים של O(1).
3. לולאת הבדיקה עוברת על n/2 זוגות, בכל אחד חיבור והשוואה ב-O(1).
סך הכול n + n + n/2 צעדים, כלומר סדר גודל לינארי. (גם יצירת המערך בגודל n היא O(n).)
תשובה: – כל איבר מועבר מספר קבוע של פעמים.
שאלה 2 · רשימת מקטעים בשרשרת חוליות
נגדיר: "רשימת מקטעים" כשרשרת חוליות של מספרים שלמים ריקה או כשרשרת חוליות אשר כל אחת מהחוליות שלה מכילה ערך קטן או שווה למספר החוליות העוקבות לה (נמצאות אחריה בשרשרת).
הערך של האיבר הראשון בשרשרת (2) הוא קטן ממספר האיברים שאחריו (6).
הערך של האיבר החמישי בשרשרת (-4) הוא קטן ממספר האיברים שאחריו (2).

כתבו פעולה חיצונית בשם numNodesFollowing המקבלת הפנייה לחוליה בשרשרת כלשהי ומחזירה את מספר החוליות העוקבות לה.
(ב-C#: NumNodesFollowing)
כתבו פעולה חיצונית בשם isSection המקבלת הפניה לשרשרת חוליות מטיפוס שלם.
הפעולה מחזירה true אם השרשרת היא "רשימת מקטעים", ואם לא, הפעולה תחזיר false.
(ב-C#: IsSection)
◂ פתרון מלא לשאלה 2
סעיף א
מתחילים מהחוליה שאחרי node וסופרים חוליות עד null.
הרעיון: החוליות העוקבות הן כל החוליות שאחרי החוליה שקיבלנו. מתחילים מ-node.getNext() ומתקדמים עד null, ובכל צעד מגדילים מונה. אם node היא החוליה האחרונה, הלולאה לא מתבצעת ומוחזר 0. הסיבוכיות לינארית במספר החוליות שאחרי node. (הנחה: node אינה null – הפעולה מקבלת חוליה בשרשרת.)
public static int numNodesFollowing(Node<Integer> node)
{
int count = 0;
Node<Integer> p = node.getNext();
while (p != null)
{
count++;
p = p.getNext();
}
return count;
}public static int NumNodesFollowing(Node<int> node)
{
int count = 0;
Node<int> p = node.GetNext();
while (p != null)
{
count++;
p = p.GetNext();
}
return count;
}דוגמה: עבור החוליה הראשונה בשרשרת שבשאלה (ערך 2) הפעולה מחזירה 6, ועבור החוליה האחרונה (ערך 0) היא מחזירה 0.
תשובה: הפעולה numNodesFollowing שלמעלה.
סעיף ב
following = numNodesFollowing(list); עוברים על החוליות, ואם ערך חוליה גדול מ-following מחזירים false; אחרי כל חוליה following קטן ב-1. שרשרת ריקה – true.
1. שרשרת ריקה (list == null) היא "רשימת מקטעים" לפי ההגדרה – מחזירים true.
2. אפשר היה לזמן את numNodesFollowing לכל חוליה, אבל אז כל זימון עובר על המשך השרשרת והסיבוכיות . יעיל יותר: מזמנים את הפעולה מסעיף א פעם אחת בלבד, עבור החוליה הראשונה, ומקבלים following – מספר החוליות שאחריה.
3. עוברים על השרשרת. לכל חוליה בודקים אם הערך שלה גדול ממספר החוליות העוקבות לה (following). אם כן – התנאי מופר ומחזירים false.
4. במעבר לחוליה הבאה מספר החוליות העוקבות קטן ב-1, לכן following-- .
5. אם עברנו על כל החוליות בלי הפרה – מחזירים true. הסיבוכיות: (מעבר אחד לספירה ומעבר אחד לבדיקה).
public static boolean isSection(Node<Integer> list)
{
if (list == null) // שרשרת ריקה היא "רשימת מקטעים"
return true;
int following = numNodesFollowing(list); // מספר החוליות אחרי הראשונה
Node<Integer> p = list;
while (p != null)
{
if (p.getValue() > following)
return false;
following--; // לחוליה הבאה יש חוליה עוקבת אחת פחות
p = p.getNext();
}
return true;
}public static bool IsSection(Node<int> list)
{
if (list == null) // שרשרת ריקה היא "רשימת מקטעים"
return true;
int following = NumNodesFollowing(list); // מספר החוליות אחרי הראשונה
Node<int> p = list;
while (p != null)
{
if (p.GetValue() > following)
return false;
following--; // לחוליה הבאה יש חוליה עוקבת אחת פחות
p = p.GetNext();
}
return true;
}מעקב על הדוגמה (2 → 3 → 2 → 1 → -4 → 1 → 0):
כל החוליות מקיימות את התנאי, ולכן הפעולה מחזירה true. לעומת זאת, בשרשרת 1 → 1 החוליה האחרונה מכילה 1 ואין אחריה חוליות, ולכן מוחזר false.
תשובה: הפעולה isSection שלמעלה.
שאלה 3 · ירושה, דריסה ומעקב אחר עצמים
נתונות ארבע המחלקות הבאות:
public class A
{
protected int x;
public A()
{
this.x = 1;
}
public A(int x)
{
this.x = x;
}
public void change()
{
this.x = this.x * 2;
}
public String toString()
{
return "X=" + this.x;
}
}
public class B extends A
{
protected int y;
public B(int y)
{
this.y = -y;
}
public B(int x,int y)
{
super(x);
this.y = -y;
}
public String toString()
{
return super.toString() + " Y=" + this.y;
}
}
public class C extends B
{
private int z;
public C(int x,int y,int z)
{
super(x,y);
this.z = z;
}
public void change()
{
this.x = 3 * this.x;
this.y = 3 * this.y;
this.z = 3 * this.z;
}
public String toString()
{
return super.toString() + " Z=" + this.z;
}
}
public class TestABC
{
public static void main(String[] args)
{
A[] data = new A[5];
data [0] = new A (5);
data [1] = new B(5,10);
data [2] = new C(5,10,15);
data [3] = data [0];
data [4] = new B(5);
for (int i = 0; i < data.length; i++)
System.out.println(data[i]);
for(int i=0;i< data.length;i++)
data [i].change();
for (int i = 0; i < data.length; i++)
System.out.println(data[i]);
}
}public class A
{
protected int x;
public A()
{
this.x = 1;
}
public A(int x)
{
this.x = x;
}
public virtual void Change()
{
this.x = this.x * 2;
}
public override string ToString()
{
return "X=" + this.x;
}
}
public class B : A
{
protected int y;
public B(int y)
{
this.y = -y;
}
public B(int x,int y): base(x)
{
this.y = -y;
}
public override string ToString()
{
return base.ToString() + " Y=" + this.y;
}
}
public class C : B
{
private int z;
public C(int x,int y,int z): base(x, y)
{
this.z = z;
}
public override void Change()
{
this.x = 3 * this.x;
this.y = 3 * this.y;
this.z = 3 * this.z;
}
public override string ToString()
{
return base.ToString() + " Z=" + this.z;
}
}
public class TestABC
{
public static void Main(string[] args)
{
A[] data = new A[5];
data [0] = new A (5);
data [1] = new B(5,10);
data [2] = new C(5,10,15);
data [3] = data [0];
data [4] = new B(5);
for (int i = 0; i < data.Length; i++)
Console.WriteLine(data[i]);
for(int i=0;i< data.Length;i++)
data [i].Change();
for (int i = 0; i < data.Length; i++)
Console.WriteLine(data[i]);
}
}עקבו אחרי ביצוע פעולה הראשית (main) של המחלקה TestABC ורשמו מה יהיה הפלט של הפעולה הראשית.
◂ פתרון מלא לשאלה 3
פתרון
X=5 / X=5 Y=-10 / X=5 Y=-10 Z=15 / X=5 / X=1 Y=-5, ואחרי change: X=20 / X=10 Y=-10 / X=15 Y=-30 Z=45 / X=20 / X=2 Y=-5
שלב 1 – יצירת העצמים. נעקוב אחרי הבנאים. בכל בנאי של תת-מחלקה מופעל קודם בנאי של מחלקת-העל: במפורש (super / base) או, אם לא נכתב, הבנאי בלי פרמטרים A().
1. data[0] = new A(5): הבנאי A(int x) קובע x = 5.
2. data[1] = new B(5,10): B(int x,int y) מזמן את A(5), כלומר x = 5, ואז y = -10.
3. data[2] = new C(5,10,15): C מזמן את B(5,10) ← A(5): x = 5, y = -10, ואז z = 15.
4. data[3] = data[0]: לא נוצר עצם חדש! data[3] מפנה לאותו עצם כמו data[0].
5. data[4] = new B(5): הבנאי B(int y) לא מזמן במפורש בנאי של A, ולכן מופעל A() הקובע x = 1; אחר כך y = -5.
סך הכול נוצרו 4 עצמים (לא 5):
שלב 2 – הדפסה ראשונה. toString של B מוסיפה " Y=" לפלט של toString של A, ושל C מוסיפה " Z=" לפלט של B (שרשור דרך super / base):
X=5
X=5 Y=-10
X=5 Y=-10 Z=15
X=5
X=1 Y=-5שלב 3 – change. מופעלת הגרסה של המחלקה בפועל של העצם (פולימורפיזם). ב-B אין change, ולכן עצם B מפעיל את change של A (מכפיל רק את x). ב-C הפעולה נדרסת ומכפילה פי 3 את x, y, z.
שימו לב: העצם של data[0] מוכפל פעמיים (פעם דרך data[0] ופעם דרך data[3]), לכן x שלו 5 → 10 → 20.
X=20
X=10 Y=-10
X=15 Y=-30 Z=45
X=20
X=2 Y=-5תשובה: הפלט המלא:
X=5
X=5 Y=-10
X=5 Y=-10 Z=15
X=5
X=1 Y=-5
X=20
X=10 Y=-10
X=15 Y=-30 Z=45
X=20
X=2 Y=-5שאלה 4 · דריסה והעמסה של equals
נתונות ארבע המחלקות הבאות:
public class B
{
protected int num;
public B( int num)
{
this.num = num;
}
} // end of B
public class C extends B
{
public C(int num)
{
super(num);
}
public boolean equals(Object other)
{
return ((other!=null) && (other instanceof C) &&
(num == ((C) other).num));
}
} // end of C
public class D extends B
{
public D( int num)
{
super(num+1);
}
public boolean equals(D other)
{
return ((other!=null) && (num == other.num));
}
} // end of Dpublic class B
{
protected int num;
public B( int num)
{
this.num = num;
}
} // end of B
public class C : B
{
public C(int num):base(num)
{
}
public override bool Equals(Object other)
{
return ((other!=null) && (other is C) &&
(num == ((C) other).num));
}
} // end of C
public class D : B
{
public D( int num): base(num+1)
{
}
public bool Equals(D other)
{
return ((other!=null) && (num == other.num));
}
} // end of Dהאם קיימת דריסה (overriding) או העמסה (overloading) של הפעולות?
הסבירו את תשובתכם.
נתונה הפעולה ראשית main במחלקה Program
public class Program
{
public static void main(String[] args)
{
B b = new B(1);
C c = new C(1);
D d = new D(1);
B b1 = new D(1);
Object c1 = new C(1);
Object d1 = new D(1);
(******)
}
}public class Program
{
public static void Main(string[] args)
{
B b = new B(1);
C c = new C(1);
D d = new D(1);
B b1 = new D(1);
Object c1 = new C(1);
Object d1 = new D(1);
(******)
}
}עקבו אחרי ביצועה וציינו מהם העצמים שנוצרו. עבור כל עצם יש להציג את ערך תכונת ה- num שלו.
בכל אחד מסעיפים הבאים השורה (*) תוחלף בשורת קוד משורות הקוד 1-4.
כתבו בעבור כל אחד מהסעיפים מה יהיה הפלט ואיזו מהפעולות equals תופעל.
System.out.println(b1.equals(b));Console.WriteLine(b1.Equals(b));System.out.println(c1.equals(c));Console.WriteLine (c1.Equals(c));System.out.println(d1.equals(d));Console.WriteLine (d1.Equals(d));System.out.println(d.equals((D)d1));Console.WriteLine (d.Equals((D)d1));◂ פתרון מלא לשאלה 4
סעיף א
ב-C יש דריסה: equals(Object) דורסת את equals(Object) של Object. ב-D יש העמסה: equals(D) היא פעולה נוספת עם פרמטר מטיפוס אחר, ולא דורסת את equals(Object).
נזכור את ההבדל:
•דריסה (overriding): תת-מחלקה מגדירה פעולה עם אותה חתימה בדיוק (שם וטיפוסי פרמטרים) כמו פעולה שירשה. בזמן ריצה נבחרת הגרסה לפי הטיפוס בפועל של העצם.
•העמסה (overloading): באותה מחלקה (כולל מה שירשה) יש כמה פעולות באותו שם עם רשימות פרמטרים שונות. הבחירה ביניהן נעשית בזמן הידור לפי הטיפוס המוצהר של הארגומנט.
כל מחלקה יורשת (דרך B) מ-Object את הפעולה equals(Object other).
1. במחלקה C: הפעולה equals(Object other) בעלת אותה חתימה כמו של Object, ולכן זו דריסה (ב-C# זה מסומן במפורש ב-override).
2. במחלקה D: הפעולה equals(D other) מקבלת פרמטר מטיפוס D ולא Object, ולכן היא לא דורסת את equals(Object). ל-D יש עכשיו שתי פעולות equals: equals(Object) שירשה מ-Object, ו-equals(D) החדשה – זו העמסה.
3. במחלקה B אין הגדרה של equals.
תשובה: ב-C קיימת דריסה של equals(Object); ב-D קיימת העמסה (equals(D) לצד equals(Object) שעברה בירושה מ-Object).
סעיף ב
b: B, num=1; c: C, num=1; d: D, num=2; b1: D, num=2; c1: C, num=1; d1: D, num=2.
הבנאים של C ו-B מעבירים את num כמו שהוא, אבל הבנאי של D מעביר לבנאי של B את num+1. הטיפוס בפועל של העצם הוא המחלקה שאחרי new (ולא הטיפוס של המשתנה).
נוצרו 6 עצמים, כל אחד במקום אחר בזיכרון.
תשובה: b (B, num=1), c (C, num=1), d (D, num=2), b1 (D, num=2), c1 (C, num=1), d1 (D, num=2).
סעיף ג
false – מופעלת equals(Object) של Object (השוואת הפניות).
1. בזמן הידור: הטיפוס המוצהר של b1 הוא B. ב-B אין equals משלה, ולכן הפעולה היחידה שהמהדר רואה היא equals(Object) שירשה מ-Object. הפעולה equals(D) של D לא נראית דרך משתנה מטיפוס B.
2. בזמן ריצה: העצם בפועל הוא D. האם D דורסת את equals(Object)? לא (יש לה רק העמסה equals(D)), ולכן מופעלת equals של Object.
3. equals של Object משווה הפניות: b1 ו-b מפנים לעצמים שונים, ולכן התוצאה false (למרות ש-num שונה בכל מקרה: 2 מול 1).
תשובה: הפלט false (ב-C#: False); הופעלה equals(Object) של המחלקה Object.
true – מופעלת equals(Object) של C (הדורסת).
1. בזמן הידור: הטיפוס המוצהר של c1 הוא Object, ולכן נבחרת החתימה equals(Object).
2. בזמן ריצה: העצם בפועל הוא C, ו-C דורסת את equals(Object) – לכן מופעלת הגרסה של C.
3. בתוך הפעולה: other הוא c – אינו null, הוא מטיפוס C, ו-num של c1 הוא 1 ושל c גם 1. כל התנאים מתקיימים.
תשובה: הפלט true (ב-C#: True); הופעלה equals(Object) של המחלקה C.
false – מופעלת equals(Object) של Object.
1. בזמן הידור: הטיפוס המוצהר של d1 הוא Object, ולכן נבחרת החתימה equals(Object) – ההעמסה equals(D) לא נראית דרך Object.
2. בזמן ריצה: העצם בפועל הוא D, אבל D לא דורסת את equals(Object), ולכן מופעלת הגרסה של Object.
3. equals של Object משווה הפניות: d1 ו-d הם שני עצמים שונים (אף על פי שלשניהם num = 2), ולכן false.
תשובה: הפלט false (ב-C#: False); הופעלה equals(Object) של המחלקה Object.
true – מופעלת equals(D) של D.
1. בזמן הידור: הטיפוס המוצהר של d הוא D, ולכן המהדר רואה שתי פעולות: equals(Object) ו-equals(D). הארגומנט הומר במפורש ל-D, ולכן נבחרת ההעמסה המתאימה ביותר – equals(D).
2. ההמרה (D)d1 תקינה בזמן ריצה, כי d1 הוא אכן עצם D.
3. בתוך הפעולה: other אינו null, ו-num של d (2) שווה ל-num של d1 (2).
תשובה: הפלט true (ב-C#: True); הופעלה equals(D) של המחלקה D.
שאלה 5 · מעקב: שרשרת מול מחסנית הפוכה
נתונה הפעולה הבאה:
public static void what(Node<Integer>f, Node<Integer> s)
{
Stack<Integer>st = new Stack<Integer>();
while(s!=null)
{
st.push(s.getValue());
s = s.getNext();
}
while(f!=null && !st.isEmpty() && (st.pop()==f.getValue()))
{
System.out.print(f.getNext()+", ");
f = f.getNext();
}
System.out.println("STOP!");
}public static void what(Node<int>f, Node<int> s)
{
Stack<int>st = new Stack<int>();
while(s!=null)
{
st.Push(s.GetValue());
s = s.GetNext();
}
while(f!=null && !st.IsEmpty() && (st.Pop()==f.GetValue()))
{
Console.Write(f.GetNext()+", ");
f = f.GetNext();
}
Console.WriteLine("STOP!");
}נתונות ארבע השרשרות הבאות:

עקבו אחרי זימון הפעולה what(a, b) ורשמו מה יהיה הפלט של הזימון. יש להציג את המעקב!
עקב זימון הפעולה what התקבל הפלט (משמאל לימין):
1, -5, 17, STOP!אילו פרמטרים נשלחו לפעולה? יש לבחור זוג פרמטרים מתוך ארבע השרשרות הנתונות (a, b, c, d).
מה מבצעת הפעולה באופן כללי?
◂ פתרון מלא לשאלה 5
סעיף א
STOP!
הפעולה פועלת בשני שלבים: קודם דוחפת את כל ערכי s למחסנית (כך ראש המחסנית הוא הערך האחרון של s), ואחר כך משווה את ערכי f מההתחלה לערכים שנשלפים מהמחסנית.
נתון: f = a = 17 → -5 → 1 → 1 → 2 → 17 → -5 → 1, s = b = 1 → -5 → 17 → 2 → 5 → 6.
כבר בבדיקה הראשונה הערך העליון 6 שונה מ-17, ולכן גוף הלולאה לא מתבצע אף פעם, ומודפס רק STOP!. (שימו לב שה-pop מתבצע גם כשההשוואה נכשלת, ו-6 הוצא מהמחסנית.)
תשובה: הפלט הוא `STOP!`
סעיף ב
what(c, a)
מה צריך להתקיים: בכל סיבוב מוצלח של הלולאה הערך הבא בתחילת f שווה לערך הבא מסוף s (המחסנית הופכת את s). שלושה ערכים הודפסו ואחריהם STOP!, כלומר היו בדיוק שלוש השוואות מוצלחות, והרביעית נכשלה (או שאחת השרשרות נגמרה).
הפלט 1, -5, 17 הוא סדרת הערכים שהושוו בהצלחה (כפי שהשאלה מתכוונת – ראו הערה בסוף), ולכן:
1. תחילת f היא 1, -5, 17: רק b ו-c מתחילות כך.
2. סוף s, מהסוף להתחלה, הוא 1, -5, 17: כלומר s מסתיימת ב-17 → -5 → 1. השרשרת a מסתיימת ב-17, -5, 1 ✓. השרשרת d מסתיימת ב-8, -5, 1 ✗. לכן s = a.
3. ההשוואה הרביעית חייבת להיכשל: האיבר הרביעי מהסוף של a הוא 2.
•אם f = b: האיבר הרביעי של b הוא 2 – שווה, והיה מודפס גם 2. ✗
•אם f = c: האיבר הרביעי של c הוא 0 ≠ 2 – הלולאה נעצרת. ✓
מעקב לאימות – what(c, a): אחרי הדחיפה המחסנית היא [1, -5, 17, 2, 1, 1, -5, 17] (ראש משמאל).
הערכים שהושוו בהצלחה: 1, -5, 17, ואחריהם STOP!.
הערה: בקוד כפי שהוא כתוב מודפס f.getNext(), כלומר החוליה שאחרי החוליה שהושוותה. אם toString של חוליה מחזירה את ערכה, הזימון what(c, a) ידפיס בפועל `-5, 17, 0, STOP!`. אף זוג מבין a, b, c, d לא נותן את הפלט 1, -5, 17, STOP! בקריאה המילולית הזו (לשם כך f הייתה צריכה להיות ?, 1, -5, 17, ואין שרשרת כזו), ולכן כוונת השאלה היא להדפסת הערכים שהושוו – והזוג המתאים הוא (c, a).
תשובה: f = c, s = a, כלומר הזימון what(c, a).
סעיף ג
משווה את תחילת השרשרת f לשרשרת s בסדר הפוך (מהסוף להתחלה), ומדפיסה את הרצף המשותף עד ההבדל הראשון, ואז STOP!.
1. הלולאה הראשונה דוחפת את ערכי s למחסנית, ולכן השליפות מהמחסנית מחזירות את s בסדר הפוך – מהאיבר האחרון לראשון.
2. הלולאה השנייה עוברת על f מההתחלה ומשווה כל ערך לערך הבא מהמחסנית. כל עוד הם שווים – היא מדפיסה (את החוליה הבאה של f) ומתקדמת. היא נעצרת בהבדל הראשון, או כש-f נגמרת, או כשהמחסנית מתרוקנת.
3. בסוף מודפס STOP!.
כלומר הפעולה מוצאת את הרישא (ההתחלה) המשותפת של f ושל s ההפוכה ומדפיסה אותה (לפי הקוד – מוסטת בחוליה אחת: לכל התאמה מודפסת החוליה שאחרי החוליה שהותאמה ב-f). אם f מתחילה ב-s ההפוכה כולה, יודפסו כל ההתאמות.
תשובה: הפעולה בודקת עד כמה תחילת f זהה ל-s בסדר הפוך, ומדפיסה את הקטע המשותף ואחריו STOP!.
שאלה 6 · ממשקים, ירושה ותרשים UML
לפניכם שלושה ממשקים ושלוש מחלקות:
(ב-C# שמות הפעולות באות גדולה: G1, G2, G3, G4.)
נתון קטע מפעולה ראשית. הקטע עובד ללא שגיאות הידור או שגיאות זמן ריצה.
Inter1 x = new F();
G y = new G();
Inter3 z = new H();
x = y;
y = new H();
y.g2();
z.g3();
((H)z).g4();
z = new F();Inter1 x = new F();
G y = new G();
Inter3 z = new H();
x = y;
y = new H();
y.G2();
z.G3();
((H)z).G4();
z = new F();

השלימו את תרשים UML: הוספו כותרות הפעולות במחלקות F ו- G, ציירו קשרים בין המחלקות והממשקים.
כתבו פעולה המקבלת מערך עצמים מסוג Object. הפעולה מדפיסה את מספר האיברים שעבורם אפשר להפעיל את הפעולה g1() ואת מספר האיברים שעבורם אי אפשר להפעיל את הפעולה g3().
◂ פתרון מלא לשאלה 6
סעיף א
F מממשת את Inter1 ואת Inter3 (g1(), g3()); G מממשת את Inter1 ואת Inter2 (g1(), g2()); H יורשת מ-G (חץ רציף H→G) ומממשת את Inter3 (חץ מקווקו H→Inter3).
הרעיון: נעבור על שורות הקטע ונסיק מכל שורה איזה קשר הכרחי כדי שהקטע יעבור הידור וריצה בלי שגיאות.
1. `Inter1 x = new F();` – עצם F מושם במשתנה מטיפוס Inter1, ולכן F מממשת את Inter1 וחייבת לממש את g1().
2. `G y = new G();` – אפשר ליצור עצם G, כלומר G אינה מופשטת.
3. `Inter3 z = new H();` – H מממשת את Inter3 (וזו הסיבה שב-H מופיעה g3()).
4. `x = y;` – y מטיפוס G מושם ב-x מטיפוס Inter1, ולכן G חייבת להיות מסוג Inter1: G מממשת את Inter1 ויש בה g1().
5. `y = new H();` – עצם H מושם במשתנה מטיפוס G, ולכן H יורשת מ-G.
6. `y.g2();` – דרך משתנה מטיפוס G מזמנים g2(), ולכן g2() מוגדרת ב-G. הממשק Inter2 מגדיר את g2(), לכן G מממשת את Inter2. ב-H הפעולה g2() דורסת את זו של G (ובזמן ריצה תופעל g2() של H).
7. `z.g3();` – z מטיפוס Inter3, שבו מוגדרת g3() – תקין.
8. `((H)z).g4();` – z מפנה בפועל לעצם H, ולכן ההמרה תקינה, ו-g4() היא פעולה של H בלבד.
9. `z = new F();` – עצם F מושם במשתנה מטיפוס Inter3, ולכן F מממשת גם את Inter3 וחייבת לממש את g3().
(H מקבלת את Inter1 ואת Inter2 בירושה מ-G, ואין צורך בחץ נוסף.)
public class F implements Inter1, Inter3
{
public void g1() { ... }
public void g3() { ... }
}
public class G implements Inter1, Inter2
{
public void g1() { ... }
public void g2() { ... }
}
public class H extends G implements Inter3
{
public void g2() { ... } // דריסה של g2 מ-G
public void g3() { ... } // מימוש Inter3
public void g4() { ... } // פעולה חדשה
}public class F : Inter1, Inter3
{
public void G1() { ... }
public void G3() { ... }
}
public class G : Inter1, Inter2
{
public void G1() { ... }
public virtual void G2() { ... }
}
public class H : G, Inter3
{
public override void G2() { ... } // דריסה של G2 מ-G
public void G3() { ... } // מימוש Inter3
public void G4() { ... } // פעולה חדשה
}תשובה: F ← Inter1, Inter3 (g1, g3); G ← Inter1, Inter2 (g1, g2); H יורשת מ-G ומממשת את Inter3.
סעיף ב
סופרים את האיברים שהם instanceof Inter1 (ב-C#: is Inter1), ואת האיברים שאינם instanceof Inter3, ומדפיסים את שני המונים.
1. אפשר להפעיל g1() על עצם אם ורק אם הוא מסוג Inter1 – כלומר מחלקתו מממשת את Inter1 (ישירות או בירושה). לפי סעיף א אלה עצמי F, G ו-H. הבדיקה: `arr[i] instanceof Inter1` (ב-C#: `arr[i] is Inter1`).
2. אפשר להפעיל g3() על עצם אם ורק אם הוא מסוג Inter3 (עצמי F ו-H). לכן סופרים את האיברים שעבורם `instanceof Inter3` שקרי.
3. תא שמכיל null: הבדיקה instanceof / is מחזירה עבורו false, ולכן הוא נספר כ"אי אפשר להפעיל g3()" ולא נספר ב-g1 – וזה נכון, כי על null אי אפשר להפעיל אף פעולה.
4. מעבר אחד על המערך – סיבוכיות .
public static void countG1G3(Object[] arr)
{
int canG1 = 0; // איברים שאפשר להפעיל עליהם g1
int cannotG3 = 0; // איברים שאי אפשר להפעיל עליהם g3
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof Inter1)
canG1++;
if (!(arr[i] instanceof Inter3))
cannotG3++;
}
System.out.println("can g1: " + canG1);
System.out.println("cannot g3: " + cannotG3);
}public static void CountG1G3(Object[] arr)
{
int canG1 = 0; // איברים שאפשר להפעיל עליהם G1
int cannotG3 = 0; // איברים שאי אפשר להפעיל עליהם G3
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is Inter1)
canG1++;
if (!(arr[i] is Inter3))
cannotG3++;
}
Console.WriteLine("can G1: " + canG1);
Console.WriteLine("cannot G3: " + cannotG3);
}דוגמה: עבור המערך {new F(), new G(), new H(), "abc", null} יודפס 3 (F, G, H) עבור g1, ו-3 (G, "abc", null) עבור "אי אפשר g3".
תשובה: הפעולה countG1G3 שלמעלה.
שאלה 7 · מעקב רקורסיבי על עץ בינארי
לפניכם ארבע פעולות:
public static int first(BinNode<Integer> bt){
if(bt==null)
return 0;
return
bt.getValue()+first(bt.getLeft())+first(bt.getRight());
}
public static int second(BinNode<Integer> bt){
return first(bt.getLeft())+first(bt.getRight());
}
public static void third(BinNode<Integer> bt){
if(bt!=null)
{
bt.setValue(second(bt));
third(bt.getLeft());
third(bt.getRight());
}
}public static int First(BinNode<int> bt){
if(bt==null)
return 0;
return
bt.GetValue()+First(bt.GetLeft())+First(bt.GetRight());
}
public static int Second(BinNode<int> bt){
return First(bt.GetLeft())+First(bt.GetRight());
}
public static void Third(BinNode<int> bt){
if(bt!=null)
{
bt.SetValue(Second(bt));
Third(bt.GetLeft());
Third(bt.GetRight());
}
}נתון העץ הבינארי הבא:

מה תהיה תוצאת זימון הפעולה second(bt)? חובה להראות את המעקב!
מה מחזירה הפעולה second(BinNode<Integer> bt) באופן כללי?
מה תהיה תוצאת הזימון third(bt) לעץ הנתון bt?
חובה להראות את המעקב אחרי הפעולה third! אין צורך במעקב אחרי הפעולה second.
מה מבצעת הפעולה third(BinNode<Integer> bt) באופן כללי?
◂ פתרון מלא לשאלה 7
סעיף א
40
מה עושה first: first(t) מחזירה 0 לעץ ריק, ואחרת את ערך השורש ועוד first של שני תתי-העצים – כלומר את סכום כל הערכים בתת-העץ.
מבנה העץ: השורש 8; בן שמאלי 3 (בנים 4 ו-2); בן ימני 8 (בן שמאלי 9 שלו בן שמאלי 8, ובן ימני 6).
second(bt) = first(bt.getLeft()) + first(bt.getRight()). נחשב כל אחד:
second(bt) = 9 + 31 = 40.
תשובה: 40
סעיף ב
את סכום ערכי כל הצמתים בעץ חוץ מהשורש (סכום הצאצאים של bt).
first(t) מחזירה את סכום כל הערכים בתת-העץ t. second(bt) מחברת את first של תת-העץ השמאלי ושל הימני, כלומר את כל הערכים בעץ פרט לערך השורש. במילים אחרות: סכום ערכי כל הצאצאים של bt. (בדוגמה: סכום העץ כולו 48, פחות השורש 8, נותן 40.)
תשובה: second מחזירה את סכום הערכים של כל הצמתים בעץ חוץ מהשורש.
סעיף ג
העץ: שורש 40; בן שמאלי 6 (בנים 0, 0); בן ימני 23 (בן שמאלי 8 עם בן שמאלי 0, בן ימני 0).
third עוברת על העץ בסדר תחילי (preorder): קודם מעדכנת את הצומת הנוכחי ל-second שלו, ואחר כך יורדת לשמאל ולימין.
נקודה חשובה: כשמעדכנים צומת, משתנה רק הערך שלו; הערכים בתת-העצים שלו עדיין המקוריים (הם יעודכנו אחריו). second של צומת תלויה רק בתתי-העצים שלו, ולכן כל צומת מקבל את סכום הצאצאים שלו בעץ המקורי.
(הזימונים third(null) עבור בנים חסרים פשוט חוזרים בלי לעשות דבר.)
העץ אחרי הזימון (אותו מבנה, ערכים חדשים):
•שורש: 40
•בן שמאלי: 6, ובניו 0 ו-0
•בן ימני: 23; בנו השמאלי 8 ולו בן שמאלי 0; בנו הימני 0
תשובה: השורש 40; 3 → 6; 8 (ימני) → 23; 9 → 8; כל העלים (4, 2, 8, 6) → 0.
סעיף ד
מחליפה את ערכו של כל צומת בסכום ערכי הצאצאים שלו (בעץ המקורי); כל עלה מקבל 0.
third עוברת על כל צמתי העץ, וכל צומת מקבל את second שלו – סכום הערכים בתת-העץ השמאלי והימני שלו. מאחר שהעדכון נעשה מלמעלה למטה (סדר תחילי), בזמן העדכון הצאצאים עדיין מכילים את ערכיהם המקוריים. לכן כל צומת מקבל את סכום הערכים המקוריים של כל צאצאיו, ועלים מקבלים 0.
תשובה: הפעולה מחליפה כל ערך בעץ בסכום הערכים (המקוריים) של צאצאיו.
שאלה 8 · הכנסה לשרשרת עם מונה איברים גדולים
נתונה המחלקה MyNode הבאה:
public class MyNode
{
private int value;
private int howManyBig;
private MyNode next;
public MyNode(int val)
{
this.value = val;
this.howManyBig = 0;
this.next = null;
}
}למחלקה הוגדר בנאי. לכל תכונה במחלקה הוגדרו פעולות get/set (ב-C#: Get/Set).
בעזרת המחלקה MyNode נבנית שרשרת חוליות לפי הכלל הבא:
כל חוליה היא מסוג MyNode. בכל איבר התכונה value מאחסנת מספר שלם, התכונה howManyBig מאחסנת מספר שלם ששווה למספר האיברים בשרשרת שנמצאים אחרי האיבר הנוכחי, שערך התכונה value שלהם גדול מערך value של האיבר הנוכחי. התכונה next מחזיקה מצביע על האיבר הבא.
P מצביע על האיבר שהתכונה value שלו שווה ל- 4, והתכונה howManyBig שווה ל- 2 כי יש שני איברים אחריו, שערכי ה- value שלהם גדולים מ- 4 (כלומר 8 ו- 7).


כתבו פעולה חיצונית המקבלת הפנייה לחוליה הראשונה של שרשרת החוליות מסוג MyNode, מספר שלם val ומספר שלם וחיובי position. כותרת הפעולה:
public static MyNode addNumber(MyNode list, int val, int position)public static MyNode AddNumber(MyNode list, int val, int position)הפעולה צריכה להכניס איבר חדש לשרשרת במיקום position (המיקום של האיבר הראשון בשרשרת הוא 1). ערך התכונה value של האיבר החדש יהיה שווה לפרמטר val.
השרשרת שתתקבל צריכה לשמור על החוקים של השרשרת המקורית לגבי התכונה howManyBig.
אחרי זימון הפעולה addNumber(list, 3, 5) השרשרת שתתקבל תהיה:
מהי סיבוכיות הפעולה? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
מעבר על position-1 החוליות הראשונות: לכל חוליה עם value < val מגדילים את howManyBig ב-1; מחברים את החוליה החדשה אחרי האחרונה מהן (או בראש); את howManyBig של החדשה קובעים לפי מספר החוליות שאחריה עם value > val; מחזירים את ראש השרשרת.
נתון: שרשרת שבה howManyBig של כל חוליה נכון. מבוקש: להכניס חוליה חדשה במקום position ולתקן רק את מה שמשתנה.
1. חוליות שאחרי המקום החדש: האיברים שאחריהן לא השתנו, ולכן howManyBig שלהן נשאר נכון.
2. חוליות שלפני המקום החדש: נוסף אחריהן איבר אחד – val. אם הערך שלהן קטן מ-val, יש להן עכשיו איבר גדול אחד נוסף: howManyBig גדל ב-1. אחרת – לא משתנה.
3. החוליה החדשה: howManyBig שלה הוא מספר החוליות שאחריה שערכן גדול מ-val – צריך לספור.
1. יוצרים חוליה חדשה newNode עם val.
2. עוברים עם p על החוליות 1 עד position-1 (ושומרים ב-prev את החוליה הקודמת). לכל אחת – אם value שלה קטן מ-val, מגדילים את howManyBig שלה ב-1.
3. בסיום p מצביע על החוליה שתבוא אחרי החדשה (או null). מחברים: newNode.next = p; אם prev == null (הכנסה במקום 1) – newNode הופכת לראש השרשרת, אחרת prev.next = newNode.
4. ממשיכים עם p עד סוף השרשרת וסופרים חוליות שערכן גדול מ-val; זה ה-howManyBig של newNode.
5. מחזירים את ראש השרשרת (שהשתנה אם הכנסנו במקום 1).
הנחה: 1 ≤ position ≤ (אורך השרשרת + 1). אם position גדול יותר, הלולאה נעצרת בסוף השרשרת והאיבר מתווסף בסופה. שרשרת ריקה (list == null) – החוליה החדשה היא השרשרת כולה.
public static MyNode addNumber(MyNode list, int val, int position)
{
MyNode newNode = new MyNode(val);
MyNode prev = null; // החוליה שתהיה לפני החדשה
MyNode p = list;
int i = 1;
// שלב 1: החוליות שלפני המיקום - כל חוליה קטנה מ-val מקבלת עוד איבר גדול ממנה
while (i < position && p != null)
{
if (p.getValue() < val)
p.setHowManyBig(p.getHowManyBig() + 1);
prev = p;
p = p.getNext();
i++;
}
// שלב 2: חיבור החוליה החדשה בין prev ל-p
newNode.setNext(p);
if (prev == null)
list = newNode; // הכנסה בראש השרשרת
else
prev.setNext(newNode);
// שלב 3: ספירת האיברים שאחרי החדשה וגדולים מ-val
int count = 0;
while (p != null)
{
if (p.getValue() > val)
count++;
p = p.getNext();
}
newNode.setHowManyBig(count);
return list;
}public static MyNode AddNumber(MyNode list, int val, int position)
{
MyNode newNode = new MyNode(val);
MyNode prev = null; // החוליה שתהיה לפני החדשה
MyNode p = list;
int i = 1;
// שלב 1: החוליות שלפני המיקום - כל חוליה קטנה מ-val מקבלת עוד איבר גדול ממנה
while (i < position && p != null)
{
if (p.GetValue() < val)
p.SetHowManyBig(p.GetHowManyBig() + 1);
prev = p;
p = p.GetNext();
i++;
}
// שלב 2: חיבור החוליה החדשה בין prev ל-p
newNode.SetNext(p);
if (prev == null)
list = newNode; // הכנסה בראש השרשרת
else
prev.SetNext(newNode);
// שלב 3: ספירת האיברים שאחרי החדשה וגדולים מ-val
int count = 0;
while (p != null)
{
if (p.GetValue() > val)
count++;
p = p.GetNext();
}
newNode.SetHowManyBig(count);
return list;
}מעקב על הדוגמה addNumber(list, 3, 5) – השרשרת 5, 2, 4, 8, 7, 1 (howManyBig: 2, 3, 2, 0, 0, 0):
בסוף הלולאה i = 5 = position, prev היא החוליה 8, ו-p היא החוליה 7. מחברים 8 → 3 → 7. סופרים אחרי החדשה: 7 > 3 (כן), 1 > 3 (לא) → howManyBig = 1.
השרשרת שמתקבלת: 5/2, 2/4, 4/2, 8/0, 3/1, 7/0, 1/0 – בדיוק כמו בדוגמה.
תשובה: הפעולה addNumber שלמעלה.
סעיף ב
O(n), כאשר n מספר החוליות בשרשרת.
נסמן ב-n את מספר החוליות בשרשרת.
1. הלולאה הראשונה עוברת על position-1 החוליות שלפני המקום, ובכל אחת מבצעת השוואה ואולי עדכון – O(1) לחוליה.
2. החיבור של החוליה החדשה – מספר קבוע של פעולות, O(1).
3. הלולאה השנייה ממשיכה מאותה נקודה עד סוף השרשרת וסופרת – O(1) לחוליה.
שתי הלולאות יחד עוברות על כל חוליה פעם אחת בלבד, ולכן סך הכול n צעדים.
תשובה: – מעבר יחיד על השרשרת.
שאלה 9 · רקורסיה על מחסנית: איבר תחתון וסימטריה
נתונות שתי הפעולות הרקורסיביות secret ו- mystery (ב-C#: Secret ו- Mystery):
הפעולה secret מקבלת מחסנית לא ריקה של מספרים שלמים.
public static int secret (Stack<Integer> s)
{
int x=s.pop();
if(s.isEmpty())
return x;
int y = secret(s);
s.push(x);
return y;
}public static int Secret (Stack<int> s)
{
int x=s.Pop();
if(s.IsEmpty())
return x;
int y = Secret(s);
s.Push(x);
return y;
}הפעולה mystery מקבלת מחסנית של מספרים שלמים ומספר שלם וחיובי c.
public static boolean mystery (Stack<Integer>s,int c)
{
if (c==0 || s.isEmpty())
return true;
int y=secret(s);
if (s.isEmpty())
return false;
int x=s.pop();
if (x==y)
return mystery (s, c-1);
return false;
}public static bool Mystery (Stack<int>s,int c)
{
if (c==0 || s.IsEmpty())
return true;
int y=Secret(s);
if (s.IsEmpty())
return false;
int x=s.Pop();
if (x==y)
return Mystery (s, c-1);
return false;
}כמו כן, נתונות המחסניות s1 ו- s2

עקבו אחר זימון הפעולה secret עבור המחסנית s1. מהו הערך שיוחזר מהפעולה?
מהי מטרת הפעולה secret?
עקבו אחר זימון הפעולה mystery(s2, 2) ורשמו מהו הערך שיוחזר מהפעולה.
מהי מטרת הפעולה mystery?
◂ פתרון מלא לשאלה 9
סעיף א
1; בסוף s1 = [2, 3, 6] (ראש משמאל).
s1 מראשה לתחתיתה: 2, 3, 6, 1. בכל זימון שולפים x; אם המחסנית התרוקנה – מחזירים את x (זה האיבר התחתון). אחרת קוראים רקורסיבית, ובחזרה דוחפים את x בחזרה ומעבירים הלאה את y.
ירידה ברקורסיה (המחסנית רשומה כשהראש משמאל):
תשובה: הפעולה מחזירה 1, ו-s1 נשארת עם 2, 3, 6 (2 בראש) – האיבר התחתון 1 הוצא.
סעיף ב
מוציאה מהמחסנית את האיבר התחתון ומחזירה אותו; שאר האיברים נשארים באותו סדר.
כל זימון שולף את האיבר העליון, ממשיך ברקורסיה עד שנשאר האיבר האחרון (התחתון), מחזיר אותו, ובדרך חזרה דוחף את כל האיברים שנשלפו באותו סדר. לכן בסיום חסר במחסנית רק האיבר התחתון, והוא הערך המוחזר.
תשובה: secret מוציאה את האיבר שבתחתית המחסנית ומחזירה אותו, ושאר המחסנית נשארת בסדרה המקורי.
סעיף ג
true
s2 מראשה לתחתיתה: 1, 2, 7, 4, 8, 2, 1. בכל זימון: y = האיבר התחתון (מוצא ע"י secret), x = האיבר העליון (מוצא ע"י pop), ואם הם שווים – ממשיכים עם c-1.
הערך true חוזר דרך כל הזימונים. בסוף נשארו במחסנית 7, 4, 8.
תשובה: mystery(s2, 2) מחזירה true.
סעיף ד
בודקת אם c האיברים העליונים במחסנית שווים בסדר הפוך ל-c האיברים התחתונים (העליון = התחתון, השני מלמעלה = השני מלמטה וכו') – סימטריה של c הזוגות החיצוניים. המחסנית נהרסת.
בכל שלב הפעולה מוציאה את האיבר התחתון (secret) ואת האיבר העליון (pop) ומשווה ביניהם. אם הם שווים, היא ממשיכה לזוג החיצוני הבא עם c-1; בהבדל הראשון היא מחזירה false. כשבדקה c זוגות (c == 0) – מחזירה true.
כלומר mystery בודקת אם המחסנית סימטרית ב-c הזוגות החיצוניים שלה: האיבר ה-i מלמעלה שווה לאיבר ה-i מלמטה, לכל i מ-1 עד c (כמו בדיקת פלינדרום חלקית).
מקרי קצה: אם המחסנית התרוקנה לפני שנבדקו c זוגות – מוחזר true; אם נשאר בה איבר יחיד (האמצעי) – secret מוציאה אותו, המחסנית מתרוקנת, ומוחזר false. הפעולה גם הורסת את המחסנית: הזוגות שנבדקו מוצאים ממנה.
תשובה: mystery בודקת אם c האיברים העליונים שווים, בסדר הפוך, ל-c האיברים התחתונים (סימטריה של c הזוגות החיצוניים).
שאלה 10 · תכנון מחלקות לחניון רב-קומות
הערה: בשאלה זאת הניחו שהפעולות get/set הוגדרו בעבור כל תכונה בכל אחת מהמחלקות.
אם הוספתם פעולות עזר נוספות, יש לציין את המחלקה שבה נמצאת פעולת העזר.
בחניון "לב העיר" קיימות מספר קומות. בכל קומה יש אזורים המזוהים לפי צבע. מספר האזורים אינו שווה בהכרח בכל קומה.
כל אזור (Area) מאופיין באמצעות:
•צבע.
•מספר מקומות פנויים כרגע.
•רשימת מספרי הרישוי של המכוניות שחונות בו כרגע (סדר המכוניות לא משנה).
כל קומה (Floor) מאופיינת על ידי מספר הקומה ואוסף האזורים שבה.
כתבו מחלקות עבור הטיפוסים: אזור– Area וקומה – Floor.
לכל מחלקה כתבו כותרת מחלקה ותכונות לפי התיאור הנ"ל.
כתבו פעולה פנימית במחלקה Floor המקבלת מספר רישוי של מכונית ובודקת אם יש בקומה מקום חניה עבורה. אם כן, המכונית "תשובץ" לחניה באחד האזורים בקומה והפעולה תחזיר את צבע האזור. אם לא, מכונית לא תשובץ והפעולה תחזיר מחרוזת "no room".
המחלקה חניון (Parking) מייצגת חניון. למחלקה יש תכונה אחת שהיא מערך עצמים מסוג Floor.
class Parking
{
private Floor[] floors;
}בכניסה לחניון עומדות מכוניות בהמתנה בתור. מכונית נכנסת רק אם יש מקום פנוי עבורה בחניון. אם נמצא מקום פנוי, המכונית יוצאת מ"תור ההמתנה" ומשובצת לחניון. אם לא נמצא מקום עבורה, היא נשארת בהמתנה.
כתבו פעולה המקבלת תור של מספרי רישוי של מכוניות שממתינות בכניסה. הפעולה תשבץ את המכוניות הממתינות בתור. מכוניות שלא נמצא עבורן מקום, תשארנה בתור ההמתנה.
עבור כל מכונית שנכנסה לחניון יודפסו מספר קומה וצבע אזור. הפעולה תסיים את עבודתה כאשר לא תשארנה מכוניות ב"תור המתנה" או כאשר לא יישאר מקום פנוי בחניון. בסיום העבודה הפעולה תדפיס הודעה: "ALL" – אם כל המכוניות שובצו במקומות חנייה, או "NOT ALL" – אם לא כולן שובצו למקום חנייה.
◂ פתרון מלא לשאלה 10
סעיף א
Area: color (מחרוזת), freePlaces (שלם), cars (Node<String> – שרשרת מספרי רישוי). Floor: floorNum (שלם), areas (Node<Area> – שרשרת אזורים).
1. Area: צבע – מחרוזת color; מקומות פנויים – שלם freePlaces; רשימת המכוניות – אוסף של מספרי רישוי. הסדר לא חשוב ומספר המכוניות משתנה, ולכן נבחר שרשרת חוליות Node<String> (הוספה בראש השרשרת ב-O(1)). מספר רישוי נשמור כמחרוזת (הוא מזהה, לא מספר לחישוב).
2. Floor: מספר קומה – שלם floorNum; אוסף האזורים – מספר האזורים שונה מקומה לקומה, ולכן שרשרת חוליות Node<Area> מתאימה (אין צורך לדעת מראש את הגודל, ואפשר לעבור עליה בלי להרוס אותה – בניגוד למחסנית או לתור).
3. במחלקה Area הוספנו פעולת עזר addCar (במחלקה Area) – משמשת בסעיף ב.
public class Area
{
private String color; // צבע האזור
private int freePlaces; // מספר המקומות הפנויים כרגע
private Node<String> cars; // מספרי הרישוי של המכוניות שחונות באזור (null - אין מכוניות)
public Area(String color, int freePlaces)
{
this.color = color;
this.freePlaces = freePlaces;
this.cars = null;
}
// פעולת עזר (במחלקה Area): מכניסה מכונית לאזור
public void addCar(String carNum)
{
this.cars = new Node<String>(carNum, this.cars);
this.freePlaces--;
}
// + פעולות get/set לכל תכונה
}
public class Floor
{
private int floorNum; // מספר הקומה
private Node<Area> areas; // שרשרת האזורים שבקומה
public Floor(int floorNum)
{
this.floorNum = floorNum;
this.areas = null;
}
// + פעולות get/set לכל תכונה
}public class Area
{
private string color; // צבע האזור
private int freePlaces; // מספר המקומות הפנויים כרגע
private Node<string> cars; // מספרי הרישוי של המכוניות שחונות באזור (null - אין מכוניות)
public Area(string color, int freePlaces)
{
this.color = color;
this.freePlaces = freePlaces;
this.cars = null;
}
// פעולת עזר (במחלקה Area): מכניסה מכונית לאזור
public void AddCar(string carNum)
{
this.cars = new Node<string>(carNum, this.cars);
this.freePlaces--;
}
// + פעולות Get/Set לכל תכונה
}
public class Floor
{
private int floorNum; // מספר הקומה
private Node<Area> areas; // שרשרת האזורים שבקומה
public Floor(int floorNum)
{
this.floorNum = floorNum;
this.areas = null;
}
// + פעולות Get/Set לכל תכונה
}תשובה: המחלקות Area ו-Floor שלמעלה.
סעיף ב
עוברים על שרשרת האזורים; באזור הראשון עם freePlaces > 0 מוסיפים את המכונית (addCar של Area – מוסיפה לשרשרת ומקטינה את המקומות הפנויים) ומחזירים את צבעו; אם אין – "no room".
1. עוברים על שרשרת האזורים של הקומה מתחילתה.
2. לכל אזור בודקים אם יש בו מקום פנוי (freePlaces > 0).
3. באזור הראשון שיש בו מקום – משבצים את המכונית: פעולת העזר addCar (במחלקה Area) מוסיפה את מספר הרישוי לשרשרת המכוניות באזור ומקטינה את מספר המקומות הפנויים ב-1. מחזירים את צבע האזור.
4. אם עברנו על כל האזורים ולא נמצא מקום – מחזירים "no room".
הסיבוכיות: O(k), כאשר k מספר האזורים בקומה.
// פעולה פנימית במחלקה Floor
public String parkCar(String carNum)
{
Node<Area> p = this.areas;
while (p != null)
{
Area a = p.getValue();
if (a.getFreePlaces() > 0)
{
a.addCar(carNum); // פעולת העזר מהמחלקה Area
return a.getColor();
}
p = p.getNext();
}
return "no room";
}// פעולה פנימית במחלקה Floor
public string ParkCar(string carNum)
{
Node<Area> p = this.areas;
while (p != null)
{
Area a = p.GetValue();
if (a.GetFreePlaces() > 0)
{
a.AddCar(carNum); // פעולת העזר מהמחלקה Area
return a.GetColor();
}
p = p.GetNext();
}
return "no room";
}תשובה: הפעולה parkCar שלמעלה (במחלקה Floor), עם פעולת העזר addCar במחלקה Area.
סעיף ג
כל עוד התור לא ריק והחניון לא מלא: לוקחים את המכונית בראש התור ומנסים parkCar בכל קומה לפי הסדר; אם שובצה – מוציאים אותה מהתור ומדפיסים קומה וצבע; אם לא שובצה באף קומה – החניון מלא ועוצרים. בסוף: תור ריק – "ALL", אחרת "NOT ALL".
1. הפעולה פנימית במחלקה Parking ומקבלת Queue<String> waiting.
2. כל עוד יש מכוניות בתור והחניון לא התמלא:
•מסתכלים על המכונית שבראש התור (head) – בלי להוציא אותה עדיין, כי אם לא יימצא לה מקום היא צריכה להישאר בתור.
•עוברים על הקומות לפי הסדר ומזמנים את parkCar מסעיף ב. בקומה הראשונה שמחזירה צבע (ולא "no room") המכונית שובצה: מוציאים אותה מהתור (remove) ומדפיסים את מספר הקומה ואת צבע האזור.
•אם אף קומה לא שיבצה את המכונית – אין מקום פנוי בשום מקום בחניון. מכיוון שכל מכונית יכולה לחנות בכל מקום פנוי, גם שאר המכוניות לא ישובצו, ולכן מסמנים full = true ומסיימים. המכונית נשארת בראש התור, וכל השאר נשארות בתור באותו סדר.
3. בסיום: אם התור ריק – כל המכוניות שובצו, ומדפיסים "ALL"; אחרת "NOT ALL".
// פעולה פנימית במחלקה Parking
public void parkAll(Queue<String> waiting)
{
boolean full = false;
while (!waiting.isEmpty() && !full)
{
String car = waiting.head();
boolean parked = false;
for (int i = 0; i < this.floors.length && !parked; i++)
{
String color = this.floors[i].parkCar(car);
if (!color.equals("no room"))
{
parked = true;
waiting.remove();
System.out.println("floor: " + this.floors[i].getFloorNum() + ", area: " + color);
}
}
if (!parked) // אין מקום פנוי באף קומה - החניון מלא
full = true;
}
if (waiting.isEmpty())
System.out.println("ALL");
else
System.out.println("NOT ALL");
}// פעולה פנימית במחלקה Parking
public void ParkAll(Queue<string> waiting)
{
bool full = false;
while (!waiting.IsEmpty() && !full)
{
string car = waiting.Head();
bool parked = false;
for (int i = 0; i < this.floors.Length && !parked; i++)
{
string color = this.floors[i].ParkCar(car);
if (color != "no room")
{
parked = true;
waiting.Remove();
Console.WriteLine("floor: " + this.floors[i].GetFloorNum() + ", area: " + color);
}
}
if (!parked) // אין מקום פנוי באף קומה - החניון מלא
full = true;
}
if (waiting.IsEmpty())
Console.WriteLine("ALL");
else
Console.WriteLine("NOT ALL");
}דוגמה: קומה 1 עם האזורים red (מקום פנוי 1) ו-blue (2), קומה 2 עם green (1); בתור שש מכוניות. ארבע הראשונות משובצות (1-red, 1-blue, 1-blue, 2-green), החמישית לא מוצאת מקום – הלולאה נעצרת, שתי המכוניות האחרונות נשארות בתור, ומודפס NOT ALL.
תשובה: הפעולה parkAll שלמעלה (במחלקה Parking).
שאלה 11 · עץ בינארי כחול-לבן
עץ בינארי bt שכל צומת שבו הוא מטיפוס תו, ייקרא כחול-לבן אם הוא עץ ריק, או אם הוא מקיים את שלושת התנאים הבאים:
1. כל צומת הוא בעל ערך כחול- 'b' או לבן- 'w'.
2. כל עלה הוא כחול ('b').
3. אם ערך צומת שאינו עלה הוא כחול ('b'), אזי יש לו שני בנים לבנים ('w').

להלן ארבעה עצים בינאריים. לגבי כל אחד מהעצים, קבעו אם הוא עץ כחול-לבן או לא.
אם העץ אינו עץ כחול-לבן, העתיקו אותו למחברת, סמנו X בצמתים שאינם מקיימים את התנאים ונמקו מדוע אינם מקיימים.
כתבו פעולה שתקבל עץ בינארי bt ותחזיר true אם הוא עץ כחול-לבן, ולא הפעולה תחזיר false.
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף ב'? נמקו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
(1) לא – העלה w (תנאי 2); (2) כן; (3) לא – הצומת הכחול הימני אינו עלה ויש לו בן יחיד כחול (תנאי 3); (4) לא – העלה הימני ביותר w (תנאי 2).
בודקים לכל עץ את שלושת התנאים. בכל העצים כל הערכים הם 'b' או 'w', כך שתנאי 1 תמיד מתקיים; נבדוק את תנאים 2 ו-3.
תשובה: רק עץ (2) כחול-לבן. בעץ (1) X על העלה w; בעץ (3) X על הצומת b הימני שיש לו בן יחיד כחול; בעץ (4) X על העלה w (הימני ביותר).
סעיף ב
רקורסיה: עץ ריק – true; ערך שאינו 'b'/'w' – false; עלה – true רק אם 'b'; צומת 'b' פנימי – חייבים שני בנים, שניהם 'w'; ולבסוף מחזירים את ה-AND של הבדיקה הרקורסיבית בשני תתי-העצים.
הרעיון: ההגדרה מקומית – כל תנאי נבדק על צומת ועל בניו הישירים. לכן עץ הוא כחול-לבן אם השורש מקיים את התנאים, ושני תתי-העצים כחולים-לבנים. (תת-עץ ריק נחשב כחול-לבן, וזה מתאים: בן חסר אינו מפר אף תנאי בפני עצמו.)
לכל צומת:
1. עץ ריק – true.
2. תנאי 1: אם הערך אינו 'b' וגם אינו 'w' – false.
3. תנאי 2: אם הצומת עלה (אין בנים) – הוא תקין רק אם הוא 'b'. (לעלה אין תתי-עצים, אז אפשר להחזיר מיד.)
4. תנאי 3: אם הצומת 'b' ואינו עלה – חייבים להיות לו שני בנים, ושניהם 'w'; אחרת false.
5. אם הצומת עבר את כל הבדיקות – מחזירים את התוצאה הרקורסיבית לשמאל וגם לימין.
public static boolean isBlueWhite(BinNode<Character> bt)
{
if (bt == null) // עץ ריק הוא כחול-לבן
return true;
char v = bt.getValue();
if (v != 'b' && v != 'w') // תנאי 1
return false;
BinNode<Character> left = bt.getLeft();
BinNode<Character> right = bt.getRight();
if (left == null && right == null) // עלה - תנאי 2
return v == 'b';
if (v == 'b') // צומת פנימי כחול - תנאי 3
{
if (left == null || right == null)
return false;
if (left.getValue() != 'w' || right.getValue() != 'w')
return false;
}
return isBlueWhite(left) && isBlueWhite(right);
}public static bool IsBlueWhite(BinNode<char> bt)
{
if (bt == null) // עץ ריק הוא כחול-לבן
return true;
char v = bt.GetValue();
if (v != 'b' && v != 'w') // תנאי 1
return false;
BinNode<char> left = bt.GetLeft();
BinNode<char> right = bt.GetRight();
if (left == null && right == null) // עלה - תנאי 2
return v == 'b';
if (v == 'b') // צומת פנימי כחול - תנאי 3
{
if (left == null || right == null)
return false;
if (left.GetValue() != 'w' || right.GetValue() != 'w')
return false;
}
return IsBlueWhite(left) && IsBlueWhite(right);
}בדיקה על העצים מסעיף א: הפעולה מחזירה false לעץ (1) (עלה 'w'), true לעץ (2), false לעץ (3) (צומת 'b' פנימי עם בן ימני חסר) ו-false לעץ (4) (עלה 'w').
תשובה: הפעולה isBlueWhite שלמעלה.
סעיף ג
O(n), כאשר n מספר הצמתים בעץ.
נסמן ב-n את מספר הצמתים בעץ.
1. הפעולה מזמנת את עצמה פעם אחת לכל צומת (ולכל היותר פעם אחת לכל מקום null שמתחת לעלה או לבן חסר – גם מספרם n + 1).
2. בכל זימון מתבצעות מספר קבוע של בדיקות (ערך הצומת, האם עלה, ערכי שני הבנים) – O(1).
3. לכן סך העבודה פרופורציונלי למספר הצמתים. (במקרה שנמצאת הפרה הפעולה עוצרת מוקדם יותר, אבל במקרה הגרוע – עץ כחול-לבן – עוברים על כל הצמתים.)
תשובה: – כל צומת נבדק פעם אחת בעבודה קבועה.