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

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

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

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

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

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

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

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

מבחן ב-JAVA (עמוד 14)

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

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

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

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

שאלות 6–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.

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

שאלות 11–12: יש לענות על שאלה אחת בלבד. ערך השאלה 16 נקודות.

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

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

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

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

שאלה 1 · מחסנית ייחודית – בדיקת חלוקה בין איברים

א.

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

כתבו פעולה המקבלת מחסנית S שאיבריה מספרים שלמים וחיוביים. אם המחסנית היא מחסנית ייחודית הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

(14 נקודות)
ב.

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

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

סעיף א

תשובה:

לכל איבר בודקים אם הוא מחלק או מתחלק באחד האיברים שמתחתיו; אם כן – false, אחרת true (המחסנית משוחזרת).

נתון: מחסנית `s` של מספרים שלמים וחיוביים.

מבוקש: להחזיר true אם אף איבר במחסנית אינו מתחלק באיבר אחר שלה (מחסנית ריקה – true).

הרעיון: צריך לבדוק כל זוג איברים. מספיק לבדוק כל זוג פעם אחת, אבל בשני הכיוונים: xx מתחלק ב-yy (`x % y == 0`) או yy מתחלק ב-xx (`y % x == 0`).

1. מוציאים מהמחסנית את האיבר העליון `x` (הוא עובר למחסנית העזר `temp1`).

2. משווים את `x` לכל האיברים שנשארו מתחתיו: מוציאים אותם אחד-אחד למחסנית עזר `temp2`, ובודקים את תנאי החלוקה בשני הכיוונים. אם אחד מהם מתקיים – המחסנית אינה ייחודית (`unique = false`).

3. מחזירים את האיברים מ-`temp2` ל-`s` (הסדר חוזר להיות המקורי), וממשיכים לאיבר הבא – כך כל זוג נבדק פעם אחת בדיוק.

4. כשנמצא זוג "אסור" אין טעם להמשיך, ולכן הלולאה החיצונית רצה רק כל עוד `unique` אמת.

5. בסוף מחזירים את כל האיברים מ-`temp1` ל-`s`, כך שהמחסנית חוזרת למצבה המקורי, ומחזירים את `unique`.

הערות:

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

•מחסנית ריקה או מחסנית עם איבר אחד – הלולאה לא מוצאת זוג "אסור", והתשובה true.

•דוגמאות: עבור 4,6,9,154, 6, 9, 15 התשובה true; עבור 4,6,124, 6, 12 התשובה false (12 מתחלק ב-4 וב-6).

כותרת הפעולה לא ניתנה בשאלה, ולכן נבחרה הכותרת שבקוד.

C#:

public static bool IsUnique(Stack<int> s)
{
    Stack<int> temp1 = new Stack<int>();
    bool unique = true;
    while (!s.IsEmpty() && unique)
    {
        int x = s.Pop();
        Stack<int> temp2 = new Stack<int>();
        while (!s.IsEmpty())              // השוואת x לכל האיברים שמתחתיו
        {
            int y = s.Pop();
            if (x % y == 0 || y % x == 0)
                unique = false;
            temp2.Push(y);
        }
        while (!temp2.IsEmpty())          // החזרת האיברים שמתחת ל-x
            s.Push(temp2.Pop());
        temp1.Push(x);
    }
    while (!temp1.IsEmpty())              // שחזור המחסנית
        s.Push(temp1.Pop());
    return unique;
}

Java:

public static boolean isUnique(Stack<Integer> s)
{
    Stack<Integer> temp1 = new Stack<Integer>();
    boolean unique = true;
    while (!s.isEmpty() && unique)
    {
        int x = s.pop();
        Stack<Integer> temp2 = new Stack<Integer>();
        while (!s.isEmpty())              // השוואת x לכל האיברים שמתחתיו
        {
            int y = s.pop();
            if (x % y == 0 || y % x == 0)
                unique = false;
            temp2.push(y);
        }
        while (!temp2.isEmpty())          // החזרת האיברים שמתחת ל-x
            s.push(temp2.pop());
        temp1.push(x);
    }
    while (!temp1.isEmpty())              // שחזור המחסנית
        s.push(temp1.pop());
    return unique;
}

תשובה: לכל איבר בודקים את כל האיברים שמתחתיו – אם אחד מהם מחלק אותו או מתחלק בו, מחזירים false; אחרת true. המחסנית משוחזרת בסוף.

סעיף ב

תשובה:

O(n2)O(n^2)

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

1. האיבר העליון מושווה ל-n−1n-1 האיברים שמתחתיו, והם מוצאים ומוחזרים: בערך 2(n−1)2(n-1) פעולות O(1)O(1).

2. האיבר הבא מושווה ל-n−2n-2 איברים, וכן הלאה עד 0.

3. סך הכול: (n−1)+(n−2)+⋯+1+0=n(n−1)2(n-1)+(n-2)+\dots+1+0=\frac{n(n-1)}{2} השוואות (ופי 2 פעולות הוצאה/החזרה), כלומר O(n2)O(n^2).

4. השחזור הסופי מ-`temp1` הוא עוד nn פעולות – O(n)O(n), שאינו משנה את הסדר.

במקרה הטוב (זוג "אסור" נמצא כבר בסיבוב הראשון) מספיק סיבוב אחד, O(n)O(n); במקרה הגרוע (מחסנית ייחודית) – O(n2)O(n^2).

תשובה: O(n2)O(n^2) – כל זוג איברים נבדק פעם אחת.

שאלה 2 · תור שווה סכומים

תור "שווה סכומים", הוא תור של מספרים שלמים המכיל מספר זוגי של איברים כך שסכומם של כל שני איברים קיצוניים (ראשון + אחרון, שני + לפני אחרון וכו') זהה.

לדוגמה:

התור הבא הוא "תור שווה סכומים"

7+18=257+18 = 25 (האיבר הראשון והאיבר האחרון)

22+3=2522+3 = 25 (האיבר השני והאיבר שלפני אחרון)

10+15=2510+15 = 25

12+13=2512+13 = 25

21+4=2521+4 = 25

א.

כתבו פעולה בשם EqualSums המקבלת תור של מספרים שלמים. אם התור הוא תור "שווה סכומים" הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר false.

(14 נקודות)
ב.

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

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

סעיף א

תשובה:

מעבר ראשון – העתקה לתור עזר ולמחסנית וספירה; מעבר שני – השוואת סכומי הזוגות הקיצוניים לסכום הזוג הראשון; true רק אם nn זוגי וכל הסכומים שווים.

נתון: תור `q` של מספרים שלמים.

מבוקש: להחזיר true אם מספר האיברים זוגי, וכל זוג איברים "קיצוניים" (ראשון + אחרון, שני + לפני אחרון וכו') נותן אותו סכום.

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

1. מעבר ראשון: מוציאים כל איבר מ-`q`, מכניסים אותו לתור עזר `temp` (כדי לשחזר את `q`), דוחפים אותו גם למחסנית `st`, וסופרים את האיברים – nn.

2. אם nn אי-זוגי – התור אינו "שווה סכומים" (`ok = false`), אבל ממשיכים כדי לשחזר את התור.

3. מעבר שני: מוציאים את האיברים מ-`temp` לפי הסדר (i=0,1,…,n−1i = 0, 1, \dots, n-1) ומחזירים כל אחד ל-`q`. בחצי הראשון (i<n/2i < n/2) שולפים במקביל איבר מ-`st` – זה בדיוק "בן הזוג" מהסוף.

4. הסכום של הזוג הראשון (i=0i=0) הוא הסכום הקובע `sum`; כל זוג אחר שסכומו שונה ממנו – `ok = false`.

5. בסוף `q` מכיל שוב את כל האיברים באותו סדר, ומחזירים את `ok`.

בדיקה עם הדוגמה: n=10n=10, והזוגות: 7+18=257+18=25, 22+3=2522+3=25, 10+15=2510+15=25, 12+13=2512+13=25, 21+4=2521+4=25 – כולם 25, ולכן מוחזר true.

תור ריק – יש בו 0 איברים (מספר זוגי) ואין זוג שמפר את התנאי, ולכן מוחזר true.

C#:

public static bool EqualSums(Queue<int> q)
{
    Queue<int> temp = new Queue<int>();
    Stack<int> st = new Stack<int>();
    int n = 0;
    while (!q.IsEmpty())              // מעבר ראשון: העתקה וספירה
    {
        int x = q.Remove();
        temp.Insert(x);
        st.Push(x);
        n++;
    }
    bool ok = (n % 2 == 0);
    int sum = 0;
    for (int i = 0; i < n; i++)       // מעבר שני: השוואה ושחזור
    {
        int x = temp.Remove();
        q.Insert(x);
        if (i < n / 2)
        {
            int y = st.Pop();         // האיבר המתאים מסוף התור
            if (i == 0)
                sum = x + y;
            else if (x + y != sum)
                ok = false;
        }
    }
    return ok;
}

Java:

public static boolean equalSums(Queue<Integer> q)
{
    Queue<Integer> temp = new Queue<Integer>();
    Stack<Integer> st = new Stack<Integer>();
    int n = 0;
    while (!q.isEmpty())              // מעבר ראשון: העתקה וספירה
    {
        int x = q.remove();
        temp.insert(x);
        st.push(x);
        n++;
    }
    boolean ok = (n % 2 == 0);
    int sum = 0;
    for (int i = 0; i < n; i++)       // מעבר שני: השוואה ושחזור
    {
        int x = temp.remove();
        q.insert(x);
        if (i < n / 2)
        {
            int y = st.pop();         // האיבר המתאים מסוף התור
            if (i == 0)
                sum = x + y;
            else if (x + y != sum)
                ok = false;
        }
    }
    return ok;
}

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

סעיף ב

תשובה:

O(n)O(n)

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

1. המעבר הראשון: nn סיבובים, ובכל אחד מספר קבוע של פעולות O(1)O(1) (remove, insert, push).

2. המעבר השני: עוד nn סיבובים של O(1)O(1) (remove, insert, ולכל היותר pop אחד והשוואה).

3. סך הכול 2n2n סיבובים, כלומר O(n)O(n).

תשובה: O(n)O(n) – שני מעברים על התור.

שאלה 3 · שרשרת מושלמת K

א.

שרשרת חוליות של מספרים שלמים נקראת "שרשרת מושלמת K" אם כל ערך בה מופיע בדיוק K פעמים. כתבו פעולה המקבלת הפניה לחוליה הראשונה בשרשרת חוליות ומספר שלם וחיובי K. הפעולה תבדוק אם השרשרת היא "שרשרת מושלמת K". אם כן – הפעולה תחזיר ערך true, אם לא – הפעולה תחזיר ערך false.

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

C#:

public static bool PerfectListK(Node<int> chain, int k)

Java:

public static boolean perfectListK(Node<Integer> chain, int k)
(14 נקודות)
ב.

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

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

סעיף א

תשובה:

לכל חוליה סופרים את מופעי הערך שלה בכל השרשרת; מונה שונה מ-K – false, אחרת true.

נתון: הפניה `chain` לחוליה הראשונה של שרשרת מספרים שלמים, ומספר שלם וחיובי `k`.

מבוקש: להחזיר true אם כל ערך בשרשרת מופיע בה בדיוק kk פעמים.

הרעיון: עוברים על החוליות אחת-אחת. לכל חוליה `p` סופרים, במעבר נוסף על כל השרשרת (מההתחלה), כמה פעמים מופיע הערך שלה. אם עבור ערך כלשהו המונה שונה מ-kk – אפשר לעצור ולהחזיר false. אם עברנו על כל החוליות ולא מצאנו ערך כזה – מחזירים true.

1. `p` עובר על כל חוליות השרשרת.

2. לכל `p`: `r` עובר על כל השרשרת מההתחלה, ו-`count` סופר את החוליות שערכן שווה לערך של `p`.

3. אם `count != k` – מחזירים false.

4. בסוף הלולאה – מחזירים true. (שרשרת ריקה: אין אף ערך שמפר את התנאי, ולכן true.)

השרשרת אינה משתנה – רק קוראים את הערכים.

דוגמה: עבור 3,5,3,5,5,33, 5, 3, 5, 5, 3 ו-k=3k=3 – כל ערך מופיע 3 פעמים, ומוחזר true; עבור 3,5,3,5,53, 5, 3, 5, 5 – הערך 3 מופיע פעמיים בלבד, ומוחזר false.

C#:

public static bool PerfectListK(Node<int> chain, int k)
{
    Node<int> p = chain;
    while (p != null)
    {
        int count = 0;
        Node<int> r = chain;
        while (r != null)                   // ספירת המופעים של הערך של p
        {
            if (r.GetValue() == p.GetValue())
                count++;
            r = r.GetNext();
        }
        if (count != k)
            return false;
        p = p.GetNext();
    }
    return true;
}

Java:

public static boolean perfectListK(Node<Integer> chain, int k)
{
    Node<Integer> p = chain;
    while (p != null)
    {
        int count = 0;
        Node<Integer> r = chain;
        while (r != null)                   // ספירת המופעים של הערך של p
        {
            if (r.getValue().equals(p.getValue()))
                count++;
            r = r.getNext();
        }
        if (count != k)
            return false;
        p = p.getNext();
    }
    return true;
}

(ב-Java משווים ערכים מטיפוס `Integer` בעזרת `equals`, כדי להשוות את הערכים ולא את ההפניות.)

תשובה: לכל חוליה סופרים את מספר המופעים של הערך שלה בכל השרשרת; אם מונה כלשהו שונה מ-kk – false, אחרת true.

סעיף ב

תשובה:

O(n2)O(n^2)

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

1. הלולאה החיצונית עוברת על nn חוליות.

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

3. סך הכול n⋅n=n2n \cdot n = n^2 צעדים (במקרה הגרוע – כשהשרשרת "מושלמת K" ואין עצירה מוקדמת), כלומר O(n2)O(n^2).

תשובה: O(n2)O(n^2) – לכל חוליה מעבר מלא על השרשרת.

שאלה 4 · המרות טיפוסים, Equals והעמסה

נתונות שתי המחלקות Car, Motorcycle. למחלקות יש תכונה אחת – מהירות מרבית.

C#:

public class Car {
    private int speed;
    public Car (int s) {
        speed = s;
    }

    public int GetSpeed () {
        return speed;
    }

    public bool Equals(Car other) {
        return (other!=null) && (speed == other.speed);
    }
}
public class Motorcycle {
    private int speed;

    public Motorcycle (int s) {
        speed = s;
    }

    public int GetSpeed () {
        return speed;
    }

    public bool Equals (Object other) {
        return ((other != null) &&
            (other is Motorcycle) &&
            (speed == ((Motorcycle)other).speed));
    }
}

Java:

public class Car {
    private int speed;
    public Car (int s) {
        speed = s;
    }

    public int getSpeed () {
        return speed;
    }

    public boolean equals(Car other) {
        return (other!=null) && (speed == other.speed);
    }
}
public class Motorcycle {
    private int speed;

    public Motorcycle (int s) {
        speed = s;
    }

    public int getSpeed () {
        return speed;
    }

    public boolean equals (Object other) {
        return ((other != null) &&
            (other instanceof Motorcycle) &&
            (speed == ((Motorcycle)other).speed));
    }
}
א.

כתבו פעולה המקבלת מערך הפניות לעצמים מסוג Object. הפעולה תחזיר מספר אופנועים (עצמים מסוג Motorcycle) שמהירותם המרבית היא בין 180 ל-250 קמ"ש.

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

C#:

public static int CountCars(Object[] vehicles)

Java:

public static int countCars(Object[] vehicles)
(6 נקודות)
ב.

נתונה המחלקה Drive:

C#:

public class Drive {
    public static void Main (string[] args) {
        Car c1 = new Car (180);
        Object c2 = new Car (180);
        Motorcycle m1 = new Motorcycle (180);
        Object m2 = new Motorcycle (180);
        //  ******
    }
}

Java:

public class Drive {
    public static void main (String[] args) {
        Car c1 = new Car (180);
        Object c2 = new Car (180);
        Motorcycle m1 = new Motorcycle (180);
        Object m2 = new Motorcycle (180);
        //  ******
    }
}

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

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

C#:

(1)     Console.WriteLine(c1.speed);
(2)     Console.WriteLine(((Motorcycle)c2).GetSpeed());
(3)     Console.WriteLine(c1.Equals(c2));
(4)     Console.WriteLine(c2.Equals(c1));
(5)     Console.WriteLine(m1.Equals(m2));
(6)     Console.WriteLine(m2.Equals(m1));
(7)     Console.WriteLine(c1.Equals((Motorcycle)m2));
(8)     Console.WriteLine(c1.Equals((Car)c2));
(9)     Console.WriteLine(m1.Equals((Car)c2));
(10)    Console.WriteLine(m1.Equals((Motorcycle)c2));

Java:

(11)    System.out.println (c1.speed);
(12)    System.out.println (((Motorcycle)c2).getSpeed());
(13)    System.out.println (c1.equals(c2));
(14)    System.out.println (c2.equals(c1));
(15)    System.out.println (m1.equals(m2));
(16)    System.out.println (m2.equals(m1));
(17)    System.out.println (c1.equals((Motorcycle)m2));
(18)    System.out.println (c1.equals((Car)c2));
(19)    System.out.println (m1.equals((Car)c2));
(20)    System.out.println (m1.equals((Motorcycle)c2));
(10 נקודות)
◂ פתרון מלא לשאלה 4

סעיף א

תשובה:

מעבר על המערך; לכל תא שהוא Motorcycle (is / instanceof) עם מהירות 180≤s≤250180 \le s \le 250 מגדילים מונה.

נתון: מערך `vehicles` של הפניות מטיפוס `Object` (בתאים יכולים להיות עצמים מסוגים שונים, וגם null).

מבוקש: מספר האופנועים (עצמים מסוג `Motorcycle`) שמהירותם המרבית בין 180 ל-250 קמ"ש (כולל הקצוות).

הרעיון: עוברים על כל תאי המערך. לכל תא בודקים קודם אם העצם הוא באמת `Motorcycle` (`is` ב-C#, `instanceof` ב-Java). רק אז מותר להמיר (casting) את ההפניה ל-`Motorcycle` ולזמן את `GetSpeed` – דרך הפניה מטיפוס `Object` אי אפשר לזמן אותה. אם המהירות בטווח – מגדילים את המונה.

•תא שמכיל null או עצם מסוג אחר (למשל `Car`) – הבדיקה מחזירה false והתא מדולג, כך שאין שגיאת המרה.

•שם הפעולה בכותרת הוא `CountCars`, אבל לפי הנוסח סופרים אופנועים.

C#:

public static int CountCars(Object[] vehicles)
{
    int count = 0;
    for (int i = 0; i < vehicles.Length; i++)
    {
        if (vehicles[i] is Motorcycle)
        {
            int s = ((Motorcycle)vehicles[i]).GetSpeed();
            if (s >= 180 && s <= 250)
                count++;
        }
    }
    return count;
}

Java:

public static int countCars(Object[] vehicles)
{
    int count = 0;
    for (int i = 0; i < vehicles.length; i++)
    {
        if (vehicles[i] instanceof Motorcycle)
        {
            int s = ((Motorcycle) vehicles[i]).getSpeed();
            if (s >= 180 && s <= 250)
                count++;
        }
    }
    return count;
}

תשובה: סופרים את התאים שהעצם בהם הוא `Motorcycle` (בדיקת טיפוס ואז המרה) ומהירותו בין 180 ל-250.

סעיף ב

תשובה:

1 – שגיאת קומפילציה; 2 – שגיאת זמן ריצה; 3 – false; 4 – false; 5 – true; 6 – Java: true, C#: False; 7 – false; 8 – true; 9 – false; 10 – שגיאת זמן ריצה.

נתון: ארבעה עצמים, כולם עם מהירות 180:

•`c1` – הפניה מטיפוס `Car` לעצם `Car`;

•`c2` – הפניה מטיפוס `Object` לעצם `Car`;

•`m1` – הפניה מטיפוס `Motorcycle` לעצם `Motorcycle`;

•`m2` – הפניה מטיפוס `Object` לעצם `Motorcycle`.

הכללים שבעזרתם עונים:

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

2. המרה (casting) מ-`Object` לטיפוס אחר תמיד עוברת קומפילציה, אבל בזמן ריצה נבדק טיפוס העצם עצמו; אם העצם אינו מהטיפוס המבוקש – שגיאת זמן ריצה (`InvalidCastException` ב-C#, `ClassCastException` ב-Java).

3. ב-`Car` יש `Equals(Car)` – זו העמסה (overload) ולא דריסה של `Equals(Object)` של `Object`. היא נבחרת רק כשהארגומנט מטיפוס `Car`. אחרת נבחרת `Equals(Object)` של `Object`, שמשווה הפניות (האם זה אותו עצם).

4. ב-`Motorcycle` הפעולה היא `Equals(Object)` – אותה חתימה כמו של `Object`:

•ב-Java זו דריסה (override), ולכן גם דרך הפניה מטיפוס `Object` תופעל הגרסה של `Motorcycle` (קישור דינמי).

•ב-C# הפעולה הוגדרה בלי `override`, ולכן היא מסתירה את `Object.Equals` (הקומפיילר נותן אזהרה בלבד, לא שגיאה). דרך הפניה מטיפוס `Object` תופעל `Object.Equals` – השוואת הפניות.

מה קורה בכל שורה (C# – שורות 1-10, Java – שורות 11-20 באותו סדר):

שורה (C# / Java)מה קורההסבר
1 / 11שגיאת קומפילציה`speed` היא תכונה פרטית (private) של `Car`, ואין גישה אליה מהמחלקה `Drive`.
2 / 12שגיאת זמן ריצהההמרה עוברת קומפילציה (`c2` מטיפוס `Object`), אבל העצם הוא `Car` ולא `Motorcycle` – חריגת המרה.
3 / 13יודפס False / falseהארגומנט מטיפוס `Object`, ולכן לא מתאימה `Equals(Car)`; מופעלת `Equals(Object)` של `Object` – שני עצמים שונים.
4 / 14יודפס False / false`c2` מטיפוס `Object` ו-`Car` לא דורסת את `Equals(Object)`, ולכן מופעלת `Object.Equals` – עצמים שונים.
5 / 15יודפס True / true`m1` מטיפוס `Motorcycle` – מופעלת `Equals(Object)` של `Motorcycle`: `m2` אינו null, הוא `Motorcycle`, והמהירויות שוות (180).
6 / 16C#: יודפס False; Java: יודפס trueההפניה `m2` מטיפוס `Object`. ב-Java הפעולה של `Motorcycle` דורסת את `equals` של `Object` ולכן היא מופעלת – true. ב-C# היא רק מסתירה (אין `override`), ולכן מופעלת `Object.Equals` – השוואת הפניות, False.
7 / 17יודפס False / falseההמרה של `m2` ל-`Motorcycle` תקינה. ל-`Car` אין `Equals(Motorcycle)` ו-`Motorcycle` אינו `Car`, לכן מופעלת `Object.Equals` – עצמים שונים.
8 / 18יודפס True / trueההמרה של `c2` ל-`Car` תקינה (העצם הוא `Car`); נבחרת `Equals(Car)`: `other` אינו null והמהירויות שוות.
9 / 19יודפס False / falseההמרה תקינה; מופעלת `Equals(Object)` של `Motorcycle`, אבל הארגומנט הוא `Car` ולא `Motorcycle`.
10 / 20שגיאת זמן ריצההעצם ש-`c2` מפנה אליו הוא `Car`, ולכן ההמרה ל-`Motorcycle` נכשלת בזמן ריצה.

(ב-C# ערך בוליאני מודפס כ-True / False, וב-Java כ-true / false.)

תשובה: 1 – שגיאת קומפילציה (private); 2, 10 – שגיאת זמן ריצה (המרה לא חוקית); 3 – false; 4 – false; 5 – true; 6 – ב-Java true, ב-C# False; 7 – false; 8 – true; 9 – false.

שאלה 5 · מעקב אחר פעולה על מחסנית

נתונה הפעולה:

C#:

public static void What(Stack<int> st, bool flag)
{
    int x, y;
    bool found;
    Stack<int> temp1 = new Stack<int>();
    Stack<int> temp2 = new Stack<int>();
    while(!st.IsEmpty())
    {
        x = st.Pop();
        found = false;
        while(!st.IsEmpty())
        {
            y = st.Pop();
            if(x > y == flag)
                found = true;
            temp1.Push(y);
        }
        while(!temp1.IsEmpty())
            st.Push(temp1.Pop());

        if(!found)
            temp2.Push(x);
    }
    while(!temp2.IsEmpty())
        st.Push(temp2.Pop());
}

Java:

public static void what(Stack<Integer> st, boolean flag)
{
    int x, y;
    boolean found;
    Stack<Integer> temp1 = new Stack<Integer>();
    Stack<Integer> temp2 = new Stack<Integer>();
    while(!st.isEmpty())
    {
        x = st.pop();
        found = false;
        while(!st.isEmpty())
        {
            y = st.pop();
            if(x > y == flag)
                found = true;
            temp1.push(y);
        }
        while(!temp1.isEmpty())
            st.push(temp1.pop());

        if(!found)
            temp2.push(x);
    }
    while(!temp2.isEmpty())
        st.push(temp2.pop());
}
א.

נתונה המחסנית st (8 נמצא בראש המחסנית):

מה יהיה התוכן של המחסנית st אחרי זימון הפעולה `What(st, true)` עבור המחסנית st?

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

(7 נקודות)
ב.

תנו דוגמה למחסנית st המכילה לפחות חמישה ערכים שונים כך שתוכן המחסנית לא ישתנה אחרי זימון הפעולה `What(st, true)`.

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

(3 נקודות)
ג.

תנו דוגמה למחסנית st המכילה לפחות חמישה ערכים שונים כך שאחרי זימון הפעולה `What(st, false)` במחסנית יישאר רק ערך אחד.

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

(3 נקודות)
ד.

מה מבצעת הפעולה `What(Stack<int> st, bool flag)` באופן כללי?

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

סעיף א

תשובה:

מהראש לתחתית: 2, 3, 7, 10

הבנת הפעולה: בכל סיבוב של הלולאה החיצונית מוציאים את האיבר העליון `x`. הלולאה הפנימית עוברת על כל האיברים שמתחתיו (ומחזירה אותם למקומם דרך `temp1`), ומדליקה את `found` אם קיים מתחתיו `y` שעבורו `(x > y) == flag`.

•עם `flag = true`: `found` נדלק אם יש מתחת ל-`x` איבר קטן ממנו.

•אם `found` נשאר false – `x` נשמר ב-`temp2`; אחרת הוא נזרק.

בסוף מעבירים את `temp2` חזרה ל-`st`. האיברים נכנסו ל-`temp2` מהעליון לתחתון, ולכן אחרי ההעברה הם חוזרים באותו סדר יחסי כמו במחסנית המקורית.

מעקב – המחסנית מהראש לתחתית: 8,9,2,9,3,10,7,108, 9, 2, 9, 3, 10, 7, 10, ו-`flag = true`:

x שהוצאהאיברים שמתחתיויש מתחתיו איבר קטן מ-x?foundנשמר ב-temp2?
89, 2, 9, 3, 10, 7, 10כן (2)trueלא
92, 9, 3, 10, 7, 10כן (2)trueלא
29, 3, 10, 7, 10לאfalseכן
93, 10, 7, 10כן (3)trueלא
310, 7, 10לאfalseכן
107, 10כן (7)trueלא
710לאfalseכן
10(אין)לאfalseכן

אחרי הלולאה `temp2` מכילה (מהראש לתחתית) 10,7,3,210, 7, 3, 2. מעבירים אותה ל-`st`, והסדר מתהפך שוב.

תשובה: המחסנית `st` מהראש לתחתית: 2,3,7,102, 3, 7, 10 (2 בראש המחסנית).

סעיף ב

תשובה:

אפשרי: מחסנית ממוינת בסדר עולה מהראש, למשל 1, 2, 3, 4, 5 (1 בראש).

עם `flag = true` איבר `x` נשאר רק אם אין מתחתיו איבר קטן ממנו, כלומר הוא קטן או שווה לכל האיברים שמתחתיו.

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

דוגמה: המחסנית מהראש לתחתית 1,2,3,4,51, 2, 3, 4, 5 (1 בראש המחסנית).

- 1: מתחתיו 2, 3, 4, 5 – אין קטן ממנו, נשאר.

- 2: מתחתיו 3, 4, 5 – נשאר. כך גם 3 ו-4.

- 5: אין מתחתיו איברים – נשאר.

כל האיברים נשמרים, ו-`temp2` מחזירה אותם באותו סדר.

תשובה: אפשרי – למשל 1,2,3,4,51, 2, 3, 4, 5 מהראש לתחתית (מחסנית ממוינת בסדר עולה מהראש).

סעיף ג

תשובה:

אפשרי: מחסנית שהגדול ביותר בתחתיתה, למשל 3, 1, 4, 2, 9 מהראש (נשאר 9).

עם `flag = false` התנאי `(x > y) == false` פירושו x≤yx \le y. לכן `found` נדלק אם יש מתחת ל-`x` איבר גדול ממנו או שווה לו, ו-`x` נשאר רק אם הוא גדול מכל האיברים שמתחתיו.

•האיבר שבתחתית תמיד נשאר (אין מתחתיו איברים, `found` נשאר false).

•כדי שיישאר רק הוא, כל איבר אחר צריך שיהיה מתחתיו איבר גדול ממנו. זה מתקיים אם האיבר הגדול ביותר נמצא בתחתית – הוא מתחת לכל האחרים.

דוגמה: המחסנית מהראש לתחתית 3,1,4,2,93, 1, 4, 2, 9 (3 בראש, 9 בתחתית).

- 3, 1, 4, 2 – לכל אחד מהם 9 נמצא מתחתיו וגדול ממנו, ולכן כולם נזרקים.

- 9 – אין מתחתיו איברים, נשאר.

תשובה: אפשרי – למשל 3,1,4,2,93, 1, 4, 2, 9 מהראש לתחתית; אחרי `What(st, false)` נשאר רק 9 (כל מחסנית שהמקסימום שלה בתחתית מתאימה).

סעיף ד

תשובה:

מוחקת כל איבר שיש מתחתיו איבר קטן ממנו (flag אמת) או גדול/שווה לו (flag שקר); סדר הנותרים נשמר.

הפעולה עוברת על איברי המחסנית מהראש לתחתית, ולכל איבר משווה אותו לכל האיברים שמתחתיו:

•`flag = true`: נשארים רק האיברים שקטנים או שווים לכל האיברים שמתחתיהם; כל איבר שיש מתחתיו איבר קטן ממנו – נמחק.

•`flag = false`: נשארים רק האיברים שגדולים ממש מכל האיברים שמתחתיהם; כל איבר שיש מתחתיו איבר גדול ממנו או שווה לו – נמחק.

האיברים שנשארים שומרים על הסדר היחסי שלהם במחסנית, והאיבר שבתחתית נשאר תמיד. מהתחתית כלפי הראש מתקבלת סדרה יורדת, לא בהכרח ממש (כש-flag אמת) או עולה ממש (כש-flag שקר).

תשובה: הפעולה מוחקת מהמחסנית כל איבר שיש מתחתיו איבר קטן ממנו (flag = true) או איבר גדול ממנו או שווה לו (flag = false), ושומרת על סדר האיברים שנשארו.

שאלה 6 · מיקומים ומרחק בין איברים זהים בתור

הערה כללית לשאלה:

•אין להשתמש במבני נתונים נוספים פרט לתור/תורים.

•יש לשמור את התור במצב מקורי בסיום הפעולה.

•אפשר להניח שקיימת הפעולה Clone המחזירה העתק של התור. כותרת הפעולה:

C#:

public static Queue<int> Clone(Queue<int> q)

Java:

public static Queue<Integer> clone(Queue<Integer> q)

סיבוכיות של הפעולה Clone היא O(n)O(n) כאשר n = מספר האיברים בתור.

א.

כתבו פעולה המקבלת תור של מספרים שלמים q ומספר שלם num. הפעולה תחזיר את מיקומו הראשון של num בתוך התור. אם num לא מופיע בתור, הפעולה תחזיר ערך −1-1.

לדוגמה:

עבור התור q הבא והמספר num=3

הפעולה תחזיר 2.

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

C#:

public static int FirstPosition(Queue<int>q, int num)

Java:

public static int firstPosition(Queue<Integer>q, int num)
(5 נקודות)
ב.

כתבו פעולה המקבלת תור של מספרים שלמים q ומספר שלם num. הפעולה תחזיר את מיקומו האחרון של num בתוך התור. אם num לא מופיע בתור, הפעולה תחזיר ערך −1-1.

לדוגמה:

עבור התור q הבא והמספר num=3

הפעולה תחזיר 10.

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

C#:

public static int LastPosition(Queue<int>q, int num)

Java:

public static int lastPosition(Queue<Integer>q, int num)
(5 נקודות)
ג.

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

המרחק בין שני איברים בתור הוא כמות האיברים הנמצאים ביניהם.

לדוגמה:

עבור התור הבא ו-K=4 הפעולה תחזיר true כי מרחק בין שני מספרים זהים (2 ו-2) הוא 4.

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

C#:

public static bool IsDistanceK(Queue<int> q, int k)

Java:

public static boolean isDistanceK(Queue<Integer> q, int k)
(5 נקודות)
ד.

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

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

סעיף א

תשובה:

מעבר על העתק (Clone) עם מונה מיקום; מוחזר מיקום המופע הראשון, או −1-1.

נתון: תור `q` ומספר `num`. המיקומים נספרים מ-1 מראש התור (בדוגמה: 18 במיקום 1, ה-3 המסומן במיקום 2).

מבוקש: המיקום הראשון של `num` בתור, או −1-1 אם הוא לא מופיע; התור המקורי לא משתנה.

הרעיון: כדי לא לפגוע בתור המקורי עובדים על העתק שלו שמתקבל מ-`Clone` (מותר – זה תור, ואין צורך במבנה נתונים אחר). מוציאים איברים מההעתק ומונים את המיקום; בפעם הראשונה שיוצא `num` – מחזירים את המיקום. אם ההעתק התרוקן – מחזירים −1-1.

בדיקה עם הדוגמה: 18 (מיקום 1) – לא; 3 (מיקום 2) – כן, מוחזר 2.

C#:

public static int FirstPosition(Queue<int> q, int num)
{
    Queue<int> copy = Clone(q);       // התור המקורי לא משתנה
    int pos = 1;
    while (!copy.IsEmpty())
    {
        if (copy.Remove() == num)
            return pos;
        pos++;
    }
    return -1;
}

Java:

public static int firstPosition(Queue<Integer> q, int num)
{
    Queue<Integer> copy = clone(q);   // התור המקורי לא משתנה
    int pos = 1;
    while (!copy.isEmpty())
    {
        if (copy.remove() == num)
            return pos;
        pos++;
    }
    return -1;
}

תשובה: מעבר על העתק של התור עם מונה מיקום; מחזירים את המיקום של המופע הראשון של num, או −1-1.

סעיף ב

תשובה:

מעבר מלא על העתק, שמירת מיקום המופע האחרון (התחלה מ-−1-1).

נתון: תור `q` ומספר `num` (מיקומים מ-1 מראש התור).

מבוקש: המיקום האחרון של `num` בתור, או −1-1.

הרעיון: כמו בסעיף א', עובדים על העתק של התור. הפעם אי אפשר לעצור במופע הראשון – צריך לעבור על כל התור ולזכור במשתנה `last` את המיקום של המופע האחרון שנמצא עד כה. `last` מאותחל ל-−1-1, כך שאם `num` לא הופיע – זה מה שיוחזר.

בדיקה עם הדוגמה: 18,3,15,13,3,12,21,12,10,3,718, 3, 15, 13, 3, 12, 21, 12, 10, 3, 7 – 3 מופיע במיקומים 2, 5, 10; אחרי המעבר `last = 10`, ומוחזר 10.

C#:

public static int LastPosition(Queue<int> q, int num)
{
    Queue<int> copy = Clone(q);
    int pos = 1;
    int last = -1;
    while (!copy.IsEmpty())
    {
        if (copy.Remove() == num)
            last = pos;               // המופע האחרון עד כה
        pos++;
    }
    return last;
}

Java:

public static int lastPosition(Queue<Integer> q, int num)
{
    Queue<Integer> copy = clone(q);
    int pos = 1;
    int last = -1;
    while (!copy.isEmpty())
    {
        if (copy.remove() == num)
            last = pos;               // המופע האחרון עד כה
        pos++;
    }
    return last;
}

תשובה: מעבר מלא על העתק של התור, שמירת המיקום של המופע האחרון של num (התחלה מ-−1-1).

סעיף ג

תשובה:

לכל איבר x שמוצא מהעתק – FirstPosition(copy, x) נותנת את המופע הבא; אם pos−1=Kpos-1=K מחזירים true, אחרת בסוף false.

נתון: תור שכל מספר מופיע בו פעמיים בדיוק, ומספר חיובי `k`.

מבוקש: true אם יש מספר ששני המופעים שלו רחוקים זה מזה בדיוק kk (יש ביניהם בדיוק kk איברים).

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

1. עובדים על העתק `copy` של התור (מ-`Clone`).

2. מוציאים מ-`copy` את האיבר הראשון `x`. עכשיו `copy` מכיל רק את האיברים שאחרי `x`.

3. `FirstPosition(copy, x)` מחזירה את המיקום של המופע הבא של `x` בתוך מה שנשאר (והיא לא משנה את `copy`). אם המיקום הוא pospos, אז בין שני המופעים יש בדיוק pos−1pos-1 איברים.

4. אם pos−1=kpos-1 = k – מחזירים true. אם `x` הוא המופע השני של המספר, `FirstPosition` מחזירה −1-1 ומדלגים.

5. אם עברנו על כל האיברים – מחזירים false.

לא נעשה שימוש במבנה נתונים מלבד תורים, והתור המקורי לא משתנה.

בדיקה עם הדוגמה: התור 4,8,2,11,4,11,1,2,8,14, 8, 2, 11, 4, 11, 1, 2, 8, 1 ו-k=4k=4:

•x=4x=4 (מיקום 1): במה שנשאר 4 מופיע במיקום 4, מרחק 4−1=34-1=3.

•x=8x=8: מיקום 7 במה שנשאר, מרחק 6.

•x=2x=2: מה שנשאר הוא 11,4,11,1,2,…11, 4, 11, 1, 2, \dots – 2 במיקום 5, מרחק 5−1=4=k5-1=4=k, מוחזר true.

C#:

public static bool IsDistanceK(Queue<int> q, int k)
{
    Queue<int> copy = Clone(q);
    while (!copy.IsEmpty())
    {
        int x = copy.Remove();                // copy מכיל עכשיו את מה שאחרי x
        int pos = FirstPosition(copy, x);     // המופע הבא של x
        if (pos != -1 && pos - 1 == k)
            return true;
    }
    return false;
}

Java:

public static boolean isDistanceK(Queue<Integer> q, int k)
{
    Queue<Integer> copy = clone(q);
    while (!copy.isEmpty())
    {
        int x = copy.remove();                // copy מכיל עכשיו את מה שאחרי x
        int pos = firstPosition(copy, x);     // המופע הבא של x
        if (pos != -1 && pos - 1 == k)
            return true;
    }
    return false;
}

תשובה: לכל איבר מוצאים בעזרת FirstPosition את המופע הבא שלו בהמשך התור; אם מספר האיברים ביניהם (pos−1pos-1) שווה ל-K – true, אחרת false.

סעיף ד

תשובה:

א' – O(n)O(n); ב' – O(n)O(n); ג' – O(n2)O(n^2)

נסמן ב-nn את מספר האיברים בתור. נתון ש-`Clone` היא O(n)O(n).

1. סעיף א' (FirstPosition): `Clone` – O(n)O(n), ועוד מעבר אחד לכל היותר על ההעתק – O(n)O(n). סך הכול O(n)O(n).

2. סעיף ב' (LastPosition): `Clone` – O(n)O(n), ומעבר מלא על ההעתק – O(n)O(n). סך הכול O(n)O(n).

3. סעיף ג' (IsDistanceK): הלולאה רצה nn פעמים (במקרה הגרוע). בכל סיבוב מזמנים את `FirstPosition` על התור שנשאר, שגודלו לכל היותר nn – O(n)O(n). סך הכול n⋅O(n)=O(n2)n \cdot O(n) = O(n^2) (בפירוט: (n−1)+(n−2)+⋯≈n22(n-1)+(n-2)+\dots \approx \frac{n^2}{2}).

תשובה: א' – O(n)O(n); ב' – O(n)O(n); ג' – O(n2)O(n^2).

שאלה 7 · סכום בין חוליות ורצף בעל סכום נתון

א.

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

לדוגמה: עבור השרשרת שלפניכם הפעולה תחזיר 23.

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

C#:

public static int GetSum(Node<int> p1, Node<int> p2)

Java:

public static int getSum(Node<Integer> p1, Node<Integer> p2)

אפשר להניח ש-p1 מצביע על חוליה שנמצאת לפני החוליה ש-p2 מצביע עליה.

(5 נקודות)
ב.

כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות של מספרים שלמים חיוביים ומספר שלם חיובי num. הפעולה תבדוק אם קיים רצף חוליות שסכום הערכים שלהן שווה ל-num. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

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

C#:

public static bool IsAmount(Node<int> ch, int num)

Java:

public static boolean isAmount(Node<Integer> ch, int num)

לדוגמה:

עבור השרשרת הבאה ו-num=23 או num=37 הפעולה תחזיר true,

עבור num=26 או num=19 הפעולה תחזיר false.

(10 נקודות)
ג.

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

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

סעיף א

תשובה:

סכימת הערכים מ-p1 עד p2 כולל שתיהן (בדוגמה 23).

נתון: שתי הפניות `p1`, `p2` לחוליות באותה שרשרת, ו-`p1` לפני `p2`.

מבוקש: סכום הערכים של החוליות מ-`p1` עד `p2`.

הבנת הדוגמה: בשרשרת 10,14,6,4,10,3,14,1410, 14, 6, 4, 10, 3, 14, 14 – `p1` מצביע על 6 ו-`p2` על 3. הסכום 6+4+10+3=236+4+10+3=23, כלומר שתי החוליות הקצוות נכללות בסכום.

הרעיון: מתקדמים עם הפניה `p` מ-`p1` ומוסיפים לסכום את הערך של כל חוליה, עד שמגיעים ל-`p2` (משווים הפניות, לא ערכים – ערכים יכולים לחזור על עצמם). בסוף מוסיפים גם את הערך של `p2`.

C#:

public static int GetSum(Node<int> p1, Node<int> p2)
{
    int sum = 0;
    Node<int> p = p1;
    while (p != p2)                   // עד החוליה ש-p2 מצביע עליה
    {
        sum += p.GetValue();
        p = p.GetNext();
    }
    sum += p2.GetValue();             // גם p2 נכללת בסכום
    return sum;
}

Java:

public static int getSum(Node<Integer> p1, Node<Integer> p2)
{
    int sum = 0;
    Node<Integer> p = p1;
    while (p != p2)                   // עד החוליה ש-p2 מצביע עליה
    {
        sum += p.getValue();
        p = p.getNext();
    }
    sum += p2.getValue();             // גם p2 נכללת בסכום
    return sum;
}

תשובה: מעבר מ-p1 עד p2 (כולל שתיהן) וסכימת הערכים; בדוגמה 6+4+10+3=236+4+10+3=23.

סעיף ב

תשובה:

מכל נקודת התחלה מצטברים ערכים כל עוד הסכום קטן מ-num; סכום שווה בדיוק ל-num – true, אחרת false.

נתון: שרשרת של מספרים שלמים חיוביים ומספר חיובי `num`.

מבוקש: true אם יש רצף חוליות צמודות שסכום ערכיו בדיוק `num`.

הרעיון: בודקים כל נקודת התחלה אפשרית `start`. מכל התחלה מוסיפים חוליות אחת אחרי השנייה לסכום. כיוון שכל המספרים חיוביים, הסכום רק גדל – ולכן ברגע שהסכום הגיע ל-`num` או עבר אותו אין טעם להמשיך מאותה התחלה:

1. `start` עובר על כל חוליות השרשרת.

2. מ-`start` מוסיפים ערכים ל-`sum` כל עוד יש חוליות ו-`sum < num`.

3. אם בסוף `sum == num` – נמצא רצף מתאים, מחזירים true.

4. אחרת עוברים להתחלה הבאה. אם אף התחלה לא הצליחה – false.

בדיקה עם הדוגמה (10,14,6,4,10,3,14,1410, 14, 6, 4, 10, 3, 14, 14):

•`num = 23`: מההתחלה 6: 6,10,20,236, 10, 20, 23 – true.

•`num = 37`: מההתחלה 6: 6+4+10+3+14=376+4+10+3+14=37 – true.

•`num = 26`: מכל התחלה הסכום "מדלג" מעל 26 (למשל 10+14=2410+14=24, 24+6=3024+6=30; 14+6+4=2414+6+4=24, 24+10=3424+10=34; 6+4+10=206+4+10=20, 20+3=2320+3=23, 23+14=3723+14=37; 10+3+14=2710+3+14=27; 3+14=173+14=17, 17+14=3117+14=31) – false.

•`num = 19`: גם כאן אין רצף מתאים (למשל 14+6=2014+6=20, 4+10=144+10=14, 14+3=1714+3=17, 17+14=3117+14=31) – false.

C#:

public static bool IsAmount(Node<int> ch, int num)
{
    Node<int> start = ch;
    while (start != null)
    {
        int sum = 0;
        Node<int> p = start;
        while (p != null && sum < num)    // מספרים חיוביים: הסכום רק גדל
        {
            sum += p.GetValue();
            p = p.GetNext();
        }
        if (sum == num)
            return true;
        start = start.GetNext();
    }
    return false;
}

Java:

public static boolean isAmount(Node<Integer> ch, int num)
{
    Node<Integer> start = ch;
    while (start != null)
    {
        int sum = 0;
        Node<Integer> p = start;
        while (p != null && sum < num)    // מספרים חיוביים: הסכום רק גדל
        {
            sum += p.getValue();
            p = p.getNext();
        }
        if (sum == num)
            return true;
        start = start.getNext();
    }
    return false;
}

תשובה: לכל חוליה כנקודת התחלה מצטברים ערכים עד שהסכום מגיע ל-num או עובר אותו; אם התקבל בדיוק num – true, אחרת false.

סעיף ג

תשובה:

א' – O(n)O(n); ב' – O(n2)O(n^2)

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

1. סעיף א' (GetSum): מעבר אחד על החוליות שבין `p1` ל-`p2`; מספרן לכל היותר nn, ובכל צעד O(1)O(1). לכן O(n)O(n).

2. סעיף ב' (IsAmount): יש עד nn נקודות התחלה, ומכל אחת הלולאה הפנימית עוברת במקרה הגרוע עד סוף השרשרת – עד nn צעדים. סך הכול n+(n−1)+⋯+1=n(n+1)2n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}, כלומר O(n2)O(n^2).

תשובה: א' – O(n)O(n); ב' – O(n2)O(n^2).

שאלה 8 · סכום, תחתית מחסנית ושרשרת מחסניות

א.

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

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

C#:

public static int GetSumOfStack(Stack<int> st)

Java:

public static int getSumOfStack(Stack<Integer> st)
(4 נקודות)
ב.

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

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

C#:

public static int GetStackLastValue(Stack<int> st)

Java:

public static int getStackLastValue(Stack<Integer> st)
(4 נקודות)

שרשרת מחסניות היא שרשרת חוליות מסוג `Node<Stack<int>>` (ב-Java: `Node<Stack<Integer>>`). כלומר, הערך (value) של כל חוליה הוא הפניה למחסנית של מספרים שלמים.

ג.

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

הפעולה תחזיר תור של מספרים שלמים באופן הזה:

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

לדוגמה,

עבור שרשרת המחסניות שלפניכם:

הפעולה תחזיר תור חדש: 22, 3, 15, 7

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

הסכום הוא 5+1+3+4+7+2=225+1+3+4+7+2 = 22

•עבור החוליה השנייה יתקבל מספר בתחתית המחסנית (3) כי אורך המחסנית אי-זוגי.

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

הסכום הוא 3+1+5+6=153+1+5+6 = 15.

•עבור החוליה הרביעית יתקבל מספר בתחתית המחסנית (7) כי אורך המחסנית אי-זוגי.

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

C#:

public static Queue<int> DoIt(Node<Stack<int>> chain)

Java:

public static Queue<Integer> doIt(Node<Stack<Integer>> chain)
(7 נקודות)
ד.

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

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

סעיף א

תשובה:

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

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

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

C#:

public static int GetSumOfStack(Stack<int> st)
{
    Stack<int> temp = new Stack<int>();
    int sum = 0;
    while (!st.IsEmpty())
    {
        int x = st.Pop();
        sum += x;
        temp.Push(x);
    }
    while (!temp.IsEmpty())           // שחזור המחסנית
        st.Push(temp.Pop());
    return sum;
}

Java:

public static int getSumOfStack(Stack<Integer> st)
{
    Stack<Integer> temp = new Stack<Integer>();
    int sum = 0;
    while (!st.isEmpty())
    {
        int x = st.pop();
        sum += x;
        temp.push(x);
    }
    while (!temp.isEmpty())           // שחזור המחסנית
        st.push(temp.pop());
    return sum;
}

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

סעיף ב

תשובה:

העברה למחסנית עזר, קריאת הראש שלה (התחתית המקורית) ושחזור.

מבוקש: הערך שבתחתית המחסנית, בלי לשנות אותה. (מניחים שהמחסנית אינה ריקה – אחרת אין "ערך אחרון".)

הרעיון: מעבירים את כל האיברים למחסנית עזר. כך הסדר מתהפך, והאיבר שהיה בתחתית נמצא עכשיו בראש מחסנית העזר – קוראים אותו עם `Top`. אחר כך מחזירים את כל האיברים למחסנית המקורית.

C#:

public static int GetStackLastValue(Stack<int> st)
{
    Stack<int> temp = new Stack<int>();
    while (!st.IsEmpty())
        temp.Push(st.Pop());
    int last = temp.Top();            // התחתית של st נמצאת בראש temp
    while (!temp.IsEmpty())           // שחזור המחסנית
        st.Push(temp.Pop());
    return last;
}

Java:

public static int getStackLastValue(Stack<Integer> st)
{
    Stack<Integer> temp = new Stack<Integer>();
    while (!st.isEmpty())
        temp.push(st.pop());
    int last = temp.top();            // התחתית של st נמצאת בראש temp
    while (!temp.isEmpty())           // שחזור המחסנית
        st.push(temp.pop());
    return last;
}

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

סעיף ג

תשובה:

לכל חוליה: אורך המחסנית זוגי – לתור נכנס סכום איבריה, אי-זוגי – הערך שבתחתיתה (בדוגמה 22, 3, 15, 7).

נתון: הפניה `chain` לחוליה הראשונה של שרשרת שבכל חוליה שלה יש מחסנית.

מבוקש: תור חדש: לכל מחסנית באורך זוגי – סכום איבריה, ולכל מחסנית באורך אי-זוגי – הערך שבתחתיתה, לפי סדר החוליות.

הרעיון: עוברים על החוליות לפי הסדר. לכל מחסנית צריך לדעת את האורך שלה – לשם כך כותבים פעולת עזר `Size` שסופרת את האיברים ומשחזרת את המחסנית. לפי זוגיות האורך מכניסים לתור את התוצאה של `GetSumOfStack` (סעיף א') או של `GetStackLastValue` (סעיף ב'). כל הפעולות משחזרות את המחסניות, כך שהשרשרת לא משתנה.

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

חוליההמחסנית (מהראש לתחתית)אורךמה נכנס לתור
15, 1, 3, 4, 7, 26 (זוגי)5+1+3+4+7+2=225+1+3+4+7+2=22
25, 1, 33 (אי-זוגי)התחתית: 3
33, 1, 5, 64 (זוגי)3+1+5+6=153+1+5+6=15
42, 1, 4, 4, 75 (אי-זוגי)התחתית: 7

התור המוחזר: 22,3,15,722, 3, 15, 7 – כמו בדוגמה.

(מחסנית ריקה – אורכה 0, זוגי, ונכנס לתור הסכום 0.)

C#:

public static int Size(Stack<int> st)
{
    Stack<int> temp = new Stack<int>();
    int count = 0;
    while (!st.IsEmpty())
    {
        temp.Push(st.Pop());
        count++;
    }
    while (!temp.IsEmpty())
        st.Push(temp.Pop());
    return count;
}

public static Queue<int> DoIt(Node<Stack<int>> chain)
{
    Queue<int> result = new Queue<int>();
    Node<Stack<int>> p = chain;
    while (p != null)
    {
        Stack<int> st = p.GetValue();
        if (Size(st) % 2 == 0)
            result.Insert(GetSumOfStack(st));      // אורך זוגי: הסכום
        else
            result.Insert(GetStackLastValue(st));  // אורך אי-זוגי: התחתית
        p = p.GetNext();
    }
    return result;
}

Java:

public static int size(Stack<Integer> st)
{
    Stack<Integer> temp = new Stack<Integer>();
    int count = 0;
    while (!st.isEmpty())
    {
        temp.push(st.pop());
        count++;
    }
    while (!temp.isEmpty())
        st.push(temp.pop());
    return count;
}

public static Queue<Integer> doIt(Node<Stack<Integer>> chain)
{
    Queue<Integer> result = new Queue<Integer>();
    Node<Stack<Integer>> p = chain;
    while (p != null)
    {
        Stack<Integer> st = p.getValue();
        if (size(st) % 2 == 0)
            result.insert(getSumOfStack(st));      // אורך זוגי: הסכום
        else
            result.insert(getStackLastValue(st));  // אורך אי-זוגי: התחתית
        p = p.getNext();
    }
    return result;
}

תשובה: לכל חוליה מחשבים את אורך המחסנית; אורך זוגי – מכניסים לתור את סכום האיברים, אי-זוגי – את הערך שבתחתית. בדוגמה מתקבל התור 22, 3, 15, 7.

סעיף ד

תשובה:

O(N+m)O(N+m) – N מספר כל האיברים במחסניות, m מספר החוליות.

נסמן ב-mm את מספר החוליות בשרשרת, ב-kik_i את גודל המחסנית בחוליה ה-ii, וב-N=k1+k2+⋯+kmN=k_1+k_2+\dots+k_m את מספר כל האיברים בכל המחסניות.

1. לכל חוליה: `Size` מוציאה ומחזירה כל איבר – O(ki)O(k_i); אחריה `GetSumOfStack` או `GetStackLastValue` – עוד O(ki)O(k_i); והכנסה לתור – O(1)O(1).

2. לכן חוליה ii עולה O(ki+1)O(k_i + 1).

3. סך הכול: ∑i=1mO(ki+1)=O(N+m)\sum_{i=1}^{m} O(k_i+1) = O(N + m).

תשובה: O(N+m)O(N+m) – כל איבר בכל מחסנית מטופל מספר קבוע של פעמים, וכל חוליה פעם אחת.

שאלה 9 · מסלולים מהשורש לעלים בעץ בינרי

נתונה הפעולה Mystery. הפעולה מקבלת הפניה לשורש עץ בינרי של מספרים שלמים חיוביים bt.

C#:

public static void Mystery(BinNode<int> bt)
{
    Mystery(bt, "");
}
private static void Mystery(BinNode<int> bt, string st)
{
    st = st + " " + bt.GetValue();
    if (bt.GetLeft()==null && bt.GetRight()==null)
    {
        Console.WriteLine(st);
    }
    else
    {
        if (bt.GetLeft() != null)
            Mystery (bt.GetLeft(), st);
        if (bt.GetRight() != null)
            Mystery (bt.GetRight(), st);
    }
}

Java:

public static void mystery(BinNode<Integer>bt)
{
    mystery(bt, "");
}
private static void mystery(BinNode<Integer> bt, String st)
{
    st = st + " " + bt.getValue();
    if (bt.getLeft()==null && bt.getRight()==null)
    {
        System.out.println(st);
    }
    else
    {
        if (bt.getLeft() != null)
            mystery (bt.getLeft(), st);
        if (bt.getRight() != null)
            mystery (bt.getRight(), st);
    }
}

נתון העץ הבינרי bt1 הבא:

א.

מה תהיה תוצאת זימון הפעולה Mystery(bt1)?

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

(6 נקודות)
ב.

לפעולה Mystery הועבר כפרמטר הפניה לשורש של עץ בינרי bt2.

הפלט שהתקבל לאחר זימון הפעולה Mystery(bt2) היה בדיוק בסדר זה (משמאל לימין):

70  20  50  40  30
70  20  50  60
70  100 120

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

(6 נקודות)
ג.

לפעולה Mystery הועבר כפרמטר הפניה לשורש של עץ חיפוש בינרי bt3.

האם ייתכן שהפלט שהתקבל אחרי זימון הפעולה Mystery(bt3) יהיה זהה לפלט שהתקבל אחרי הזימון Mystery(bt2)? אם כן – ציירו עץ חיפוש בינרי bt3. אם הדבר בלתי אפשרי – הסבירו מדוע.

(3 נקודות)
ד.

מה מבצעת הפעולה Mystery באופן כללי?

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

סעיף א

תשובה:

שלוש שורות: " 18 6 1 3", " 18 20 17 1", " 18 20 13".

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

העץ bt1: 18 בשורש; בניו 6 (שמאלי) ו-20 (ימני); ל-6 בן שמאלי 1, ול-1 בן ימני 3; ל-20 בן שמאלי 17 ובן ימני 13; ל-17 בן שמאלי 1.

מעקב:

זימוןהצומתst אחרי השרשורעלה?פעולה
118" 18"לאזימון לשמאל (6) ואחר כך לימין (20)
26" 18 6"לאזימון לשמאל (1); אין בן ימני
31" 18 6 1"לאאין בן שמאלי; זימון לימין (3)
43" 18 6 1 3"כןהדפסה: ` 18 6 1 3`
520" 18 20"לאזימון לשמאל (17) ואחר כך לימין (13)
617" 18 20 17"לאזימון לשמאל (1); אין בן ימני
71" 18 20 17 1"כןהדפסה: ` 18 20 17 1`
813" 18 20 13"כןהדפסה: ` 18 20 13`

תשובה: יודפסו שלוש שורות (בתחילת כל שורה רווח):

 18 6 1 3
 18 20 17 1
 18 20 13

סעיף ב

תשובה:

70: שמאל 20, ימין 100; 20 – בן יחיד 50; 50: שמאל 40, ימין 60; 40 – בן יחיד 30; 100 – בן יחיד 120.

מה יודעים מהפלט:

1. כל שורה בפלט היא מסלול מהשורש לעלה. לכן השורש הוא 70, ויש שלושה עלים: 30, 60, 120.

2. המסלולים 70→20→50→40→3070 \to 20 \to 50 \to 40 \to 30 ו-70→20→50→6070 \to 20 \to 50 \to 60 משותפים עד 50, ולכן ל-50 יש שני בנים: 40 ו-60.

3. המסלול השלישי מתפצל כבר בשורש: ל-70 שני בנים – 20 ו-100.

4. הפעולה מבקרת קודם בתת-העץ השמאלי ואחר כך בימני, ולכן העלים מודפסים משמאל לימין:

•מסלולי 20 הודפסו לפני מסלול 100, ולכן 20 הוא הבן השמאלי של 70 ו-100 הבן הימני.

•המסלול דרך 40 הודפס לפני המסלול של 60, ולכן 40 הוא הבן השמאלי של 50 ו-60 הבן הימני.

5. לצמתים 20, 40, 100 יש בן אחד בלבד (50, 30, 120). הפלט אינו קובע אם הבן הזה שמאלי או ימני – כל בחירה נותנת אותו פלט. בציור בחרנו: 50 בן ימני של 20, 30 בן שמאלי של 40, 120 בן ימני של 100.

העץ bt2:

צומתבן שמאליבן ימני
7020100
20–50
504060
4030–
100–120
30, 60, 120–– (עלים)
          70
        /    \
      20      100
        \        \
         50       120
        /  \
      40    60
     /
   30

תשובה: השורש 70 עם בן שמאלי 20 ובן ימני 100; ל-20 בן יחיד 50; ל-50 בן שמאלי 40 ובן ימני 60; ל-40 בן יחיד 30; ל-100 בן יחיד 120 (הצד של בן יחיד אינו נקבע מהפלט).

סעיף ג

תשובה:

כן: 70 (20, 100); 50 בן ימני של 20; 50 (40, 60); 30 בן שמאלי של 40; 120 בן ימני של 100.

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

1. השורש 70: תת-העץ השמאלי {20,50,40,30,60}\{20, 50, 40, 30, 60\} – כולם קטנים מ-70; תת-העץ הימני {100,120}\{100, 120\} – גדולים מ-70. מתאים (וזה גם הסדר שהפלט מחייב).

2. 20: הבן היחיד 50 גדול מ-20, ולכן חייב להיות בן ימני; כל תת-העץ שלו {50,40,30,60}\{50, 40, 30, 60\} גדול מ-20.

3. 50: 40 בן שמאלי (40<5040<50) ו-60 בן ימני (60>5060>50) – בדיוק הסדר שהפלט מחייב.

4. 40: הבן היחיד 30 קטן מ-40, ולכן בן שמאלי; וגם 30>2030>20, כנדרש מצומת שנמצא בתת-העץ הימני של 20.

5. 100: הבן היחיד 120 גדול מ-100, ולכן בן ימני.

6. גם 60 מתאים לכל אבותיו: 60<7060<70, 60>2060>20, 60>5060>50.

כל התנאים מתקיימים, ולכן עץ החיפוש bt3 הוא בדיוק העץ שצויר בסעיף ב' (ובעץ חיפוש הצדדים נקבעים באופן יחיד):

          70
        /    \
      20      100
        \        \
         50       120
        /  \
      40    60
     /
   30

זה אותו עץ כמו bt2, ולכן גם המעבר עליו זהה: העלים 30, 60, 120 מודפסים באותו סדר, והפלט זהה לפלט של bt2.

תשובה: כן – עץ החיפוש: 70 (שמאל 20, ימין 100); 20 – בן ימני 50; 50 – שמאל 40, ימין 60; 40 – בן שמאלי 30; 100 – בן ימני 120.

סעיף ד

תשובה:

מדפיסה את כל המסלולים מהשורש לעלים, כל מסלול בשורה, לפי סדר העלים משמאל לימין.

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

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

שאלה 10 · ירושה, בנאי מעתיק והפניות משותפות

בבית החולים, לכל רופא מתמחה הוצמד רופא ותיק מנוסה. כדי לנהל את תהליך ההתמחות פותחו המחלקות האלה: Doctor, Intern, Test.

המחלקה Doctor מתארת רופא:

C#:

public class Doctor {
    protected string name;// שם
    protected string specialization;// התמחות
    protected int numOfPatients; // מספר חולים

    public Doctor(string name, string spec) {
        this.name = name;
        this.specialization = spec;
        this.numOfPatients = 0;
    }
    public Doctor(string name, string spec, int num) {
        this.name = name;
        this.specialization = spec;
        this.numOfPatients = num;
    }
    public Doctor(Doctor other) {
        this.name = other.name;
        this.specialization = other.specialization;
        this.numOfPatients = other.numOfPatients;
    }
    public void AddPatients(int num)
    {
       if(numOfPatients + num >=0)
          this.numOfPatients += num;
    }
    public string ToString(){
      return "Doctor:" + name + ", " + specialization+ ","
                +numOfPatients;
    }
}

Java:

public class Doctor {
    protected String name;// שם
    protected String specialization;// התמחות
    protected int numOfPatients; // מספר חולים

    public Doctor(String name, String spec) {
        this.name = name;
        this.specialization = spec;
        this.numOfPatients = 0;
    }
    public Doctor(String name, String spec, int num) {
        this.name = name;
        this.specialization = spec;
        this.numOfPatients = num;
    }
    public Doctor(Doctor other) {
        this.name = other.name;
        this.specialization = other.specialization;
        this.numOfPatients = other.numOfPatients;
    }
    public void addPatients(int num)
    {
       if(numOfPatients + num >=0)
          this.numOfPatients += num;
    }
    public String toString(){
      return "Doctor:" + name + ", " + specialization+ ","
                +numOfPatients;
    }
}

במחלקה הוגדרו גם פעולות set/Get לכל התכונות.

המחלקה Intern מתארת מתמחה:

C#:

public class Intern : Doctor {
    private Doctor mentor;

    public Intern(string name, string spec, Doctor mentor):
                  base(name, spec){
        this.mentor = mentor;
        this.numOfPatients = mentor.numOfPatients/2;
    }
    public Doctor GetMentor(){return mentor;}
    public string ToString() {
       return "Intern: " + name + ", " + specialization +
          ", Mentor: " + mentor.name +", " +
          mentor.numOfPatients +"," + numOfPatients;
    }
}

Java:

public class Intern extends Doctor {
    private Doctor mentor;

    public Intern(String name, String spec, Doctor mentor) {
        super(name, spec);
        this.mentor = mentor;
        this.numOfPatients = mentor.numOfPatients/2;
    }
    public Doctor getMentor(){return mentor;}
    public String toString() {
       return "Intern: " + name + ", " + specialization +
          ", Mentor: " + mentor.name +", " +
          mentor.numOfPatients +"," + numOfPatients;
    }
}
א.

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

C#:

public static void Main(string[] args) {
 Doctor[] d = new Doctor[9];
 d[0] = new Doctor("Dr. Cohen", "Cardiology",12);
 d[1] = new Doctor("Dr. Levy", "Neurology");
 d[2] = new Doctor("Dr. Sharon", "Pediatrics",8);

 d[3] = new Intern("Dani", "Cardiology", new Doctor(d[0]));
 d[4] = new Intern("Yael", "Surgery", d[0]);
 d[5] = new Intern("Avi", "Pediatrics", new Doctor(d[2]));
 d[6] = new Intern("Ruth", "Oncology", d[2]);
 d[7] = new Intern("Noam", "Cardiology", new Doctor(d[1]));
 d[8] = new Intern("Maya", "Neurology", new Doctor(d[0]));

 for (int i=0; I < d.Length; i++) {
    Console.WriteLine(d[i]);
 }

 d[0] = new Doctor("Dr. Goldman","Neurology",20);
 d[2].SetName("Dr. Galper");

 d[2].AddPatients(100);
 d[3].AddPatients(200);
 d[5].AddPatients(100);

 Console.WriteLine("After change:");

 for (int i=0; i < d.Length; i++) {
    Console.WriteLine(d[i]);
 }
}

Java:

public static void main(String[] args) {
 Doctor[] d = new Doctor[9];
 d[0] = new Doctor("Dr. Cohen", "Cardiology",12);
 d[1] = new Doctor("Dr. Levy", "Neurology");
 d[2] = new Doctor("Dr. Sharon", "Pediatrics",8);

 d[3] = new Intern("Dani", "Cardiology", new Doctor(d[0]));
 d[4] = new Intern("Yael", "Surgery", d[0]);
 d[5] = new Intern("Avi", "Pediatrics", new Doctor(d[2]));
 d[6] = new Intern("Ruth", "Oncology", d[2]);
 d[7] = new Intern("Noam", "Cardiology", new Doctor(d[1]));
 d[8] = new Intern("Maya", "Neurology", new Doctor(d[0]));

 for (int i=0; i<d.length; i++) {
    System.out.println(d [i]);
 }

 d[0] = new Doctor("Dr. Goldman","Neurology",20);
 d[2].setName("Dr. Galper");

 d[2].addPatients(100);
 d[3].addPatients(200);
 d[5].addPatients(100);

 System.out.println("After change:");

 for (int i=0; i<d.length; i++) {
    System.out.println(d[i]);
 }
}
(9 נקודות)
ב.

מהו הפלט של הפעולה Main?

(6 נקודות)
ג.

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

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

C#:

public static void PrintNotSameSpec(Doctor[] d)

Java:

public static void printNotSameSpec(Doctor[] d)
(3 נקודות)
◂ פתרון מלא לשאלה 10

סעיף א

תשובה:

14 עצמים (טבלה בפתרון); בסוף: C = Dr. Galper עם 108, Dani – 206, Avi – 104, d[0] = Dr. Goldman (Neurology, 20).

כללים חשובים למעקב:

1. `new Doctor(d[0])` – בנאי מעתיק: נוצר עצם חדש עם אותם ערכים. שינוי מאוחר של העצם המקורי לא משפיע על העותק.

2. `new Intern(..., d[0])` – המנחה הוא אותו עצם ש-`d[0]` מפנה אליו (הפניה משותפת), ולכן שינוי בו נראה גם דרך המתמחה.

3. בבנאי של `Intern` הבנאי של `Doctor` מאפס את `numOfPatients`, ואז הוא נקבע ל-`mentor.numOfPatients/2` (חילוק שלמים).

4. `d[0] = new Doctor(...)` משנה רק את התא במערך – העצם הקודם ממשיך להתקיים, ומתמחים שמפנים אליו עדיין מפנים אליו.

5. `AddPatients(num)` מוסיפה רק אם התוצאה אינה שלילית – כאן כל ההוספות חיוביות.

נסמן את העצמים באותיות. הערכים מוצגים בזמן היצירה ובסוף הביצוע:

עצםנוצר ב-namespecializationnumOfPatients ביצירהmentorבסוף הביצוע
A`d[0]`Dr. CohenCardiology12–ללא שינוי (כבר לא ב-`d[0]`, אבל E מפנה אליו)
B`d[1]`Dr. LevyNeurology0–ללא שינוי
C`d[2]`Dr. SharonPediatrics8–name = Dr. Galper, numOfPatients = 8+100=1088+100=108
D1עותק של A (בשורת `d[3]`)Dr. CohenCardiology12–ללא שינוי
E`d[3]` – InternDaniCardiology12/2=612/2=6D1numOfPatients = 6+200=2066+200=206
F`d[4]` – InternYaelSurgery12/2=612/2=6Aללא שינוי
D2עותק של C (בשורת `d[5]`)Dr. SharonPediatrics8–ללא שינוי (עותק – לא מושפע מהשינוי ב-C)
G`d[5]` – InternAviPediatrics8/2=48/2=4D2numOfPatients = 4+100=1044+100=104
H`d[6]` – InternRuthOncology8/2=48/2=4Cללא שינוי בעצם עצמו; המנחה C השתנה
D3עותק של B (בשורת `d[7]`)Dr. LevyNeurology0–ללא שינוי
I`d[7]` – InternNoamCardiology0/2=00/2=0D3ללא שינוי
D4עותק של A (בשורת `d[8]`)Dr. CohenCardiology12–ללא שינוי
J`d[8]` – InternMayaNeurology12/2=612/2=6D4ללא שינוי
K`d[0]` אחרי השינויDr. GoldmanNeurology20––

סדר השינויים אחרי ההדפסה הראשונה:

1. `d[0]` מפנה לעצם חדש K (Dr. Goldman, Neurology, 20). העצם A לא השתנה, ו-F (Yael) עדיין מפנה אליו.

2. `d[2].SetName("Dr. Galper")` – משנה את C. גם H (Ruth) רואה את השינוי, כי המנחה שלה הוא C עצמו; G (Avi) לא – המנחה שלו הוא העותק D2.

3. `d[2].AddPatients(100)` – ב-C: 8+100=1088+100=108.

4. `d[3].AddPatients(200)` – ב-E (Dani): 6+200=2066+200=206.

5. `d[5].AddPatients(100)` – ב-G (Avi): 4+100=1044+100=104.

תשובה: נוצרו 14 עצמים: 9 עצמים במערך, 4 עותקים של רופאים (D1-D4) ו-Dr. Goldman. ערכי כל עצם מופיעים בטבלה. בסוף: C – Dr. Galper עם 108 חולים, Dani עם 206 חולים, Avi עם 104 חולים, ו-`d[0]` הוא Dr. Goldman.

סעיף ב

תשובה:

9 שורות לפני "After change:" ו-9 אחריה, כמפורט בפתרון (למשל Intern: Ruth, Oncology, Mentor: Dr. Galper, 108,4).

מדפיסים כל תא לפי `ToString` של העצם (קישור דינמי: עצם `Intern` מודפס לפי `ToString` של `Intern`).

•תבנית רופא: `Doctor:` + שם + `, ` + התמחות + `,` + מספר חולים.

•תבנית מתמחה: `Intern: ` + שם + `, ` + התמחות + `, Mentor: ` + שם המנחה + `, ` + חולי המנחה + `,` + חולי המתמחה.

ההדפסה הראשונה – לפי ערכי היצירה בטבלה של סעיף א'.

ההדפסה השנייה – אחרי השינויים:

•שורה 1: `d[0]` הוא Dr. Goldman.

•שורה 3: C – השם Dr. Galper ו-108 חולים.

•שורה 4: Dani – 206 חולים; המנחה שלו הוא העותק D1 (Dr. Cohen, 12) – לא השתנה.

•שורה 5: Yael – המנחה A (Dr. Cohen, 12) – לא השתנה, למרות ש-`d[0]` מפנה עכשיו לעצם אחר.

•שורה 6: Avi – 104 חולים; המנחה העותק D2 – עדיין Dr. Sharon, 8.

•שורה 7: Ruth – המנחה הוא C עצמו, ולכן מודפס Dr. Galper, 108.

הערה לנוסח C#: כדי שהקוד יעבור הידור ויפעל לפי הכוונה, צריך לתקן שלושה דברים. בלולאה הראשונה נכתב `I` (אות גדולה) במקום `i`. ב-C# מחלקה יורשת אינה רשאית לגשת לתכונה protected דרך הפניה מטיפוס `Doctor` (`mentor.numOfPatients`, `mentor.name`), ולכן צריך להשתמש בפעולות Get. כמו כן, `ToString` צריכה להיות מוגדרת עם `override` כדי ש-`Console.WriteLine` תפעיל אותה. הפלט שלהלן הוא לפי הכוונה, והוא זהה לפלט של נוסח Java.

תשובה:

Doctor:Dr. Cohen, Cardiology,12
Doctor:Dr. Levy, Neurology,0
Doctor:Dr. Sharon, Pediatrics,8
Intern: Dani, Cardiology, Mentor: Dr. Cohen, 12,6
Intern: Yael, Surgery, Mentor: Dr. Cohen, 12,6
Intern: Avi, Pediatrics, Mentor: Dr. Sharon, 8,4
Intern: Ruth, Oncology, Mentor: Dr. Sharon, 8,4
Intern: Noam, Cardiology, Mentor: Dr. Levy, 0,0
Intern: Maya, Neurology, Mentor: Dr. Cohen, 12,6
After change:
Doctor:Dr. Goldman, Neurology,20
Doctor:Dr. Levy, Neurology,0
Doctor:Dr. Galper, Pediatrics,108
Intern: Dani, Cardiology, Mentor: Dr. Cohen, 12,206
Intern: Yael, Surgery, Mentor: Dr. Cohen, 12,6
Intern: Avi, Pediatrics, Mentor: Dr. Sharon, 8,104
Intern: Ruth, Oncology, Mentor: Dr. Galper, 108,4
Intern: Noam, Cardiology, Mentor: Dr. Levy, 0,0
Intern: Maya, Neurology, Mentor: Dr. Cohen, 12,6

סעיף ג

תשובה:

לכל Intern במערך: אם ההתמחות שלו שונה מזו של המנחה – מדפיסים את שמו (במערך מהשאלה: Yael, Ruth, Noam, Maya).

הרעיון: עוברים על המערך. רק לתאים שהעצם בהם הוא מתמחה (`is Intern` ב-C#, `instanceof Intern` ב-Java) יש מנחה, ולכן בודקים קודם את הטיפוס ורק אז ממירים ל-`Intern`. משווים את ההתמחות של המתמחה להתמחות של המנחה (בעזרת פעולות ה-Get, כי התכונות protected), ואם הן שונות – מדפיסים את שם המתמחה. תא null או רופא רגיל – מדלגים.

בדיקה עם המערך מהסעיף הקודם: Dani – Cardiology כמו המנחה (לא מודפס); Yael – Surgery מול Cardiology (מודפס); Avi – Pediatrics כמו המנחה (לא); Ruth – Oncology מול Pediatrics (מודפס); Noam – Cardiology מול Neurology (מודפס); Maya – Neurology מול Cardiology (מודפס). יודפסו: Yael, Ruth, Noam, Maya.

C#:

public static void PrintNotSameSpec(Doctor[] d)
{
    for (int i = 0; i < d.Length; i++)
    {
        if (d[i] is Intern)
        {
            Intern intern = (Intern)d[i];
            string mentorSpec = intern.GetMentor().GetSpecialization();
            if (!intern.GetSpecialization().Equals(mentorSpec))
                Console.WriteLine(intern.GetName());
        }
    }
}

Java:

public static void printNotSameSpec(Doctor[] d)
{
    for (int i = 0; i < d.length; i++)
    {
        if (d[i] instanceof Intern)
        {
            Intern intern = (Intern) d[i];
            String mentorSpec = intern.getMentor().getSpecialization();
            if (!intern.getSpecialization().equals(mentorSpec))
                System.out.println(intern.getName());
        }
    }
}

תשובה: לכל תא שהוא Intern משווים את ההתמחות שלו להתמחות של המנחה ומדפיסים את שמו אם הן שונות (במערך מהשאלה: Yael, Ruth, Noam, Maya).

שאלה 11 · מוקד חירום – רשימות קריאות לפי סוג

מוקד החירום העירוני מקבל קריאות לעזרה בעקבות מצבי חירום שונים. בעת קבלת הקריאה נקבעת רמת הדחיפות של האירוע (1 – גבוהה, 2 – בינונית, 3 – נמוכה) וסוג האירוע (1 – שריפה, 2 – תאונה, 3 – חילוץ, 4 – פלילי, 5 – ביטחוני).

המחלקה Call מייצגת קריאה לעזרה.

תכונות המחלקה:

C#:

private int type;  // סוג אירוע חירום
private string location; //  אזור
private string description;  //  תיאור
private string callerName; // שם המתקשר
private int priority; // רמת הדחיפות

Java:

private int type;  // סוג אירוע חירום
private String location; //  אזור
private String description;  //  תיאור
private String callerName; // שם המתקשר
private int priority; // רמת הדחיפות

במחלקה הוגדרה פעולה בונה (constructor) המקבלת פרמטרים לכל תכונה וכן פעולות Get/Set.

המחלקה EmergencyList מייצגת רשימת קריאות לאירועי חירום.

א.

כתבו את כותרת המחלקה EmergencyList ואת התכונות שלה.

לייצוג אוסף (רשימה) אפשר להשתמש במחלקות Node, Queue, Stack. אפשר להוסיף תכונות נוספות. יש לתעד את התכונות.

(2 נקודות)

המחלקה EmergencyCenter מייצגת את מוקד החירום. למחלקה תכונה אחת – מערך של רשימות הקריאות לפי סוג אירוע החירום:

private EmergencyList[] arr = new EmergencyList[6];

(השורה זהה בשתי השפות.)

התא 0 מיועד לרשימת קריאות שהטיפול בהן הסתיים.

ב.

כתבו במחלקה EmergencyCenter פעולה המקבלת את הפרטים של הקריאה ומוסיפה אותה לרשימת קריאות <u>בהתאם לסוג האירוע</u> שלה.

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

C#:

public void AddCall(int type, string location, string
                    description, string callerName, int priority)

Java:

public void addCall(int type, String location, String
                    description, String callerName, int priority)
(2 נקודות)
ג.

כתבו במחלקה EmergencyCenter פעולה המקבלת סוג אירוע type ומחזירה קריאה לאירוע הדחוף ביותר מסוג זה. הפעולה גם תמחק את הקריאה מרשימת הקריאות ותעביר אותה לרשימת הקריאות שהטיפול בהן הסתיים.

אם יש מספר קריאות באותה רמת הדחיפות (הגבוהה ביותר), יש להחזיר את הקריאה שהתקבלה ראשונה. אם אין שום קריאה מסוג type, הפעולה תחזיר null.

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

C#:

public Call MostUrgentCall(int type)

Java:

public Call mostUrgentCall(int type)
(6 נקודות)
ד.

כתבו במחלקה EmergencyCenter פעולה המקבלת אזור בעיר (location) ומדפיסה עבור כל סוג אירוע את מספר הקריאות באזור זה.

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

סעיף א

תשובה:

`public class EmergencyList` עם התכונה `Queue<Call> calls` – הקריאות לפי סדר קבלתן.

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

התכונה היחידה הנחוצה היא התור. נוסיף בנאי שיוצר תור ריק, פעולה שמחזירה את התור ופעולה להוספת קריאה – בהן ישתמשו הפעולות של `EmergencyCenter`.

C#:

public class EmergencyList
{
    private Queue<Call> calls;   // הקריאות לפי סדר קבלתן (הראשונה שהתקבלה – בראש התור)

    public EmergencyList()
    {
        calls = new Queue<Call>();
    }
    public Queue<Call> GetCalls()
    {
        return calls;
    }
    public void Add(Call c)      // הוספת קריאה לסוף הרשימה
    {
        calls.Insert(c);
    }
}

Java:

public class EmergencyList
{
    private Queue<Call> calls;   // הקריאות לפי סדר קבלתן (הראשונה שהתקבלה – בראש התור)

    public EmergencyList()
    {
        calls = new Queue<Call>();
    }
    public Queue<Call> getCalls()
    {
        return calls;
    }
    public void add(Call c)      // הוספת קריאה לסוף הרשימה
    {
        calls.insert(c);
    }
}

תשובה: `public class EmergencyList` עם התכונה `private Queue<Call> calls` – תור הקריאות לפי סדר קבלתן (ובנוסף בנאי, GetCalls ו-Add).

סעיף ב

תשובה:

יצירת `new Call(...)` והוספתה לרשימה `arr[type]`.

הרעיון: יוצרים עצם `Call` חדש מהפרטים שהתקבלו (בבנאי שמקבל פרמטר לכל תכונה, לפי סדר התכונות במחלקה), ומוסיפים אותו לרשימה שבתא `arr[type]` – התא של סוג האירוע (1-5).

המערך נוצר עם `new EmergencyList[6]`, ולכן בהתחלה כל התאים null. בבנאי של `EmergencyCenter` יוצרים בכל תא רשימה ריקה, כדי שאפשר יהיה להוסיף אליה.

C#:

public class EmergencyCenter
{
    private EmergencyList[] arr = new EmergencyList[6];

    public EmergencyCenter()
    {
        for (int i = 0; i < arr.Length; i++)
            arr[i] = new EmergencyList();
    }

    public void AddCall(int type, string location, string
                        description, string callerName, int priority)
    {
        Call c = new Call(type, location, description, callerName, priority);
        arr[type].Add(c);
    }
}

Java:

public class EmergencyCenter
{
    private EmergencyList[] arr = new EmergencyList[6];

    public EmergencyCenter()
    {
        for (int i = 0; i < arr.length; i++)
            arr[i] = new EmergencyList();
    }

    public void addCall(int type, String location, String
                        description, String callerName, int priority)
    {
        Call c = new Call(type, location, description, callerName, priority);
        arr[type].add(c);
    }
}

תשובה: יוצרים `new Call(type, location, description, callerName, priority)` ומוסיפים לסוף הרשימה `arr[type]` (הרשימות נוצרות בבנאי של EmergencyCenter).

סעיף ג

תשובה:

מציאת הקריאה עם priority מינימלי (הראשונה בשוויון) בתור של arr[type], הוצאתה והעברתה ל-arr[0]; null אם אין.

נתון: סוג אירוע `type`.

מבוקש: להחזיר את הקריאה הדחופה ביותר מסוג זה (רמת דחיפות 1 היא הגבוהה ביותר, כלומר הערך הקטן ביותר של `priority`), ובשוויון – את זו שהתקבלה ראשונה. הקריאה נמחקת מהרשימה `arr[type]` ומועברת לרשימה `arr[0]`. אם אין קריאות – מחזירים null.

הרעיון: שני מעברים על התור של `arr[type]`:

1. מעבר ראשון – חיפוש: מעבירים את כל הקריאות לתור עזר `temp`, ושומרים ב-`best` את הקריאה עם ה-`priority` הקטן ביותר. מחליפים את `best` רק כשנמצאת קריאה עם ערך קטן ממש – כך בשוויון נשארת הקריאה הראשונה (הקריאות עוברות לפי סדר קבלתן).

2. מעבר שני – מחיקה: מחזירים את הקריאות מ-`temp` לתור המקורי, חוץ מהעצם `best` עצמו (השוואת הפניות). סדר שאר הקריאות נשמר.

3. אם נמצאה קריאה – מוסיפים אותה לרשימה `arr[0]` (טיפול הסתיים) ומחזירים אותה. אם התור היה ריק, `best` נשאר null ומוחזר null.

C#:

public Call MostUrgentCall(int type)
{
    Queue<Call> q = arr[type].GetCalls();
    Queue<Call> temp = new Queue<Call>();
    Call best = null;
    while (!q.IsEmpty())                      // מעבר ראשון: מציאת הדחופה ביותר
    {
        Call c = q.Remove();
        if (best == null || c.GetPriority() < best.GetPriority())
            best = c;
        temp.Insert(c);
    }
    while (!temp.IsEmpty())                   // מעבר שני: החזרה בלי best
    {
        Call c = temp.Remove();
        if (c != best)
            q.Insert(c);
    }
    if (best != null)
        arr[0].Add(best);                     // מעבר לרשימת הקריאות שטופלו
    return best;
}

Java:

public Call mostUrgentCall(int type)
{
    Queue<Call> q = arr[type].getCalls();
    Queue<Call> temp = new Queue<Call>();
    Call best = null;
    while (!q.isEmpty())                      // מעבר ראשון: מציאת הדחופה ביותר
    {
        Call c = q.remove();
        if (best == null || c.getPriority() < best.getPriority())
            best = c;
        temp.insert(c);
    }
    while (!temp.isEmpty())                   // מעבר שני: החזרה בלי best
    {
        Call c = temp.remove();
        if (c != best)
            q.insert(c);
    }
    if (best != null)
        arr[0].add(best);                     // מעבר לרשימת הקריאות שטופלו
    return best;
}

דוגמה: אם ברשימת השריפות (סוג 1) התקבלו לפי הסדר קריאות עם דחיפות 2, 1, 1 – תוחזר הקריאה השנייה (הראשונה מבין שתי הקריאות בדחיפות 1), והיא תעבור ל-`arr[0]`.

תשובה: מעבר על תור הקריאות של `arr[type]` ומציאת הקריאה עם ה-priority הקטן ביותר (הראשונה בשוויון), הוצאתה מהתור והוספתה ל-`arr[0]`; אם אין קריאות – null.

סעיף ד

תשובה:

לכל סוג 1-5: ספירת הקריאות בתור של arr[t] שהאזור שלהן location (עם שחזור) והדפסת המונה.

נתון: אזור `location`.

מבוקש: לכל סוג אירוע (1 עד 5) להדפיס כמה קריאות מהאזור הזה יש ברשימה שלו.

הרעיון: לכל תא `t` מ-1 עד 5 עוברים על תור הקריאות של `arr[t]` דרך תור עזר (כדי לשחזר אותו), וסופרים קריאות שהאזור שלהן שווה ל-`location` (השוואת מחרוזות לפי תוכן). אחרי כל סוג מדפיסים את המונה. התא 0 (קריאות שהטיפול בהן הסתיים) אינו שייך לסוג אירוע מסוים, ולכן לא נספר.

כותרת הפעולה לא ניתנה בשאלה, ולכן נבחרה הכותרת שבקוד.

C#:

public void PrintCallsInLocation(string location)
{
    for (int t = 1; t < arr.Length; t++)
    {
        Queue<Call> q = arr[t].GetCalls();
        Queue<Call> temp = new Queue<Call>();
        int count = 0;
        while (!q.IsEmpty())
        {
            Call c = q.Remove();
            if (c.GetLocation().Equals(location))
                count++;
            temp.Insert(c);
        }
        while (!temp.IsEmpty())               // שחזור הרשימה
            q.Insert(temp.Remove());
        Console.WriteLine("Type " + t + ": " + count);
    }
}

Java:

public void printCallsInLocation(String location)
{
    for (int t = 1; t < arr.length; t++)
    {
        Queue<Call> q = arr[t].getCalls();
        Queue<Call> temp = new Queue<Call>();
        int count = 0;
        while (!q.isEmpty())
        {
            Call c = q.remove();
            if (c.getLocation().equals(location))
                count++;
            temp.insert(c);
        }
        while (!temp.isEmpty())               // שחזור הרשימה
            q.insert(temp.remove());
        System.out.println("Type " + t + ": " + count);
    }
}

תשובה: לכל סוג אירוע 1-5 סופרים בתור שלו את הקריאות שהאזור שלהן הוא location (תוך שחזור התור) ומדפיסים את המונה.

שאלה 12 · רקורסיה על שרשרת: מחיקה וספירת מופעים

נתונה השרשרת הבאה:

נתונות שתי הפעולות הרקורסיביות הבאות:

C#:

public static int One(Node<int> ch, int num)
{
    if(ch.GetNext()!= null)
    {
        if(ch.GetNext().GetValue() == num)
        {
            ch.SetNext(ch.GetNext().GetNext());
            return 1 + One(ch, num);
        }
        else
        {
            ch = ch.GetNext();
            return One(ch, num);
        }
    }
    else
        return 0;
}

public static void Two(Node<int> ch)
 {
    if(ch != null)
    {
        int x = One(ch, ch.GetValue());
        ch.SetNext(new Node<int> (x+1, ch.GetNext()));
        ch = ch.GetNext();
        Two(ch.GetNext());
    }
}

Java:

public static int one(Node<Integer> ch, int num)
{
    if(ch.getNext()!= null)
    {
        if(ch.getNext().getValue() == num)
        {
            ch.setNext(ch.getNext().getNext());
            return 1 + one(ch, num);
        }
        else
        {
            ch = ch.getNext();
            return one(ch, num);
        }
    }
    else
        return 0;
}

public static void two(Node<Integer> ch)
 {
    if(ch != null)
    {
        int x = one(ch, ch.getValue());
        ch.setNext(new Node<Integer> (x+1, ch.getNext()));
        ch = ch.getNext();
        two(ch.getNext());
    }
}
א.

מה תהיה תוצאת זימון הפעולה One(ch1, 14)?

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

(6 נקודות)
ב.

מה מבצעת הפעולה One באופן כללי?

(2 נקודות)
ג.

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

יש להראות מעקב אחרי ביצוע הפעולה Two, אין צורך במעקב אחרי הזימונים של One.

(6 נקודות)
ד.

מה מבצעת הפעולה Two באופן כללי?

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

סעיף א

תשובה:

3; השרשרת אחרי הזימון: 10, 12, 12, 10, 12.

הבנת הפעולה: `One` בודקת תמיד את החוליה שאחרי `ch`:

•אם הערך שלה שווה ל-`num` – "מדלגים" עליה (`ch.SetNext(...)`), כלומר מוחקים אותה מהשרשרת, ומזמנים שוב מאותה חוליה `ch` (כי עכשיו יש אחריה חוליה אחרת) ומוסיפים 1.

•אחרת מתקדמים לחוליה הבאה בלי להוסיף.

•כשאין חוליה הבאה – מחזירים 0.

השרשרת בהתחלה: 10,14,12,12,10,12,14,1410, 14, 12, 12, 10, 12, 14, 14. כדי להבחין בין חוליות עם אותו ערך נסמן אותן לפי מיקומן: 101,142,123,124,105,126,147,14810_1, 14_2, 12_3, 12_4, 10_5, 12_6, 14_7, 14_8.

מעקב אחרי `One(ch1, 14)`:

זימוןchהערך הבאפעולההשרשרת אחרי הזימוןערך מוחזר
110110_114 = numמחיקת 14214_2, החזרת 1 + זימון 210, 12, 12, 10, 12, 14, 141+2=31+2=3
210110_112מעבר ל-12312_3ללא שינוי2
312312_312מעבר ל-12412_4ללא שינוי2
412412_410מעבר ל-10510_5ללא שינוי2
510510_512מעבר ל-12612_6ללא שינוי2
612612_614 = numמחיקת 14714_7, החזרת 1 + זימון 710, 12, 12, 10, 12, 141+1=21+1=2
712612_614 = numמחיקת 14814_8, החזרת 1 + זימון 810, 12, 12, 10, 121+0=11+0=1
812612_6אין (null)עצירהללא שינוי0

הערכים חוזרים מלמטה למעלה: 0→1→2→2→2→2→2→30 \to 1 \to 2 \to 2 \to 2 \to 2 \to 2 \to 3.

תשובה: הפעולה מחזירה 3, והשרשרת אחרי הזימון: 10,12,12,10,1210, 12, 12, 10, 12 (נמחקו שלוש החוליות עם הערך 14).

סעיף ב

תשובה:

מוחקת אחרי ch את כל החוליות שערכן num ומחזירה את מספר החוליות שנמחקו.

הפעולה עוברת על השרשרת מהחוליה שאחרי `ch` ועד סופה, מוחקת ממנה כל חוליה שהערך שלה שווה ל-`num`, ומחזירה את מספר החוליות שנמחקו. החוליה `ch` עצמה לא נבדקת ולא נמחקת.

תשובה: One מוחקת מהשרשרת (אחרי החוליה ch) את כל החוליות שערכן num ומחזירה כמה חוליות נמחקו.

סעיף ג

תשובה:

10, 2, 14, 3, 12, 3

הבנת הפעולה: בכל זימון של `Two` עם חוליה `ch`:

1. `One(ch, ch.GetValue())` מוחקת את כל החוליות שאחרי `ch` עם אותו ערך כמו `ch`, ומחזירה כמה נמחקו – `x`.

2. מוסיפים מיד אחרי `ch` חוליה חדשה עם הערך `x+1` – זה מספר המופעים של הערך בשרשרת המקורית (המופע של `ch` עצמה ועוד `x` שנמחקו).

3. `ch` מתקדם לחוליה החדשה, והזימון הרקורסיבי ממשיך מהחוליה שאחריה – החוליה הבאה מהשרשרת המקורית.

השרשרת בהתחלה: 10,14,12,12,10,12,14,1410, 14, 12, 12, 10, 12, 14, 14.

מעקב:

זימוןchx = One(ch, ערך)נמחקוהחוליה החדשההשרשרת אחרי הזימוןהזימון הבא
110 (הראשונה)1ה-10 החמישית210, 2, 14, 12, 12, 12, 14, 14Two(14)
2142שתי ה-14 שבסוף310, 2, 14, 3, 12, 12, 12Two(12)
3122שתי ה-12 שאחריה310, 2, 14, 3, 12, 3Two(null)
4null–––ללא שינוי – עצירה–

תשובה: אחרי `Two(ch1)` השרשרת היא 10,2,14,3,12,310, 2, 14, 3, 12, 3.

סעיף ד

תשובה:

משאירה כל ערך שונה פעם אחת (לפי סדר ההופעה) ואחריו חוליה עם מספר מופעיו בשרשרת.

הפעולה משאירה בשרשרת רק את המופע הראשון של כל ערך (לפי סדר ההופעה), ומיד אחריו מוסיפה חוליה שהערך שלה הוא מספר הפעמים שהערך הופיע בשרשרת המקורית. בדוגמה: 10 הופיע פעמיים, 14 – שלוש פעמים, 12 – שלוש פעמים, ולכן התקבל 10,2,14,3,12,310, 2, 14, 3, 12, 3.

תשובה: Two הופכת את השרשרת לרשימת זוגות "ערך, מספר המופעים שלו" – כל ערך שונה מופיע פעם אחת, לפי סדר ההופעה הראשונה, ואחריו מספר הפעמים שהופיע.

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

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

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