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



כתבו פעולה המקבלת תור של מחרוזות "תקין" q ומחרוזת st. הפעולה תוסיף את המחרוזת לתור כך שהוא יישאר תקין.
כותרת הפעולה:
public static void addToProperQueue(Queue<String> q, String s)public static void AddToProperQueue(Queue<string> q, string s)כתבו פעולה המקבלת תור של מחרוזות. הפעולה תבדוק אם תור הוא "תור תקין". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isProperQueue(Queue<String> q)public static bool IsProperQueue(Queue<string> q)כתבו פעולה המקבלת תור של מחרוזות. הפעולה תבדוק אם התור הוא "תור תקין". אם כן – הפעולה לא תבצע דבר, ואם לא – הפעולה תשנה את סדר המחרוזות בתור כך שהוא יהיה "תקין".
כותרת הפעולה:
public static void fixIt(Queue<String> q)public static void FixIt(Queue<string> q)מהי סיבוכיות הפעולות שכתבתם בסעיפים א'–ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
מכניסים את s מיד אחרי רצף המחרוזות שמתחילות באות של ראש התור (בעזרת תור עזר), ומחזירים את האיברים לתור.
נתון: תור "תקין" q – כל המחרוזות שמתחילות באות של המחרוזת שבראש התור נמצאות ברצף אחד בתחילת התור – ומחרוזת s.
מבוקש: להכניס את s לתור כך שהתור יישאר תקין.
הרעיון: נסמן ב-first את האות הראשונה של המחרוזת שבראש התור. בתור תקין כל המחרוזות שמתחילות ב-first נמצאות ברצף בתחילת התור. אם נכניס את s מיד אחרי הרצף הזה, התור יישאר תקין בכל מקרה:
•אם s מתחילה ב-first – היא מאריכה את הרצף שבתחילת התור;
•אם s מתחילה באות אחרת – היא נמצאת אחרי הרצף, ושם מותר להיות למחרוזות שאינן מתחילות ב-first.
שלבים:
1. אם התור ריק – מכניסים את s וסיימנו (תור בן איבר אחד תקין).
2. שומרים את first – האות הראשונה של `q.head()`.
3. מעבירים לתור עזר temp את כל המחרוזות שבראש q ומתחילות ב-first (הרצף שבתחילת התור).
4. מכניסים את s ל-temp.
5. מעבירים ל-temp את שאר איברי q, ואז מחזירים את כל temp ל-q – כך נשמר הסדר של כל שאר המחרוזות.
public static void addToProperQueue(Queue<String> q, String s)
{
if (q.isEmpty())
{
q.insert(s);
return;
}
char first = q.head().charAt(0);
Queue<String> temp = new Queue<String>();
while (!q.isEmpty() && q.head().charAt(0) == first) // הרצף שבתחילת התור
temp.insert(q.remove());
temp.insert(s); // s נכנסת מיד אחרי הרצף
while (!q.isEmpty()) // שאר המחרוזות
temp.insert(q.remove());
while (!temp.isEmpty()) // החזרה לתור המקורי
q.insert(temp.remove());
}public static void AddToProperQueue(Queue<string> q, string s)
{
if (q.IsEmpty())
{
q.Insert(s);
return;
}
char first = q.Head()[0];
Queue<string> temp = new Queue<string>();
while (!q.IsEmpty() && q.Head()[0] == first) // הרצף שבתחילת התור
temp.Insert(q.Remove());
temp.Insert(s); // s נכנסת מיד אחרי הרצף
while (!q.IsEmpty()) // שאר המחרוזות
temp.Insert(q.Remove());
while (!temp.IsEmpty()) // החזרה לתור המקורי
q.Insert(temp.Remove());
}דוגמה: בתור Cure, Cube, Cab, Crowd, Apple, Banana, Dog הוספת Cat נותנת Cure, Cube, Cab, Crowd, Cat, Apple, Banana, Dog, והוספת Egg נותנת Cure, Cube, Cab, Crowd, Egg, Apple, Banana, Dog – בשני המקרים התור נשאר תקין.
תשובה: הפעולה addToProperQueue שלמעלה – s מוכנסת מיד אחרי רצף המחרוזות שמתחילות באות של ראש התור.
סעיף ב
מעבר אחד על התור: אם אחרי מחרוזת שאינה מתחילה באות של ראש התור מופיעה שוב מחרוזת שמתחילה בה – false, אחרת true; התור משוחזר.
נתון: תור מחרוזות q. מבוקש: לבדוק שכל המחרוזות שמתחילות באות של ראש התור (first) נמצאות ברצף אחד בתחילת התור.
הרעיון: עוברים על התור פעם אחת. משתנה בוליאני afterRun מציין שכבר פגשנו מחרוזת שאינה מתחילה ב-first (כלומר הרצף שבתחילת התור הסתיים). אם אחרי זה מופיעה שוב מחרוזת שמתחילה ב-first – התור אינו תקין.
1. תור ריק – תקין (מחזירים true).
2. שומרים את first – האות הראשונה של ראש התור.
3. מוציאים כל מחרוזת ומכניסים אותה לתור עזר temp (כדי לשחזר את התור בסוף):
•מחרוזת שאינה מתחילה ב-first → afterRun = true;
•מחרוזת שמתחילה ב-first כאשר afterRun כבר true → proper = false.
4. מחזירים את כל האיברים מ-temp ל-q (התור לא משתנה) ומחזירים את proper.
public static boolean isProperQueue(Queue<String> q)
{
if (q.isEmpty())
return true;
char first = q.head().charAt(0);
Queue<String> temp = new Queue<String>();
boolean proper = true;
boolean afterRun = false; // האם הרצף שבתחילת התור כבר הסתיים
while (!q.isEmpty())
{
String str = q.remove();
temp.insert(str);
if (str.charAt(0) != first)
afterRun = true;
else if (afterRun)
proper = false; // first מופיעה שוב אחרי סוף הרצף
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return proper;
}public static bool IsProperQueue(Queue<string> q)
{
if (q.IsEmpty())
return true;
char first = q.Head()[0];
Queue<string> temp = new Queue<string>();
bool proper = true;
bool afterRun = false; // האם הרצף שבתחילת התור כבר הסתיים
while (!q.IsEmpty())
{
string str = q.Remove();
temp.Insert(str);
if (str[0] != first)
afterRun = true;
else if (afterRun)
proper = false; // first מופיעה שוב אחרי סוף הרצף
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return proper;
}בדיקה על הדוגמאות: בשני התורים התקינים אחרי Crowd אין עוד מחרוזת שמתחילה ב-C → true. בתור Cure, Cube, Cab, Crowd, Apple, Cat, Dog – אחרי Apple (afterRun = true) מגיעה Cat → false.
תשובה: הפעולה isProperQueue שלמעלה (התור משוחזר בסיומה).
סעיף ג
אם התור אינו תקין – מפצלים לשני תורים (מתחילות באות של הראש / שאר) ומחזירים קודם את הראשון ואחריו את השני.
הרעיון: משתמשים בפעולה מסעיף ב'. אם התור אינו תקין – מפרידים אותו לשני תורי עזר: same – המחרוזות שמתחילות באות first של ראש התור, others – כל השאר (בסדר המקורי). מחזירים ל-q קודם את כל same ואחריהן את others. כך כל המחרוזות שמתחילות ב-first נמצאות בתחילת התור, ברצף אחד – התור תקין.
public static void fixIt(Queue<String> q)
{
if (isProperQueue(q))
return; // התור תקין – לא עושים דבר
char first = q.head().charAt(0);
Queue<String> same = new Queue<String>();
Queue<String> others = new Queue<String>();
while (!q.isEmpty())
{
String str = q.remove();
if (str.charAt(0) == first)
same.insert(str);
else
others.insert(str);
}
while (!same.isEmpty()) // קודם כל המחרוזות שמתחילות ב-first
q.insert(same.remove());
while (!others.isEmpty()) // אחריהן כל השאר
q.insert(others.remove());
}public static void FixIt(Queue<string> q)
{
if (IsProperQueue(q))
return; // התור תקין – לא עושים דבר
char first = q.Head()[0];
Queue<string> same = new Queue<string>();
Queue<string> others = new Queue<string>();
while (!q.IsEmpty())
{
string str = q.Remove();
if (str[0] == first)
same.Insert(str);
else
others.Insert(str);
}
while (!same.IsEmpty()) // קודם כל המחרוזות שמתחילות ב-first
q.Insert(same.Remove());
while (!others.IsEmpty()) // אחריהן כל השאר
q.Insert(others.Remove());
}דוגמה: התור Cure, Cube, Cab, Crowd, Apple, Cat, Dog הופך ל-Cure, Cube, Cab, Crowd, Cat, Apple, Dog – תור תקין.
תשובה: הפעולה fixIt שלמעלה.
סעיף ד
לכל שלוש הפעולות (מספר קבוע של מעברים על התור).
נסמן ב-n את מספר המחרוזות בתור. כל פעולות התור (insert, remove, head, isEmpty) הן .
1. סעיף א': כל מחרוזת עוברת פעם אחת מ-q ל-temp ופעם אחת חזרה – פעולות, כלומר .
2. סעיף ב': מעבר אחד על התור ומעבר אחד לשחזור – .
3. סעיף ג': זימון isProperQueue – , ואחריו מעבר אחד לפיצול ומעבר אחד להחזרה – . בסך הכול .
אין בשום פעולה לולאה בתוך לולאה על איברי התור, ולכן כולן לינאריות.
תשובה: שלוש הפעולות בסיבוכיות .
שאלה 2 · רצפי K בשרשרת חוליות
נגדיר "רצף K" כרצף של K חוליות של מספרים שלמים שהערך של כל אחת מהן הוא K.

כתבו פעולה המקבלת שתי הפניות p1 ו-p2 לחוליות שונות בשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם החוליות בין p1 (כולל) ל-p2 (לא כולל) מהוות את "רצף K". אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
לדוגמה, עבור השרשרת שלפניכם (איור לסעיף א) הפעולה תחזיר ערך true.
כותרת הפעולה:
public static boolean isSequenceK(Node<Integer> p1,
Node<Integer> p2)public static bool IsSequenceK(Node<int> p1, Node<int> p2)
שרשרת חוליות נקראת "שרשרת רצפים" אם היא מורכבת מכמה "רצפי K".
כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם השרשרת היא "שרשרת רצפים". אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
לדוגמה, השרשרת שלפניכם היא "שרשרת רצפים" (איור לסעיף ב).
כותרת הפעולה:
public static boolean isSequenceList(Node<Integer> chain)public static bool IsSequenceList(Node<int> chain)מהי סיבוכיות הפעולות שכתבתם בסעיפים א'–ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
K = ערך החוליה p1; סופרים את החוליות מ-p1 עד p2 ובודקים שכולן שוות K ושמספרן K.
נתון: הפניות p1 ו-p2 לחוליות בשרשרת. מבוקש: לבדוק שכל החוליות מ-p1 (כולל) עד p2 (לא כולל) מכילות את אותו ערך K, ושמספרן בדיוק K.
הרעיון: הערך K הוא הערך של החוליה p1 (החוליה הראשונה ברצף). עוברים עם מצביע p מ-p1 עד p2 וסופרים את החוליות. אם נמצאת חוליה שערכה שונה מ-K – מחזירים false מיד. בסוף בודקים שמספר החוליות שנספרו שווה ל-K.
1. `k = p1.getValue()`, count = 0.
2. כל עוד p אינו p2 (וגם לא הגענו לסוף השרשרת – הגנה למקרה ש-p2 הוא null): אם ערך p שונה מ-k – false; אחרת count++ ומתקדמים.
3. מחזירים `count == k`.
public static boolean isSequenceK(Node<Integer> p1, Node<Integer> p2)
{
int k = p1.getValue();
int count = 0;
Node<Integer> p = p1;
while (p != p2 && p != null)
{
if (p.getValue() != k)
return false; // ערך שונה – זה לא רצף K
count++;
p = p.getNext();
}
return count == k; // בדיוק K חוליות
}public static bool IsSequenceK(Node<int> p1, Node<int> p2)
{
int k = p1.GetValue();
int count = 0;
Node<int> p = p1;
while (p != p2 && p != null)
{
if (p.GetValue() != k)
return false; // ערך שונה – זה לא רצף K
count++;
p = p.GetNext();
}
return count == k; // בדיוק K חוליות
}בדיקה על הדוגמה: p1 מצביע על ה-4 הראשון ו-p2 על ה-14 שאחרי ארבעת ה-4. k = 4, נספרות 4 חוליות שערכן 4 → count = 4 = k → true.
תשובה: הפעולה isSequenceK שלמעלה.
סעיף ב
מחלקים את השרשרת לקטעים מקסימליים של ערכים שווים ובודקים כל קטע עם isSequenceK; אם כולם תקינים – true.
נתון: שרשרת חוליות. מבוקש: לבדוק שהשרשרת מתחלקת לרצפים, וכל רצף של ערכים שווים שערכם K מכיל בדיוק K חוליות (בדוגמה: 2,2 | 4,4,4,4 | 1 | 3,3,3).
הרעיון: מחלקים את השרשרת לקטעים מקסימליים של ערכים שווים, ובודקים כל קטע בעזרת הפעולה מסעיף א'.
1. p מצביע על תחילת הקטע הנוכחי.
2. מקדמים מצביע q מ-p כל עוד הערך שווה לערך של p. בסיום q מצביע על החוליה הראשונה שאחרי הקטע (או null בסוף השרשרת).
3. מזמנים `isSequenceK(p, q)` – הוא בודק שאורך הקטע שווה לערך שבו. אם לא – מחזירים false.
4. ממשיכים מ-q (p = q) עד סוף השרשרת. אם כל הקטעים תקינים – מחזירים true.
public static boolean isSequenceList(Node<Integer> chain)
{
Node<Integer> p = chain;
while (p != null)
{
Node<Integer> q = p;
while (q != null && q.getValue().equals(p.getValue()))
q = q.getNext(); // q - החוליה הראשונה אחרי הקטע
if (!isSequenceK(p, q))
return false; // אורך הקטע שונה מהערך שבו
p = q; // מעבר לקטע הבא
}
return true;
}public static bool IsSequenceList(Node<int> chain)
{
Node<int> p = chain;
while (p != null)
{
Node<int> q = p;
while (q != null && q.GetValue() == p.GetValue())
q = q.GetNext(); // q - החוליה הראשונה אחרי הקטע
if (!IsSequenceK(p, q))
return false; // אורך הקטע שונה מהערך שבו
p = q; // מעבר לקטע הבא
}
return true;
}בדיקה על הדוגמה: הקטעים הם 2,2 (שתי חוליות, ערך 2 ✓), 4,4,4,4 (✓), 1 (✓), 3,3,3 (✓) → true. לעומת זאת עבור 2,2,4,4,4,1,3,3,3 הקטע 4,4,4 מכיל 3 חוליות בלבד → false.
תשובה: הפעולה isSequenceList שלמעלה.
סעיף ג
שתיהן .
נסמן ב-n את מספר החוליות בשרשרת.
1. סעיף א': הלולאה עוברת פעם אחת על החוליות שבין p1 ל-p2 – לכל היותר n חוליות, ולכן .
2. סעיף ב': כל חוליה נסרקת פעמיים בלבד: פעם אחת בלולאה הפנימית שמקדמת את q, ופעם אחת בתוך isSequenceK שבודקת את אותו קטע. הקטעים זרים זה לזה ו-p קופץ ישר לסוף הקטע, ולכן סך כל הצעדים הוא לכל היותר , כלומר – אף שיש לולאה בתוך לולאה.
תשובה: שתי הפעולות בסיבוכיות .
שאלה 3 · היררכיית ירושה, בנאים וכותרות פעולות
בשאלה זו שלושה סעיפים. אין קשר בין הסעיפים.
נתונה פעולה ראשית במחלקה Test.
public class Test {
public static void main(String[] args){
S s1 = new R();
P p1 = (P)(new R());
S s2 = new P();
P p2 = new Q();
// (*****)
}
}public class Test {
public static void Main(string[] args){
S s1 = new R();
P p1 = (P)(new R());
S s2 = new P();
P p2 = new Q();
// (*****)
}
}שרטטו את עצי הירושה עבור שתי אפשרויות היררכיה בין המחלקות כך שהפעולה הראשית תהיה תקינה והתוכנית תרוץ ללא שגיאות.
רוצים להוסיף בסוף התוכנית את שורת הקוד שלפניכם:
Q q1 =(Q) p1;האם התוכנית הראשית תהיה תקינה עבור שתי האפשרויות שציינתם? אם לא – מהו סוג השגיאה שתתרחש?
לפניכם המחלקות First, Second ו-Program. במחלקות First ו-Second חסר מימוש בנאים ופעולות toString.
public class First {
private static int c = 0;
protected int num;
public First(int num){…}
public String toString(){…}
}
public class Second extends First{
private char ch;
public Second(int num, char ch){…}
public String toString(){…}
}public class First {
private static int c = 0;
protected int num;
public First(int num){…}
public override string
ToString(){…}
}
public class Second : First{
private char ch;
public Second(int num, char ch):
base(num){…}
public override string
ToString(){…}
}השלימו את הפעולות במחלקות First ו-Second כך שאחרי הרצת הפעולה הראשית של המחלקה Program יתקבל הפלט הזה:
public class Program{
public static void main(String[] args) {
First f1 = new First(10);
System.out.println("f1 is "+f1);
First f2 = new Second(3,'A');
System.out.println("f2 is "+f2);
First f3 = new Second(4,'Z');
System.out.println("f3 is "+f3);
First f4 = new First(7);
System.out.println("f4 is "+f4);
}
}public class Program{
public static void Main(string[] args) {
First f1 = new First(10);
Console.WriteLine("f1 is "+f1);
First f2 = new Second(3,'A');
Console.WriteLine("f2 is "+f2);
First f3 = new Second(4,'Z');
Console.WriteLine("f3 is "+f3);
First f4 = new First(7);
Console.WriteLine("f4 is "+f4);
}
}f1 is 1-10
f2 is 2-6-A
f3 is 3-12-Z
f4 is 4-28לפניכם קוד המחלקה Two. המחלקה יורשת מהמחלקה One.
public class Two extends One
{
private int z;
public Two()
{
this.z = 11;
}
public Two(String s1, int z)
{
super(s1);
this.z = z;
}
public double p1(int a)
{
return a * super.p1(a);
}
public int p2()
{
return One.w + this.m();
}
public void print()
{
One.d();
System.out.println(s+"SON");
}
}public class Two : One
{
private int z;
public Two()
{
this.z = 11;
}
public Two(string s1, int z): base(s1)
{
this.z = z;
}
public override double P1(int a)
{
return a * base.P1(a);
}
public int P2()
{
return One.w + this.M();
}
public void Print()
{
One.D();
Console.WriteLine(s+" SON");
}
}כתבו במחלקה One את התכונות והכותרות של הפעולות הנדרשות.
יש לציין הרשאת הגישה (public, protected, private) לכל תכונה ולכל פעולה.
◂ פתרון מלא לשאלה 3
סעיף א
1) S ← P, ו-R, Q יורשות מ-P; 2) S ← P ← R ← Q.
נבדוק מה כל שורה מחייבת. השמה של עצם למשתנה מטיפוס אחר תקינה רק אם המחלקה של העצם יורשת (ישירות או בעקיפין) מטיפוס המשתנה.
1. `S s1 = new R();` – R יורשת מ-S.
2. `S s2 = new P();` – P יורשת מ-S.
3. `P p2 = new Q();` – Q יורשת מ-P.
4. `P p1 = (P)(new R());` – המרה של עצם מטיפוס R ל-P. כדי שהשורה תעבור הידור וגם לא תיכשל בזמן ריצה, העצם מטיפוס R חייב להיות גם P, כלומר R יורשת מ-P. (אילו R ו-P היו "אחיות" – שתיהן יורשות רק מ-S – ההמרה לא הייתה עוברת הידור.)
מכאן: P יורשת מ-S, ו-R ו-Q יורשות שתיהן מ-P (ישירות או אחת דרך השנייה). שתי אפשרויות מתאימות:
אפשרות 1: S ← P, ו-R ו-Q שתיהן יורשות ישירות מ-P.
אפשרות 2: שרשרת S ← P ← R ← Q (Q יורשת מ-R).
(אפשרות שלישית תקינה: S ← P ← Q ← R.)
תשובה: אפשרות 1 – P יורשת מ-S, ו-R, Q יורשות מ-P; אפשרות 2 – S ← P ← R ← Q.
לא – בשתי האפשרויות שגיאת זמן ריצה (חריגת המרה), כי p1 מפנה לעצם R שאינו Q.
1. הטיפוס הסטטי של p1 הוא P, ו-Q יורשת מ-P בשתי האפשרויות – לכן ההמרה (הורדה בעץ, downcasting) עוברת הידור.
2. בזמן ריצה p1 מפנה לעצם מטיפוס R. ההמרה מצליחה רק אם העצם הוא Q (כלומר R יורשת מ-Q).
•באפשרות 1 R ו-Q הן אחיות – עצם R אינו Q.
•באפשרות 2 Q יורשת מ-R ולא להפך – עצם R אינו Q.
3. לכן בשתי האפשרויות השורה תיכשל בזמן ריצה: חריגת המרה – ClassCastException ב-Java (InvalidCastException ב-C#).
(רק בהיררכיה S ← P ← Q ← R, שבה R יורשת מ-Q, השורה הייתה תקינה.)
תשובה: לא. בשתי האפשרויות תתרחש שגיאת זמן ריצה – חריגת המרה (ClassCastException / InvalidCastException), כי p1 מפנה לעצם R שאינו Q.
סעיף ב
First: c++; num = c*num; toString → c + "-" + num. Second: super(num); this.ch = ch; toString → super.toString() + "-" + ch.
ניתוח הפלט: בכל שורה המספר הראשון הוא מספר העצם שנוצר (1, 2, 3, 4) – זה המונה הסטטי c, שמשותף לכל העצמים וגדל ב-1 בכל יצירת עצם (גם עצם Second, כי הבנאי שלו מזמן את הבנאי של First). המספר השני הוא num כפול מספר העצם:
•f1: c = 1, num = 1·10 = 10 → "1-10";
•f2: c = 2, num = 2·3 = 6, ch = 'A' → "2-6-A";
•f3: c = 3, num = 3·4 = 12, ch = 'Z' → "3-12-Z";
•f4: c = 4, num = 4·7 = 28 → "4-28".
1. בנאי First: מגדילים את c ושומרים `num = c * num`.
2. toString של First: מחזירה c, מקף ו-num. (c הוא ערך המונה ברגע ההדפסה; בתוכנית כל עצם מודפס מיד אחרי שנוצר, ולכן c הוא בדיוק מספר העצם.)
3. בנאי Second: מעביר את num לבנאי של First (`super(num)` / `base(num)`) ושומר את ch.
4. toString של Second: מוסיפה לתוצאה של First מקף ואת התו ch.
public class First {
private static int c = 0;
protected int num;
public First(int num)
{
c++;
this.num = c * num;
}
public String toString()
{
return c + "-" + this.num;
}
}
public class Second extends First {
private char ch;
public Second(int num, char ch)
{
super(num);
this.ch = ch;
}
public String toString()
{
return super.toString() + "-" + this.ch;
}
}public class First {
private static int c = 0;
protected int num;
public First(int num)
{
c++;
this.num = c * num;
}
public override string ToString()
{
return c + "-" + this.num;
}
}
public class Second : First {
private char ch;
public Second(int num, char ch) : base(num)
{
this.ch = ch;
}
public override string ToString()
{
return base.ToString() + "-" + this.ch;
}
}תשובה: בנאי First: `c++; num = c * num;`, toString: `c + "-" + num`; בנאי Second: `super(num)` ו-`this.ch = ch`, toString: `super.toString() + "-" + ch`.
סעיף ג
protected String s; public static int w; public One(); public One(String s1); public double p1(int a); public int m(); public static void d().
נעבור על הקוד של Two ונראה מה הוא דורש מ-One:
1. `public Two()` – אין קריאה מפורשת ל-super, ולכן מתבצעת קריאה אוטומטית לבנאי ללא פרמטרים של One → One צריכה בנאי `One()`.
2. `super(s1)` / `base(s1)` – בנאי `One(String s1)`.
3. `super.p1(a)` – פעולה `p1(int)` ב-One. Two דורסת אותה עם ערך מוחזר double, ולכן גם ב-One הערך המוחזר הוא double (ב-C# הפעולה מסומנת virtual, כי ב-Two כתוב override).
4. `this.m()` – Two לא מגדירה את m, ולכן היא עוברת בירושה מ-One: פעולה `m()` שמחזירה int (הסכום `One.w + this.m()` מוחזר כ-int).
5. `One.w` – תכונה סטטית w מטיפוס int (ניגשים אליה דרך שם המחלקה).
6. `One.d()` – פעולה סטטית d ללא ערך מוחזר.
7. `s` – תכונה מטיפוס מחרוזת שנגישה ב-Two, ולכן היא לא private: protected (או public).
הרשאות: w, p1, m, d והבנאים חייבים להיות נגישים מ-Two – לכן public (ל-w ול-m אפשר גם protected).
public class One
{
protected String s;
public static int w;
public One() {…}
public One(String s1) {…}
public double p1(int a) {…}
public int m() {…}
public static void d() {…}
}public class One
{
protected string s;
public static int w;
public One() {…}
public One(string s1) {…}
public virtual double P1(int a) {…}
public int M() {…}
public static void D() {…}
}תשובה: תכונות: `protected String s`, `public static int w`; פעולות: `public One()`, `public One(String s1)`, `public double p1(int a)` (ב-C# virtual), `public int m()`, `public static void d()`.
שאלה 4 · מחלקות מפגש וירטואלי: חלוקה לחדרים
החברה "סוד זה הצלחה" החליטה שכל הישיבות והכנסים שלה יתקיימו באופן וירטואלי דרך מערכת מפגשים וירטואליים Boom שפיתחו מתכנתים שלה. במפגשי Boom ניתן לחלק משתתפים בין "חדרים וירטואליים". לשם ניהול המפגשים הווירטואליים פותחו מחלקות Meeting, VRoom, Participant.
•כל משתתף (Participant) מאופיין על ידי שם (name) ומספר היחידה שבה הוא עובד (dep, מספר שלם בין 1 ל-10).
•כל חדר (VRoom) מאופיין על ידי מספר חדר (num, מספר שלם וחיובי) ותור משתתפים (parts).
•למחלקה Meeting תכונה אחת – רשימת חדרים וירטואליים (rooms - שרשרת חוליות מסוג VRoom).
public class User {
private String name;
private int dep;
public User(String n, int d){
this.name = n;
this.dep = d;
}
} //אפשר להניח שהוגדרו הפעולות set/get
public class Meeting {
private Node<VRoom> rooms;
public Meeting() {
this.rooms = null;
}
}
public class Vroom {
private int num;
Queue<Participant> parts;
public VRoom(int n){… }
}public class User {
private string name;
private int dep;
public User(string n, int d){
this.name = n;
this.dep = d;
}
} //אפשר להניח שהוגדרו Set/Get
public class Meeting {
private Node<VRoom> rooms;
public Meeting() {
this.rooms = null;
}
}
public class Vroom {
private int num;
Queue<Participant> parts;
public VRoom(int n){
…
}
}כתבו במחלקה VRoom פעולה בונה המקבלת מספר חדר ובונה חדר ריק ממשתתפים.
כתבו במחלקה VRoom פעולה add המקבלת משתתף ומוסיפה אותו לחדר.
לפני כל ישיבה, הנהלת החברה מחליטה על מספר המשתתפים שיהיו בחדר וירטואלי.
כתבו במחלקה Meeting פעולה המקבלת מספר שלם וחיובי number. הפעולה תקלוט את פרטי המשתתפים (שם ומספר יחידה). הפעולה תיצור חדר שמספרו אחד ואליו יצטרפו number משתתפים ראשונים, לאחריו חדר מספר שתיים ואליו יצטרפו number משתתפים הבאים וכך הלאה. הקלט יסתיים כאשר ייקלט 0 כמספר המחלקה.
כותרת הפעולה:
public void divide (int number)public void Divide (int number)כאשר מטרת הישיבה היא סיעור מוחות (brainstorming), חשוב שבכל חדר יהיו נציגים מכל עשר יחידות החברה.
כתבו במחלקה Meeting פעולה אשר מדפיסה עבור כל חדר את מספרי יחידות החברה שנציגיהן לא נמצאים בחדר.
כותרת הפעולה:
public void printMissingUnits()public void PrintMissingUnits()◂ פתרון מלא לשאלה 4
סעיף א
num = n; parts = new Queue<Participant>();
הפעולה הבונה מקבלת את מספר החדר, שומרת אותו בתכונה num ויוצרת תור משתתפים ריק – החדר עדיין ריק ממשתתפים.
public class VRoom {
private int num;
private Queue<Participant> parts;
public VRoom(int n)
{
this.num = n;
this.parts = new Queue<Participant>(); // חדר ריק
}
}public class VRoom {
private int num;
private Queue<Participant> parts;
public VRoom(int n)
{
this.num = n;
this.parts = new Queue<Participant>(); // חדר ריק
}
}הערה: בקוד שבשאלה המחלקה של המשתתף נקראת User והמחלקה של החדר נכתבה Vroom; לפי הנוסח מדובר במחלקות Participant ו-VRoom, ובשמות אלה נשתמש. כמו כן נניח שבכל המחלקות הוגדרו פעולות get/set לתכונות (כמו שנאמר בהערה שבקוד).
תשובה: `num = n; parts = new Queue<Participant>();`
סעיף ב
this.parts.insert(p);
הוספת משתתף לחדר היא הכנסה שלו לסוף תור המשתתפים של החדר.
public void add(Participant p)
{
this.parts.insert(p);
}public void Add(Participant p)
{
this.parts.Insert(p);
}תשובה: `parts.insert(p)`.
סעיף ג
קליטה עד dep = 0; בכל פעם ש-number משתתפים מילאו חדר – נוצר חדר חדש (מספר עוקב) ומוסף לסוף rooms; כל משתתף מוסף לחדר הנוכחי.
נתון: number – מספר המשתתפים בכל חדר. מבוקש: לקלוט משתתפים עד שנקלט 0 כמספר יחידה, ולפזר אותם לחדרים 1, 2, 3, ... – number משתתפים בכל חדר. החדרים נשמרים בשרשרת rooms לפי הסדר.
1. מאתחלים את rooms לשרשרת ריקה, ומחזיקים הפניה last לחוליה האחרונה בשרשרת (כדי להוסיף חדרים בסוף, לפי סדר מספריהם), את החדר הנוכחי current ומונה count של המשתתפים בחדר הנוכחי. מתחילים עם `count = number` – כך שהמשתתף הראשון יגרום לפתיחת חדר 1.
2. קולטים שם ומספר יחידה. כל עוד מספר היחידה אינו 0:
•אם החדר הנוכחי מלא (`count == number`) – יוצרים חדר חדש שמספרו roomNum+1, מוסיפים אותו בסוף השרשרת rooms ומאפסים את count;
•יוצרים משתתף חדש, מוסיפים אותו לחדר הנוכחי (בעזרת add מסעיף ב') ומגדילים את count;
•קולטים את המשתתף הבא.
3. חדר האחרון יכול להכיל פחות מ-number משתתפים (אם מספר המשתתפים אינו מתחלק ב-number). אם הקלט הראשון כבר 0 – לא נוצר אף חדר.
public void divide(int number)
{
Scanner in = new Scanner(System.in);
this.rooms = null;
Node<VRoom> last = null; // החוליה האחרונה בשרשרת החדרים
VRoom current = null; // החדר שאליו מצטרפים כעת
int roomNum = 0;
int count = number; // החדר "מלא" - המשתתף הראשון יפתח חדר 1
System.out.print("Enter name: ");
String name = in.next();
System.out.print("Enter unit number (0 to stop): ");
int dep = in.nextInt();
while (dep != 0)
{
if (count == number) // פותחים חדר חדש
{
roomNum++;
current = new VRoom(roomNum);
Node<VRoom> node = new Node<VRoom>(current);
if (last == null)
this.rooms = node;
else
last.setNext(node);
last = node;
count = 0;
}
current.add(new Participant(name, dep));
count++;
System.out.print("Enter name: ");
name = in.next();
System.out.print("Enter unit number (0 to stop): ");
dep = in.nextInt();
}
}public void Divide(int number)
{
this.rooms = null;
Node<VRoom> last = null; // החוליה האחרונה בשרשרת החדרים
VRoom current = null; // החדר שאליו מצטרפים כעת
int roomNum = 0;
int count = number; // החדר "מלא" - המשתתף הראשון יפתח חדר 1
Console.Write("Enter name: ");
string name = Console.ReadLine();
Console.Write("Enter unit number (0 to stop): ");
int dep = int.Parse(Console.ReadLine());
while (dep != 0)
{
if (count == number) // פותחים חדר חדש
{
roomNum++;
current = new VRoom(roomNum);
Node<VRoom> node = new Node<VRoom>(current);
if (last == null)
this.rooms = node;
else
last.SetNext(node);
last = node;
count = 0;
}
current.Add(new Participant(name, dep));
count++;
Console.Write("Enter name: ");
name = Console.ReadLine();
Console.Write("Enter unit number (0 to stop): ");
dep = int.Parse(Console.ReadLine());
}
}(ב-Java נדרש `import java.util.Scanner;` בראש הקובץ.)
דוגמה: עבור number = 3 ושבעה משתתפים – חדר 1 מקבל את שלושת הראשונים, חדר 2 את שלושת הבאים וחדר 3 את המשתתף השביעי.
תשובה: הפעולה divide שלמעלה – פותחת חדר חדש בכל פעם ש-number משתתפים מילאו את החדר הקודם, ומוסיפה את החדרים לסוף rooms.
סעיף ד
לכל חדר: מערך found[1..10] מסומן לפי יחידות המשתתפים (התור משוחזר), ומודפסים מספרי היחידות שלא סומנו.
הרעיון: עוברים על שרשרת החדרים. לכל חדר:
1. מגדירים מערך בוליאני found בגודל 11 (אינדקסים 1–10 = מספרי היחידות), כולו false.
2. עוברים על תור המשתתפים של החדר: מוציאים כל משתתף, מסמנים `found[dep] = true` ומכניסים אותו לתור עזר. בסוף מחזירים את המשתתפים לתור החדר – כך החדר לא משתנה.
3. מדפיסים את מספר החדר ואת כל i בין 1 ל-10 שעבורו `found[i]` נשאר false – אלה היחידות שאין להן נציג בחדר.
public void printMissingUnits()
{
Node<VRoom> p = this.rooms;
while (p != null)
{
VRoom room = p.getValue();
Queue<Participant> parts = room.getParts();
Queue<Participant> temp = new Queue<Participant>();
boolean[] found = new boolean[11]; // found[i] - יש נציג מיחידה i
while (!parts.isEmpty())
{
Participant x = parts.remove();
found[x.getDep()] = true;
temp.insert(x);
}
while (!temp.isEmpty()) // שחזור תור המשתתפים
parts.insert(temp.remove());
System.out.print("Room " + room.getNum() + ":");
for (int i = 1; i <= 10; i++)
if (!found[i])
System.out.print(" " + i);
System.out.println();
p = p.getNext();
}
}public void PrintMissingUnits()
{
Node<VRoom> p = this.rooms;
while (p != null)
{
VRoom room = p.GetValue();
Queue<Participant> parts = room.GetParts();
Queue<Participant> temp = new Queue<Participant>();
bool[] found = new bool[11]; // found[i] - יש נציג מיחידה i
while (!parts.IsEmpty())
{
Participant x = parts.Remove();
found[x.GetDep()] = true;
temp.Insert(x);
}
while (!temp.IsEmpty()) // שחזור תור המשתתפים
parts.Insert(temp.Remove());
Console.Write("Room " + room.GetNum() + ":");
for (int i = 1; i <= 10; i++)
if (!found[i])
Console.Write(" " + i);
Console.WriteLine();
p = p.GetNext();
}
}דוגמה: בחדר שבו משתתפים מהיחידות 1, 2, 3 יודפס `Room 1: 4 5 6 7 8 9 10`.
תשובה: הפעולה printMissingUnits שלמעלה – לכל חדר מסמנים במערך found את היחידות שמיוצגות ומדפיסים את היחידות שלא סומנו.
שאלה 5 · מעקב אחר רקורסיה הבונה שרשרת
כתבו פעולה getLast המקבלת הפניה לחוליה הראשונה של שרשרת של מספרים שלמים. הפעולה תחזיר הפנייה לחוליה האחרונה של השרשרת.
נתונה הפעולה what המקבלת שני מספרים שלמים . הפעולה משתמשת בפעולה getLast.
public static Node<Integer> what (int n, int k){
if (n == k)
return new Node<Integer>(n);
else
{
if (k % 2 == 0)
return new Node<Integer>(k, what(n, k+1));
else
{
Node<Integer> p = new Node<Integer>(k);
Node<Integer> chain = what (n, k+1);
Node<Integer> last = getLast (chain);
last.setNext (p);
return chain;
}
}
}public static Node<int> What (int n, int k){
if (n == k)
return new Node<int>(n);
else
{
if (k % 2 == 0)
return new Node<int>(k, What(n, k+1));
else
{
Node<int> p = new Node<int>(k);
Node<int> chain = What (n, k+1);
Node<int> last = GetLast (chain);
last.SetNext (p);
return chain;
}
}
}עקבו אחרי זימון הפעולה what(10,5) ורשמו מה תחזיר הפעולה.
נתונה הפעולה secret:
public static Node<Integer> secret (int n, int k) {
if (n == k)
return new Node<Integer>(n);
else
{
if (n % 2 == 0)
return new Node<Integer>(n, secret(n-1, k));
else
{
Node<Integer> chain = secret (n-1, k);
getLast (chain).setNext (new Node<Integer>(n));
return chain;
}
}
}public static Node<int> Secret (int n, int k) {
if (n == k)
return new Node<int>(n);
else
{
if (n % 2 == 0)
return new Node<int>(n, Secret(n-1, k));
else
{
Node<int> chain = Secret (n-1, k);
GetLast (chain).SetNext (new Node<int>(n));
return chain;
}
}
}מה תהיה תוצאת הזימון secret(6, 2)?
האם קיימים שני מספרים שלמים וחיוביים כך שתוצאות הזימונים secret(n, k) ו-what(n, k) יהיו זהות? אם כן – תנו דוגמה לזוג מספרים שכזה, ואם לא – הסבירו למה הדבר אינו אפשרי.
כתבו את הפעולה what בצורה הלא רקורסיבית.
◂ פתרון מלא לשאלה 5
סעיף א
מתקדמים כל עוד getNext() אינו null ומחזירים את החוליה האחרונה.
מתקדמים מהחוליה הראשונה כל עוד יש חוליה עוקבת; החוליה שבה נעצרים – שאין לה עוקבת – היא האחרונה. (מניחים שהשרשרת אינה ריקה, כמו בכל הזימונים בשאלה.)
public static Node<Integer> getLast(Node<Integer> chain)
{
Node<Integer> p = chain;
while (p.getNext() != null)
p = p.getNext();
return p;
}public static Node<int> GetLast(Node<int> chain)
{
Node<int> p = chain;
while (p.GetNext() != null)
p = p.GetNext();
return p;
}תשובה: הפעולה getLast שלמעלה, .
סעיף ב
6 → 8 → 10 → 9 → 7 → 5
מה הפעולה עושה: אם k זוגי – החוליה k נוספת בתחילת השרשרת שמחזירה הקריאה what(n, k+1); אם k אי-זוגי – החוליה k נוספת בסוף השרשרת שמחזירה הקריאה. תנאי העצירה: k = n מחזיר שרשרת של חוליה אחת n.
הקריאות (בירידה): what(10,5) → what(10,6) → what(10,7) → what(10,8) → what(10,9) → what(10,10).
תשובה: הפעולה מחזירה הפניה לשרשרת 6 → 8 → 10 → 9 → 7 → 5.
סעיף ג
6 → 4 → 2 → 3 → 5
מה הפעולה עושה: כאן n יורד עד k. אם n זוגי – n נוסף בתחילת השרשרת של secret(n-1, k); אם n אי-זוגי – n נוסף בסוף. תנאי העצירה: n = k מחזיר את החוליה k.
תשובה: 6 → 4 → 2 → 3 → 5.
סעיף ד
כן, למשל n = 6, k = 5 (שתיהן 6 → 5); מתאים לכל .
השוואה כללית: בשתי הפעולות השרשרת מכילה את כל המספרים מ-k עד n. ב-what המספרים הזוגיים מופיעים בהתחלה בסדר עולה (כל זוגי קטן נוסף לפני הגדולים ממנו) והאי-זוגיים בסוף בסדר יורד; ב-secret הזוגיים מופיעים בהתחלה בסדר יורד והאי-זוגיים בסוף בסדר עולה. כאשר יש לפחות שני מספרים זוגיים או שני אי-זוגיים בתחום – הסדרים שונים. לכן מחפשים תחום קטן: .
1. what(6,5): k = 5 אי-זוגי → השרשרת של what(6,6), שהיא 6, ואחריה 5 → 6 → 5.
2. secret(6,5): n = 6 זוגי → 6 ואחריו secret(5,5), שהיא 5 → 6 → 5.
התוצאות זהות. באופן כללי, לכל שתי הפעולות מחזירות את שני המספרים כשהזוגי ביניהם ראשון (למשל עבור n = 3, k = 2 שתיהן מחזירות 2 → 3).
לעומת זאת, למשל עבור n = 6, k = 2: what(6,2) = 2 → 4 → 6 → 5 → 3 ואילו secret(6,2) = 6 → 4 → 2 → 3 → 5 – שונות.
תשובה: כן. לדוגמה n = 6, k = 5: שתי הפעולות מחזירות 6 → 5 (כל זוג שבו מתאים).
סעיף ה
מתחילים מחוליה n; עבור i מ-n-1 עד k: זוגי – מוסיפים בהתחלה, אי-זוגי – בסוף (בעזרת מצביע last).
הרעיון: לפי סעיף ב', what(n, k) בונה את השרשרת מהחוליה n ומוסיפה לה, מ-n-1 ועד k (בסדר יורד – כך חוזרים מהרקורסיה): מספר זוגי בהתחלה ומספר אי-זוגי בסוף. נממש זאת בלולאה:
1. first = last = חוליה חדשה עם הערך n.
2. עבור i מ-n-1 עד k (יורד): אם i זוגי – חוליה חדשה לפני first, והיא הופכת ל-first; אחרת – חוליה חדשה אחרי last, והיא הופכת ל-last.
3. מחזירים את first.
המצביע last חוסך את החיפוש של getLast, ולכן הגרסה הלא רקורסיבית היא .
public static Node<Integer> what(int n, int k)
{
Node<Integer> first = new Node<Integer>(n);
Node<Integer> last = first;
for (int i = n - 1; i >= k; i--)
{
if (i % 2 == 0)
first = new Node<Integer>(i, first); // זוגי - בהתחלה
else
{
Node<Integer> node = new Node<Integer>(i);
last.setNext(node); // אי-זוגי - בסוף
last = node;
}
}
return first;
}public static Node<int> What(int n, int k)
{
Node<int> first = new Node<int>(n);
Node<int> last = first;
for (int i = n - 1; i >= k; i--)
{
if (i % 2 == 0)
first = new Node<int>(i, first); // זוגי - בהתחלה
else
{
Node<int> node = new Node<int>(i);
last.SetNext(node); // אי-זוגי - בסוף
last = node;
}
}
return first;
}בדיקה: עבור what(10,5): מתחילים מ-10; i = 9 → 10 → 9; i = 8 → 8 → 10 → 9; i = 7 → 8 → 10 → 9 → 7; i = 6 → 6 → 8 → 10 → 9 → 7; i = 5 → 6 → 8 → 10 → 9 → 7 → 5 – כמו בסעיף ב'.
תשובה: הפעולה what הלא רקורסיבית שלמעלה.
שאלה 6 · עצים בינאריים: סכום עלים, סיווג צמתים
כתבו פעולה sumLeaves שמקבלת עץ בינארי של מספרים שלמים ומחזירה את סכום הערכים של כל העלים בעץ.
נתונה המחלקה NodeInfo שמכילה שתי תכונות: מספר שלם num, ומחרוזת info.
במחלקה הוגדרה פעולה בונה:
public NodeInfo(int num, String info)public NodeInfo(int num, string info)במחלקה הוגדרו פעולות get ו-set במחלקה NodeInfo.


כתבו פעולה createQueue המקבלת עץ בינארי של מספרים שלמים ומחזירה תור מטיפוס NodeInfo שבו:
•ערך ה-num בכל איבר זהה לערך הצומת בעץ המתקבל כפרמטר.
•ערך ה-info מכיל את המחרוזת "*leaf*" אם הצומת הוא עלה, ואת המחרוזת "*internal*" אם הצומת הוא צומת פנימי.
לדוגמה, עבור העץ שלפניכם (איור 1 לסעיף ב) הפעולה תחזיר את התור הזה (איור 2 לסעיף ב).
כותרת הפעולה:
public static Queue<NodeInfo> createQueue (BinNode<Integer> bt)public static Queue<NodeInfo> CreateQueue (BinNode<int> bt)כתבו פעולה maxLeaveValue המקבלת עץ בינארי של מספרים שלמים ומחזירה את הערך הגדול ביותר מבין העלים של העץ.
◂ פתרון מלא לשאלה 6
סעיף א
ריק → 0; עלה → ערכו; אחרת סכום העלים של שני תתי-העצים (בדוגמה: 20).
1. עץ ריק – סכום העלים 0.
2. אם הצומת הוא עלה (אין לו בן שמאלי ואין בן ימני) – הסכום הוא ערכו.
3. אחרת – סכום העלים בתת-העץ השמאלי ועוד סכום העלים בתת-העץ הימני.
public static int sumLeaves(BinNode<Integer> bt)
{
if (bt == null)
return 0;
if (!bt.hasLeft() && !bt.hasRight()) // עלה
return bt.getValue();
return sumLeaves(bt.getLeft()) + sumLeaves(bt.getRight());
}public static int SumLeaves(BinNode<int> bt)
{
if (bt == null)
return 0;
if (!bt.HasLeft() && !bt.HasRight()) // עלה
return bt.GetValue();
return SumLeaves(bt.GetLeft()) + SumLeaves(bt.GetRight());
}דוגמה: בעץ שבסעיף ב' העלים הם 4, 2, 8, 6, והסכום .
תשובה: הפעולה sumLeaves שלמעלה, .
סעיף ב
סריקה רקורסיבית של כל הצמתים; לכל צומת מכניסים לתור new NodeInfo(value, "leaf"/"internal").
הרעיון: יוצרים תור ריק ועוברים על כל צומתי העץ בסריקה רקורסיבית (תחילית: צומת, שמאל, ימין). פעולת עזר fillQueue מקבלת צומת ואת התור, מכניסה לתור עצם NodeInfo חדש עם ערך הצומת והמחרוזת "leaf" (אם לצומת אין בנים) או "internal" (אחרת), וממשיכה לשני תתי-העצים. התור נוצר פעם אחת בלבד ומועבר לכל הקריאות.
public static Queue<NodeInfo> createQueue(BinNode<Integer> bt)
{
Queue<NodeInfo> q = new Queue<NodeInfo>();
fillQueue(bt, q);
return q;
}
public static void fillQueue(BinNode<Integer> bt, Queue<NodeInfo> q)
{
if (bt == null)
return;
if (!bt.hasLeft() && !bt.hasRight())
q.insert(new NodeInfo(bt.getValue(), "leaf"));
else
q.insert(new NodeInfo(bt.getValue(), "internal"));
fillQueue(bt.getLeft(), q);
fillQueue(bt.getRight(), q);
}public static Queue<NodeInfo> CreateQueue(BinNode<int> bt)
{
Queue<NodeInfo> q = new Queue<NodeInfo>();
FillQueue(bt, q);
return q;
}
public static void FillQueue(BinNode<int> bt, Queue<NodeInfo> q)
{
if (bt == null)
return;
if (!bt.HasLeft() && !bt.HasRight())
q.Insert(new NodeInfo(bt.GetValue(), "leaf"));
else
q.Insert(new NodeInfo(bt.GetValue(), "internal"));
FillQueue(bt.GetLeft(), q);
FillQueue(bt.GetRight(), q);
}בדיקה על הדוגמה: הסריקה מכניסה לפי הסדר: 8 internal, 3 internal, 4 leaf, 2 leaf, 8 internal, 9 internal, 8 leaf, 6 leaf – בדיוק התור שבשאלה.
תשובה: הפעולה createQueue (עם פעולת העזר fillQueue) שלמעלה.
סעיף ג
עלה → ערכו; בן אחד → התשובה של תת-העץ שלו; שני בנים → המקסימום של שתי התשובות (בדוגמה: 8).
1. אם הצומת הוא עלה – הערך הגדול ביותר בין העלים שלו הוא ערכו.
2. אם יש לו רק בן אחד – התשובה היא המקסימום בתת-העץ של הבן הזה (צומת פנימי אינו עלה ולכן ערכו לא נספר).
3. אם יש שני בנים – המקסימום מבין שתי התשובות של תתי-העצים.
כך לא נדרש ערך התחלתי "קטן מאוד", והפעולה נכונה גם לערכים שליליים.
public static int maxLeaveValue(BinNode<Integer> bt)
{
if (!bt.hasLeft() && !bt.hasRight()) // עלה
return bt.getValue();
if (!bt.hasLeft())
return maxLeaveValue(bt.getRight());
if (!bt.hasRight())
return maxLeaveValue(bt.getLeft());
return Math.max(maxLeaveValue(bt.getLeft()), maxLeaveValue(bt.getRight()));
}public static int MaxLeaveValue(BinNode<int> bt)
{
if (!bt.HasLeft() && !bt.HasRight()) // עלה
return bt.GetValue();
if (!bt.HasLeft())
return MaxLeaveValue(bt.GetRight());
if (!bt.HasRight())
return MaxLeaveValue(bt.GetLeft());
return Math.Max(MaxLeaveValue(bt.GetLeft()), MaxLeaveValue(bt.GetRight()));
}דוגמה: בעץ שבסעיף ב' העלים הם 4, 2, 8, 6 והפעולה מחזירה 8 (הצומת 9 אינו עלה ולכן אינו נספר).
תשובה: הפעולה maxLeaveValue שלמעלה, .
שאלה 7 · תורים, עץ תורים "מעולה" ובדיקת טענה
כתבו פעולה המקבלת שני תורים של מספרים שלמים q1 ו-q2. הפעולה תבדוק אם כל הערכים של תור q1 קטנים מכל הערכים של q2. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isSmaller(Queue<Integer>q1,
Queue<Integer> q2)public static bool IsSmaller(Queue<int>q1, Queue<int> q2)
נתון עץ שבו כל צומת מכיל תור של מספרים שלמים. עץ נקרא "עץ מעולה" אם הוא עונה על שני התנאים האלה:
•לכל צומת שאינו עלה יש שני בנים.
•כל הערכים הנמצאים בצומת האב גדולים מכל הערכים הנמצאים בבן השמאלי וקטנים מכל הערכים הנמצאים בבן הימני.
לדוגמה, העץ שלפניכם הוא "עץ מעולה" (איור לסעיף ב).
כתבו פעולה המקבלת עץ תורים של מספרים שלמים ובודקת אם הוא "עץ מעולה". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
נתונה טענה: ערך הכי קטן ב"עץ מעולה" נמצא בעלה הכי שמאלי. האם הטענה נכונה? הסבירו את תשובתכם.
מהי הסיבוכיות של הפעולות שכתבתם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
true אם ורק אם המקסימום של q1 קטן מהמינימום של q2 (התורים משוחזרים).
נתון: שני תורים q1, q2 (נניח שאינם ריקים). מבוקש: לבדוק שכל ערך ב-q1 קטן מכל ערך ב-q2.
הרעיון: כל ערכי q1 קטנים מכל ערכי q2 בדיוק כאשר הגדול ביותר ב-q1 קטן מהקטן ביותר ב-q2. כך במקום להשוות כל זוג () מספיקים שני מעברים.
1. פעולת עזר maxInQueue: מעבר על התור (דרך תור עזר, כדי לשחזר אותו) ומציאת המקסימום.
2. פעולת עזר minInQueue: כנ"ל למינימום.
3. מחזירים `maxInQueue(q1) < minInQueue(q2)`.
public static int maxInQueue(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int max = q.head();
while (!q.isEmpty())
{
int x = q.remove();
if (x > max)
max = x;
temp.insert(x);
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return max;
}
public static int minInQueue(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int min = q.head();
while (!q.isEmpty())
{
int x = q.remove();
if (x < min)
min = x;
temp.insert(x);
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return min;
}
public static boolean isSmaller(Queue<Integer> q1, Queue<Integer> q2)
{
return maxInQueue(q1) < minInQueue(q2);
}public static int MaxInQueue(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int max = q.Head();
while (!q.IsEmpty())
{
int x = q.Remove();
if (x > max)
max = x;
temp.Insert(x);
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return max;
}
public static int MinInQueue(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int min = q.Head();
while (!q.IsEmpty())
{
int x = q.Remove();
if (x < min)
min = x;
temp.Insert(x);
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return min;
}
public static bool IsSmaller(Queue<int> q1, Queue<int> q2)
{
return MaxInQueue(q1) < MinInQueue(q2);
}דוגמה: q1 = 4, 6, 2, 3 (מקסימום 6), q2 = 12, 10, 7 (מינימום 7): → true.
תשובה: isSmaller מחזירה `max(q1) < min(q2)` (בעזרת שתי פעולות עזר ששומרות על התורים).
סעיף ב
רקורסיה: עלה/ריק → true; בן אחד → false; אחרת isSmaller(שמאל, אב) וגם isSmaller(אב, ימין) וגם שני תתי-העצים מעולים.
נתון: עץ בינארי שבכל צומת תור של מספרים. מבוקש: לבדוק את שני התנאים בכל צומת.
1. עץ ריק או עלה – תקין (true).
2. צומת עם בן אחד בלבד – מפר את התנאי הראשון → false.
3. צומת עם שני בנים – בודקים בעזרת isSmaller מסעיף א':
•כל ערכי הבן השמאלי קטנים מכל ערכי האב: `isSmaller(left, current)`;
•כל ערכי האב קטנים מכל ערכי הבן הימני: `isSmaller(current, right)`.
אם אחד מהם נכשל → false.
4. אם הצומת תקין – העץ מעולה רק אם גם תת-העץ השמאלי וגם הימני מעולים.
כותרת הפעולה (שם לבחירתנו): isMagicTree.
public static boolean isMagicTree(BinNode<Queue<Integer>> t)
{
if (t == null)
return true;
if (!t.hasLeft() && !t.hasRight()) // עלה
return true;
if (!t.hasLeft() || !t.hasRight()) // בן אחד בלבד
return false;
if (!isSmaller(t.getLeft().getValue(), t.getValue()))
return false; // בן שמאלי לא קטן מהאב
if (!isSmaller(t.getValue(), t.getRight().getValue()))
return false; // בן ימני לא גדול מהאב
return isMagicTree(t.getLeft()) && isMagicTree(t.getRight());
}public static bool IsMagicTree(BinNode<Queue<int>> t)
{
if (t == null)
return true;
if (!t.HasLeft() && !t.HasRight()) // עלה
return true;
if (!t.HasLeft() || !t.HasRight()) // בן אחד בלבד
return false;
if (!IsSmaller(t.GetLeft().GetValue(), t.GetValue()))
return false; // בן שמאלי לא קטן מהאב
if (!IsSmaller(t.GetValue(), t.GetRight().GetValue()))
return false; // בן ימני לא גדול מהאב
return IsMagicTree(t.GetLeft()) && IsMagicTree(t.GetRight());
}בדיקה על הדוגמה: בשורש: max(4,6,2,3) = 6 < min(12,10,7) = 7 ✓, max(12,10,7) = 12 < min(20,25,43) = 20 ✓. בצומת 20,25,43: max(13,18,16) = 18 < 20 ✓, 43 < min(48,50,66) = 48 ✓. שאר הצמתים עלים → true.
תשובה: הפעולה isMagicTree שלמעלה.
סעיף ג
לפי ההגדרה (השוואה לבנים הישירים בלבד) – לא נכונה; דוגמה נגדית: 10 / (5, 20 / (1, 30)). נכונה רק אם התנאי חל על תתי-עצים שלמים.
נבדוק את הטענה לפי ההגדרה: התנאי השני משווה כל צומת רק לשני בניו הישירים.
1. ננסה להראות שהטענה נכונה: מהשורש, הערכים בבן השמאלי קטנים מערכי השורש. אבל ההגדרה אינה מגבילה את הנכדים ביחס לשורש: הבן השמאלי של הבן הימני צריך להיות קטן רק מאביו (הבן הימני), ולא גדול מהשורש.
2. דוגמה נגדית: שורש עם התור 10; בן שמאלי (עלה) עם 5; בן ימני עם 20, ולו שני בנים-עלים: שמאלי עם 1 וימני עם 30.
•בשורש: ✓; בצומת 20: ✓; לכל צומת פנימי שני בנים ✓ – זה "עץ מעולה".
•העלה השמאלי ביותר מכיל 5, אבל הערך הקטן ביותר בעץ הוא 1 – בעלה אחר.
3. הטענה הייתה נכונה אילו התנאי היה חל על תתי-עצים שלמים (כל ערכי תת-העץ השמאלי קטנים מערכי הצומת, וכל ערכי תת-העץ הימני גדולים מהם – כמו בעץ חיפוש בינארי, וכמו בעץ שבדוגמה). אז, ביורדים תמיד שמאלה, כל תת-עץ ימני שמדלגים עליו מכיל רק ערכים גדולים מהצומת, והערך הקטן ביותר נמצא בעלה השמאלי ביותר.
תשובה: לפי ההגדרה כפי שנוסחה (השוואה לבנים הישירים בלבד) הטענה אינה נכונה – למשל בעץ 10 / (5, 20 / (1, 30)) המינימום 1 אינו בעלה השמאלי ביותר. היא נכונה רק אם התנאי חל על כל ערכי תתי-העצים.
סעיף ד
א' – ; ב' – לינארי בסך הערכים, ( כאשר ).
1. isSmaller (סעיף א'): עבור תורים בגודל n ו-m – מעבר אחד (ושחזור) על כל תור: .
2. isMagicTree (סעיף ב'): כל צומת מבקר פעם אחת. בכל צומת פנימי מזמנים isSmaller פעמיים, כלומר עוברים על התור של הצומת ועל התורים של שני בניו. כל תור נסרק לכל היותר 3 פעמים (פעמיים כאב ופעם אחת כבן), ולכן הסיבוכיות לינארית במספר הערכים הכולל N בכל התורים: . אם בעץ n צמתים ובכל תור עד m ערכים, – כלומר , ואם גודל התורים מאותו סדר גודל כמו מספר הצמתים – .
תשובה: סעיף א' – (לינארי); סעיף ב' – לינארי בסך כל הערכים בעץ, , כלומר כאשר .
שאלה 8 · ירושה, דריסה והעמסה: מעקב פלט
נתונות המחלקות האלה:
public abstract class A
{
protected int x;
public A() {
this.x = 1;
}
public abstract int f(int v);
public void f(A a) {
x = a.x;
}
public String toString(){
return "x =" + this.x;
}
} //end of class A
public class B extends A {
public B() {
super();
}
public B(int val) {
this.x = f(val);
}
public int f(int val) {
return this.x + val;
}
public void f(B b) {
this.x = this.x * b.x;
}
public String toString(){
return "B: " +
super.toString();
}
} //end of class B
public class D extends B {
public D(int val) {
this.x = val - this.x;
}
public void f(A a) {
this.x = this.x + a.x + 1;
}
public void f(B b) {
this.x = this.x * b.x;
}
public void f(D d) {
this.x = d.x - 1;
}
public String toString(){
return "D: " +
super.toString();
}
} //end of class D
public class Driver
{
public static void main
(String [] args){
A a;
B b;
int m;
// ************
}
}public abstract class A {
public int x;
public A() {
this.x = 1;
}
public abstract int F(int v);
public virtual void F(A a) {
x = a.x;
}
public override
string ToString(){
return "x =" + this.x;
}
} //end of class A
public class B : A {
public B():base() {
}
public B(int val):base(){
this.x = F(val);
}
public override int F(int val){
return this.x + val;
}
public virtual void F(B b){
this.x = this.x * b.x;
}
public override
string ToString(){
return "B: " + base.ToString();
}
} //end of class B
public class D : B {
public D(int val):base(){
this.x = val - this.x;
}
public override void F(A a){
this.x = this.x + a.x + 1;
}
public override void F(B b){
this.x = this.x * b.x;
}
public void F(D d) {
this.x = d.x - 1;
}
public override string ToString(){return "D: " + base.ToString();}
} //end of class D
public class Driver {
public static void Main (string [] args){
A a;
B b;
int m;
// ************
}
}מהו הפלט של קטע הקוד שלפניכם:
m = 11;
a = new B(m);
System.out.println(a);
a = new D(m);
System.out.println(a);m = 11;
a = new B(m);
Console.WriteLine(a);
a = new D(m);
Console.WriteLine(a);מהו הפלט של קטע הקוד שלפניכם:
b = new B(3);
m = b.f(4);
System.out.println(m);
m = b.f(m);
System.out.println(m);b = new B(3);
m = b.F(4);
Console.WriteLine(m);
m = b.F(m);
Console.WriteLine(m);מהו הפלט של קטע הקוד שלפניכם:
a = new B(5);
int m = a.f(a.f(2));
System.out.println(m);a = new B(5);
m = a.F(a.F(2));
Console.WriteLine(m);מהו הפלט של קטע הקוד שלפניכם:
a = new D(10);
b = new B(20);
a.f(b);
System.out.println(a);a = new D(10);
b = new B(20);
a.F(b);
Console.WriteLine(a);אחרי ביצוע קטע הקוד הבא, הערך של התכונה x של העצם d יהיה 5.
מהו הערך של המשתנה m?
D d = new D(m);
b = new B();
((A)d).f(b);D d = new D(m);
b = new B();
((A)d).F(b);◂ פתרון מלא לשאלה 8
סעיף א
B: x =12, ואחריו D: B: x =10.
1. `new B(11)`: הבנאי B(int) מזמן קודם את הבנאי של A → . אחר כך `x = f(11)` – הפעולה f(int) של B מחזירה , ולכן .
2. הדפסת a מזמנת את toString של B (העצם מטיפוס B): `"B: " + super.toString()` → `B: x =12`.
3. `new D(11)`: הבנאי של B ללא פרמטרים ← A → , ואז .
4. הדפסה: toString של D מוסיפה "D: " לפני התוצאה של B, שמוסיפה "B: " לפני "x =" ו-x.
שימו לב: הבנאי של D מזמן קודם (במפורש או במובלע) את הבנאי הריק של B, שמזמן את הבנאי של A, ולכן לפני השורה `this.x = val - this.x` מתקיים . מכאן שעצם D שנוצר עם val מקבל .
הסעיף זהה ב-Java וב-C#.
B: x =12
D: B: x =10סעיף ב
8 ואחריו 12.
1. `new B(3)`: , ואז .
2. `b.f(4)`: הארגומנט מטיפוס int, ולכן נבחרת f(int) של B – היא מחזירה ולא משנה את x. – מודפס 8.
3. `b.f(m)`: שוב ארגומנט int (m = 8) → f(int): . – מודפס 12. (x של b נשאר 4.)
הסעיף זהה ב-Java וב-C#.
8
12סעיף ג
14
1. `new B(5)`: , ואז .
2. הטיפוס הסטטי של a הוא A, וב-A מוגדרת f(int) (מופשטת). בזמן ריצה מופעלת f(int) של B (העצם מטיפוס B):
•הקריאה הפנימית `a.f(2)` → ;
•הקריאה החיצונית `a.f(8)` → .
3. – מודפס 14.
(בגרסת Java כתוב `int m = ...`, אבל m כבר הוגדר בתחילת main – הגדרה כפולה הייתה שגיאת הידור. הכוונה להשמה `m = a.f(a.f(2));`, כמו בגרסת C#.)
תשובה: `14`
סעיף ד
D: B: x =31
1. `new D(10)`: .
2. `new B(20)`: .
3. `a.f(b)`: בחירת הגרסה בזמן הידור נעשית לפי הטיפוס הסטטי של a, שהוא A. ב-A יש רק f(int) ו-f(A); הארגומנט b מטיפוס B הוא גם A, ולכן נבחרת f(A a) (הגרסאות f(B) ו-f(D) לא מוכרות דרך הטיפוס A).
4. בזמן ריצה העצם הוא D, ו-D דורסת את f(A): `x = x + a.x + 1` → .
5. ההדפסה מזמנת את toString של D.
תשובה: `D: B: x =31` (זהה ב-Java וב-C#).
סעיף ה
נעבוד מהסוף להתחלה.
1. `b = new B()`: (הבנאי של A).
2. `((A)d).f(b)`: הטיפוס הסטטי הוא A (ההמרה), ולכן – כמו בסעיף ד' – נבחרת f(A). בזמן ריצה העצם הוא D, ומופעלת f(A) של D: .
3. אחרי הקריאה , ולכן לפניה – זה הערך ש-d קיבל בבנאי.
4. הבנאי D(m) נותן , ולכן → .
תשובה: .
שאלה 9 · חיפוש במחסניות: הכלה, סדר ותת-מחסנית
נתונות שתי הפעולות isExist1 ו-isExist2
public static boolean isExist1(Stack<Integer> st, int x){
while(!st.isEmpty()){
if(st.pop()==x) return true;
}
return false;
}
public static boolean isExist2(Stack<Integer> st, int x){
Stack<Integer> temp = new Stack<Integer>();
boolean f = false;
while(!st.isEmpty()){
if(st.top()==x) f = true;
temp.push(st.pop());
}
while(!temp.isEmpty()) {
st.push(temp.pop());
}
return f;
}public static bool IsExist1(Stack<int> st, int x){
while(!st.IsEmpty()){
if(st.Pop()==x) return true;
}
return false;
}
public static bool IsExist2(Stack<int> st, int x){
Stack<int> temp = new Stack<int>();
bool f = false;
while(!st.IsEmpty()){
if(st.Top()==x) f = true;
temp.Push(st.Pop());
}
while(!temp.IsEmpty()) {
st.Push(temp.Pop());
}
return f;
}הסבירו מה מבצעת כל אחת מהפעולות, מה הבדל ביניהן ומהי הסיבוכיות של כל אחת מהן.
כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים st1 ו-st2. הפעולה תבדוק אם כל האיברים של המחסנית st1 נמצאים במחסנית st2. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
לדוגמה, עבור זוג המחסניות שלפניכם הפעולה תחזיר true (איור לסעיף ב).
כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים st1 ו-st2. הפעולה תבדוק אם כל האיברים של המחסנית st1 נמצאים במחסנית st2 באותו הסדר. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
לדוגמה, עבור זוג המחסניות מסעיף ב' הפעולה תחזיר false. אבל אם המחסנית st2 תהיה כך (איור לסעיף ג) הפעולה תחזיר ערך true.
כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים st1 ו-st2. הפעולה תבדוק אם המחסנית st1 היא תת-מחסנית של st2 (כלומר, אם כל האיברים של המחסנית st1 נמצאים במחסנית st2 ברצף ובאותו הסדר). אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
לדוגמה, עבור זוג המחסניות מסעיף ב' או ג' הפעולה תחזיר false. אבל אם המחסנית st2 תהיה כך (איור לסעיף ד) הפעולה תחזיר ערך true.
מהי הסיבוכיות של כל אחת מהפעולות שכתבתם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 9
סעיף א
שתיהן בודקות אם x במחסנית; isExist1 הורסת את המחסנית, isExist2 משחזרת אותה; שתיהן .
מה מבצעות: שתי הפעולות בודקות אם הערך x נמצא במחסנית st ומחזירות true/false.
1. isExist1 מוציאה איברים מהמחסנית ואינה מחזירה אותם: אם x נמצא – כל האיברים שמעליו ו-x עצמו נמחקים, ואם x לא נמצא – המחסנית מתרוקנת. כלומר היא הורסת את המחסנית. מצד שני, היא עוצרת מיד כשמוצאים את x.
2. isExist2 מעבירה את כל האיברים למחסנית עזר temp תוך כדי הבדיקה, ובסוף מחזירה אותם ל-st – המחסנית נשמרת בסדרה המקורי. היא תמיד עוברת על כל המחסנית (גם אם x נמצא בראש).
סיבוכיות (n – מספר האיברים):
•isExist1: במקרה הגרוע (x בתחתית או לא קיים) n הוצאות – ; במקרה הטוב (x בראש) .
•isExist2: תמיד העברות – .
תשובה: שתיהן בודקות אם x במחסנית; isExist1 הורסת את המחסנית (ועוצרת כשמוצאת), isExist2 משחזרת אותה. שתיהן .
סעיף ב
לכל איבר של st1 בודקים isExist2(st2, x); אם כולם קיימים – true (st1 משוחזרת).
הרעיון: מוציאים את איברי st1 אחד אחד (ומעבירים למחסנית עזר כדי לשחזר אותה), ולכל איבר בודקים בעזרת isExist2 מסעיף א' אם הוא נמצא ב-st2 – כי היא שומרת על st2 (isExist1 הייתה הורסת את st2). אם איבר כלשהו חסר – התשובה false. בסוף מחזירים את איברי st1 למקומם.
כותרת הפעולה (שם לבחירתנו): containsAll.
public static boolean containsAll(Stack<Integer> st1, Stack<Integer> st2)
{
Stack<Integer> temp = new Stack<Integer>();
boolean all = true;
while (!st1.isEmpty())
{
int x = st1.pop();
temp.push(x);
if (!isExist2(st2, x)) // isExist2 שומרת על st2
all = false;
}
while (!temp.isEmpty()) // שחזור st1
st1.push(temp.pop());
return all;
}public static bool ContainsAll(Stack<int> st1, Stack<int> st2)
{
Stack<int> temp = new Stack<int>();
bool all = true;
while (!st1.IsEmpty())
{
int x = st1.Pop();
temp.Push(x);
if (!IsExist2(st2, x)) // IsExist2 שומרת על st2
all = false;
}
while (!temp.IsEmpty()) // שחזור st1
st1.Push(temp.Pop());
return all;
}בדיקה על הדוגמה: 2, 3, 10, 7 – כל אחד מהם נמצא ב-st2 → true.
תשובה: הפעולה containsAll שלמעלה.
סעיף ג
מעבר מקביל: כל איבר של st2 ששווה לראש st1 "מסמן" אותו; true אם st1 נמצאה כולה (המחסניות משוחזרות).
הרעיון: צריך לבדוק ש-st1 היא "תת-סדרה" של st2: אפשר למצוא את איברי st1 בתוך st2 לפי אותו סדר (לא בהכרח ברצף). עוברים על שתי המחסניות מהראש לתחתית במקביל:
1. מוציאים איבר מ-st2 (ושומרים אותו במחסנית עזר t2).
2. אם הוא שווה לאיבר שבראש st1 – האיבר של st1 "נמצא": מוציאים אותו מ-st1 (לעזר t1) ומחפשים מעכשיו את האיבר הבא של st1.
3. ממשיכים עד ש-st1 התרוקנה (כל האיברים נמצאו בסדר) או ש-st2 נגמרה.
4. התשובה: האם st1 התרוקנה. לבסוף משחזרים את שתי המחסניות.
ההתאמה החמדנית (לקחת את ההופעה הראשונה המתאימה) נכונה: אם יש התאמה כלשהי, אפשר תמיד להחליף כל איבר בהופעה המוקדמת יותר שלו מבלי לפגוע בהמשך. הבדיקה מהראש לתחתית שקולה לבדיקה מהתחתית לראש, כי הסדר היחסי של האיברים נשמר בשני הכיוונים.
כותרת הפעולה (שם לבחירתנו): containsInOrder.
public static boolean containsInOrder(Stack<Integer> st1, Stack<Integer> st2)
{
Stack<Integer> t1 = new Stack<Integer>();
Stack<Integer> t2 = new Stack<Integer>();
while (!st1.isEmpty() && !st2.isEmpty())
{
int x = st2.pop();
t2.push(x);
if (x == st1.top()) // נמצא האיבר הבא של st1
t1.push(st1.pop());
}
boolean ans = st1.isEmpty(); // כל איברי st1 נמצאו לפי הסדר
while (!t1.isEmpty()) // שחזור המחסניות
st1.push(t1.pop());
while (!t2.isEmpty())
st2.push(t2.pop());
return ans;
}public static bool ContainsInOrder(Stack<int> st1, Stack<int> st2)
{
Stack<int> t1 = new Stack<int>();
Stack<int> t2 = new Stack<int>();
while (!st1.IsEmpty() && !st2.IsEmpty())
{
int x = st2.Pop();
t2.Push(x);
if (x == st1.Top()) // נמצא האיבר הבא של st1
t1.Push(st1.Pop());
}
bool ans = st1.IsEmpty(); // כל איברי st1 נמצאו לפי הסדר
while (!t1.IsEmpty()) // שחזור המחסניות
st1.Push(t1.Pop());
while (!t2.IsEmpty())
st2.Push(t2.Pop());
return ans;
}בדיקה על הדוגמאות (לפי סדר הציור): st1 = 2, 3, 10, 7.
•st2 = 3, 14, 2, 2, 3, 7, 10, 2, 7: נמצאים 2 (שלישי), 3 (חמישי), 10 (שביעי), 7 (תשיעי) → true.
•st2 מסעיף ב' = 3, 14, 2, 2, 3, 7, 10, 2, 10: נמצאים 2, 3, 10, אבל אחרי ה-10 אין 7 → false.
תשובה: הפעולה containsInOrder שלמעלה.
סעיף ד
לכל נקודת התחלה ב-st2 בודקים אם st1 מופיעה בה ברצף (isPrefix); true אם נמצאה אחת.
הרעיון: st1 היא תת-מחסנית של st2 אם קיים מקום ב-st2 שממנו מופיעים כל איברי st1 ברצף. נבדוק כל נקודת התחלה ב-st2:
1. פעולת עזר isPrefix(st1, st2): בודקת אם st1 מופיעה בראש st2 – משווה את הראשים, מוציאה את שניהם למחסניות עזר כל עוד הם שווים, ועוצרת בחוסר התאמה. בסוף משחזרת את שתי המחסניות. אם st1 נגמרה – true.
2. isSubStack: בודקת את isPrefix על st2 כמו שהיא; אם לא – מוציאה איבר אחד מראש st2 (למחסנית עזר) ובודקת שוב, עד שנמצאה התאמה או ש-st2 התרוקנה. בסוף משחזרת את st2.
כותרות הפעולות (שמות לבחירתנו): isPrefix, isSubStack.
public static boolean isPrefix(Stack<Integer> st1, Stack<Integer> st2)
{
Stack<Integer> t1 = new Stack<Integer>();
Stack<Integer> t2 = new Stack<Integer>();
boolean ok = true;
while (ok && !st1.isEmpty())
{
if (st2.isEmpty() || !st1.top().equals(st2.top()))
ok = false;
else
{
t1.push(st1.pop());
t2.push(st2.pop());
}
}
while (!t1.isEmpty()) // שחזור המחסניות
st1.push(t1.pop());
while (!t2.isEmpty())
st2.push(t2.pop());
return ok;
}
public static boolean isSubStack(Stack<Integer> st1, Stack<Integer> st2)
{
Stack<Integer> temp = new Stack<Integer>();
boolean found = isPrefix(st1, st2);
while (!found && !st2.isEmpty())
{
temp.push(st2.pop()); // נקודת ההתחלה הבאה ב-st2
found = isPrefix(st1, st2);
}
while (!temp.isEmpty()) // שחזור st2
st2.push(temp.pop());
return found;
}public static bool IsPrefix(Stack<int> st1, Stack<int> st2)
{
Stack<int> t1 = new Stack<int>();
Stack<int> t2 = new Stack<int>();
bool ok = true;
while (ok && !st1.IsEmpty())
{
if (st2.IsEmpty() || st1.Top() != st2.Top())
ok = false;
else
{
t1.Push(st1.Pop());
t2.Push(st2.Pop());
}
}
while (!t1.IsEmpty()) // שחזור המחסניות
st1.Push(t1.Pop());
while (!t2.IsEmpty())
st2.Push(t2.Pop());
return ok;
}
public static bool IsSubStack(Stack<int> st1, Stack<int> st2)
{
Stack<int> temp = new Stack<int>();
bool found = IsPrefix(st1, st2);
while (!found && !st2.IsEmpty())
{
temp.Push(st2.Pop()); // נקודת ההתחלה הבאה ב-st2
found = IsPrefix(st1, st2);
}
while (!temp.IsEmpty()) // שחזור st2
st2.Push(temp.Pop());
return found;
}(ב-Java משווים את הראשים עם equals, כי top מחזירה Integer.)
בדיקה על הדוגמה: ב-st2 = 3, 14, 2, 2, 3, 10, 7, 2, 7 מופיע הרצף 2, 3, 10, 7 (איברים 4–7) → true. ב-st2 של סעיף ג' האיברים מופיעים בסדר אך לא ברצף → false.
תשובה: הפעולה isSubStack (עם פעולת העזר isPrefix) שלמעלה.
סעיף ה
ב' – ; ג' – ; ד' – .
נסמן ב-n את מספר האיברים ב-st1 וב-m את מספר האיברים ב-st2.
1. סעיף ב' (containsAll): לכל אחד מ-n איברי st1 מזמנים isExist2 על st2, שעולה . סך הכול .
2. סעיף ג' (containsInOrder): מעבר אחד במקביל על שתי המחסניות ושחזור – כל איבר מוצא ומוחזר פעם אחת: .
3. סעיף ד' (isSubStack): יש עד m+1 נקודות התחלה, ולכל אחת isPrefix עולה עד (משווים לכל היותר n איברים ומשחזרים). סך הכול .
אם שתי המחסניות באותו סדר גודל n, סעיפים ב' ו-ד' הם וסעיף ג' .
תשובה: ב' – ; ג' – ; ד' – .