מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2023 מועד ב'
הנדסת תוכנה · סמל 97105 · 10 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2023 מועד ב', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 14)
בכל מבחן 10 שאלות.
שאלות 1-4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 5-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 9-10: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · פיצול תור ציונים לתור ציונים ותור ספירה
ציוני תלמידים שמורים בתור כך שציוניו של תלמיד מסויים מופרדים מציונים של תלמיד אחר עם הערך -1.
תלמיד ראשון השלים שלוש בחינות וקיבל את הציונים הבאים: 80, 90, 100.
תלמיד שני השלים שתי בחינות וקיבל את הציונים הבאים: 75, 96.
תלמיד שלישי השלים ארבע בחינות וקיבל את הציונים 100, 100, 97, 96.
תלמיד רביעי לא השלים אף בחינה ואין לו ציונים.
תלמיד חמישי השלים שתי בחינות וקיבל את הציונים הבאים: 88, 94
בבית הספר התקבלה החלטה לשמור את המידע בצורה אחרת, בעזרת שני תורים:
תור ראשון (marks) יכיל ציונים ותור שני (tests) יכיל עבור כל אחד מהתלמידים את מספר הבחינות שהשלים.



כתבו פעולה בשם arrangeData המקבלת תור ציונים ומחזירה תור חדש המכיל עבור כל אחד מהתלמידים את מספר הבחינות שהשלים. הפעולה גם צריכה לעדכן את תור הציונים כך שיכיל רק ציונים ללא ערך ההפרדה -1.
כותרת הפעולה:
public static Queue<Integer> arrangeData(Queue<Integer> marks)public static Queue<int> ArrangeData(Queue<int> marks)מהי סיבוכיות הפעולה arrangeData שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
מרוקנים את marks איבר-איבר: ציון נשמר בתור עזר ומגדיל מונה; מכניס את המונה ל-tests ומאפס אותו. בסוף מחזירים את הציונים מתור העזר ל-marks ומחזירים את tests.
הרעיון: בתור אפשר לגשת רק לראש, ולכן עוברים על כל האיברים של marks בעזרת הוצאה (remove) עד שהתור מתרוקן.
•מונה count סופר כמה ציונים יש לתלמיד הנוכחי.
•כל ציון (ערך שונה מ-) נשמר בתור עזר temp, והמונה גדל ב-1.
•ערך מסמן שהציונים של התלמיד הנוכחי הסתיימו: מכניסים את count לתור tests ומאפסים אותו. כך גם תלמיד בלי ציונים (שני צמודים) מקבל 0.
•בסוף temp מכיל את כל הציונים בלי ערכי ההפרדה ובאותו סדר, ומעבירים אותו חזרה ל-marks (התור המקורי עודכן, כפי שנדרש).
1. יוצרים את tests ואת temp ריקים, ו-count = 0.
2. כל עוד marks לא ריק – מוציאים איבר x:
•אם x == -1 – מכניסים את count ל-tests ומאפסים את count.
•אחרת – מכניסים את x ל-temp ומגדילים את count.
3. אם בסוף נשאר count > 0 (התור לא הסתיים ב-), מכניסים אותו ל-tests – כך הפעולה עמידה גם לקלט כזה.
4. מעבירים את כל temp חזרה ל-marks ומחזירים את tests.
public static Queue<Integer> arrangeData(Queue<Integer> marks)
{
Queue<Integer> tests = new Queue<Integer>(); // התור שיוחזר
Queue<Integer> temp = new Queue<Integer>(); // הציונים בלי ערכי ההפרדה
int count = 0; // מונה הבחינות של התלמיד הנוכחי
while (!marks.isEmpty())
{
int x = marks.remove();
if (x == -1) // הסתיימו הציונים של תלמיד
{
tests.insert(count);
count = 0;
}
else // ציון רגיל
{
temp.insert(x);
count++;
}
}
if (count > 0) // ליתר ביטחון: אם אחרי התלמיד האחרון אין -1
tests.insert(count);
while (!temp.isEmpty()) // מחזירים את הציונים לתור marks
marks.insert(temp.remove());
return tests;
}public static Queue<int> ArrangeData(Queue<int> marks)
{
Queue<int> tests = new Queue<int>(); // התור שיוחזר
Queue<int> temp = new Queue<int>(); // הציונים בלי ערכי ההפרדה
int count = 0; // מונה הבחינות של התלמיד הנוכחי
while (!marks.IsEmpty())
{
int x = marks.Remove();
if (x == -1) // הסתיימו הציונים של תלמיד
{
tests.Insert(count);
count = 0;
}
else // ציון רגיל
{
temp.Insert(x);
count++;
}
}
if (count > 0) // ליתר ביטחון: אם אחרי התלמיד האחרון אין -1
tests.Insert(count);
while (!temp.IsEmpty()) // מחזירים את הציונים לתור marks
marks.Insert(temp.Remove());
return tests;
}בדיקה על הדוגמה: 80, 90, 100 נכנסים ל-temp (count = 3), ה- מכניס 3 ל-tests. אחר כך 75, 96 → 2; אחר כך 100, 100, 97, 96 → 4; שני צמודים → 0; ולבסוף 88, 94 → 2. מתקבל tests = 3, 2, 4, 0, 2 ו-marks = 80, 90, 100, 75, 96, 100, 100, 97, 96, 88, 94 – בדיוק כמו באיורים.
תשובה: הפעולה arrangeData שלמעלה.
סעיף ב
, כאשר n מספר האיברים בתור marks (כולל ערכי ההפרדה).
נסמן ב-n את מספר האיברים בתור marks לפני הזימון (ציונים וערכי ).
1. הלולאה הראשונה מוציאה כל איבר פעם אחת בדיוק, ועושה עליו מספר קבוע של פעולות (השוואה, insert, הגדלת מונה) – .
2. הלולאה השנייה מעבירה את הציונים מ-temp חזרה ל-marks; יש בו לכל היותר n איברים – .
3. שאר הפעולות (יצירת התורים, אתחול) הן .
סך הכול – סיבוכיות לינארית.
תשובה: .
שאלה 2 · איזון שרשרת חוליות: אורך זוגי וסכום אפס
שרשרת חוליות המכילה מספרים שלמים (חיוביים, שלילים ואפסים) נקראת "מאוזנת" אם אורכה זוגי וסכום כל הערכים שווה לאפס.
כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות. אם שרשרת "מאוזנת", הפעולה לא עושה דבר. אם לא – הפעולה תוסיף לסוף שרשרת איבר אחד או שני איברים כדי "לאזן" את השרשרת.
כותרת הפעולה:
public static void balance(Node<Integer> chain)public static void Balance(Node<int> chain)מהי סיבוכיות הפעולה balance שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
סורקים פעם אחת ומחשבים אורך len, סכום sum וחוליה אחרונה. אם len זוגי ו-sum = 0 – לא עושים דבר; אם len אי-זוגי – מוסיפים חוליה -sum; אם len זוגי ו-sum ≠ 0 – מוסיפים שתי חוליות: -sum ו-0.
הרעיון: כדי להחליט מה להוסיף צריך לדעת שלושה דברים: אורך השרשרת len, סכום הערכים sum, והחוליה האחרונה (כדי לחבר אחריה). את שלושתם מקבלים במעבר אחד על השרשרת.
אחרי המעבר יש שלושה מקרים:
1. len זוגי ו-sum = 0 – השרשרת כבר "מאוזנת", לא עושים דבר.
2. len אי-זוגי – מוסיפים חוליה אחת עם הערך -sum. האורך נעשה זוגי () והסכום נעשה . (זה נכון גם כש-sum = 0: מוסיפים חוליה עם 0.)
3. len זוגי ו-sum ≠ 0 – הוספת חוליה אחת הייתה הופכת את האורך לאי-זוגי, ולכן מוסיפים שתי חוליות: -sum ואחריה 0. האורך זוגי והסכום .
ההנחה: chain מפנה לחוליה הראשונה, כלומר השרשרת אינה ריקה.
public static void balance(Node<Integer> chain)
{
int len = 1; // מספר החוליות
int sum = chain.getValue(); // סכום הערכים
Node<Integer> last = chain; // בסוף הלולאה: החוליה האחרונה
while (last.hasNext())
{
last = last.getNext();
len++;
sum += last.getValue();
}
if (len % 2 == 0 && sum == 0) // השרשרת כבר "מאוזנת"
return;
if (len % 2 == 1) // אורך אי-זוגי: מוסיפים חוליה אחת
{
last.setNext(new Node<Integer>(-sum));
}
else // אורך זוגי וסכום שונה מ-0: מוסיפים שתי חוליות
{
last.setNext(new Node<Integer>(-sum));
last.getNext().setNext(new Node<Integer>(0));
}
}public static void Balance(Node<int> chain)
{
int len = 1; // מספר החוליות
int sum = chain.GetValue(); // סכום הערכים
Node<int> last = chain; // בסוף הלולאה: החוליה האחרונה
while (last.HasNext())
{
last = last.GetNext();
len++;
sum += last.GetValue();
}
if (len % 2 == 0 && sum == 0) // השרשרת כבר "מאוזנת"
return;
if (len % 2 == 1) // אורך אי-זוגי: מוסיפים חוליה אחת
{
last.SetNext(new Node<int>(-sum));
}
else // אורך זוגי וסכום שונה מ-0: מוסיפים שתי חוליות
{
last.SetNext(new Node<int>(-sum));
last.GetNext().SetNext(new Node<int>(0));
}
}- 4, 1, (אורך 3, סכום 3) → מוסיפים : מתקבל 4, 1, , – אורך 4, סכום 0.
- 2, 3 (אורך 2, סכום 5) → מוסיפים ו-0: מתקבל 2, 3, , 0 – אורך 4, סכום 0.
- 3, – כבר מאוזנת, לא משתנה.
תשובה: הפעולה balance שלמעלה.
סעיף ב
, כאשר n מספר החוליות בשרשרת.
נסמן ב-n את מספר החוליות בשרשרת.
1. הלולאה עוברת על כל חוליה פעם אחת ומבצעת בכל חוליה מספר קבוע של פעולות – .
2. הבדיקות שאחרי הלולאה והוספת חוליה אחת או שתיים (יש לנו כבר הפניה לחוליה האחרונה) – .
סך הכול .
תשובה: – לינארית באורך השרשרת.
שאלה 3 · העמסה, דריסה ו-equals בירושה
נתונה המחלקה Square המתארת ריבוע:
public class Square {
protected double width;
protected String color;
public Square(double val){ width = val; color = "black";}
public void paint(double scale, String color){..}
public double perimeter(double scale){ … }
}public class Square {
protected double width;
protected string color;
public Square(double val){ width = val; color = "black";}
public void Paint(double scale, string color){..}
public virtual double Perimeter(double scale){ … }
}אילו מהחתימות הבאות היא העמסה (overloading) חוקית של הפעולה paint?
1. public int paint (double y, String x)
2. public void paint (int x)
3. public double paint (double a, char b)
4. private void paint(double x, String y)
5. private double paint (String y, double x)1. public int Paint (double y, string x)
2. public void Paint (int x)
3. public double Paint (double a, char b)
4. private void Paint(double x, string y)
5. private double Paint (string y, double x)נתונה המחלקה Rectangle (מלבן) יורשת מ- Square
public class Rectangle extends Square {
private double length;
public Rectangle(double val1, double val2){
super(val1);
length = val2;
}
public boolean equals(Rectangle other){
return width == other.width && length == other.length;
}
}public class Rectangle : Square {
private double length;
public Rectangle(double val1, double val2):base(val1)
{
length = val2;
}
public bool Equals(Rectangle other){
return width == other.width && length == other.length;
}
}עבור כל אחת מבין הפעולות הבאות קבעו אם אפשר להוסיף אותה למחלקה Rectangle?
1. private double perimeter (double x){…}
2. public double perimeter (double y) {…}
3. public void perimeter (){…}
4. public int perimeter (int y) {…}
5. public void perimeter (double x) {…}1. private override double Perimeter (double x){…}
2. public override double Perimeter (double y) {…}
3. public override void Perimeter (){…}
4. public override int Perimeter (int y) {…}
5. public override void Perimeter (double x) {…}לפניכם קטע קוד מהתוכנית הראשית:
Square sqr1 = new Square(1);
Square sqr2 =new Square(1);
Square sqrRec = new Rectangle(1,2);
Rectangle rec = new Rectangle(1,2);
System.out.println(sqr1.equals(sqr2));
System.out.println(sqrRec.equals(rec));
System.out.println(sqrRec.equals((Square)rec));
System.out.println(((Rectangle)sqrRec).equals(rec));
System.out.println(rec.equals(sqrRec));Square sqr1 = new Square(1);
Square sqr2 =new Square(1);
Square sqrRec = new Rectangle(1,2);
Rectangle rec = new Rectangle(1,2);
Console.WriteLine(sqr1.Equals(sqr2));
Console.WriteLine(sqrRec.Equals(rec));
Console.WriteLine(sqrRec.Equals((Square)rec));
Console.WriteLine(((Rectangle)sqrRec).Equals(rec));
Console.WriteLine(rec.Equals(sqrRec));עקבו אחרי ביצוע קטע קוד ורשמו מה יהיה הפלט.
◂ פתרון מלא לשאלה 3
סעיף א
העמסות חוקיות: 2, 3, 5. לא חוקיות: 1, 4 (אותה רשימת פרמטרים (double, String) כמו paint הקיימת; שינוי טיפוס ההחזרה או ההרשאה בלבד אינו העמסה).
הכלל: העמסה (overloading) היא פעולה נוספת עם אותו שם במחלקה, שרשימת הפרמטרים שלה שונה – במספר הפרמטרים, בטיפוסים או בסדר הטיפוסים. שמות הפרמטרים, טיפוס הערך המוחזר ומשנה ההרשאה (public / private) אינם חלק מהחתימה, ולכן שינוי שלהם בלבד אינו מבדיל בין פעולות – המהדר מדווח שהפעולה כבר מוגדרת.
החתימה הקיימת: paint(double, String) (ב-C#: Paint(double, string)).
התשובה זהה ב-Java וב-C#.
תשובה: חתימות 2, 3, 5 הן העמסות חוקיות; 1 ו-4 אינן חוקיות.
סעיף ב
Java: אפשר להוסיף את 2, 3, 4; אי אפשר את 1 (דריסה שמצמצמת הרשאה) ואת 5 (אותה חתימה עם טיפוס החזרה אחר). C#: אפשר להוסיף רק את 2.
הכללים: Rectangle יורשת מ-Square את perimeter(double) שמחזירה double ומוגדרת public.
•פעולה במחלקה היורשת עם אותה חתימה (אותו שם ואותה רשימת פרמטרים) היא דריסה (override). בדריסה טיפוס ההחזרה חייב להיות זהה (או תואם) ואסור לצמצם את ההרשאה (אסור להפוך פעולה public ל-private).
•פעולה עם אותו שם ורשימת פרמטרים אחרת היא העמסה – מותרת תמיד, עם כל טיפוס החזרה.
•ב-C# יש גם המילה override: מותר לכתוב אותה רק אם במחלקת הבסיס יש פעולה virtual עם אותה חתימה בדיוק (שם, פרמטרים וטיפוס החזרה), ועם אותה הרשאה. פעולה virtual/override לא יכולה להיות private.
C# (בכל החתימות כתוב override):
תשובה: ב-Java אפשר להוסיף את הפעולות 2, 3, 4 (ואי אפשר את 1, 5); ב-C# אפשר להוסיף רק את פעולה 2.
סעיף ג
Java: false, false, false, true, false (כל אחד בשורה). C#: False, False, False, True, False.
נקודת המפתח: ב-Square אין equals משלה, ולכן יש לה את equals(Object) של Object, שבודקת זהות הפניות (האם זה אותו עצם). ב-Rectangle הפעולה equals(Rectangle other) מקבלת פרמטר מטיפוס Rectangle, ולכן היא העמסה ולא דריסה של equals(Object). איזו גרסה תופעל נקבע בזמן הידור לפי הטיפוס המוצהר של המשתנה שעליו מפעילים ושל הארגומנט:
•אם הטיפוס המוצהר של המשתנה הוא Square – המהדר מכיר רק את equals(Object), והיא לא נדרסה ב-Rectangle, לכן תמיד משווים הפניות.
•אם הטיפוס המוצהר הוא Rectangle וגם הארגומנט מוצהר Rectangle – נבחרת equals(Rectangle), המדויקת יותר, שמשווה את width ו-length.
(ב-C# המצב זהה: ל-Square יש רק Equals(object) של object, ו-Equals(Rectangle) היא העמסה.)
false
false
false
true
falseפלט ב-C# (ערך bool מודפס באות גדולה):
False
False
False
True
Falseתשובה: false, false, false, true, false (ב-C#: False, False, False, True, False).
שאלה 4 · עצי ירושה, המרות טיפוסים ובנאי super
נתונה הפעולה main במחלקה Driver:
public static void main(String[] args)
{
Three x1 = new One();
Two x2 = (Two)(new One());
Two x3 = new Four();
One x4 = new Four();
}public static void Main(string[] args)
{
Three x1 = new One();
Two x2 = (Two)(new One());
Two x3 = new Four();
One x4 = new Four();
}נתונות חמש האפשרויות לעץ הירושה הכולל את המחלקות One, Two, Three, Four.
1. Three יורשת מ-One, Two יורשת מ-One, Four יורשת מ-One
2. Three יורשת מ-One, Two יורשת מ-One, Four יורשת מ-Two
3. One יורשת מ-Three, Four יורשת מ-Two, Three יורשת מ-Two
4. One יורשת מ-Three, Three יורשת מ-Two, Four יורשת מ-One
5. One יורשת מ-Three, Two יורשת מ-One, Four יורשת מ-One
עבור כל אחת מהאפשרויות 5-1 ציירו עץ ירושה וכתבו אם הפעולה main תהיה תקינה או תתרחש שגיאת הידור (קומפילציה) או שגיאת זמן ריצה. הסבירו את תשובתכם.
(אין קשר לסעיף א')
נתונות שלוש המחלקות הבאות:
•המחלקה Point מתארת נקודה על ציר ה-X.
public class Point
{
private int x;
public Point (int x)
{
this.x = x;
}
public String toString()
{
return " x= " + this.x;
}
}public class Point
{
protected int x;
public Point (int x)
{
this.x = x;
}
public override string ToString()
{
return " x= " + this.x;
}
}•המחלקה Circle מתארת מעגל עם מרכז על ציר ה-X
public class Circle extends Point
{
private int radius;
public Circle( int x, int radius)
{
…..
}
public String toString()
{
…..
}
}public class Circle : Point
{
private int radius;
public Circle( int x, int radius): base(…..)
{
…..
}
public override string ToString()
{
…..
}
}•המחלקה Cylinder מייצגת גליל
public class Cylinder extends Circle
{
private int height;
…….
}public class Cylinder : Circle
{
private int height;
…….
}נתונה הפעולה main הבאה
public static void main(String[] args)
{
Circle b = new Circle (1, 2);
System.out.println(b);
Cylinder c = new Cylinder (10, 20, 30);
System.out.println(c);
}public static void Main(string[] args)
{
Circle b = new Circle (1, 2);
Console.WriteLine(b);
Cylinder c = new Cylinder (10, 20, 30);
Console.WriteLine(c);
}השלימו את הפעולות החסרות במחלקות Cylinder ו- Circle כך שפלט של הפעולה main יהיה
x = 1, radius = 2
x = 10, radius = 20, height = 30◂ פתרון מלא לשאלה 4
סעיף א
1 – שגיאת הידור; 2 – שגיאת הידור; 3 – שגיאת הידור; 4 – תקינה; 5 – שגיאת הידור.
•`A v = new B();` עובר הידור רק אם B היא A או יורשת ממנה (ישירות או דרך מחלקות ביניים) – הצבה "כלפי מעלה". אחרת – שגיאת הידור.
•`(A)(new B())` – המרה מפורשת עוברת הידור רק אם A ו-B באותו קו ירושה (אחת יורשת מהשנייה). בזמן ריצה היא מצליחה רק אם העצם (B) הוא באמת A, כלומר B היא A או יורשת ממנה. אם A יורשת מ-B (המרה "כלפי מטה" של עצם שאינו A) – שגיאת זמן ריצה (ClassCastException ב-Java, InvalidCastException ב-C#). אם אין ביניהן קשר – שגיאת הידור.
•שגיאת הידור באחת השורות מונעת את הרצת התוכנית כולה, ולכן היא "קודמת" לשגיאת זמן ריצה.
לכל אפשרות צריך: One יורשת מ-Three (שורה x1), Four יורשת מ-Two (x3), Four יורשת מ-One (x4), ו-One היא Two (x2, כדי שלא תהיה שגיאה בזמן ריצה).
עצי הירושה (המחלקה העליונה – מחלקת הבסיס):
אפשרות 1:
One
/ | \
Two Three Four
אפשרות 2:
One
/ \
Two Three
|
Four
אפשרות 3:
Two
/ \
Three Four
|
One
אפשרות 4:
Two
|
Three
|
One
|
Four
אפשרות 5:
Three
|
One
/ \
Two Fourהסבר קצר לכל אפשרות:
1. השורה x1 מנסה לשים עצם One במשתנה Three, אבל One היא מחלקת הבסיס של Three ולא להפך – שגיאת הידור (וגם x3 שגויה).
2. אותה שגיאה בשורה x1 – שגיאת הידור.
3. השורות x1–x3 תקינות, אבל ב-x4 העצם Four יורש רק מ-Two ואין לו קשר ל-One – שגיאת הידור.
4. כל ההצבות הן "כלפי מעלה" לאורך השרשרת: Four יורשת מ-One, One מ-Three ו-Three מ-Two; וגם ההמרה (Two) של עצם One מצליחה כי One היא Two – התוכנית תקינה.
5. בשורה x3 המחלקות Four ו-Two שתיהן יורשות מ-One ואין ביניהן קשר ירושה – שגיאת הידור. (גם אילו תוקנה שורה זו, השורה x2 הייתה נכשלת בזמן ריצה, כי עצם One אינו Two.)
ב-C# התוצאות זהות.
תשובה: אפשרות 4 תקינה; באפשרויות 1, 2, 3, 5 תתרחש שגיאת הידור.
סעיף ב
Circle: בנאי super(x) / base(x) ואתחול radius; toString מחזירה את תיאור הנקודה ועוד ", radius = " + radius. Cylinder: בנאי (x, radius, height) שקורא ל-super(x, radius) / base(x, radius) ומאתחל height; toString מחזירה super.toString() + ", height = " + height.
הרעיון: כל מחלקה מאתחלת ומדפיסה רק את התכונות שהיא עצמה מוסיפה, ואת השאר משאירה למחלקת הבסיס:
1. בנאי Circle – מקבל x ו-radius. את x אי אפשר להציב ישירות ב-Java (הוא private ב-Point), ולכן קוראים לבנאי של Point: super(x) (ב-C#: base(x)). אחר כך מאתחלים את radius.
2. toString של Circle – מוסיפה את הרדיוס לתיאור של הנקודה.
3. בנאי Cylinder – ב-main נקרא new Cylinder(10, 20, 30), ולכן צריך בנאי עם שלושה פרמטרים: super(x, radius) מאתחל את החלק של Circle (ודרכו את Point), ואחר כך height.
4. toString של Cylinder – מחזירה את התיאור של Circle (super.toString()) ומוסיפה ", height = " והגובה. כך בלי לשכפל קוד מתקבלת השורה השנייה.
public class Circle extends Point
{
private int radius;
public Circle(int x, int radius)
{
super(x); // את x מאתחלת Point
this.radius = radius;
}
public String toString()
{
return super.toString() + ", radius = " + this.radius;
}
}
public class Cylinder extends Circle
{
private int height;
public Cylinder(int x, int radius, int height)
{
super(x, radius); // את x ו-radius מאתחלת Circle
this.height = height;
}
public String toString()
{
return super.toString() + ", height = " + this.height;
}
}public class Circle : Point
{
private int radius;
public Circle(int x, int radius): base(x) // את x מאתחלת Point
{
this.radius = radius;
}
public override string ToString()
{
return "x = " + x + ", radius = " + this.radius; // x מוגדר protected ב-Point
}
}
public class Cylinder : Circle
{
private int height;
public Cylinder(int x, int radius, int height): base(x, radius)
{
this.height = height;
}
public override string ToString()
{
return base.ToString() + ", height = " + this.height;
}
}הערה על Java: ב-Point של Java השדה x הוא private ואין לו פעולת get, ולכן Circle יכולה לקבל את x רק דרך super.toString(), שמחזירה בדיוק " x= " + x כפי שהיא כתובה בשאלה. לכן ב-Java השורות יודפסו כ-` x= 1, radius = 2` ו-` x= 10, radius = 20, height = 30` – אותו תוכן, וההבדל בריווח נובע מה-toString הנתונה של Point. אם רוצים את הריווח המדויק, אפשר לכתוב ב-Circle:
`return super.toString().trim().replace("x=", "x =") + ", radius = " + this.radius;`
ב-C# השדה x מוגדר protected, ולכן Circle ניגשת אליו ישירות והפלט זהה בדיוק לנדרש.
מעקב (C#): new Circle(1, 2) – base(1) מציב x = 1, ואז radius = 2; ToString מחזירה "x = 1, radius = 2". new Cylinder(10, 20, 30) – base(10, 20) בונה את חלק ה-Circle, ואז height = 30; ToString של Cylinder קוראת ל-ToString של Circle ומוסיפה ", height = 30".
תשובה: הבנאים ופעולות toString של Circle ו-Cylinder שלמעלה.
שאלה 5 · רשימה סופר-עולה בשרשרת חוליות
רשימת מספרים שלמים וחיוביים נקראת "סופר עולה" (super-increasing sequence) אם כל איבר ברשימה גדול מסכום של כל האיברים שנמצאים לפניו ברשימה.
שרשרת החוליות הבאה מייצגת רשימה "סופר עולה":

כתבו פעולה חיצונית בשם isSuper המקבלת הפניה לחוליה ראשונה של שרשרת חוליות ובודקת אם היא מייצגת רשימה "סופר עולה". אם כן – הפעולה תחזיר true, ואם לא – הפעולה תחזיר false.
כותרת הפעולה:
public static boolean isSuper(Node<Integer> n)public static bool IsSuper(Node<int> n)כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות שהיא רשימה "סופר עולה", ומספר שלם וחיובי num. הפעולה תבדוק האם אפשר להוסיף את המספר num לשרשרת כך שרשימה תישאר "סופר עולה". אם כן – הפעולה תכניס את המספר למיקומו ותחזיר true. אם לא – הפעולה תחזיר false ולא תבצע שום שינוי.
אפשר להניח שמספר num גדול מאיבר הראשון בשרשרת.
לדוגמה: אפשר להוסיף לרשימה כל אחד מהמספרים 60, 90, 1200 שבאיור. לעומת זאת, כל אחד מהמספרים 15, 40, 700, אי אפשר להוסיף לשרשרת שבאיור והיא עדיין תישאר "סופר עולה".
כותרת הפעולה:
public static boolean addToSuper(Node<Integer> n, int num)public static bool AddToSuper(Node<int> n, int num)מהי סיבוכיות הפעולות isSuper ו- addToSuper מהסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 5
סעיף א
עוברים על השרשרת עם צובר sum של האיברים הקודמים; אם איבר כלשהו קטן או שווה ל-sum מחזירים false, אחרת מוסיפים אותו ל-sum; בסוף מחזירים true.
הרעיון: לכל איבר צריך לדעת את סכום כל האיברים שלפניו. במקום לחשב את הסכום מחדש לכל איבר, שומרים צובר sum שמתעדכן תוך כדי מעבר: לפני הבדיקה של איבר, sum הוא בדיוק סכום קודמיו.
1. sum = 0 (לפני האיבר הראשון אין איברים).
2. לכל חוליה: אם הערך קטן או שווה ל-sum – האיבר אינו גדול מסכום קודמיו, ומחזירים false. (עבור האיבר הראשון זו בדיקה שהוא חיובי, כנדרש.)
3. אחרת מוסיפים את הערך ל-sum ועוברים לחוליה הבאה.
4. אם עברנו על כל השרשרת בלי לעצור – מחזירים true.
public static boolean isSuper(Node<Integer> n)
{
int sum = 0; // סכום האיברים שלפני החוליה הנוכחית
while (n != null)
{
if (n.getValue() <= sum) // האיבר אינו גדול מסכום קודמיו
return false;
sum += n.getValue();
n = n.getNext();
}
return true;
}public static bool IsSuper(Node<int> n)
{
int sum = 0; // סכום האיברים שלפני החוליה הנוכחית
while (n != null)
{
if (n.GetValue() <= sum) // האיבר אינו גדול מסכום קודמיו
return false;
sum += n.GetValue();
n = n.GetNext();
}
return true;
}בדיקה על הדוגמה: 1 > 0, 3 > 1, 6 > 4, 13 > 10, 27 > 23, 300 > 50, 600 > 350 – כל הבדיקות עוברות ומוחזר true. לעומת זאת עבור 1, 3, 4 מתקבל 4 ≤ 4 ומוחזר false.
תשובה: הפעולה isSuper שלמעלה.
סעיף ב
מוצאים את החוליה prev האחרונה שערכה קטן מ-num (תוך צבירת הסכום sum עד prev). אם num ≤ sum – false. אחרת בודקים שכל איבר שאחרי prev גדול מסכום קודמיו כולל num; אם כן – מכניסים חוליה חדשה אחרי prev ומחזירים true, אחרת false בלי שינוי.
הרעיון: רשימה "סופר עולה" היא בפרט רשימה עולה ממש (כל איבר גדול מקודמו, כי הוא גדול מסכום כל קודמיו). לכן ל-num יש מקום אחד אפשרי בלבד: אחרי כל האיברים הקטנים ממנו ולפני הגדולים ממנו. נתון ש-num גדול מהאיבר הראשון, ולכן ההכנסה לעולם לא תהיה בראש השרשרת (וההפניה n לא משתנה).
בהכנסה במקום הזה צריך לבדוק שני תנאים:
•num עצמו גדול מסכום כל האיברים שלפניו.
•כל איבר שאחרי num עדיין גדול מסכום קודמיו – הסכום של כל אחד מהם גדל עכשיו ב-num.
האיברים שלפני num לא מושפעים מההכנסה. את כל הבדיקות עושים לפני שמשנים את השרשרת, כדי שבמקרה של false היא תישאר כמו שהייתה.
1. מתקדמים עם prev מהחוליה הראשונה כל עוד הערך בחוליה הבאה קטן מ-num, וצוברים ב-sum את סכום הערכים עד prev כולל.
2. אם num ≤ sum – מחזירים false.
3. מציבים s = sum + num ועוברים על החוליות שאחרי prev: אם ערך כלשהו ≤ s – מחזירים false; אחרת מוסיפים אותו ל-s. (אם num שווה לאיבר קיים, האיבר הזה ייכשל כאן, כי הוא לא גדול מ-s.)
4. אם כל הבדיקות עברו – יוצרים חוליה חדשה עם num, שה-next שלה הוא החוליה שאחרי prev, ומחברים אותה אחרי prev. מחזירים true.
public static boolean addToSuper(Node<Integer> n, int num)
{
// שלב 1: מחפשים את החוליה prev שאחריה num צריך להיכנס
Node<Integer> prev = n;
int sum = n.getValue(); // סכום האיברים עד prev כולל
while (prev.hasNext() && prev.getNext().getValue() < num)
{
prev = prev.getNext();
sum += prev.getValue();
}
// שלב 2: num חייב להיות גדול מסכום כל האיברים שלפניו
if (num <= sum)
return false;
// שלב 3: כל איבר שאחרי num חייב להישאר גדול מסכום קודמיו (כולל num)
int s = sum + num;
Node<Integer> p = prev.getNext();
while (p != null)
{
if (p.getValue() <= s)
return false;
s += p.getValue();
p = p.getNext();
}
// שלב 4: ההכנסה חוקית - מכניסים את num אחרי prev
prev.setNext(new Node<Integer>(num, prev.getNext()));
return true;
}public static bool AddToSuper(Node<int> n, int num)
{
// שלב 1: מחפשים את החוליה prev שאחריה num צריך להיכנס
Node<int> prev = n;
int sum = n.GetValue(); // סכום האיברים עד prev כולל
while (prev.HasNext() && prev.GetNext().GetValue() < num)
{
prev = prev.GetNext();
sum += prev.GetValue();
}
// שלב 2: num חייב להיות גדול מסכום כל האיברים שלפניו
if (num <= sum)
return false;
// שלב 3: כל איבר שאחרי num חייב להישאר גדול מסכום קודמיו (כולל num)
int s = sum + num;
Node<int> p = prev.GetNext();
while (p != null)
{
if (p.GetValue() <= s)
return false;
s += p.GetValue();
p = p.GetNext();
}
// שלב 4: ההכנסה חוקית - מכניסים את num אחרי prev
prev.SetNext(new Node<int>(num, prev.GetNext()));
return true;
}בדיקה על הדוגמאות (השרשרת 1, 3, 6, 13, 27, 300, 600):
התוצאות מתאימות לדוגמאות שבשאלה. למשל אחרי הוספת 60 השרשרת היא 1, 3, 6, 13, 27, 60, 300, 600.
תשובה: הפעולה addToSuper שלמעלה.
סעיף ג
שתיהן , כאשר n מספר החוליות בשרשרת.
נסמן ב-n את מספר החוליות בשרשרת.
1. isSuper: לולאה אחת שעוברת על כל חוליה לכל היותר פעם אחת, עם מספר קבוע של פעולות בכל חוליה – (במקרה הגרוע, כשהרשימה אכן "סופר עולה", עוברים על כולה).
2. addToSuper: הלולאה הראשונה עוברת על החוליות עד prev, והלולאה השנייה ממשיכה מהחוליה שאחרי prev עד הסוף – יחד כל חוליה נבדקת פעם אחת לכל היותר, כלומר . ההכנסה עצמה (יצירת חוליה ושינוי הפניה אחת) היא .
תשובה: הסיבוכיות של שתי הפעולות היא .
שאלה 6 · היררכיית עובדים במכללה: UML, בנאים וניהול צוות
במכללה מסוימת פותח פרויקט לניהול צוות העובדים. לכל עובד (Employee) במכללה יש שם ומספר עובד. מספר העובד הוא מספר ייחודי הניתן באופן אוטומטי עם הוספת עובד חדש למאגר העובדים כך העובד הראשון יקבל את המספר 1, העובד השני יקבל את המספר 2 וכך הלאה.
למתרגל (Tutor) יש את התכונות:
•num – מספר עובד, מטיפוס שלם, int.
•name – שם, מטיפוס מחרוזת, String.
•courseNum – מספר קורס, מטיפוס שלם, int.
למרצה (Lecturer) יש את התכונות:
•num – מספר עובד, מטיפוס שלם, int.
•name – שם, מטיפוס מחרוזת, String.
•specialization – התמחות (מתמטיקה, מדעי המחשב, אנגלית וכו'), מטיפוס מחרוזת, String.
לראש מחלקה (Head) – ראש מחלקה הוא מרצה שאחראי על צוות שמונה עד עשרים מרצים ומתרגלים, יש את התכונות הבאות:
•arr – מערך של אנשי הצוות הכפופים לראש הצוות.
•current – מספר אנשי הצוות בפועל, מטיפוס שלם, int.
סרטטו תרשים UML המתאר את הקשר בין המחלקות Employee, Tutor, Lecturer, Head באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.
לכל אחת מהמחלקות Employee, Tutor, Lecturer, Head כתבו:
•כותרת המחלקה.
•תכונות.
•פעולה בונה – הפעולה הבונה של כל מחלקה מקבלת את כל הפרמטרים הנדרשים.
המחלקה TeachingStaff מיועדת לנהל את כל העובדים במכללה. תכונות המחלקה:
•arr – מערך של כל אנשי הצוות. במכללה יכולים לעבוד לא יותר מ- 200 אנשי צוות.
•current – מספר אנשי הצוות בפועל, מטיפוס שלם, int.
כתבו את כותרת המחלקה ואת התכונות של המחלקה TeachingStaff והוסיפו את הפעולות הפנימיות הבאות:
1. פעולה בשם numHeads המחזירה את מספר הצוותים.
2. פעולה בשם getNewTutor המקבלת את מספר הקורס ומחזירה את המתרגל המלמד בקורס שהצטרף אחרון למאגר העובדים (מספר העובד שלו מקסימלי). אם אין מתרגל בקורס הנדרש, הפעולה תחזיר null.
הערה: הניחו שהפעולות get ו- set מוגדרות בעבור כל תכונה בכל אחת מהמחלקות.
◂ פתרון מלא לשאלה 6
סעיף א
Employee מחלקה מופשטת (num, name, מונה סטטי); Tutor ו-Lecturer יורשות מ-Employee; Head יורשת מ-Lecturer ומכילה מערך של Employee (8 עד 20 אנשי צוות) ואת current.
1. התכונות num ו-name משותפות למתרגל ולמרצה, ולכן מעבירים אותן למחלקת בסיס Employee – כך לא משכפלים קוד. כל עובד במכללה הוא מתרגל או מרצה, ולכן Employee מופשטת (abstract): לא יוצרים ממנה עצמים ישירות.
2. כדי שמספר העובד יינתן אוטומטית, ב-Employee יש תכונה סטטית counter – משותפת לכל העצמים – שהבנאי מגדיל ומעתיק ל-num.
3. Tutor יורשת מ-Employee ומוסיפה courseNum. Lecturer יורשת מ-Employee ומוסיפה specialization.
4. "ראש מחלקה הוא מרצה" – יחס "הוא" (is-a), ולכן Head יורשת מ-Lecturer (ויש לו גם התמחות).
5. לראש המחלקה יש צוות – יחס "יש לו" (has-a): Head מכילה מערך arr מטיפוס Employee[] (המערך יכול להחזיק גם מרצים וגם מתרגלים) בגודל 20, ו-current. בתרשים זה קשר הכלה (אגרגציה) מ-Head אל Employee עם ריבוי 8..20.
סימונים: `-` פרטי (private), `#` מוגן (protected), `+` ציבורי (public); החץ עם ראש משולש (^) – ירושה; `<>` – הכלה.
+-----------------------------+
| Employee {abstract} |
|-----------------------------|
| - counter : int {static} |
| # num : int |
| # name : String |
|-----------------------------|
| + Employee(name) |
+-----------------------------+
^ ^
| (ירושה) | (ירושה)
+---------------------------+ +-------------------------------+
| Tutor | | Lecturer |
|---------------------------| |-------------------------------|
| - courseNum : int | | - specialization : String |
|---------------------------| |-------------------------------|
| + Tutor(name, courseNum) | | + Lecturer(name, spec.) |
+---------------------------+ +-------------------------------+
^
| (ירושה)
+-------------------------------+
| Head |
|-------------------------------|
| - arr : Employee[] |<>------> Employee
| - current : int | 8..20
|-------------------------------|
| + Head(name, spec.) |
+-------------------------------+תשובה: Employee (מופשטת) ← Tutor, Lecturer; Lecturer ← Head; Head מכילה מערך של Employee (8 עד 20).
סעיף ב
Employee: מונה סטטי counter, num, name; הבנאי מקבל name, מגדיל את counter ומציב num = counter. Tutor(name, courseNum), Lecturer(name, specialization) קוראות לבנאי של Employee; Head(name, specialization) קוראת לבנאי של Lecturer ויוצרת מערך Employee[20] עם current = 0.
1. מספר עובד אוטומטי: ב-Employee מגדירים `private static int counter = 0`. תכונה סטטית שייכת למחלקה ולא לעצם, ולכן כל העצמים חולקים אותה. בכל יצירת עובד (מכל סוג – כי כל בנאי של מחלקה יורשת קורא בסוף לבנאי של Employee) הבנאי מגדיל את counter ומציב אותו ב-num: העובד הראשון יקבל 1, השני 2 וכן הלאה. num לא מועבר כפרמטר.
2. שרשור בנאים: כל מחלקה יורשת מאתחלת רק את מה שהיא מוסיפה, ואת השאר מעבירה לבנאי של מחלקת הבסיס (super ב-Java, base ב-C#).
3. Head: הבנאי מקבל את מה שדרוש למרצה (שם והתמחות), יוצר מערך ריק בגודל 20 (המקסימום בצוות) ומאפס את current; אנשי הצוות יתווספו אחר כך.
4. התכונות num ו-name מוגדרות protected כדי שמחלקות יורשות יוכלו לגשת אליהן; שאר התכונות private.
public abstract class Employee
{
private static int counter = 0; // כמה עובדים נוצרו עד עכשיו
protected int num; // מספר עובד - נקבע אוטומטית
protected String name;
public Employee(String name)
{
counter++;
this.num = counter;
this.name = name;
}
}
public class Tutor extends Employee
{
private int courseNum;
public Tutor(String name, int courseNum)
{
super(name);
this.courseNum = courseNum;
}
}
public class Lecturer extends Employee
{
private String specialization;
public Lecturer(String name, String specialization)
{
super(name);
this.specialization = specialization;
}
}
public class Head extends Lecturer
{
private Employee[] arr; // אנשי הצוות הכפופים לראש המחלקה
private int current; // מספר אנשי הצוות בפועל
public Head(String name, String specialization)
{
super(name, specialization);
this.arr = new Employee[20]; // לכל היותר עשרים אנשי צוות
this.current = 0;
}
}public abstract class Employee
{
private static int counter = 0; // כמה עובדים נוצרו עד עכשיו
protected int num; // מספר עובד - נקבע אוטומטית
protected string name;
public Employee(string name)
{
counter++;
this.num = counter;
this.name = name;
}
}
public class Tutor : Employee
{
private int courseNum;
public Tutor(string name, int courseNum) : base(name)
{
this.courseNum = courseNum;
}
}
public class Lecturer : Employee
{
private string specialization;
public Lecturer(string name, string specialization) : base(name)
{
this.specialization = specialization;
}
}
public class Head : Lecturer
{
private Employee[] arr; // אנשי הצוות הכפופים לראש המחלקה
private int current; // מספר אנשי הצוות בפועל
public Head(string name, string specialization) : base(name, specialization)
{
this.arr = new Employee[20]; // לכל היותר עשרים אנשי צוות
this.current = 0;
}
}תשובה: המחלקות שלמעלה.
סעיף ג
TeachingStaff: Employee[] arr בגודל 200 ו-current. numHeads סופרת את האיברים ב-arr[0..current-1] שהם Head. getNewTutor עוברת על המערך, בוחרת מבין העצמים שהם Tutor עם courseNum המבוקש את בעל מספר העובד הגדול ביותר, ומחזירה אותו או null.
1. תכונות: מערך arr מטיפוס Employee[] בגודל 200 – טיפוס הבסיס מאפשר לשמור בו מתרגלים, מרצים וראשי מחלקות. current מציין כמה תאים בשימוש (התאים 0 עד current-1).
2. numHeads: לכל צוות יש ראש מחלקה אחד, ולכן מספר הצוותים הוא מספר העצמים מטיפוס Head במערך. עוברים על התאים התפוסים ובודקים כל עצם עם instanceof (ב-C#: is) – מונים את אלה שהם Head.
3. getNewTutor(courseNum): "הצטרף אחרון" = מספר העובד הגדול ביותר. זה חיפוש מקסימום עם תנאי:
•result = null (עוד לא נמצא מתרגל מתאים).
•לכל עצם שהוא Tutor ממירים אותו ל-Tutor (המרה כלפי מטה, כדי לגשת ל-getCourseNum), ואם הקורס שלו הוא המבוקש ו-result עדיין null או שמספר העובד שלו גדול משל result – מעדכנים את result.
•בסוף מחזירים את result; אם אף מתרגל לא לימד בקורס, הוא נשאר null, כנדרש.
(בודקים לפי מספר העובד ולא לפי המיקום במערך, כדי שהתשובה תהיה נכונה גם אם הסדר במערך אינו סדר ההצטרפות.)
public class TeachingStaff
{
private Employee[] arr; // כל אנשי הצוות במכללה
private int current; // מספר אנשי הצוות בפועל
public TeachingStaff()
{
this.arr = new Employee[200];
this.current = 0;
}
// 1. מספר הצוותים = מספר ראשי המחלקות
public int numHeads()
{
int count = 0;
for (int i = 0; i < current; i++)
if (arr[i] instanceof Head)
count++;
return count;
}
// 2. המתרגל בקורס courseNum עם מספר העובד הגדול ביותר
public Tutor getNewTutor(int courseNum)
{
Tutor result = null;
for (int i = 0; i < current; i++)
{
if (arr[i] instanceof Tutor)
{
Tutor t = (Tutor) arr[i];
if (t.getCourseNum() == courseNum &&
(result == null || t.getNum() > result.getNum()))
result = t;
}
}
return result;
}
}public class TeachingStaff
{
private Employee[] arr; // כל אנשי הצוות במכללה
private int current; // מספר אנשי הצוות בפועל
public TeachingStaff()
{
this.arr = new Employee[200];
this.current = 0;
}
// 1. מספר הצוותים = מספר ראשי המחלקות
public int NumHeads()
{
int count = 0;
for (int i = 0; i < current; i++)
if (arr[i] is Head)
count++;
return count;
}
// 2. המתרגל בקורס courseNum עם מספר העובד הגדול ביותר
public Tutor GetNewTutor(int courseNum)
{
Tutor result = null;
for (int i = 0; i < current; i++)
{
if (arr[i] is Tutor)
{
Tutor t = (Tutor) arr[i];
if (t.GetCourseNum() == courseNum &&
(result == null || t.GetNum() > result.GetNum()))
result = t;
}
}
return result;
}
}סיבוכיות: כל פעולה עוברת פעם אחת על current התאים – .
תשובה: המחלקה TeachingStaff שלמעלה עם הפעולות numHeads ו-getNewTutor.
שאלה 7 · מעקב אחרי חיפוש מסלול בעץ בינרי עם מחסנית
לפניכם הפעולות הבאות:
public static void what(Stack<Integer> s)
{
if (!s.isEmpty())
{
System.out.print(s.pop()+" ");
what(s);
}
}
public static void doWhat(BinNode<Integer> t, int data)
{
Stack<Integer>s = new Stack<Integer>();
doWhat(t, s, data);
}
private static void doWhat(BinNode<Integer> t, Stack<Integer> s,
int val)
{
if (t!=null)
{
int x = t.getValue();
s.push(x);
if(x == val)
{
what(s);
}
else
{
doWhat(t.getLeft(), s, val);
if (!s.isEmpty())
doWhat(t.getRight(), s, val);
if (!s.isEmpty())
s.pop();
}
}
}public static void What(Stack<int> s)
{
if (!s.IsEmpty())
{
Console.Write(s.Pop()+" ");
What(s);
}
}
public static void DoWhat(BinNode<int> t, int data)
{
Stack<int>s = new Stack<int>();
DoWhat(t, s, data);
}
private static void DoWhat(BinNode<int> t, Stack<int> s,
int val)
{
if (t!=null)
{
int x = t.GetValue();
s.Push(x);
if(x == val)
{
What(s);
}
else
{
DoWhat(t.GetLeft(), s, val);
if (!s.IsEmpty())
DoWhat(t.GetRight(), s, val);
if (!s.IsEmpty())
s.Pop();
}
}
}
מה מבצעת הפעולה what(Stack<Integer> s) עבור מחסנית של מספרים שלמים s?
עקבו אחרי זימון הפעולה doWhat(bt,3) עבור עץ bt שבאיור וכתבו מה יהיה הפלט של הזימון.
עקבו אחרי זימון הפעולה doWhat(bt,5) עבור עץ bt שבאיור וכתבו מה יהיה הפלט של הזימון.
מה יהיה פלט של זימון הפעולה doWhat(bt,10) עבור עץ bt שבאיור?
מה מבצעת הפעולה doWhat(t, val) עבור עץ בינרי t ומספר שלם val באופן כללי?
◂ פתרון מלא לשאלה 7
סעיף א
מדפיסה את איברי המחסנית מהראש לתחתית (עם רווח אחרי כל איבר) ומרוקנת אותה.
הפעולה רקורסיבית: אם המחסנית לא ריקה, היא מוציאה את האיבר העליון (pop), מדפיסה אותו ואחריו רווח, וקוראת לעצמה עם המחסנית שנשארה. תנאי העצירה – מחסנית ריקה.
לכן האיברים מודפסים לפי סדר ההוצאה – מראש המחסנית ועד התחתית – ובסוף המחסנית ריקה (התוכן נהרס, לא משוחזר).
תשובה: what מדפיסה את כל איברי s מהראש עד התחתית ומרוקנת את המחסנית.
סעיף ב
3 2 1
doWhat(bt, 3) יוצרת מחסנית ריקה וקוראת לפעולת העזר. בכל צומת: דוחפים את הערך; אם הוא 3 – מדפיסים ומרוקנים את המחסנית; אחרת יורדים שמאלה, ואם המחסנית לא התרוקנה – ימינה, ואם עדיין לא התרוקנה – מוציאים את הצומת.
המחסנית רשומה כשהראש משמאל.
תשובה: יודפס `3 2 1`.
סעיף ג
5 4 2 1
מעקב באותו אופן (ראש המחסנית משמאל):
הצומת 3 נכנס למחסנית ויצא ממנה (הוא לא על המסלול ל-5), ולכן לא מודפס.
תשובה: יודפס `5 4 2 1`.
סעיף ד
לא יודפס דבר.
הערך 10 לא נמצא בעץ, ולכן התנאי x == val לא מתקיים אף פעם ו-what לא נקראת. הסריקה עוברת על כל הצמתים בסדר תחילי (1, 2, 3, 4, 5, 6, 7): כל צומת נדחף כשנכנסים אליו ומוצא כשמסיימים את שני תת-העצים שלו. המחסנית אף פעם לא מתרוקנת באמצע (תמיד נשארים בה לפחות אבות הצומת הנוכחי), ובסוף, אחרי ה-pop של 1, היא ריקה.
תשובה: אין פלט (לא יודפס כלום).
סעיף ה
מחפשת את val בעץ (בסדר תחילי) ומדפיסה את המסלול מהצומת הראשון שערכו val עד השורש (val, ההורה שלו, ... השורש). אם val לא בעץ – אין פלט.
המחסנית מחזיקה בכל רגע את המסלול מהשורש לצומת הנוכחי: צומת נדחף כשנכנסים אליו ומוצא כשיוצאים ממנו בלי למצוא את val. כשנמצא צומת עם הערך val, המחסנית מכילה בדיוק את המסלול מהשורש אליו, ו-what מדפיסה אותו מהראש – כלומר מ-val כלפי מעלה עד השורש – ומרוקנת אותה. מחסנית ריקה עוצרת את המשך החיפוש (אין ירידה ימינה ואין pop), ולכן מודפס רק המסלול של המופע הראשון של val בסדר תחילי (שורש, שמאל, ימין).
תשובה: הפעולה מדפיסה את המסלול מהצומת הראשון (בסריקה תחילית) שערכו val ועד שורש העץ – val, אביו, סבו, ... השורש. אם val לא נמצא בעץ – לא מודפס דבר.
שאלה 8 · מעקב אחרי ירושה, דריסה, super והמרות
נתונות שלוש המחלקות הבאות:
public class A
{
public A()
{
System.out.println("A");
}
public void one()
{
System.out.println("one of A");
}
public void two()
{
System.out.println("two of A");
this.one();
}
public void four()
{
System.out.println ("four of A");
this.two();
}
} //end of class A
public class B extends A
{
public B()
{
System.out.println("B");
}
public void one()
{
System.out.println("one of B");
}
public void two()
{
System.out.println("two of B");
}
public void three()
{
System.out.println("three of B");
super.two();
}
} //end of class B
public class C extends B
{
public void four()
{
System.out.println ("four of C");
}
} //end of class Cpublic class A
{
public A()
{
Console.WriteLine("A");
}
public virtual void One()
{
Console.WriteLine("One of A");
}
public virtual void Two()
{
Console.WriteLine("Two of A");
this.One();
}
public virtual void Four()
{
Console.WriteLine ("Four of A");
this.Two();
}
} //end of class A
public class B : A
{
public B()
{
Console.WriteLine("B");
}
public override void One()
{
Console.WriteLine("One of B");
}
public override void Two()
{
Console.WriteLine("Two of B");
}
public void Three()
{
Console.WriteLine("Three of B");
base.Two();
}
} //end of class B
public class C : B
{
public override void Four()
{
Console.WriteLine ("Four of C");
}
} //end of class Cכמו כן נתונה המחלקה Test הבאה באותו פרויקט:
public class Test
{
public static void main (String [] args)
{
// כאן יופיעו הפקודות שבסעיפים להלן
}
}public class Test
{
public static void Main(string [] args)
{
// כאן יופיעו הפקודות שבסעיפים להלן
}
}בכל סעיף עליכם לכתוב מה יקרה בשל הרצת קטע הקוד. אם תהיה שגיאת קומפילציה או הרצה, כתבו איזו שגיאה ונמקו. אם הקוד תקין, כתבו מה יודפס בפלט.
A a1 = new A();
((B) a1).two();A a1 = new A();
((B) a1).Two();B b1 = new B();
((A) b1).three();B b1 = new B();
((A) b1).Three();A a2 = new A();
a2.one();
((A) a2).two();A a2 = new A();
a2.One();
((A) a2).Two();A a3 = new B();
a3.two();
((B) a3).two();
((B) a3).three();A a3 = new B();
a3.Two();
((B) a3).Two();
((B) a3).Three();B b2 = new B();
b2.two();
((A) b2).two();B b2 = new B();
b2.Two();
((A) b2).Two();B b3 = new C();
b3.four();
((B)new C()).four();B b3 = new C();
b3.Four();
((B)new C()).Four();◂ פתרון מלא לשאלה 8
סעיף א
יודפס A ואז שגיאת זמן ריצה (ClassCastException ב-Java, InvalidCastException ב-C#).
1. `new A()` מפעיל את הבנאי של A – מודפס `A`.
2. `((B) a1)` – ההמרה עוברת הידור, כי B יורשת מ-A ומשתנה מטיפוס A יכול להפנות לעצם B. אבל בזמן ריצה העצם הוא A ולא B, ולכן ההמרה נכשלת: שגיאת זמן ריצה ClassCastException (ב-C#: InvalidCastException). two לא מופעלת.
Aואחריו שגיאת זמן ריצה.
תשובה: מודפס A ואחר כך שגיאת זמן ריצה – אי אפשר להמיר עצם A ל-B.
סעיף ב
שגיאת הידור: במחלקה A אין פעולה three, ולכן אי אפשר לקרוא לה דרך הפניה מטיפוס A.
המהדר בודק אילו פעולות מותר לזמן לפי הטיפוס המוצהר של הביטוי. הביטוי `((A) b1)` הוא מטיפוס A, ובמחלקה A אין פעולה three (היא מוגדרת רק ב-B). לכן זו שגיאת הידור (cannot find symbol; ב-C#: 'A' does not contain a definition for 'Three'), והתוכנית לא רצה כלל – לא יודפס דבר, גם לא A ו-B של הבנאים.
תשובה: שגיאת הידור – לא ניתן לזמן את three על הפניה מטיפוס A.
סעיף ג
A / one of A / two of A / one of A
1. `new A()` – מודפס `A`.
2. `a2.one()` – העצם הוא A – מודפס `one of A`.
3. `((A) a2).two()` – ההמרה ל-A לא משנה דבר. two של A מדפיסה `two of A` וקוראת ל-`this.one()`; this הוא עצם A, ולכן מודפס `one of A`.
A
one of A
two of A
one of AA
One of A
Two of A
One of Aתשובה: A, one of A, two of A, one of A.
סעיף ד
A / B / two of B / two of B / three of B / two of A / one of B
1. `new B()` – הבנאי של B קורא קודם (במובלע) לבנאי של A: מודפס `A` ואחריו `B`.
2. `a3.two()` – הטיפוס המוצהר A (יש בו two – ההידור תקין), והעצם בפועל B. הפעולה נדרסה ב-B, ולכן מופעלת two של B: `two of B`.
3. `((B) a3).two()` – ההמרה תקינה (העצם הוא B) – שוב `two of B`.
4. `((B) a3).three()` – three של B מדפיסה `three of B` וקוראת ל-`super.two()` (ב-C#: base.Two()) – זו קריאה ישירה ל-two של A, בלי פולימורפיזם: מודפס `two of A`. בתוכה `this.one()` – this הוא עצם B ו-one נדרסה ב-B, ולכן מודפס `one of B`.
A
B
two of B
two of B
three of B
two of A
one of BA
B
Two of B
Two of B
Three of B
Two of A
One of Bתשובה: A, B, two of B, two of B, three of B, two of A, one of B.
סעיף ה
A / B / two of B / two of B
1. `new B()` – מודפס `A` ואחריו `B`.
2. `b2.two()` – two של B: `two of B`.
3. `((A) b2).two()` – ההמרה ל-A משנה רק את הטיפוס המוצהר; הפעולה שמופעלת נקבעת לפי העצם בפועל (B), ולכן שוב two של B: `two of B`.
A
B
two of B
two of BA
B
Two of B
Two of Bתשובה: A, B, two of B, two of B.
סעיף ו
A / B / four of C / A / B / four of C
1. `new C()` – ל-C אין בנאי מפורש, ולכן יש לה בנאי ברירת מחדל שקורא לבנאי של B, שקורא לבנאי של A: מודפס `A` ואחריו `B`.
2. `b3.four()` – לטיפוס המוצהר B יש four (בירושה מ-A) – ההידור תקין. העצם הוא C, ו-four נדרסה ב-C: `four of C`.
3. `((B)new C()).four()` – נוצר עצם C חדש – שוב `A` ו-`B` – ההמרה ל-B תקינה, ומופעלת four של C: `four of C`.
A
B
four of C
A
B
four of CA
B
Four of C
A
B
Four of Cתשובה: A, B, four of C, A, B, four of C.
שאלה 9 · מעקב אחרי פעולה רקורסיבית על שתי מחסניות
נתונה הפעולה הרקורסיבית הבאה:
public static int secret(Stack<Integer> s1, Stack<Integer> s2)
{
if(s1.isEmpty() || s2.isEmpty())
return 0;
if(s1.top() > s2.top())
return s1.pop() + s2.top() + secret(s1, s2);
else
return s1.top() + s2.pop() + secret(s1, s2);
}public static int Secret(Stack<int> s1, Stack<int> s2)
{
if(s1.IsEmpty() || s2.IsEmpty())
return 0;
if(s1.Top() > s2.Top())
return s1.Pop() + s2.Top() + Secret(s1, s2);
else
return s1.Top() + s2.Pop() + Secret(s1, s2);
}
נתונות שתי המחסניות הבאות:
עקבו אחרי זימון הפעולה secret(st1, st2) וכתבו מה תחזיר הפעולה.
נתונה הטענה הבאה:
secret(s1, s2) == secret(s2, s1)האם הטענה נכונה לכל זוג מחסניות של מספרים שלמים s1 ו- s2? נמקו את תשובתכם.

נתונות שתי המחסניות הבאות:
האם קיים ערך X כזה שתוצאת זימון הפעולה secret(s1, s2) תהיה 19?
◂ פתרון מלא לשאלה 9
סעיף א
33 (בסוף s1 מכילה , 1 ו-s2 ריקה).
איך הפעולה עובדת: בכל קריאה משווים את שני הראשים. מוסיפים לתוצאה את שני הראשים, ומוציאים את הראש של המחסנית שראשה גדול יותר (ב-s1 – רק אם גדול ממש; בשוויון מוציאים מ-s2). מסתיימים כשאחת המחסניות מתרוקנת. (הזימון רשום בשאלה כ-secret(st1, st2); הכוונה למחסניות s1 ו-s2 שבאיור.)
המחסניות רשומות כשהראש משמאל: s1 = 7, 6, , 1 ו-s2 = 5, 2, 4, 3.
הערך המוחזר הוא סכום הערכים שהתווספו בכל הקריאות:
בסוף הזימון ב-s1 נשארו (בראש) ו-1, ו-s2 ריקה.
תשובה: הפעולה תחזיר 33.
סעיף ב
לא. כשהראשים שווים, secret(s1, s2) מוציאה מ-s2 ו-secret(s2, s1) מוציאה מ-s1. דוגמה: s1 = 5, s2 = 5, 1 (5 בראש): secret(s1, s2) = 16, secret(s2, s1) = 10.
ניתוח: כשהראשים שונים, שתי הקריאות מתנהגות אותו דבר: בשתיהן מוציאים את הראש הגדול מבין השניים ומוסיפים לתוצאה את סכום שני הראשים (החיבור חילופי). ההבדל מופיע רק כשהראשים שווים: אז התנאי `s1.top() > s2.top()` לא מתקיים ונבחר ה-else, שמוציא תמיד מהמחסנית שהועברה כפרמטר השני. ב-secret(s1, s2) יוצא איבר מ-s2, וב-secret(s2, s1) יוצא איבר מ-s1. מכאן ההמשך שונה, והתוצאה יכולה להיות שונה.
דוגמה נגדית (בכל זימון מתחילים מאותן מחסניות; הראש משמאל): s1 = 5 ו-s2 = 5, 1.
secret(s1, s2):
1. ראשים 5 ו-5 – שווים, else: , מוציאים מ-s2. עכשיו s1 = 5, s2 = 1.
2. 5 > 1 – מוציאים מ-s1: . s1 ריקה.
3. מוחזר 0.
סך הכול .
secret(s2, s1) (עכשיו הפרמטר הראשון הוא 5, 1 והשני הוא 5):
1. ראשים 5 ו-5 – שווים, else: , מוציאים מהפרמטר השני (המחסנית 5), והיא מתרוקנת.
2. מוחזר 0.
סך הכול .
, ולכן הטענה לא נכונה לכל זוג מחסניות.
תשובה: הטענה לא נכונה. דוגמה: s1 = 5, s2 = 5, 1 (5 בראש) – secret(s1, s2) = 16 אבל secret(s2, s1) = 10.
סעיף ג
כן – יש שני ערכים: X = 1 או X = 7.
המחסניות (הראש משמאל): s1 = 4, X, ו-s2 = 1, 2, 3, 4.
הקריאה הראשונה: 4 > 1 – מוציאים 4 מ-s1, ומתווסף . עכשיו s1 = X, ו-s2 = 1, 2, 3, 4. ההמשך תלוי בהשוואה בין X לבין 1.
1. X > 1 – מוציאים את X מ-s1, ומתווסף . s1 = .
2. קטן מכל איברי s2, ולכן מוציאים את כולם אחד-אחד, ומתווספים , , , . s2 מתרוקנת ומוחזר 0.
סך הכול: .
, ואכן – הערך מתאים למקרה.
X אינו גדול מאף איבר של s2 (שכולם לפחות 1), ולכן X נשאר בראש s1 ומוציאים את כל איברי s2. מתווספים , , , , ואז s2 ריקה ומוחזר 0.
סך הכול: .
, ואכן – הערך מתאים למקרה.
•עבור X = 1: .
•עבור X = 7: .
תשובה: כן. קיימים שני ערכים מתאימים: X = 1 ו-X = 7.
שאלה 10 · מחלקת קבוצת מספרים דרך ממשק בלבד
קבוצת מספרים – SetOfNumbers – היא אוסף של מספרים, כאשר כל מספר יכול להופיע בקבוצה פעם אחת בלבד. אין חשיבות לסדר המספרים בקבוצה.
לפניכם ממשק חלקי של המחלקה SetOfNumbers המייצגת קבוצת מספרים שלמים.
כתבו במחלקה SetOfNumbers פעולה פנימית המחזירה את המספר הקטן בקבוצה.
הנחה: הקבוצה לא ריקה.
כותרת הפעולה:
public int getMin()public int GetMin()כתבו במחלקה SetOfNumbers פעולה פנימית המקבלת קבוצה אחרת. הפעולה תחזיר true, אם שתי קבוצות זהות, אם לא – הפעולה תחזיר false.
כותרת הפעולה:
public boolean equals(SetOfNumbers other)public bool Equals(SetOfNumbers other)כתבו פעולה חיצונית שמקבלת קבוצה של מספרים שלמים sn ומחזירה קבוצה חדשה שתכיל רק את המספרים הדו-ספרתיים שנמצאים ב-sn. יש לשמור על המספרים שנמצאים בקבוצה sn
כותרת הפעולה:
public static SetOfNumbers make(SetOfNumbers sn)public static SetOfNumbers Make(SetOfNumbers sn)◂ פתרון מלא לשאלה 10
סעיף א
מוציאים שוב ושוב את המקסימום מהקבוצה לקבוצת עזר עד שהיא מתרוקנת – האיבר האחרון שהוצא הוא המינימום; אחר כך מחזירים את כל האיברים מקבוצת העזר ומחזירים את המינימום.
הרעיון: בממשק יש רק getMax, ואין דרך "לעבור" על האיברים. אבל אם מוציאים כל פעם את הגדול ביותר, האיברים יוצאים בסדר יורד, והאיבר האחרון שיוצא לפני שהקבוצה מתרוקנת הוא הקטן ביותר. כדי לא להרוס את הקבוצה, כל איבר שמוציאים נשמר בקבוצת עזר, ובסוף מחזירים את כולם.
1. יוצרים קבוצת עזר temp ריקה.
2. כל עוד this לא ריקה: min = getMax(), מוחקים את min מ-this ומוסיפים אותו ל-temp.
3. בסוף הלולאה min מכיל את האיבר האחרון שהוצא – המינימום.
4. מעבירים את כל האיברים מ-temp חזרה ל-this (שוב בעזרת getMax ו-removeFromSet).
5. מחזירים את min.
public int getMin()
{
SetOfNumbers temp = new SetOfNumbers();
int min = 0;
while (!this.isEmpty()) // מוציאים כל פעם את הגדול ביותר
{
min = this.getMax();
this.removeFromSet(min);
temp.addToSet(min);
}
// האיבר האחרון שהוצא הוא הקטן ביותר
while (!temp.isEmpty()) // משחזרים את הקבוצה
{
int x = temp.getMax();
temp.removeFromSet(x);
this.addToSet(x);
}
return min;
}public int GetMin()
{
SetOfNumbers temp = new SetOfNumbers();
int min = 0;
while (!this.IsEmpty()) // מוציאים כל פעם את הגדול ביותר
{
min = this.GetMax();
this.RemoveFromSet(min);
temp.AddToSet(min);
}
// האיבר האחרון שהוצא הוא הקטן ביותר
while (!temp.IsEmpty()) // משחזרים את הקבוצה
{
int x = temp.GetMax();
temp.RemoveFromSet(x);
this.AddToSet(x);
}
return min;
}דוגמה: בקבוצה {9, , 40} יוצאים בסדר 40, 9, , ולכן מוחזר , והקבוצה משוחזרת.
סיבוכיות: מספר הקריאות לפעולות הממשק הוא (כל איבר יוצא ונכנס פעמיים), כאשר n גודל הקבוצה; זמן הריצה בפועל תלוי במימוש הלא ידוע של הפעולות.
תשובה: הפעולה getMin שלמעלה.
סעיף ב
מוציאים בו-זמנית את המקסימום משתי הקבוצות ומשווים; הבדל במקסימום או קבוצה אחת שמתרוקנת לפני השנייה – false. כל איבר שהוצא נשמר בקבוצת עזר, ובסוף משחזרים את שתי הקבוצות ומחזירים את התוצאה.
הרעיון: שתי קבוצות זהות אם ורק אם, כשמוציאים מהן את האיברים בסדר יורד (בעזרת getMax), מתקבלת אותה סדרה בדיוק. לכן מוציאים מהן "במקביל":
1. יוצרים שתי קבוצות עזר temp1 (לאיברים של this) ו-temp2 (לאיברים של other), ומשתנה same = true.
2. כל עוד same, ושתי הקבוצות לא ריקות: משווים את getMax של שתיהן. אם המקסימומים שונים – same = false (יש איבר שנמצא באחת ולא בשנייה). אם שווים – מוחקים את המקסימום משתי הקבוצות ושומרים אותו בקבוצות העזר.
3. אחרי הלולאה, אם נשארו איברים באחת הקבוצות (גם כשהשנייה כבר ריקה) – הקבוצות בגודל שונה, same = false.
4. משחזרים את שתי הקבוצות מקבוצות העזר – הפעולה לא אמורה לשנות את this ולא את other.
5. מחזירים את same.
public boolean equals(SetOfNumbers other)
{
SetOfNumbers temp1 = new SetOfNumbers(); // מה שהוצא מ-this
SetOfNumbers temp2 = new SetOfNumbers(); // מה שהוצא מ-other
boolean same = true;
while (same && !this.isEmpty() && !other.isEmpty())
{
int m1 = this.getMax();
int m2 = other.getMax();
if (m1 != m2)
same = false;
else
{
this.removeFromSet(m1);
temp1.addToSet(m1);
other.removeFromSet(m2);
temp2.addToSet(m2);
}
}
if (!this.isEmpty() || !other.isEmpty()) // נשארו איברים באחת הקבוצות
same = false;
while (!temp1.isEmpty()) // משחזרים את this
{
int x = temp1.getMax();
temp1.removeFromSet(x);
this.addToSet(x);
}
while (!temp2.isEmpty()) // משחזרים את other
{
int x = temp2.getMax();
temp2.removeFromSet(x);
other.addToSet(x);
}
return same;
}public bool Equals(SetOfNumbers other)
{
SetOfNumbers temp1 = new SetOfNumbers(); // מה שהוצא מ-this
SetOfNumbers temp2 = new SetOfNumbers(); // מה שהוצא מ-other
bool same = true;
while (same && !this.IsEmpty() && !other.IsEmpty())
{
int m1 = this.GetMax();
int m2 = other.GetMax();
if (m1 != m2)
same = false;
else
{
this.RemoveFromSet(m1);
temp1.AddToSet(m1);
other.RemoveFromSet(m2);
temp2.AddToSet(m2);
}
}
if (!this.IsEmpty() || !other.IsEmpty()) // נשארו איברים באחת הקבוצות
same = false;
while (!temp1.IsEmpty()) // משחזרים את this
{
int x = temp1.GetMax();
temp1.RemoveFromSet(x);
this.AddToSet(x);
}
while (!temp2.IsEmpty()) // משחזרים את other
{
int x = temp2.GetMax();
temp2.RemoveFromSet(x);
other.AddToSet(x);
}
return same;
}דוגמאות: {1, 5, 9} ו-{9, 5, 1}: המקסימומים 9=9, 5=5, 1=1 ושתיהן מתרוקנות יחד – true. {1, 5, 9} ו-{5, 9}: 9=9, 5=5, ואז השנייה ריקה והראשונה לא – false. {1, 5, 9} ו-{1, 4, 9}: 9=9 ואז 5≠4 – false.
תשובה: הפעולה equals שלמעלה.
סעיף ג
מוציאים את כל איברי sn (בעזרת getMax) לקבוצת עזר; כל איבר שערכו המוחלט בין 10 ל-99 מוסיפים גם לקבוצה החדשה; בסוף מחזירים את האיברים מקבוצת העזר ל-sn ומחזירים את הקבוצה החדשה.
הרעיון: שוב עוברים על איברי sn בעזרת הוצאת המקסימום, ושומרים כל איבר בקבוצת עזר כדי לשחזר את sn בסוף ("יש לשמור על המספרים שנמצאים בקבוצה sn").
1. יוצרים קבוצה חדשה result וקבוצת עזר temp.
2. כל עוד sn לא ריקה: x = sn.getMax(), מוחקים את x מ-sn ומוסיפים ל-temp.
3. מספר שלם הוא דו-ספרתי אם הערך המוחלט שלו בין 10 ל-99 (כך נכללים גם מספרים שליליים כמו ). אם כן – מוסיפים את x ל-result.
4. מחזירים את כל האיברים מ-temp ל-sn.
5. מחזירים את result.
public static SetOfNumbers make(SetOfNumbers sn)
{
SetOfNumbers result = new SetOfNumbers(); // הקבוצה החדשה
SetOfNumbers temp = new SetOfNumbers(); // לשחזור sn
while (!sn.isEmpty())
{
int x = sn.getMax();
sn.removeFromSet(x);
temp.addToSet(x);
int a = Math.abs(x);
if (a >= 10 && a <= 99) // מספר דו-ספרתי
result.addToSet(x);
}
while (!temp.isEmpty()) // מחזירים את המספרים ל-sn
{
int x = temp.getMax();
temp.removeFromSet(x);
sn.addToSet(x);
}
return result;
}public static SetOfNumbers Make(SetOfNumbers sn)
{
SetOfNumbers result = new SetOfNumbers(); // הקבוצה החדשה
SetOfNumbers temp = new SetOfNumbers(); // לשחזור sn
while (!sn.IsEmpty())
{
int x = sn.GetMax();
sn.RemoveFromSet(x);
temp.AddToSet(x);
int a = Math.Abs(x);
if (a >= 10 && a <= 99) // מספר דו-ספרתי
result.AddToSet(x);
}
while (!temp.IsEmpty()) // מחזירים את המספרים ל-sn
{
int x = temp.GetMax();
temp.RemoveFromSet(x);
sn.AddToSet(x);
}
return result;
}דוגמה: עבור sn = {5, , 40, 99, 100, 10, 9} תוחזר הקבוצה {, 10, 40, 99}, ו-sn נשארת כפי שהייתה.
תשובה: הפעולה make שלמעלה.