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



כתבו פעולה בשם averageQueue המקבלת שני תורים ומחזירה תור חדש של ממוצעי ציונים של כל התלמידים יחד.
עבור שני התורים שבדוגמה הפעולה תחזיר תור חדש המכיל את ממוצע הציונים של כל אחד מבין ארבעת התלמידים (התור באיור לסעיף).
כותרת הפעולה:
public static Queue<Double> averageQueue(Queue<Integer> marks,
Queue<Integer> tests)public static Queue<double> AverageQueue(Queue<int> marks,
Queue<int> tests)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
פעולה שמוציאה מ-tests את מספר הבחינות של כל תלמיד, מוציאה מ-marks בדיוק כמספר הזה ציונים, ומכניסה לתור החדש את הממוצע; בדוגמה: 90.0, 85.5, 98.25, 91.0.
הרעיון: הציונים של כל תלמיד נמצאים ברצף בתור marks, לפי סדר התלמידים בתור tests. לכן עוברים על tests: לכל תלמיד מוציאים את מספר הבחינות שלו num, מוציאים מראש marks בדיוק num ציונים וסוכמים אותם, ומכניסים לתור התוצאה את הממוצע.
1. יוצרים תור ריק result לממוצעים.
2. כל עוד tests לא ריק: מוציאים ממנו את num (מספר הבחינות של התלמיד הבא).
3. בלולאה של num סיבובים מוציאים ציון מ-marks ומוסיפים לצובר sum.
4. מחשבים את הממוצע כמספר ממשי: `(double) sum / num` - ההמרה חשובה, אחרת יתבצע חילוק שלמים (למשל ייתן 85 במקום 85.5).
5. מכניסים את הממוצע ל-result. בסוף מחזירים את result.
הערה: הפעולה מרוקנת את שני התורים שהתקבלו (השאלה אינה דורשת לשמור עליהם).
public static Queue<Double> averageQueue(Queue<Integer> marks,
Queue<Integer> tests)
{
Queue<Double> result = new Queue<Double>();
while (!tests.isEmpty())
{
int num = tests.remove(); // מספר הבחינות של התלמיד הנוכחי
int sum = 0;
for (int i = 0; i < num; i++)
{
sum += marks.remove(); // הציונים שלו נמצאים ברצף בראש התור
}
result.insert((double) sum / num);
}
return result;
}public static Queue<double> AverageQueue(Queue<int> marks,
Queue<int> tests)
{
Queue<double> result = new Queue<double>();
while (!tests.IsEmpty())
{
int num = tests.Remove(); // מספר הבחינות של התלמיד הנוכחי
int sum = 0;
for (int i = 0; i < num; i++)
{
sum += marks.Remove(); // הציונים שלו נמצאים ברצף בראש התור
}
result.Insert((double) sum / num);
}
return result;
}תשובה: הפעולה שלמעלה; עבור הדוגמה מוחזר התור 90.0, 85.5, 98.25, 91.0 (90.0 בראש התור).
סעיף ב
, כאשר הוא מספר הציונים בתור marks (התור הארוך) - כל איבר בכל אחד מהתורים מוצא פעם אחת בדיוק.
נסמן ב- את מספר הציונים בתור marks וב- את מספר התלמידים (אורך tests). מתקיים , כי לכל תלמיד יש לפחות בחינה אחת.
1. הלולאה החיצונית מבצעת סיבובים - בכל סיבוב מוציאים איבר אחד מ-tests.
2. הלולאה הפנימית מוציאה בכל סיבוב ציון אחד מ-marks. בסך כל הסיבובים של כל התלמידים יחד מוצאים בדיוק ציונים (כל ציון מוצא פעם אחת).
3. כל פעולה על תור (remove, insert, isEmpty) היא .
לכן זמן הריצה הכולל הוא - סורקים כל אחד מהתורים פעם אחת בלבד.
תשובה: , כאשר הוא אורך התור הארוך (marks).
שאלה 2 · מספר גדול כשרשרת ספרות: ספירה והשוואה
אפשר לייצג מספר שלם חיובי גדול מאוד כשרשרת חוליות כאשר כל חוליה מכילה ספרה אחת של המספר.
החוליה האחרונה מכילה ספרת האחדות.
המספר 2321418 (במילים: "שני מיליון שלוש מאות עשרים ואחד אלף ארבע מאות ושמונה עשרה"), מיוצג על ידי שרשרת החוליות הבאה:

כתבו פעולה חיצונית בשם numDigits המקבלת הפניה לחוליה ראשונה של שרשרת חוליות המייצגת מספר שלם וחיובי. הפעולה תחזיר כמות ספרות של מספר.
כותרת הפעולה:
public static int numDigits(Node<Integer> n)public static int NumDigits(Node<int> n)כתבו פעולה חיצונית בשם compare המקבלת הפניות לשתי שרשראות חוליות n1 ו-n2 המייצגות שני מספרים שלמים חיוביים.
אם המספר המיוצג בשרשרת הראשונה גדול מהמספר המיוצג בשרשרת השנייה, הפעולה תחזיר 1.
אם המספר המיוצג בשרשרת הראשונה קטן מהמספר המיוצג בשרשרת השנייה, הפעולה תחזיר 2.
אם שני מספרים שווים, הפעולה תחזיר 0.
כותרת הפעולה:
public static int compare(Node<Integer> n1, Node<Integer> n2)public static int Compare(Node<int> n1, Node<int> n2)מהי סיבוכיות הפעולה compare מהסעיף הקודם? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
מספר הספרות שווה למספר החוליות בשרשרת - סופרים את החוליות במעבר אחד (עבור הדוגמה: 7).
הרעיון: כל חוליה מכילה ספרה אחת, ולכן מספר הספרות הוא בדיוק מספר החוליות. עוברים על השרשרת עם הפניה pos מהחוליה הראשונה ועד הסוף (null), ומקדמים מונה בכל חוליה.
public static int numDigits(Node<Integer> n)
{
int count = 0;
Node<Integer> pos = n;
while (pos != null)
{
count++; // חוליה = ספרה
pos = pos.getNext();
}
return count;
}public static int NumDigits(Node<int> n)
{
int count = 0;
Node<int> pos = n;
while (pos != null)
{
count++; // חוליה = ספרה
pos = pos.GetNext();
}
return count;
}עבור השרשרת שבדוגמה (2→3→2→1→4→1→8) הפעולה מחזירה 7.
תשובה: הפעולה שלמעלה (סופרת את החוליות).
סעיף ב
קודם משווים את מספר הספרות (בעזרת numDigits): יותר ספרות - מספר גדול יותר. אם מספר הספרות שווה, עוברים במקביל על שתי השרשראות מהספרה השמאלית; הספרה הראשונה השונה קובעת (1 או 2); אם אין הבדל - 0.
הרעיון: מספרים שלמים חיוביים (בלי אפסים מובילים) משווים כמו בהשוואה ידנית:
1. מספר עם יותר ספרות הוא הגדול. לכן קודם מחשבים את אורך שתי השרשראות בעזרת numDigits מסעיף א'. אם len1 > len2 מחזירים 1, ואם len2 > len1 מחזירים 2.
2. אם האורכים שווים, הספרות מסודרות מהספרה הגבוהה (בחוליה הראשונה) עד ספרת האחדות (בחוליה האחרונה). עוברים במקביל על שתי השרשראות; בספרה הראשונה שבה יש הבדל - המספר שבו הספרה גדולה יותר הוא הגדול.
3. אם הגענו לסוף בלי למצוא הבדל - המספרים שווים ומחזירים 0.
public static int compare(Node<Integer> n1, Node<Integer> n2)
{
int len1 = numDigits(n1);
int len2 = numDigits(n2);
if (len1 > len2)
return 1;
if (len2 > len1)
return 2;
// אותו מספר ספרות: משווים ספרה-ספרה מהספרה השמאלית
while (n1 != null)
{
if (n1.getValue() > n2.getValue())
return 1;
if (n2.getValue() > n1.getValue())
return 2;
n1 = n1.getNext();
n2 = n2.getNext();
}
return 0;
}public static int Compare(Node<int> n1, Node<int> n2)
{
int len1 = NumDigits(n1);
int len2 = NumDigits(n2);
if (len1 > len2)
return 1;
if (len2 > len1)
return 2;
// אותו מספר ספרות: משווים ספרה-ספרה מהספרה השמאלית
while (n1 != null)
{
if (n1.GetValue() > n2.GetValue())
return 1;
if (n2.GetValue() > n1.GetValue())
return 2;
n1 = n1.GetNext();
n2 = n2.GetNext();
}
return 0;
}דוגמאות: 2321418 מול 2321518 - אורך שווה, ההבדל הראשון בספרה החמישית () ולכן מוחזר 2. 99 מול 100 - לראשון פחות ספרות, מוחזר 2. 51 מול 51 - מוחזר 0.
תשובה: הפעולה שלמעלה.
סעיף ג
, כאשר הוא אורך השרשרת הארוכה - כל שרשרת נסרקת מספר קבוע של פעמים.
נסמן ב- את מספר החוליות בשרשרת הארוכה מבין השתיים.
1. שתי הקריאות ל-numDigits סורקות כל שרשרת פעם אחת: .
2. אם האורכים שונים - חוזרים מיד.
3. אם האורכים שווים, לולאת ההשוואה עוברת לכל היותר פעם אחת על כל השרשראות, ובכל סיבוב מבצעת מספר קבוע של פעולות: .
סך הכול .
תשובה: - סורקים כל שרשרת מספר קבוע של פעמים (פעמיים לכל היותר).
שאלה 3 · ירושה: היגדים, המרות והפעולה instanceof
נתונות שתי המחלקות Fruit ו-Apple.
public class Fruit
{
protected int weight;
public Fruit (int val) { weight = val; }
public int getWeight() { return weight; }
}
public class Apple extends Fruit
{
private String color;
public Apple (int val, String col)
{
super(val);
color=col;
}
public boolean validWeight()
{
return weight > 80 && weight < 140;
}
}public class Fruit
{
protected int weight;
public Fruit (int val) { weight = val; }
public int GetWeight() { return weight; }
}
public class Apple : Fruit
{
private string color;
public Apple (int val, string col):base(val)
{
color=col;
}
public bool ValidWeight()
{
return weight > 80 && weight < 140;
}
}לפניכם ארבעה היגדים. קבעו לכל אחד מהם אם הוא נכון או אינו נכון ונמקו את קביעתכם.
1. המחלקה Fruit יורשת את הפעולה validWeight() מהמחלקה Apple.
2. המחלקה Apple יורשת את כל התכונות ואת כל הפעולות של המחלקה Fruit.
3. המחלקה Apple יכולה לגשת ישירות לתכונה weight של המחלקה Fruit.
4. המחלקה Fruit יכולה לגשת לתכונה color של המחלקה Apple.
5. למחלקה Apple אין פעולה toString()
(ב-C#: ValidWeight() ו-ToString())
לפניכם קטע קוד מהפעולה הראשית ( main ) של המחלקה TestFruit:
Fruit first = new Apple (100, "RED");
Fruit second = new Fruit (90);
Apple third = new Apple(100, "RED");Fruit first = new Apple (100, "RED");
Fruit second = new Fruit (90);
Apple third = new Apple(100, "RED");בעבור כל אחת מההוראות שלפניכם קבעו אם היא תקינה או אינה תקינה.
אם היא אינה תקינה, כתבו אם זו שגיאת ריצה או שגיאת הידור (קומפילציה).
1. boolean b = first. validWeight();
2. boolean b = second. validWeight();
3. boolean b = ((Apple)first). validWeight();
4. boolean b = ((Apple)second). validWeight();
5. boolean b = ((Apple)first).color.equals(third.color);1. bool b = first. ValidWeight();
2. bool b = second. ValidWeight();
3. bool b = ((Apple)first). ValidWeight();
4. bool b = ((Apple)second). ValidWeight();
5. bool b = ((Apple)first).color.Equals(third.color);כתבו פעולה המקבלת מערך עצמים מטיפוס Object. הפעולה תדפיס כמה עצמים הם מטיפוס Apple, כמה עצמים מטיפוס Fruit ואינו מטיפוס Apple וכמה עצמים הם לא מטיפוס Fruit.
◂ פתרון מלא לשאלה 3
סעיף א
1 - לא נכון; 2 - נכון; 3 - נכון; 4 - לא נכון; 5 - לא נכון.
נזכור את כיוון הירושה: Apple יורשת מ-Fruit (Fruit היא מחלקת הבסיס). מחלקה יורשת מקבלת את מה שבמחלקת הבסיס, ולא להפך.
1. לא נכון. הירושה היא בכיוון אחד בלבד - מהבסיס אל היורשת. validWeight() מוגדרת רק ב-Apple, ו-Fruit אינה מכירה אותה.
2. נכון. זו הגדרת הירושה: Apple מקבלת את התכונה weight ואת הפעולה getWeight() של Fruit (פעולה בונה אינה עוברת בירושה, אבל Apple קוראת לה ב-super(val) / base(val)).
3. נכון. weight מוגדרת protected, ולכן מחלקה יורשת רשאית לגשת אליה ישירות - וכך אכן עושה validWeight() (`weight > 80`).
4. לא נכון. color מוגדרת ב-Apple (וגם private). מחלקת הבסיס Fruit אינה מכירה תכונות שהוגדרו במחלקה שיורשת ממנה.
5. לא נכון. כל מחלקה יורשת (במישרין או בעקיפין) מהמחלקה Object, שבה מוגדרת toString() (ב-C#: ToString()). לכן גם ל-Apple יש פעולה כזו בירושה, אף על פי שלא כתבנו אותה.
תשובה: 1 - לא נכון; 2 - נכון; 3 - נכון; 4 - לא נכון; 5 - לא נכון.
סעיף ב
1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקינה (b = true); 4 - שגיאת ריצה; 5 - שגיאת הידור.
הכלל: המהדר בודק לפי הטיפוס של ההפניה (הטיפוס המוצהר), ואילו בזמן ריצה נבדק הטיפוס האמיתי של העצם. בהמרה כלפי מטה (מ-Fruit ל-Apple) המהדר מאשר, אבל בזמן ריצה ההמרה מצליחה רק אם העצם הוא באמת Apple.
תשובה: 1 - שגיאת הידור; 2 - שגיאת הידור; 3 - תקינה; 4 - שגיאת ריצה; 5 - שגיאת הידור.
סעיף ג
לולאה על המערך: אם arr[i] instanceof Apple (ב-C#: is Apple) - מונה Apple; אחרת אם instanceof Fruit - מונה Fruit בלבד; אחרת - מונה 'לא Fruit'; בסוף מדפיסים את שלושת המונים.
הרעיון: משתמשים באופרטור instanceof (ב-C#: is), שבודק את הטיפוס האמיתי של העצם בזמן ריצה, כולל ירושה: עצם Apple הוא גם Fruit. לכן סדר הבדיקות חשוב:
1. קודם בודקים אם העצם הוא Apple - אם כן, סופרים אותו כ-Apple.
2. אחרת בודקים אם הוא Fruit - כאן מגיעים רק עצמים שהם Fruit ואינם Apple.
3. אחרת - העצם אינו Fruit (גם תא שמכיל null נספר כאן, כי null instanceof Fruit מחזיר false).
בסוף מדפיסים את שלושת המונים. שם הפעולה לא ניתן בשאלה, ובחרנו countTypes.
public static void countTypes(Object[] arr)
{
int countApple = 0, countFruit = 0, countOther = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof Apple)
countApple++;
else if (arr[i] instanceof Fruit)
countFruit++; // Fruit שאינו Apple
else
countOther++; // לא Fruit
}
System.out.println("Apple: " + countApple);
System.out.println("Fruit (not Apple): " + countFruit);
System.out.println("Not Fruit: " + countOther);
}public static void CountTypes(object[] arr)
{
int countApple = 0, countFruit = 0, countOther = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is Apple)
countApple++;
else if (arr[i] is Fruit)
countFruit++; // Fruit שאינו Apple
else
countOther++; // לא Fruit
}
Console.WriteLine("Apple: " + countApple);
Console.WriteLine("Fruit (not Apple): " + countFruit);
Console.WriteLine("Not Fruit: " + countOther);
}דוגמה: עבור המערך {first, second, third, "abc"} (מסעיף ב') יודפס: Apple: 2, Fruit (not Apple): 1, Not Fruit: 1.
תשובה: הפעולה שלמעלה.
שאלה 4 · שרשור בנאים, דריסה והעמסה
נתונות שלוש המחלקות הבאות:
public class A
{
protected int x;
public A(){
this.x = 5;
}
public A(int x) {
this.x = x;
}
public A(int x, int y) {
this(x + y);
}
public int method (int i) {
return x + i;
}
public String toString() {
return this.x + " * ";
}
}
public class B extends A
{
private int y ;
public B (int x) {
super(x, x);
this.y = x;
}
public B(int x, int y) {
this(x * y);
}
public B(String s) {
System.out.println (s + "% " + this.y);
}
public String toString() {
return this.x + " " + this.y ;
}
}public class Test
{
public static void main(String[] args)
{
A a1 = new B(4, 2);
System.out.println(a1);
A a2 = new A(4, 2);
System.out.println(a2);
B a3 = new B(4, 2);
System.out.println(a3);
A b1 = new A();
System.out.println(b1);
A c1 = new B("something");
System.out.println(c1);
}
}public class A
{
protected int x;
public A(){
this.x = 5;
}
public A(int x) {
this.x = x;
}
public A(int x, int y): this(x +y) {
}
public int Method (int i) {
return x + i;
}
public override string ToString () {
return this.x + " * ";
}
}
public class B : A
{
private int y;
public B (int x): base(x, x) {
this.y = x;
}
public B(int x, int y): this(x * y){
}
public B(string s) {
Console.WriteLine (s + "% " + this.y);
}
public override string ToString () {
return this.x + " " + this.y ;
}
}public class Test
{
public static void Main(string[] args)
{
A a1 = new B(4, 2);
Console.WriteLine(a1);
A a2 = new A(4, 2);
Console.WriteLine(a2);
B a3 = new B(4, 2);
Console.WriteLine(a3);
A b1 = new A();
Console.WriteLine(b1);
A c1 = new B("something");
Console.WriteLine(c1);
}
}עקבו אחרי ביצוע פעולה הראשית main ורשמו מה יהיה הפלט. יש להראות את העצמים שנוצרו ואת ערכי התכונות שלהם.
לכל אחת מהפעולות הבאות קבעו אם אפשר להוסיף אותה במחלקה A, וציינו את האפשרות המתאימה מבין האפשרויות הבאות:
•שגיאת קומפילציה.
•קוד תקין, דריסה (overriding).
•קוד תקין, העמסה (overloading).
1. public int method () { return 1; }
2. public double method (int i){ return i; }
3. public void method (double i){ System.out.print(i); }1. public virtual int Method () { return 1; }
2. public virtual double Method (int i){ return i; }
3. public virtual void Method (double i){ Console.Write(i); }לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה B וציינו את האפשרות המתאימה מבין האפשרויות הבאות:
•שגיאת קומפילציה.
•קוד תקין, דריסה (overriding).
•קוד תקין, העמסה (overloading).
1. public int method () { return 10; }
2. public int method (int i){ return i*10; }
3. public void method (int i){ System.out.print(10*i); }1. public override int Method () { return 10; }
2. public override int Method (int i){ return i*10; }
3. public override void Method (int i){ Console.Write(10*i); }◂ פתרון מלא לשאלה 4
סעיף א
הפלט: `16 8`, `6 * `, `16 8`, `5 * `, `something% 0`, `5 0` (כל אחד בשורה). העצמים: a1 - B (x=16, y=8); a2 - A (x=6); a3 - B (x=16, y=8); b1 - A (x=5); c1 - B (x=5, y=0).
•`this(...)` קורא לפעולה בונה אחרת של אותה מחלקה; `super(...)` (ב-C#: `base(...)`) קורא לפעולה בונה של מחלקת הבסיס.
•פעולה בונה של B שאינה קוראת במפורש ל-super / this, קוראת אוטומטית לפעולה הבונה ללא פרמטרים של A.
•תכונה מטיפוס int שלא הוצב בה ערך מאותחלת ל-0.
•ההדפסה של עצם מפעילה את toString() של הטיפוס האמיתי שלו (דריסה), ולא של טיפוס ההפניה.
1. `A a1 = new B(4, 2)` - נקראת B(int x, int y) עם x=4, y=2, והיא קוראת ל-`this(4*2)`, כלומר B(8). B(8) קוראת ל-`super(8, 8)`, כלומר A(int x, int y), שקוראת ל-`this(8+8)` = A(16): x=16. חזרה ל-B(8): y=8. העצם: B עם x=16, y=8. ההדפסה מפעילה את toString() של B: `16 8`.
2. `A a2 = new A(4, 2)` - A(4, 2) קוראת ל-A(4+2) = A(6): x=6. ההדפסה (toString של A): `6 * `.
3. `B a3 = new B(4, 2)` - בדיוק כמו a1: x=16, y=8. הדפסה: `16 8`.
4. `A b1 = new A()` - x=5. הדפסה: `5 * `.
5. `A c1 = new B("something")` - הפעולה הבונה B(String s) אינה קוראת במפורש ל-super, ולכן קודם מופעלת A() ו-x=5. y לא קיבלה ערך ולכן y=0. בגוף הפעולה הבונה מודפס `something% 0`. אחר כך ההדפסה של c1 (toString של B): `5 0`.
16 8
6 *
16 8
5 *
something% 0
5 0הפלט זהה ב-Java וב-C#.
תשובה: `16 8` / `6 * ` / `16 8` / `5 * ` / `something% 0` / `5 0`.
סעיף ב
1 - קוד תקין, העמסה; 2 - שגיאת קומפילציה; 3 - קוד תקין, העמסה (זהה ב-Java וב-C#).
בתוך אותה מחלקה אין דריסה - דריסה קיימת רק בין מחלקת בסיס למחלקה יורשת. בתוך A יש כבר `int method(int i)`. פעולה נוספת באותו שם תקינה רק אם רשימת הפרמטרים שלה שונה (העמסה). שינוי של טיפוס ההחזרה בלבד אינו מספיק.
1. `method()` - ללא פרמטרים, רשימת פרמטרים שונה מ-`method(int)`: קוד תקין, העמסה.
2. `double method(int i)` - אותה חתימה בדיוק כמו `int method(int i)` הקיימת (שם + פרמטר int), ההבדל רק בטיפוס ההחזרה: שגיאת קומפילציה (הפעולה כבר מוגדרת במחלקה).
3. `void method(double i)` - פרמטר מטיפוס double, חתימה שונה: קוד תקין, העמסה.
ב-C# התשובות זהות; המילה virtual רק מאפשרת דריסה בעתיד במחלקה יורשת ואינה משנה את הקביעה.
תשובה: 1 - העמסה; 2 - שגיאת קומפילציה; 3 - העמסה.
סעיף ג
Java: 1 - העמסה; 2 - דריסה; 3 - שגיאת קומפילציה. C#: שלושתן שגיאת קומפילציה (אין ב-A פעולה Method() לדרוס, ו-Method(int) של A אינה virtual).
B יורשת מ-A את `int method(int i)` (בגרסה המקורית של A, ללא התוספות מסעיף ב').
Java (כל פעולה שאינה private ניתנת לדריסה):
1. `int method()` - חתימה שונה מ-`method(int)`: קוד תקין, העמסה.
2. `int method(int i)` - אותה חתימה ואותו טיפוס החזרה כמו בפעולה שבמחלקת הבסיס: קוד תקין, דריסה.
3. `void method(int i)` - אותה חתימה כמו הפעולה שבבסיס אבל טיפוס החזרה אחר (void במקום int). זו אינה העמסה (הפרמטרים זהים) וגם אינה דריסה חוקית: שגיאת קומפילציה.
C# (המילה override מחייבת שבבסיס תהיה פעולה עם אותה חתימה המסומנת virtual / abstract / override):
1. `override int Method()` - ב-A אין פעולה Method() ללא פרמטרים, אין מה לדרוס: שגיאת קומפילציה.
2. `override int Method(int i)` - ב-A קיימת Method(int), אבל היא אינה מוגדרת virtual: שגיאת קומפילציה.
3. `override void Method(int i)` - גם כאן הבסיס אינו virtual, ובנוסף טיפוס ההחזרה שונה: שגיאת קומפילציה.
תשובה: ב-Java: 1 - העמסה, 2 - דריסה, 3 - שגיאת קומפילציה. ב-C#: 1, 2, 3 - שגיאת קומפילציה.
שאלה 5 · מרחק של ערך מקצוות שרשרת חוליות
נתונה שרשרת חוליות המכילה מספרים שלמים. כל ערך בשרשרת יכול להופיע כמה פעמים.
נגדיר "מרחק" של ערך כלשהו בשרשרת כסכום המרחקים הקטנים ביותר של מופע של אותו מספר מקצוות השרשרת.
דוגמה 1: ה"מרחק" של מספר 7 בשרשרת הבאה הינו 5 (3 מתחילת השרשרת ו- 2 עד לסוף השרשרת).
דוגמה 2: ה"מרחק" של מספר 3 בשרשרת הבאה הינו 9 (2 מתחילת השרשרת ו-7 עד לסוף השרשרת)


כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות ומספר num ומחזירה את ה"מרחק" של המספר num. אם num לא נמצא בשרשרת הפעולה תחזיר 1-.
כותרת הפעולה:
public static int distance(Node<Integer> lst, int num)public static int Distance(Node<int> lst, int num)
כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות ומחזירה את המספר בעל ה"מרחק" הקטן ביותר.
עבור השרשרת הבאה הפעולה תחזיר 9 ( ה"מרחק" של הערך 9 הוא הקטן ביותר).
כותרת הפעולה:
public static int minDistanceValue(Node<Integer> lst)public static int MinDistanceValue(Node<int> lst)מהן סיבוכיות של הפעולות Distance ו-MinDistanceValue מסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 5
סעיף א
מונים את החוליות שלפני המופע הראשון של num (dist1); אם לא נמצא - מחזירים 1-; ממשיכים עד הסוף וסופרים חוליות, ומאפסים את המונה dist2 בכל מופע נוסף של num; מחזירים dist1 + dist2 (בדוגמאות: 5 עבור 7, 9 עבור 3).
הרעיון: המרחק מתחילת השרשרת נקבע לפי המופע הראשון של num: מספר החוליות שלפניו. המרחק מסוף השרשרת נקבע לפי המופע האחרון: מספר החוליות שאחריו. אפשר לחשב את שניהם במעבר אחד:
1. מתקדמים מתחילת השרשרת וסופרים ב-dist1 חוליות עד שמגיעים לחוליה הראשונה שערכה num.
2. אם הגענו לסוף (null) בלי למצוא - num לא נמצא, מחזירים 1-.
3. ממשיכים מהחוליה שאחרי המופע הראשון עד הסוף. dist2 סופר חוליות שאינן num, וכל פעם שפוגשים מופע נוסף של num מאפסים אותו - כך בסוף dist2 הוא מספר החוליות שאחרי המופע האחרון.
4. מחזירים dist1 + dist2.
public static int distance(Node<Integer> lst, int num)
{
Node<Integer> pos = lst;
int dist1 = 0; // חוליות לפני המופע הראשון
while (pos != null && pos.getValue() != num)
{
dist1++;
pos = pos.getNext();
}
if (pos == null)
return -1; // num לא נמצא בשרשרת
int dist2 = 0; // חוליות אחרי המופע האחרון
pos = pos.getNext();
while (pos != null)
{
if (pos.getValue() == num)
dist2 = 0; // מופע נוסף - מתחילים לספור מחדש
else
dist2++;
pos = pos.getNext();
}
return dist1 + dist2;
}public static int Distance(Node<int> lst, int num)
{
Node<int> pos = lst;
int dist1 = 0; // חוליות לפני המופע הראשון
while (pos != null && pos.GetValue() != num)
{
dist1++;
pos = pos.GetNext();
}
if (pos == null)
return -1; // num לא נמצא בשרשרת
int dist2 = 0; // חוליות אחרי המופע האחרון
pos = pos.GetNext();
while (pos != null)
{
if (pos.GetValue() == num)
dist2 = 0; // מופע נוסף - מתחילים לספור מחדש
else
dist2++;
pos = pos.GetNext();
}
return dist1 + dist2;
}בדיקה על הדוגמאות (השרשרת 4, 9, 3, 7, 9, 9, 7, 7, 2, 9):
•num = 7: לפני המופע הראשון 4, 9, 3, כלומר dist1 = 3; אחרי המופע האחרון 2, 9, כלומר dist2 = 2; מוחזר .
•num = 3: dist1 = 2, dist2 = 7; מוחזר .
•num = 5: לא נמצא; מוחזר 1-.
תשובה: הפעולה שלמעלה.
סעיף ב
עוברים על כל חוליה, מחשבים לערך שבה את distance(lst, value) מסעיף א', ושומרים את הערך שהמרחק שלו הקטן ביותר; בדוגמה מוחזר 9 (מרחק 1).
הרעיון: חיפוש מינימום רגיל, כשה"מפתח" של כל ערך הוא המרחק שלו, המחושב בעזרת distance מסעיף א'.
1. מאתחלים את המועמד minNum לערך שבחוליה הראשונה ואת minDis למרחק שלו.
2. עוברים על שאר החוליות; לכל ערך מחשבים את המרחק שלו. אם הוא קטן מ-minDis - מעדכנים את minNum ואת minDis.
3. מחזירים את minNum. (במקרה של שוויון נשאר הערך שהופיע ראשון בשרשרת.)
הנחה: השרשרת אינה ריקה.
public static int minDistanceValue(Node<Integer> lst)
{
int minNum = lst.getValue();
int minDis = distance(lst, minNum);
Node<Integer> pos = lst.getNext();
while (pos != null)
{
int dis = distance(lst, pos.getValue());
if (dis < minDis)
{
minDis = dis;
minNum = pos.getValue();
}
pos = pos.getNext();
}
return minNum;
}public static int MinDistanceValue(Node<int> lst)
{
int minNum = lst.GetValue();
int minDis = Distance(lst, minNum);
Node<int> pos = lst.GetNext();
while (pos != null)
{
int dis = Distance(lst, pos.GetValue());
if (dis < minDis)
{
minDis = dis;
minNum = pos.GetValue();
}
pos = pos.GetNext();
}
return minNum;
}המרחק הקטן ביותר הוא 1, של הערך 9.
תשובה: הפעולה שלמעלה; עבור הדוגמה מוחזר 9.
סעיף ג
distance: - מעבר אחד על השרשרת; minDistanceValue: - לכל אחת מ- החוליות מופעלת distance שעולה .
נסמן ב- את מספר החוליות בשרשרת.
1. distance: שתי הלולאות יחד עוברות על כל חוליה בשרשרת פעם אחת לכל היותר (הלולאה השנייה ממשיכה מהמקום שבו עצרה הראשונה), ובכל חוליה מתבצע מספר קבוע של פעולות. לכן .
2. minDistanceValue: הלולאה עוברת על חוליות, ובכל חוליה מופעלת distance שעולה . לכן .
תשובה: distance - ; minDistanceValue - .
שאלה 6 · היררכיית מחלקות וממשקים של ענפי ספורט
נתונה היררכיית המחלקות הבאה הכוללת שש מחלקות: Sport, MRace, RGymnastic, Ball, TTennis, BBall ושני ממשקים: IHall ו-IGroup.
בכל מחלקה מוגדרת פעולה בונה ללא פרמטרים.

כתבו עבור כל מחלקה, את כותרת המחלקה.
עבור כל אחת מהפקודות הבאות קבעו אם היא נכונה או אינה נכונה. נמקו את קביעתכם.
1. Sport s1 = new BBall();
2. Sport s2 = new MRace();
3. TTennis t1 = new Ball();
4. BBall b1 = new IGroup();
5. IHall i1 = new Ball();
6. IHall i2 = new TTennis();כתבו פעולה המקבלת מערך עצמים מסוג Sport. הפעולה תחזיר מספר עצמים המייצגים ענף ספורט קבוצתי שמתקיים באולם.
כותרת הפעולה:
public static int count (Sport[] s)public static int Count (Sport[] s)שימו לב: יש לכתוב את הפעולה כך שהיא תעבוד נכון גם כאשר יתווספו לפרויקט מחלקות נוספות, כמו VBall (כדורעף), HBall (כדוריד) וכד'
רוצים להוסיף לפרויקט מחלקה חדשה המתארת כדורגל. האם אפשר להוסיף את המחלקה FBall תוך שמירה על היררכיה קיימת או שיש לשנות את ההיררכיה? ציירו תרשים של היררכיית המחלקות החדשה (כולל את המחלקה FBall).
◂ פתרון מלא לשאלה 6
סעיף א
Sport; MRace extends Sport; RGymnastic extends Sport implements IHall; Ball extends Sport implements IHall; TTennis extends Ball; BBall extends Ball implements IGroup (ב-C#: נקודתיים במקום extends / implements); IHall ו-IGroup הם interface.
קוראים את התרשים: חץ רציף = ירושה (extends), חץ מקווקו = מימוש ממשק (implements).
•MRace, RGymnastic ו-Ball יורשות מ-Sport.
•RGymnastic ו-Ball מממשות את IHall (ספורט באולם).
•TTennis ו-BBall יורשות מ-Ball (ולכן גם הן IHall דרך Ball).
•BBall מממשת גם את IGroup (ספורט קבוצתי).
public interface IHall
public interface IGroup
public class Sport
public class MRace extends Sport
public class RGymnastic extends Sport implements IHall
public class Ball extends Sport implements IHall
public class TTennis extends Ball
public class BBall extends Ball implements IGrouppublic interface IHall
public interface IGroup
public class Sport
public class MRace : Sport
public class RGymnastic : Sport, IHall
public class Ball : Sport, IHall
public class TTennis : Ball
public class BBall : Ball, IGroupתשובה: הכותרות שלמעלה.
סעיף ב
1 - נכונה; 2 - נכונה; 3 - לא נכונה; 4 - לא נכונה; 5 - נכונה; 6 - נכונה.
הכלל: הפניה מטיפוס X יכולה להפנות לעצם מטיפוס X או מכל טיפוס שיורש מ-X / מממש את X. לא ניתן ליצור עצם (new) מממשק.
תשובה: 1 - נכונה; 2 - נכונה; 3 - לא נכונה; 4 - לא נכונה; 5 - נכונה; 6 - נכונה.
סעיף ג
סופרים את העצמים שמקיימים גם instanceof IGroup וגם instanceof IHall (ב-C#: is IGroup && is IHall).
הרעיון: "ספורט קבוצתי" מיוצג על ידי הממשק IGroup, ו"ספורט באולם" - על ידי IHall. ענף שהוא גם קבוצתי וגם באולם הוא עצם שמממש את שני הממשקים.
כדי שהפעולה תעבוד גם כשיתווספו מחלקות חדשות (VBall, HBall וכו'), לא בודקים שמות מחלקות מסוימות (כמו instanceof BBall), אלא בודקים את הממשקים. כל מחלקה חדשה שתממש את IGroup ואת IHall (במישרין או בירושה) תיספר אוטומטית, בלי לשנות את הפעולה.
public static int count (Sport[] s)
{
int count = 0;
for (int i = 0; i < s.length; i++)
{
if (s[i] instanceof IGroup && s[i] instanceof IHall)
count++;
}
return count;
}public static int Count (Sport[] s)
{
int count = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] is IGroup && s[i] is IHall)
count++;
}
return count;
}בהיררכיה הנוכחית רק BBall מקיימת את שני התנאים. בדיקה של IGroup בלבד הייתה מספיקה כרגע, אבל הייתה נכשלת עבור ענף קבוצתי חדש שאינו באולם (למשל כדורגל - סעיף ד'), ולכן בודקים את שני הממשקים.
תשובה: הפעולה שלמעלה.
סעיף ד
יש לשנות את ההיררכיה: כדורגל הוא משחק כדור קבוצתי שאינו באולם, אבל Ball מממשת את IHall. מעבירים את מימוש IHall מ-Ball אל TTennis ואל BBall, ומוסיפים FBall extends Ball implements IGroup.
1. כדורגל הוא משחק כדור, ולכן FBall צריכה לרשת מ-Ball. כדורגל הוא ספורט קבוצתי, ולכן FBall מממשת את IGroup.
2. הבעיה: בהיררכיה הקיימת Ball מממשת את IHall. אם FBall תירש מ-Ball, היא תהיה "ספורט באולם" - וזה לא נכון, כי כדורגל משוחק במגרש פתוח. (גם הפעולה count מסעיף ג' הייתה סופרת אותה בטעות.)
3. הפתרון - שינוי ההיררכיה: מוחקים את מימוש IHall מהמחלקה Ball, ומוסיפים אותו ישירות למחלקות של משחקי הכדור שמתקיימים באולם: TTennis ו-BBall.
ההיררכיה החדשה (חץ רציף = ירושה, חץ מקווקו = מימוש ממשק):
•Sport ← MRace, RGymnastic, Ball (ירושה).
•RGymnastic - - → IHall.
•Ball ← TTennis, BBall, FBall (ירושה); Ball אינה מממשת עוד את IHall.
•TTennis - - → IHall.
•BBall - - → IHall, BBall - - → IGroup.
•FBall - - → IGroup.
public class Ball extends Sport
public class TTennis extends Ball implements IHall
public class BBall extends Ball implements IHall, IGroup
public class FBall extends Ball implements IGrouppublic class Ball : Sport
public class TTennis : Ball, IHall
public class BBall : Ball, IHall, IGroup
public class FBall : Ball, IGroupהשינוי שומר על נכונות כל הקביעות מסעיף ב' פרט ל-5: אחרי השינוי Ball אינה IHall, ולכן `IHall i1 = new Ball();` לא יעבור הידור.
תשובה: אי אפשר בלי לשנות את ההיררכיה; מעבירים את IHall מ-Ball ל-TTennis ול-BBall, ו-FBall יורשת מ-Ball ומממשת את IGroup בלבד.
שאלה 7 · סריקות תוכית ותחילית של עץ בינרי
לפניכם הפעולות הבאות:
public static String what(BinNode<Integer> t)
{
String output = "(";
if (t.getLeft()!= null)
output += what(t.getLeft());
output += t.getValue();
if (t.getRight()!= null)
output += what (t.getRight());
output += ")";
return output;
}
public static String why(BinNode<Integer> t)
{
String output = "(";
output += t.getValue();
if (t.getLeft()!= null)
output += why(t.getLeft());
if (t.getRight()!= null)
output += why (t.getRight());
output += ")";
return output;
}public static string What(BinNode<int> t)
{
string output = "(";
if (t.GetLeft()!= null)
output += What(t.GetLeft());
output += t.GetValue();
if (t.GetRight()!= null)
output += What (t.GetRight());
output += ")";
return output;
}
public static string Why(BinNode<int> t)
{
string output = "(";
output += t.GetValue();
if (t.GetLeft()!= null)
output += Why(t.GetLeft());
if (t.GetRight()!= null)
output += Why (t.GetRight());
output += ")";
return output;
}
נתון העץ הבינרי bt הבא:
מה תהיה תוצאת זימון הפעולה what(bt)? חובה להראות את המעקב!
לפעולה what הועברה כפרמטר הפניה לשורש של עץ בינרי. המחרוזת שהוחזרה מהשיטה היא:
`(((30) 20 ((50) 5)) 40 (10))`
ציירו את העץ הבינרי שהועבר כפרמטר פעולה.
האם קיים עץ בינארי bt בעל שלושה צמתים לפחות שעבורו תוצאת זימון הפעולה what(bt) תהיה זהה לתוצאת זימון הפעולה why(bt)? אם כן – ציירו את העץ, אם לא – הסבירו מדוע.
◂ פתרון מלא לשאלה 7
סעיף א
((1(9))4((2)20(7)))
מה עושה what: לכל צומת היא כותבת סוגר פותח, אחריו את התוצאה של תת-העץ השמאלי (אם יש), את ערך הצומת, את התוצאה של תת-העץ הימני (אם יש) וסוגר סוגר. זו סריקה תוכית (שמאל-שורש-ימין), כשכל תת-עץ עטוף בסוגריים.
בעץ: השורש 4; בן שמאלי 1 (עם בן ימני 9); בן ימני 20 (עם בן שמאלי 2 ובן ימני 7).
מעקב (מהעלים כלפי מעלה):
סדר הזימונים בפועל: what(4) → what(1) → what(9) חוזר `(9)` → what(1) חוזר `(1(9))` → what(20) → what(2) חוזר `(2)` → what(7) חוזר `(7)` → what(20) חוזר `((2)20(7))` → what(4) מחזיר את המחרוזת המלאה.
תשובה: `((1(9))4((2)20(7)))`
סעיף ב
שורש 40; בן שמאלי 20 (בן שמאלי 30, בן ימני 5); בן ימני 10; ל-5 יש בן שמאלי 50.
הרעיון: כל תת-עץ מוחזר בצורה `( שמאל ערך ימין )`. כדי למצוא את השורש מפרקים את הסוגריים החיצוניים: מה שבתוכם הוא [סוגריים מאוזנים של תת-העץ השמאלי, אם יש] ערך [סוגריים מאוזנים של תת-העץ הימני, אם יש].
1. בתוך הסוגריים החיצוניים: `((30) 20 ((50) 5))` `40` `(10)`. לכן השורש הוא 40, תת-העץ השמאלי הוא `((30) 20 ((50) 5))` ותת-העץ הימני הוא `(10)`.
2. `(10)` - צומת 10 בלי בנים: בן ימני של 40.
3. `((30) 20 ((50) 5))` - שמאל `(30)`, ערך 20, ימין `((50) 5)`. לכן 20 הוא בן שמאלי של 40, ו-30 (עלה) הוא בנו השמאלי.
4. `((50) 5)` - שמאל `(50)`, ערך 5, ואין ימין. לכן 5 הוא בן ימני של 20, ו-50 הוא בנו השמאלי (ל-5 אין בן ימני).
- 40: בן שמאלי 20, בן ימני 10.
- 20: בן שמאלי 30, בן ימני 5.
- 5: בן שמאלי 50.
- 30, 50, 10 - עלים.
בדיקה: הפעלת what על העץ הזה מחזירה `(((30)20((50)5))40(10))` - אותה מחרוזת (בלי הרווחים).
תשובה: העץ באיור הפתרון: שורש 40 עם בן שמאלי 20 ובן ימני 10; ל-20 בן שמאלי 30 ובן ימני 5; ל-5 בן שמאלי 50.

סעיף ג
כן: כל עץ שבו לאף צומת אין בן שמאלי (שרשרת של בנים ימניים), למשל 1 ← בן ימני 3 ← בן ימני 0; לשתי הפעולות מוחזר (1(3(0))).
ההבדל בין הפעולות: what היא סריקה תוכית (שמאל, ערך, ימין) ו-why היא סריקה תחילית (ערך, שמאל, ימין). שתיהן כותבות סוגר פותח בהתחלה, את תת-העץ הימני אחרי השמאלי, וסוגר סוגר בסוף.
1. ההבדל היחיד הוא המקום של הערך ביחס לתת-העץ השמאלי: ב-why הערך כתוב לפני תת-העץ השמאלי וב-what - אחריו.
2. אם לצומת אין בן שמאלי, שתי הפעולות כותבות עבורו בדיוק `(` ערך, [תת-עץ ימני] `)` - אותו דבר.
3. לכן, אם לאף צומת בעץ אין בן שמאלי, שתי הפעולות מחזירות מחרוזות זהות (לפי אינדוקציה על העץ).
דוגמה עם שלושה צמתים: שורש 1, לו בן ימני 3, ולו בן ימני 0.
•what: `(1` + what(3) + `)` = `(1(3(0)))`.
•why: `(1` + why(3) + `)` = `(1(3(0)))`.
שתי התוצאות זהות.
תשובה: כן. למשל העץ שבאיור הפתרון (1 ← בן ימני 3 ← בן ימני 0); כל עץ שבו אין לאף צומת בן שמאלי מתאים.

שאלה 8 · מעקב: דריסה, super ומערך הפניות
נתונות שלוש המחלקות הבאות: One, Two, Tester
public class One
{
protected int x;
public One(){
this.x = 1;
}
public One(int x) {
this.x = x;
}
public void f(int x) {
this.x += x;
}
public String toString() {
return "x=" + this.x;
}
} // end of One
public class Two extends One
{
public Two() {
super(3);
}
public Two(int x) {
super.f(x);
f(x);
}
public void f(int x)
{
this.x -= x;
super.f(x);
}
}// end of Twopublic class Tester
{
public static void print(One[] arr)
{
for(int i=0; i < arr.length; i++)
{
System.out.println(i+" "+arr[i]);
}
}
public static void doF(One[] arr, int num)
{
for(int i=0; i < arr.length; i++)
{
arr[i].f(num);
}
}
public static void what(One[] arr)
{
int k=0;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] instanceof Two)
k++;
}
k = arr.length - k;
System.out.println("k = "+ k);
}
public static void main(String [] args)
{
One[] arr = new One[6];
arr[0]= new One();
arr[1]= new One(3);
arr[2] = new Two();
arr[3] = new Two(2);
arr[4] = new Two(5);
arr[5] = arr[1];
print(arr);
doF(arr, 2);
print(arr);
what(arr);
}
}public class One
{
protected int x;
public One(){
this.x = 1;
}
public One(int x) {
this.x = x;
}
public virtual void F(int x) {
this.x += x;
}
public override string ToString () {
return "x=" + this.x;
}
} // end of One
public class Two : One
{
public Two(): base(3) {
}
public Two(int x) {
base.F(x);
F(x);
}
public override void F(int x)
{
this.x -= x;
base.F(x);
}
}// end of Twopublic class Tester
{
public static void Print(One[] arr)
{
for(int i=0; i < arr.Length; i++)
{
Console.WriteLine(i+" "+arr[i]);
}
}
public static void DoF(One[] arr, int num)
{
for(int i=0; i < arr.Length; i++)
{
arr[i].F(num);
}
}
public static void What(One[] arr)
{
int k=0;
for(int i = 0; i < arr.Length; i++)
{
if(arr[i] is Two)
k++;
}
k = arr.Length - k;
Console.WriteLine("k = "+ k);
}
public static void Main(string [] args)
{
One[] arr = new One[6];
arr[0]= new One();
arr[1]= new One(3);
arr[2] = new Two();
arr[3] = new Two(2);
arr[4] = new Two(5);
arr[5] = arr[1];
Print(arr);
DoF(arr, 2);
Print(arr);
What(arr);
}
}עקבו אחרי ביצוע הפעולה הראשית ורשמו מה יהיה הפלט של הפעולה.
יש להציג את כל העצמים שנוצרו ואת השינויים בערכי התכונות שלהם במהלך הביצוע.
מה מבצעת הפעולה what?
◂ פתרון מלא לשאלה 8
סעיף א
הפלט: 0 x=1, 1 x=3, 2 x=3, 3 x=3, 4 x=6, 5 x=3, 0 x=3, 1 x=7, 2 x=3, 3 x=3, 4 x=6, 5 x=7, k = 3 (כל אחד בשורה).
•`Two(int x)` אינה קוראת במפורש ל-super, ולכן קודם מופעלת `One()` ו-x=1.
•`super.f(x)` מפעילה את f של One (מוסיפה x). קריאה רגילה `f(x)` בתוך עצם Two מפעילה את f של Two (דריסה): מחסירה x ואז מוסיפה x בחזרה - כלומר בסך הכול לא משנה את x.
•`arr[5] = arr[1]` אינה יוצרת עצם חדש: שני התאים מפנים לאותו עצם.
print ראשון: `0 x=1`, `1 x=3`, `2 x=3`, `3 x=3`, `4 x=6`, `5 x=3`.
doF(arr, 2) - מפעילה f(2) על כל תא לפי הסדר:
העצם המשותף ל-arr[1] ול-arr[5] קיבל f(2) פעמיים: 3 → 5 → 7.
print שני: `0 x=3`, `1 x=7`, `2 x=3`, `3 x=3`, `4 x=6`, `5 x=7`.
what(arr): יש 3 עצמים מטיפוס Two (תאים 2, 3, 4), לכן ומודפס `k = 3`.
0 x=1
1 x=3
2 x=3
3 x=3
4 x=6
5 x=3
0 x=3
1 x=7
2 x=3
3 x=3
4 x=6
5 x=7
k = 3תשובה: הפלט שלמעלה (זהה ב-Java וב-C#).
סעיף ב
מדפיסה כמה תאים במערך מפנים לעצמים שאינם מטיפוס Two (אורך המערך פחות מספר העצמים מטיפוס Two).
1. הלולאה סופרת ב-k את התאים שבהם arr[i] instanceof Two (ב-C#: is Two), כלומר עצמים מטיפוס Two (או ממחלקה שיורשת מ-Two).
2. אחר כך : מספר התאים שאינם מטיפוס Two.
3. הפעולה מדפיסה את הערך הזה. בדוגמה: .
תשובה: הפעולה מדפיסה את מספר האיברים במערך שאינם עצמים מטיפוס Two.
שאלה 9 · רקורסיה על מחסנית: מציאת החציון
לפניכם מספר פעולות המוגדרות על המחסנית:
•`public static int numOf(Stack<Integer> m)`
הפעולה מחזירה מספר איברים במחסנית m.
•`public static int randChoice (Stack<Integer> m)`
הפעולה מחזירה איבר שנבחר באקראי מתוך מחסנית m.
•`public static Stack<Integer> createSmall(Stack<Integer> m, int a)`
הפעולה מקבלת מחסנית m המכילה מספרים שלמים וערך a ומחזירה מחסנית חדשה המכילה את כל המספרים מתוך m הקטנים מ- a.
•`public static Stack<Integer> createLarge(Stack<Integer> m, int a)`
הפעולה מקבלת מחסנית m המכילה מספרים שלמים וערך a ומחזירה מחסנית חדשה המכילה את כל המספרים מתוך m הגדולים מ- a.
•`public static void eraseSmalls(Stack<Integer> m, int k)`
הפעולה מוחקת ממחסנית m את k האיברים הקטנים ביותר. הנחה: במחסנית יש לפחות k איברים.
•`public static void eraseLarges(Stack<Integer> m, int k)`
הפעולה מוחקת ממחסנית m את k האיברים הגדולים ביותר. הנחה: במחסנית יש לפחות k איברים
כותרות הפעולות ב-C#:
public static int NumOf(Stack<int> m)
public static int RandChoice (Stack<int> m)
public static Stack<int> CreateSmall(Stack<int> m, int a)
public static Stack<int> CreateLarge(Stack<int> m, int a)
public static void EraseSmalls(Stack<int> m, int k)
public static void EraseLarges(Stack<int> m, int k)
נתונה פעולה רקורסיבית what המשתמשת בפעולות הנ"ל. הפעולה מקבלת מחסנית s, המכילה מספר אי זוגי של מספרים שלמים, שכולם שונים זה מזה.
public static int what(Stack<Integer> s)
{
int a = randChoice(s);
Stack<Integer> m1 = createSmall(s,a);
int k1 = numOf(m1);
Stack<Integer> m2 = createLarge(s,a);
int k2 = numOf(m2);
if(k1 > k2)
{
eraseSmalls(m1, k2+1);
return what(m1);
}
if(k2 > k1)
{
eraseLarges(m2, k1+1);
return what(m2);
}
return a;
}public static int What(Stack<int> s)
{
int a = RandChoice(s);
Stack<int> m1 = CreateSmall(s,a);
int k1 = NumOf(m1);
Stack<int> m2 = CreateLarge(s,a);
int k2 = NumOf(m2);
if(k1 > k2)
{
EraseSmalls(m1, k2+1);
return What(m1);
}
if(k2 > k1)
{
EraseLarges(m2, k1+1);
return What(m2);
}
return a;
}עקבו אחרי זימון הפעולה what(s) עבור מחסנית הבאה ורשמו מה תהיה תוצאת הזימון.
מה מבצעת הפעולה what עבור מחסנית המכילה מספר אי זוגי של מספרים שלמים, שכולם שונים זה מזה?
ממשו את הפעולה createSmall.
ממשו את הפעולה randChoice.
◂ פתרון מלא לשאלה 9
סעיף א
7 (לכל בחירה אקראית של a). למשל עבור a = 8: m1 = {-3, -9, 7, 3, 1}, k1 = 5, m2 = {43, 9, 12}, k2 = 3; מוחקים מ-m1 את 4 הקטנים ונשאר {7}; what({7}) מחזיר 7.
המחסנית (43 בראש): 43, -3, 8, 9, 12, -9, 7, 3, 1. כל המספרים שונים ויש 9 מספרים (אי-זוגי).
ה-a נבחר באקראי, ולכן מסלול הרקורסיה תלוי בבחירה; נעקוב אחרי הבחירה a = 8 (ונראה בהמשך שהתוצאה אינה תלויה בבחירה). בתיאור המחסניות סדר האיברים אינו חשוב לפעולה - חשוב רק אילו איברים בהן.
זימון 1: what({43, -3, 8, 9, 12, -9, 7, 3, 1})
, לכן eraseSmalls(m1, ): נמחקים 4 הקטנים ביותר ב-m1, כלומר -9, -3, 1, 3, ונשאר m1 = {7}. מבצעים return what({7}).
זימון 2: what({7})
, ולכן שני התנאים אינם מתקיימים ומוחזר a = 7. הערך 7 חוזר לזימון 1, שמחזיר אותו.
לבחירה אחרת התוצאה זהה. למשל a = -3: m1 = {-9} (k1 = 1), m2 = {43, 8, 9, 12, 7, 3, 1} (k2 = 7); מוחקים מ-m2 את 2 הגדולים (43, 12) ונשאר {8, 9, 7, 3, 1}; בזימון הבא, למשל a = 3: m1 = {1}, m2 = {8, 9, 7}; מוחקים את 2 הגדולים (9, 8) ונשאר {7}, ומוחזר 7.
תשובה: what(s) מחזירה 7.
סעיף ב
מחזירה את החציון של המחסנית - האיבר האמצעי, שמספר האיברים הגדולים ממנו שווה למספר האיברים הקטנים ממנו.
1. a נבחר באקראי; m1 מכילה את האיברים הקטנים ממנו ו-m2 את האיברים הגדולים ממנו.
2. אם , מתחת ל-a ומעליו יש אותו מספר איברים - a הוא בדיוק האיבר האמצעי (החציון), והוא מוחזר.
3. אם , החציון נמצא ב-m1 (בין הקטנים). מוחקים מ-m1 את הקטנים ביותר: כך "מאזנים" - מורידים מהצד הקטן כמה איברים שירדו מהצד הגדול ( האיברים של m2 ועוד a). החציון של מה שנשאר ב-m1 הוא החציון של המחסנית המקורית, והרקורסיה ממשיכה עליו. מספר האיברים שנשאר, , שוב אי-זוגי, כי זוגי.
4. המקרה סימטרי (מוחקים מ-m2 את הגדולים).
5. בכל זימון המחסנית קטנה, ולכן הרקורסיה מסתיימת.
בדוגמה: הסדר הממוין הוא -9, -3, 1, 3, 7, 8, 9, 12, 43, והאיבר האמצעי הוא 7.
תשובה: הפעולה מחזירה את החציון - האיבר שמספר האיברים הקטנים ממנו שווה למספר האיברים הגדולים ממנו.
סעיף ג
מעבירים את m למחסנית עזר; כל איבר קטן מ-a נדחף גם למחסנית התוצאה; בסוף מחזירים את האיברים מהעזר ל-m ומחזירים את מחסנית התוצאה.
הרעיון: אפשר לגשת רק לראש המחסנית, ולכן מוציאים את כל איברי m אחד-אחד. כל איבר נשמר במחסנית עזר temp (כדי לשחזר את m בסוף), ואם הוא קטן מ-a - נדחף גם למחסנית החדשה smalls. אחרי הלולאה מחזירים את האיברים מ-temp ל-m (הסדר המקורי משוחזר), ומחזירים את smalls.
סיבוכיות: - כל איבר יוצא ונכנס מספר קבוע של פעמים.
public static Stack<Integer> createSmall(Stack<Integer> m, int a)
{
Stack<Integer> temp = new Stack<Integer>();
Stack<Integer> smalls = new Stack<Integer>();
while (!m.isEmpty())
{
int x = m.pop();
if (x < a)
smalls.push(x);
temp.push(x);
}
while (!temp.isEmpty()) // שחזור m
m.push(temp.pop());
return smalls;
}public static Stack<int> CreateSmall(Stack<int> m, int a)
{
Stack<int> temp = new Stack<int>();
Stack<int> smalls = new Stack<int>();
while (!m.IsEmpty())
{
int x = m.Pop();
if (x < a)
smalls.Push(x);
temp.Push(x);
}
while (!temp.IsEmpty()) // שחזור m
m.Push(temp.Pop());
return smalls;
}תשובה: הפעולה שלמעלה.
סעיף ד
סופרים את האיברים (numOf), מגרילים מקום place בין 0 ל-count-1, מוציאים למחסנית עזר את place האיברים העליונים, קוראים את האיבר שבראש (top), משחזרים את המחסנית ומחזירים את האיבר.
הרעיון: הפעולה צריכה להחזיר איבר מהמחסנית (ולא סתם מספר אקראי), וכל איבר צריך להיבחר באותה הסתברות.
1. סופרים את האיברים: count = numOf(m).
2. מגרילים מקום place בין 0 ל- (מספר האיברים שנמצאים מעל האיבר שייבחר).
3. מוציאים place איברים מ-m למחסנית עזר temp; עכשיו האיבר שנבחר נמצא בראש m וקוראים אותו ב-top (בלי להוציא).
4. מחזירים את האיברים מ-temp ל-m כדי ש-m לא תשתנה, ומחזירים את האיבר שנבחר.
הנחה: המחסנית אינה ריקה. סיבוכיות: .
public static int randChoice (Stack<Integer> m)
{
Random rand = new Random();
int count = numOf(m); // מספר האיברים
int place = rand.nextInt(count); // 0 עד count-1
Stack<Integer> temp = new Stack<Integer>();
for (int i = 0; i < place; i++) // מוציאים את האיברים שמעליו
temp.push(m.pop());
int chosen = m.top(); // האיבר שנבחר
while (!temp.isEmpty()) // משחזרים את המחסנית
m.push(temp.pop());
return chosen;
}public static int RandChoice (Stack<int> m)
{
Random rand = new Random();
int count = NumOf(m); // מספר האיברים
int place = rand.Next(0, count); // 0 עד count-1
Stack<int> temp = new Stack<int>();
for (int i = 0; i < place; i++) // מוציאים את האיברים שמעליו
temp.Push(m.Pop());
int chosen = m.Top(); // האיבר שנבחר
while (!temp.IsEmpty()) // משחזרים את המחסנית
m.Push(temp.Pop());
return chosen;
}תשובה: הפעולה שלמעלה.
שאלה 10 · בדיקת תור מחסניות מושלם
תור מחסניות נקרא תור מושלם אם הוא עונה על שלושת התנאים הבאים:
•הערכים בכל מחסנית הם סדרה עולה (הערך הקטן ביותר נמצא בראש המחסנית).
•האורכים של המחסניות (מספר האיברים בכל מחסנית) הם סדרה עולה (המחסנית הקצרה ביותר נמצאת בראש התור).
•איבר הנמצא בראש כל מחסנית שווה לאיבר הנמצא בתחתית המחסנית הקודמת לה בתור.
לדוגמה: תור מחסניות הבא הוא תור מושלם:

כתבו פעולה המקבלת תור מחסניות ובודקת אם הוא תור מושלם. אם כן – הפעולה תחזיר true, ואם לא – הפעולה תחזיר false.
כותרת הפעולה:
public static boolean isPerfect(Queue <Stack<Integer>> q)public static bool IsPerfect(Queue <Stack<int>> q)מהי סיבוכיות הפעולה isPerfect?
◂ פתרון מלא לשאלה 10
סעיף א
עוברים על המחסניות לפי סדר התור ושומרים את האורך ואת התחתית של המחסנית הקודמת; כל מחסנית חייבת להיות עולה מהראש לתחתית (isAscending), ארוכה ממש מהקודמת (count), וראשה שווה לתחתית הקודמת (bottom); אחרת מחזירים false. התור משוחזר בסוף.
הרעיון: בודקים כל מחסנית לפי סדר התור, ושומרים שני נתונים על המחסנית הקודמת: האורך שלה (prevLen) והאיבר שבתחתיתה (prevBottom). לכל מחסנית s בודקים:
1. הערכים ב-s עולים מהראש לתחתית;
2. (מהמחסנית השנייה והלאה) האורך של s גדול ממש מ-prevLen;
3. (מהמחסנית השנייה והלאה) הראש של s שווה ל-prevBottom.
אם אחד התנאים נכשל - התור אינו מושלם. כדי לא להרוס את התור, כל מחסנית שמוצאת נשמרת בתור עזר temp, ובסוף מחזירים את כולן ל-q (גם אם נמצאה בעיה, ממשיכים רק להעביר בלי לבדוק). כל פעולות העזר משחזרות את המחסנית שקיבלו.
הנחה: כל המחסניות בתור אינן ריקות. תור ריק או תור עם מחסנית אחת עולה נחשב מושלם.
פעולות עזר ( = מספר האיברים במחסנית):
•`count(s)` - מקבלת מחסנית s ומחזירה את מספר האיברים בה; המחסנית נשמרת. .
•`bottom(s)` - מקבלת מחסנית לא ריקה s ומחזירה את האיבר שבתחתיתה; המחסנית נשמרת. .
•`isAscending(s)` - מקבלת מחסנית s ומחזירה true אם הערכים בה עולים ממש מהראש לתחתית; המחסנית נשמרת. . בכל שלב משווים את האיבר שיצא עכשיו לאיבר שיצא לפניו (שנמצא בראש temp): הוא חייב להיות גדול ממנו.
// מחזירה את מספר האיברים במחסנית s. המחסנית נשמרת. O(m)
public static int count(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
int c = 0;
while (!s.isEmpty())
{
c++;
temp.push(s.pop());
}
while (!temp.isEmpty())
s.push(temp.pop());
return c;
}
// מחזירה את האיבר שבתחתית מחסנית לא ריקה s. המחסנית נשמרת. O(m)
public static int bottom(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
while (!s.isEmpty())
temp.push(s.pop());
int x = temp.top(); // התחתית של s נמצאת עכשיו בראש temp
while (!temp.isEmpty())
s.push(temp.pop());
return x;
}
// מחזירה true אם ערכי s עולים ממש מהראש לתחתית. המחסנית נשמרת. O(m)
public static boolean isAscending(Stack<Integer> s)
{
Stack<Integer> temp = new Stack<Integer>();
boolean ok = true;
while (!s.isEmpty())
{
int x = s.pop();
if (!temp.isEmpty() && temp.top() >= x) // האיבר הקודם אינו קטן ממנו
ok = false;
temp.push(x);
}
while (!temp.isEmpty())
s.push(temp.pop());
return ok;
}
public static boolean isPerfect(Queue <Stack<Integer>> q)
{
Queue<Stack<Integer>> temp = new Queue<Stack<Integer>>();
boolean ok = true;
boolean first = true;
int prevLen = 0, prevBottom = 0;
while (!q.isEmpty())
{
Stack<Integer> s = q.remove();
temp.insert(s);
if (ok)
{
int len = count(s);
if (!isAscending(s))
ok = false; // תנאי 1
else if (!first && len <= prevLen)
ok = false; // תנאי 2
else if (!first && s.top() != prevBottom)
ok = false; // תנאי 3
prevLen = len;
prevBottom = bottom(s);
first = false;
}
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return ok;
}// מחזירה את מספר האיברים במחסנית s. המחסנית נשמרת. O(m)
public static int Count(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
int c = 0;
while (!s.IsEmpty())
{
c++;
temp.Push(s.Pop());
}
while (!temp.IsEmpty())
s.Push(temp.Pop());
return c;
}
// מחזירה את האיבר שבתחתית מחסנית לא ריקה s. המחסנית נשמרת. O(m)
public static int Bottom(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
while (!s.IsEmpty())
temp.Push(s.Pop());
int x = temp.Top(); // התחתית של s נמצאת עכשיו בראש temp
while (!temp.IsEmpty())
s.Push(temp.Pop());
return x;
}
// מחזירה true אם ערכי s עולים ממש מהראש לתחתית. המחסנית נשמרת. O(m)
public static bool IsAscending(Stack<int> s)
{
Stack<int> temp = new Stack<int>();
bool ok = true;
while (!s.IsEmpty())
{
int x = s.Pop();
if (!temp.IsEmpty() && temp.Top() >= x) // האיבר הקודם אינו קטן ממנו
ok = false;
temp.Push(x);
}
while (!temp.IsEmpty())
s.Push(temp.Pop());
return ok;
}
public static bool IsPerfect(Queue <Stack<int>> q)
{
Queue<Stack<int>> temp = new Queue<Stack<int>>();
bool ok = true;
bool first = true;
int prevLen = 0, prevBottom = 0;
while (!q.IsEmpty())
{
Stack<int> s = q.Remove();
temp.Insert(s);
if (ok)
{
int len = Count(s);
if (!IsAscending(s))
ok = false; // תנאי 1
else if (!first && len <= prevLen)
ok = false; // תנאי 2
else if (!first && s.Top() != prevBottom)
ok = false; // תנאי 3
prevLen = len;
prevBottom = Bottom(s);
first = false;
}
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return ok;
}בדיקה על הדוגמה: אורכים 3, 5, 6, 7, 8 (עולים); כל מחסנית עולה מהראש לתחתית; ראשים מול תחתיות קודמות: , , , . מוחזר true.
תשובה: הפעולה isPerfect עם פעולות העזר שלמעלה.
סעיף ב
, כאשר מספר המחסניות בתור ו- אורך המחסנית הארוכה (כלומר לינארי במספר האיברים הכולל); כל פעולת עזר היא .
נסמן ב- את מספר המחסניות בתור וב- את מספר האיברים במחסנית הארוכה ביותר.
1. כל פעולת עזר (count, bottom, isAscending) מעבירה את איברי המחסנית למחסנית עזר ובחזרה: .
2. בכל סיבוב של הלולאה ב-isPerfect מופעלות שלוש פעולות עזר על מחסנית אחת, ועוד מספר קבוע של פעולות תור: לסיבוב.
3. יש סיבובים, ועוד לולאת שחזור של .
סך הכול . בפועל זה אפילו לינארי במספר האיברים הכולל בכל המחסניות: , כי כל מחסנית נסרקת מספר קבוע של פעמים.
תשובה: ; פעולות העזר - כל אחת.