דילוג לתוכן המרכזי

מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2023 מועד א'

הנדסת תוכנה · סמל 97105 · 10 שאלות · פתרון מלא לכל סעיף

מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2023 מועד א', כל 10 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.

הנחיות הבחינה

משך הבחינה: ארבע שעות וחצי.

מבנה השאלון: בשאלון זה שני מבחנים, עליכם לענות על מבחן אחד בלבד בהתאם למוסד הלימודים:

מבחן ב- Java (עמוד 2)

מבחן ב- C# (עמוד 14)

בכל מבחן 10 שאלות.

חלק א' – 48 נקודות

שאלות 1-4: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.

חלק ב' – 36 נקודות

שאלות 5-8: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.

חלק ג' – 16 נקודות

שאלות 9-10: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.

בסך הכול: 100 נקודות.

חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).

2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.

אין לצרף ספרים או חוברות עם פתרונות.

שאלה 1 · ממוצעי ציונים מתור ציונים ותור בחינות

ציוני תלמידים שמורים בשני תורים: תור ראשון מכיל ציונים ותור שני מכיל עבור כל אחד מהתלמידים את מספר הבחינות שהשלים.

לדוגמה:

תור ציונים marks: (באיור הראשון לשאלה)

תור בחינות tests: (באיור השני לשאלה)

תלמיד ראשון השלים שלוש בחינות וקיבל את הציונים הבאים: 80, 90, 100.

תלמיד שני השלים שתי בחינות וקיבל את הציונים הבאים: 75, 96.

תלמיד שלישי השלים ארבע בחינות וקיבל את הציונים הבאים: 100, 100, 97, 96.

תלמיד רביעי השלים שתי בחינות וקיבל את הציונים הבאים: 94, 88.

א.

כתבו פעולה בשם averageQueue המקבלת שני תורים ומחזירה תור חדש של ממוצעי ציונים של כל התלמידים יחד.

עבור שני התורים שבדוגמה הפעולה תחזיר תור חדש המכיל את ממוצע הציונים של כל אחד מבין ארבעת התלמידים (התור באיור לסעיף).

כותרת הפעולה:

Java:

public static Queue<Double> averageQueue(Queue<Integer> marks,
                                         Queue<Integer> tests)

C#:

public static Queue<double> AverageQueue(Queue<int> marks,
                                         Queue<int> tests)
(12 נקודות)
ב.

מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.

(4 נקודות)
◂ פתרון מלא לשאלה 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` - ההמרה חשובה, אחרת יתבצע חילוק שלמים (למשל 171/2171/2 ייתן 85 במקום 85.5).

5. מכניסים את הממוצע ל-result. בסוף מחזירים את result.

הערה: הפעולה מרוקנת את שני התורים שהתקבלו (השאלה אינה דורשת לשמור עליהם).

Java:

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;
}

C#:

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;
}

בדיקה על הדוגמה:

תלמידnumציוניםsumממוצע
1380, 90, 100270270/3=90.0270/3=90.0
2275, 96171171/2=85.5171/2=85.5
34100, 100, 97, 96393393/4=98.25393/4=98.25
4288, 94182182/2=91.0182/2=91.0

תשובה: הפעולה שלמעלה; עבור הדוגמה מוחזר התור 90.0, 85.5, 98.25, 91.0 (90.0 בראש התור).

סעיף ב

תשובה:

O(n)O(n), כאשר nn הוא מספר הציונים בתור marks (התור הארוך) - כל איבר בכל אחד מהתורים מוצא פעם אחת בדיוק.

נסמן ב-nn את מספר הציונים בתור marks וב-kk את מספר התלמידים (אורך tests). מתקיים k≤nk \le n, כי לכל תלמיד יש לפחות בחינה אחת.

1. הלולאה החיצונית מבצעת kk סיבובים - בכל סיבוב מוציאים איבר אחד מ-tests.

2. הלולאה הפנימית מוציאה בכל סיבוב ציון אחד מ-marks. בסך כל הסיבובים של כל התלמידים יחד מוצאים בדיוק nn ציונים (כל ציון מוצא פעם אחת).

3. כל פעולה על תור (remove, insert, isEmpty) היא O(1)O(1).

לכן זמן הריצה הכולל הוא O(k+n)=O(n)O(k+n)=O(n) - סורקים כל אחד מהתורים פעם אחת בלבד.

תשובה: O(n)O(n), כאשר nn הוא אורך התור הארוך (marks).

שאלה 2 · מספר גדול כשרשרת ספרות: ספירה והשוואה

אפשר לייצג מספר שלם חיובי גדול מאוד כשרשרת חוליות כאשר כל חוליה מכילה ספרה אחת של המספר.

החוליה האחרונה מכילה ספרת האחדות.

לדוגמה:

המספר 2321418 (במילים: "שני מיליון שלוש מאות עשרים ואחד אלף ארבע מאות ושמונה עשרה"), מיוצג על ידי שרשרת החוליות הבאה:

א.

כתבו פעולה חיצונית בשם numDigits המקבלת הפניה לחוליה ראשונה של שרשרת חוליות המייצגת מספר שלם וחיובי. הפעולה תחזיר כמות ספרות של מספר.

כותרת הפעולה:

Java:

public static int numDigits(Node<Integer> n)

C#:

public static int NumDigits(Node<int> n)
(5 נקודות)
ב.

כתבו פעולה חיצונית בשם compare המקבלת הפניות לשתי שרשראות חוליות n1 ו-n2 המייצגות שני מספרים שלמים חיוביים.

אם המספר המיוצג בשרשרת הראשונה גדול מהמספר המיוצג בשרשרת השנייה, הפעולה תחזיר 1.

אם המספר המיוצג בשרשרת הראשונה קטן מהמספר המיוצג בשרשרת השנייה, הפעולה תחזיר 2.

אם שני מספרים שווים, הפעולה תחזיר 0.

כותרת הפעולה:

Java:

public static int compare(Node<Integer> n1, Node<Integer> n2)

C#:

public static int Compare(Node<int> n1, Node<int> n2)
(8 נקודות)
ג.

מהי סיבוכיות הפעולה compare מהסעיף הקודם? הסבירו את תשובתכם.

(3 נקודות)
◂ פתרון מלא לשאלה 2

סעיף א

תשובה:

מספר הספרות שווה למספר החוליות בשרשרת - סופרים את החוליות במעבר אחד (עבור הדוגמה: 7).

הרעיון: כל חוליה מכילה ספרה אחת, ולכן מספר הספרות הוא בדיוק מספר החוליות. עוברים על השרשרת עם הפניה pos מהחוליה הראשונה ועד הסוף (null), ומקדמים מונה בכל חוליה.

Java:

public static int numDigits(Node<Integer> n)
{
    int count = 0;
    Node<Integer> pos = n;
    while (pos != null)
    {
        count++;               // חוליה = ספרה
        pos = pos.getNext();
    }
    return count;
}

C#:

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.

Java:

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;
}

C#:

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 - אורך שווה, ההבדל הראשון בספרה החמישית (4<54<5) ולכן מוחזר 2. 99 מול 100 - לראשון פחות ספרות, מוחזר 2. 51 מול 51 - מוחזר 0.

תשובה: הפעולה שלמעלה.

סעיף ג

תשובה:

O(n)O(n), כאשר nn הוא אורך השרשרת הארוכה - כל שרשרת נסרקת מספר קבוע של פעמים.

נסמן ב-nn את מספר החוליות בשרשרת הארוכה מבין השתיים.

1. שתי הקריאות ל-numDigits סורקות כל שרשרת פעם אחת: O(n)O(n).

2. אם האורכים שונים - חוזרים מיד.

3. אם האורכים שווים, לולאת ההשוואה עוברת לכל היותר פעם אחת על כל השרשראות, ובכל סיבוב מבצעת מספר קבוע של פעולות: O(n)O(n).

סך הכול O(n)+O(n)=O(n)O(n)+O(n)=O(n).

תשובה: O(n)O(n) - סורקים כל שרשרת מספר קבוע של פעמים (פעמיים לכל היותר).

שאלה 3 · ירושה: היגדים, המרות והפעולה instanceof

נתונות שתי המחלקות Fruit ו-Apple.

Java:

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;
     }
}

C#:

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())

(5 נקודות)
ב.

לפניכם קטע קוד מהפעולה הראשית ( main ) של המחלקה TestFruit:

Java:

Fruit     first = new Apple (100, "RED");
Fruit     second = new Fruit (90);
Apple     third = new Apple(100, "RED");

C#:

Fruit     first = new Apple (100, "RED");
Fruit     second = new Fruit (90);
Apple     third = new Apple(100, "RED");

בעבור כל אחת מההוראות שלפניכם קבעו אם היא תקינה או אינה תקינה.

אם היא אינה תקינה, כתבו אם זו שגיאת ריצה או שגיאת הידור (קומפילציה).

Java:

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);

C#:

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);
(5 נקודות)
ג.

כתבו פעולה המקבלת מערך עצמים מטיפוס Object. הפעולה תדפיס כמה עצמים הם מטיפוס Apple, כמה עצמים מטיפוס Fruit ואינו מטיפוס Apple וכמה עצמים הם לא מטיפוס Fruit.

(6 נקודות)
◂ פתרון מלא לשאלה 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שגיאת הידורfirst מוצהר כ-Fruit, ול-Fruit אין פעולה validWeight(). המהדר אינו "יודע" שהעצם הוא Apple.
2שגיאת הידוראותה סיבה: second מטיפוס Fruit, אין בו validWeight().
3תקינהההמרה (Apple)first מתקבלת אצל המהדר, ובזמן ריצה העצם הוא באמת Apple. weight = 100, ולכן 80<100<14080<100<140 ו-b = true.
4שגיאת ריצההמהדר מאשר המרה מ-Fruit ל-Apple, אבל העצם ש-second מפנה אליו נוצר כ-Fruit ומעולם לא היה Apple; ההמרה נכשלת בזמן ריצה (ClassCastException ב-Java, InvalidCastException ב-C#).
5שגיאת הידורcolor מוגדרת private ב-Apple, ולכן אי אפשר לפנות אליה ישירות מתוך הפעולה הראשית של מחלקה אחרת (TestFruit).

תשובה: 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.

Java:

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);
}

C#:

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 · שרשור בנאים, דריסה והעמסה

נתונות שלוש המחלקות הבאות:

Java:

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);
    }
}

C#:

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 ורשמו מה יהיה הפלט. יש להראות את העצמים שנוצרו ואת ערכי התכונות שלהם.

(10 נקודות)
ב.

לכל אחת מהפעולות הבאות קבעו אם אפשר להוסיף אותה במחלקה A, וציינו את האפשרות המתאימה מבין האפשרויות הבאות:

•שגיאת קומפילציה.

•קוד תקין, דריסה (overriding).

•קוד תקין, העמסה (overloading).

Java:

1. public int method () { return 1; }
2. public double method (int i){ return i; }
3. public void method (double i){ System.out.print(i); }

C#:

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); }
(3 נקודות)
ג.

אין קשר לסעיף ב'.

לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה B וציינו את האפשרות המתאימה מבין האפשרויות הבאות:

•שגיאת קומפילציה.

•קוד תקין, דריסה (overriding).

•קוד תקין, העמסה (overloading).

Java:

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); }

C#:

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); }
(3 נקודות)
◂ פתרון מלא לשאלה 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`.

העצמים שנוצרו:

הפניהטיפוס העצםxy
a1B168
a2A6-
a3B168
b1A5-
c1B50

הפלט:

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-.

כותרת הפעולה:

Java:

public static int distance(Node<Integer> lst, int num)

C#:

public static int Distance(Node<int> lst, int num)
(7 נקודות)
ב.

כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות ומחזירה את המספר בעל ה"מרחק" הקטן ביותר.

עבור השרשרת הבאה הפעולה תחזיר 9 ( ה"מרחק" של הערך 9 הוא הקטן ביותר).

כותרת הפעולה:

Java:

public static int minDistanceValue(Node<Integer> lst)

C#:

public static int MinDistanceValue(Node<int> lst)
(7 נקודות)
ג.

מהן סיבוכיות של הפעולות Distance ו-MinDistanceValue מסעיפים א' ו- ב'? הסבירו את תשובתכם.

(4 נקודות)
◂ פתרון מלא לשאלה 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.

Java:

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;
}

C#:

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; מוחזר 3+2=53+2=5.

•num = 3: dist1 = 2, dist2 = 7; מוחזר 2+7=92+7=9.

•num = 5: לא נמצא; מוחזר 1-.

תשובה: הפעולה שלמעלה.

סעיף ב

תשובה:

עוברים על כל חוליה, מחשבים לערך שבה את distance(lst, value) מסעיף א', ושומרים את הערך שהמרחק שלו הקטן ביותר; בדוגמה מוחזר 9 (מרחק 1).

הרעיון: חיפוש מינימום רגיל, כשה"מפתח" של כל ערך הוא המרחק שלו, המחושב בעזרת distance מסעיף א'.

1. מאתחלים את המועמד minNum לערך שבחוליה הראשונה ואת minDis למרחק שלו.

2. עוברים על שאר החוליות; לכל ערך מחשבים את המרחק שלו. אם הוא קטן מ-minDis - מעדכנים את minNum ואת minDis.

3. מחזירים את minNum. (במקרה של שוויון נשאר הערך שהופיע ראשון בשרשרת.)

הנחה: השרשרת אינה ריקה.

Java:

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;
}

C#:

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;
}

בדיקה על הדוגמה:

ערךחוליות לפני המופע הראשוןחוליות אחרי המופע האחרוןמרחק
4099
9101
3279
7325
2819

המרחק הקטן ביותר הוא 1, של הערך 9.

תשובה: הפעולה שלמעלה; עבור הדוגמה מוחזר 9.

סעיף ג

תשובה:

distance: O(n)O(n) - מעבר אחד על השרשרת; minDistanceValue: O(n2)O(n^2) - לכל אחת מ-nn החוליות מופעלת distance שעולה O(n)O(n).

נסמן ב-nn את מספר החוליות בשרשרת.

1. distance: שתי הלולאות יחד עוברות על כל חוליה בשרשרת פעם אחת לכל היותר (הלולאה השנייה ממשיכה מהמקום שבו עצרה הראשונה), ובכל חוליה מתבצע מספר קבוע של פעולות. לכן O(n)O(n).

2. minDistanceValue: הלולאה עוברת על nn חוליות, ובכל חוליה מופעלת distance שעולה O(n)O(n). לכן n⋅O(n)=O(n2)n \cdot O(n)=O(n^2).

תשובה: distance - O(n)O(n); minDistanceValue - O(n2)O(n^2).

שאלה 6 · היררכיית מחלקות וממשקים של ענפי ספורט

נתונה היררכיית המחלקות הבאה הכוללת שש מחלקות: Sport, MRace, RGymnastic, Ball, TTennis, BBall ושני ממשקים: IHall ו-IGroup.

בכל מחלקה מוגדרת פעולה בונה ללא פרמטרים.

א.

כתבו עבור כל מחלקה, את כותרת המחלקה.

(3 נקודות)
ב.

עבור כל אחת מהפקודות הבאות קבעו אם היא נכונה או אינה נכונה. נמקו את קביעתכם.

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();
(6 נקודות)
ג.

כתבו פעולה המקבלת מערך עצמים מסוג Sport. הפעולה תחזיר מספר עצמים המייצגים ענף ספורט קבוצתי שמתקיים באולם.

כותרת הפעולה:

Java:

public static int count (Sport[] s)

C#:

public static int Count (Sport[] s)

שימו לב: יש לכתוב את הפעולה כך שהיא תעבוד נכון גם כאשר יתווספו לפרויקט מחלקות נוספות, כמו VBall (כדורעף), HBall (כדוריד) וכד'

(6 נקודות)
ד.

רוצים להוסיף לפרויקט מחלקה חדשה המתארת כדורגל. האם אפשר להוסיף את המחלקה FBall תוך שמירה על היררכיה קיימת או שיש לשנות את ההיררכיה? ציירו תרשים של היררכיית המחלקות החדשה (כולל את המחלקה FBall).

(3 נקודות)
◂ פתרון מלא לשאלה 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 (ספורט קבוצתי).

Java:

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 IGroup

C#:

public 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נכונהBBall יורשת מ-Ball, ש-יורשת מ-Sport; לכן BBall היא Sport.
2נכונהMRace יורשת ישירות מ-Sport.
3לא נכונהBall אינה TTennis (הירושה בכיוון ההפוך: TTennis יורשת מ-Ball). שגיאת הידור.
4לא נכונהIGroup הוא ממשק - אסור ליצור ממנו עצם ב-new. שגיאת הידור.
5נכונהBall מממשת את IHall.
6נכונהTTennis יורשת מ-Ball, שמממשת את IHall, ולכן גם TTennis היא IHall.

תשובה: 1 - נכונה; 2 - נכונה; 3 - לא נכונה; 4 - לא נכונה; 5 - נכונה; 6 - נכונה.

סעיף ג

תשובה:

סופרים את העצמים שמקיימים גם instanceof IGroup וגם instanceof IHall (ב-C#: is IGroup && is IHall).

הרעיון: "ספורט קבוצתי" מיוצג על ידי הממשק IGroup, ו"ספורט באולם" - על ידי IHall. ענף שהוא גם קבוצתי וגם באולם הוא עצם שמממש את שני הממשקים.

כדי שהפעולה תעבוד גם כשיתווספו מחלקות חדשות (VBall, HBall וכו'), לא בודקים שמות מחלקות מסוימות (כמו instanceof BBall), אלא בודקים את הממשקים. כל מחלקה חדשה שתממש את IGroup ואת IHall (במישרין או בירושה) תיספר אוטומטית, בלי לשנות את הפעולה.

Java:

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;
}

C#:

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.

כותרות המחלקות שהשתנו (Java):

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 IGroup

C#:

public 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 · סריקות תוכית ותחילית של עץ בינרי

לפניכם הפעולות הבאות:

Java:

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;
}

C#:

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)? חובה להראות את המעקב!

(7 נקודות)
ב.

לפעולה what הועברה כפרמטר הפניה לשורש של עץ בינרי. המחרוזת שהוחזרה מהשיטה היא:

`(((30) 20 ((50) 5)) 40 (10))`

ציירו את העץ הבינרי שהועבר כפרמטר פעולה.

(7 נקודות)
ג.

האם קיים עץ בינארי bt בעל שלושה צמתים לפחות שעבורו תוצאת זימון הפעולה what(bt) תהיה זהה לתוצאת זימון הפעולה why(bt)? אם כן – ציירו את העץ, אם לא – הסבירו מדוע.

(4 נקודות)
◂ פתרון מלא לשאלה 7

סעיף א

תשובה:

((1(9))4((2)20(7)))

מה עושה what: לכל צומת היא כותבת סוגר פותח, אחריו את התוצאה של תת-העץ השמאלי (אם יש), את ערך הצומת, את התוצאה של תת-העץ הימני (אם יש) וסוגר סוגר. זו סריקה תוכית (שמאל-שורש-ימין), כשכל תת-עץ עטוף בסוגריים.

בעץ: השורש 4; בן שמאלי 1 (עם בן ימני 9); בן ימני 20 (עם בן שמאלי 2 ובן ימני 7).

מעקב (מהעלים כלפי מעלה):

זימוןבן שמאליערךבן ימנימוחזר
what(9)-9-`(9)`
what(1)-1`(9)``(1(9))`
what(2)-2-`(2)`
what(7)-7-`(7)`
what(20)`(2)`20`(7)``((2)20(7))`
what(4)`(1(9))`4`((2)20(7))``((1(9))4((2)20(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

Java:

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 Two
public 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);
    }
}

C#:

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 Two
public 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);
    }
}
א.

עקבו אחרי ביצוע הפעולה הראשית ורשמו מה יהיה הפלט של הפעולה.

יש להציג את כל העצמים שנוצרו ואת השינויים בערכי התכונות שלהם במהלך הביצוע.

(15 נקודות)
ב.

מה מבצעת הפעולה what?

(3 נקודות)
◂ פתרון מלא לשאלה 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]` אינה יוצרת עצם חדש: שני התאים מפנים לאותו עצם.

יצירת העצמים (5 עצמים בלבד):

תאיצירהחישוב xx
arr[0]new One()x=1x=11
arr[1]new One(3)x=3x=33
arr[2]new Two()super(3): x=3x=33
arr[3]new Two(2)One(): x=1x=1; super.f(2): 1+2=31+2=3; f(2) של Two: 3−2=13-2=1, ואז 1+2=31+2=33
arr[4]new Two(5)One(): x=1x=1; super.f(5): 1+5=61+5=6; f(5) של Two: 6−5=16-5=1, ואז 1+5=61+5=66
arr[5]= arr[1]אותו עצם כמו arr[1]3

print ראשון: `0 x=1`, `1 x=3`, `2 x=3`, `3 x=3`, `4 x=6`, `5 x=3`.

doF(arr, 2) - מפעילה f(2) על כל תא לפי הסדר:

תאטיפוס העצםf שמופעלתx לפניx אחרי
0Oneשל One11+2=31+2=3
1Oneשל One33+2=53+2=5
2Twoשל Two33−2+2=33-2+2=3
3Twoשל Two33
4Twoשל Two66
5One (העצם של arr[1])של One55+2=75+2=7

העצם המשותף ל-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=6−3=3k=6-3=3 ומודפס `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. אחר כך k=arr.length−kk = arr.length - k: מספר התאים שאינם מטיפוס Two.

3. הפעולה מדפיסה את הערך הזה. בדוגמה: 6−3=36-3=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, המכילה מספר אי זוגי של מספרים שלמים, שכולם שונים זה מזה.

Java:

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;
}

C#:

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) עבור מחסנית הבאה ורשמו מה תהיה תוצאת הזימון.

יש להראות ערכי משתנים ותכנים של מחסניות בכל זימון הרקורסיבי.

(7 נקודות)
ב.

מה מבצעת הפעולה what עבור מחסנית המכילה מספר אי זוגי של מספרים שלמים, שכולם שונים זה מזה?

(3 נקודות)
ג.

ממשו את הפעולה createSmall.

(3 נקודות)
ד.

ממשו את הפעולה randChoice.

(3 נקודות)
◂ פתרון מלא לשאלה 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})

משתנהערך
a8
m1 (הקטנים מ-8){-3, -9, 7, 3, 1}
k15
m2 (הגדולים מ-8){43, 9, 12}
k23

k1>k2k1 > k2, לכן eraseSmalls(m1, k2+1=4k2+1=4): נמחקים 4 הקטנים ביותר ב-m1, כלומר -9, -3, 1, 3, ונשאר m1 = {7}. מבצעים return what({7}).

זימון 2: what({7})

משתנהערך
a7 (האיבר היחיד)
m1{}
k10
m2{}
k20

k1=k2k1 = k2, ולכן שני התנאים אינם מתקיימים ומוחזר 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 מכילה את k1k1 האיברים הקטנים ממנו ו-m2 את k2k2 האיברים הגדולים ממנו.

2. אם k1=k2k1 = k2, מתחת ל-a ומעליו יש אותו מספר איברים - a הוא בדיוק האיבר האמצעי (החציון), והוא מוחזר.

3. אם k1>k2k1 > k2, החציון נמצא ב-m1 (בין הקטנים). מוחקים מ-m1 את k2+1k2+1 הקטנים ביותר: כך "מאזנים" - מורידים מהצד הקטן כמה איברים שירדו מהצד הגדול (k2k2 האיברים של m2 ועוד a). החציון של מה שנשאר ב-m1 הוא החציון של המחסנית המקורית, והרקורסיה ממשיכה עליו. מספר האיברים שנשאר, k1−k2−1k1-k2-1, שוב אי-זוגי, כי k1+k2k1+k2 זוגי.

4. המקרה k2>k1k2 > k1 סימטרי (מוחקים מ-m2 את k1+1k1+1 הגדולים).

5. בכל זימון המחסנית קטנה, ולכן הרקורסיה מסתיימת.

בדוגמה: הסדר הממוין הוא -9, -3, 1, 3, 7, 8, 9, 12, 43, והאיבר האמצעי הוא 7.

תשובה: הפעולה מחזירה את החציון - האיבר שמספר האיברים הקטנים ממנו שווה למספר האיברים הגדולים ממנו.

סעיף ג

תשובה:

מעבירים את m למחסנית עזר; כל איבר קטן מ-a נדחף גם למחסנית התוצאה; בסוף מחזירים את האיברים מהעזר ל-m ומחזירים את מחסנית התוצאה.

הרעיון: אפשר לגשת רק לראש המחסנית, ולכן מוציאים את כל איברי m אחד-אחד. כל איבר נשמר במחסנית עזר temp (כדי לשחזר את m בסוף), ואם הוא קטן מ-a - נדחף גם למחסנית החדשה smalls. אחרי הלולאה מחזירים את האיברים מ-temp ל-m (הסדר המקורי משוחזר), ומחזירים את smalls.

סיבוכיות: O(n)O(n) - כל איבר יוצא ונכנס מספר קבוע של פעמים.

Java:

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;
}

C#:

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 ל-count−1count-1 (מספר האיברים שנמצאים מעל האיבר שייבחר).

3. מוציאים place איברים מ-m למחסנית עזר temp; עכשיו האיבר שנבחר נמצא בראש m וקוראים אותו ב-top (בלי להוציא).

4. מחזירים את האיברים מ-temp ל-m כדי ש-m לא תשתנה, ומחזירים את האיבר שנבחר.

הנחה: המחסנית אינה ריקה. סיבוכיות: O(n)O(n).

Java:

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;
}

C#:

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.

כותרת הפעולה:

Java:

public static boolean isPerfect(Queue <Stack<Integer>> q)

C#:

public static bool IsPerfect(Queue <Stack<int>> q)

הערה: אם כתבתם פעולות עזר חובה לתעד אותן (לציין פרמטרים שהפעולה מקבלת, הנחות, ותיאור של מה הפעולה מבצעת). כמו כן, יש לציין את הסיבוכיות של כל פעולת עזר שכתבתם.

(12 נקודות)
ב.

מהי סיבוכיות הפעולה isPerfect?

(4 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

עוברים על המחסניות לפי סדר התור ושומרים את האורך ואת התחתית של המחסנית הקודמת; כל מחסנית חייבת להיות עולה מהראש לתחתית (isAscending), ארוכה ממש מהקודמת (count), וראשה שווה לתחתית הקודמת (bottom); אחרת מחזירים false. התור משוחזר בסוף.

הרעיון: בודקים כל מחסנית לפי סדר התור, ושומרים שני נתונים על המחסנית הקודמת: האורך שלה (prevLen) והאיבר שבתחתיתה (prevBottom). לכל מחסנית s בודקים:

1. הערכים ב-s עולים מהראש לתחתית;

2. (מהמחסנית השנייה והלאה) האורך של s גדול ממש מ-prevLen;

3. (מהמחסנית השנייה והלאה) הראש של s שווה ל-prevBottom.

אם אחד התנאים נכשל - התור אינו מושלם. כדי לא להרוס את התור, כל מחסנית שמוצאת נשמרת בתור עזר temp, ובסוף מחזירים את כולן ל-q (גם אם נמצאה בעיה, ממשיכים רק להעביר בלי לבדוק). כל פעולות העזר משחזרות את המחסנית שקיבלו.

הנחה: כל המחסניות בתור אינן ריקות. תור ריק או תור עם מחסנית אחת עולה נחשב מושלם.

פעולות עזר (mm = מספר האיברים במחסנית):

•`count(s)` - מקבלת מחסנית s ומחזירה את מספר האיברים בה; המחסנית נשמרת. O(m)O(m).

•`bottom(s)` - מקבלת מחסנית לא ריקה s ומחזירה את האיבר שבתחתיתה; המחסנית נשמרת. O(m)O(m).

•`isAscending(s)` - מקבלת מחסנית s ומחזירה true אם הערכים בה עולים ממש מהראש לתחתית; המחסנית נשמרת. O(m)O(m). בכל שלב משווים את האיבר שיצא עכשיו לאיבר שיצא לפניו (שנמצא בראש temp): הוא חייב להיות גדול ממנו.

Java:

// מחזירה את מספר האיברים במחסנית 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;
}

C#:

// מחזירה את מספר האיברים במחסנית 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 (עולים); כל מחסנית עולה מהראש לתחתית; ראשים מול תחתיות קודמות: 7=77=7, 15=1515=15, 70=7070=70, 115=115115=115. מוחזר true.

תשובה: הפעולה isPerfect עם פעולות העזר שלמעלה.

סעיף ב

תשובה:

O(n⋅m)O(n \cdot m), כאשר nn מספר המחסניות בתור ו-mm אורך המחסנית הארוכה (כלומר לינארי במספר האיברים הכולל); כל פעולת עזר היא O(m)O(m).

נסמן ב-nn את מספר המחסניות בתור וב-mm את מספר האיברים במחסנית הארוכה ביותר.

1. כל פעולת עזר (count, bottom, isAscending) מעבירה את איברי המחסנית למחסנית עזר ובחזרה: O(m)O(m).

2. בכל סיבוב של הלולאה ב-isPerfect מופעלות שלוש פעולות עזר על מחסנית אחת, ועוד מספר קבוע של פעולות תור: O(m)O(m) לסיבוב.

3. יש nn סיבובים, ועוד לולאת שחזור של O(n)O(n).

סך הכול O(n⋅m)O(n \cdot m). בפועל זה אפילו לינארי במספר האיברים הכולל NN בכל המחסניות: O(N+n)O(N+n), כי כל מחסנית נסרקת מספר קבוע של פעמים.

תשובה: O(n⋅m)O(n \cdot m); פעולות העזר - O(m)O(m) כל אחת.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.