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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

נקודה אחת תינתן על הערכה.

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

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

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

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

שאלה 1 · מחסנית אחידה: בדיקת זוגיות כל הערכים

א.

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

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

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

Java:

public static boolean isUniform(Stack<Integer> st)

C#:

public static bool IsUniform(Stack<int> st)
(12 נקודות)
ב.

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

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

סעיף א

תשובה:

הפעולה isUniform שלהלן: משווה את הזוגיות של כל איבר לזוגיות של האיבר העליון, ומשחזרת את המחסנית בעזרת מחסנית עזר.

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

1. אם המחסנית ריקה - אין בה איבר שמפר את התנאי, והיא נחשבת אחידה (מחזירים true).

2. שומרים את `parity = st.top() % 2` - הזוגיות של האיבר העליון (0 לזוגי, 1 לאי-זוגי; המספרים חיוביים ולכן השארית אינה שלילית).

3. שולפים את האיברים אחד אחד. לכל איבר `x` בודקים אם `x % 2` שונה מ-`parity`; אם כן - המחסנית אינה אחידה (`uniform = false`). כל איבר שנשלף נדחף למחסנית העזר `temp`.

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

5. מחזירים את `uniform`.

Java:

public static boolean isUniform(Stack<Integer> st)
{
    Stack<Integer> temp = new Stack<Integer>();   // לשחזור המחסנית
    boolean uniform = true;
    if (!st.isEmpty())
    {
        int parity = st.top() % 2;                 // הזוגיות של האיבר העליון
        while (!st.isEmpty())
        {
            int x = st.pop();
            if (x % 2 != parity)                   // נמצא איבר בזוגיות אחרת
                uniform = false;
            temp.push(x);
        }
        while (!temp.isEmpty())                    // החזרת האיברים למקומם
            st.push(temp.pop());
    }
    return uniform;
}

C#:

public static bool IsUniform(Stack<int> st)
{
    Stack<int> temp = new Stack<int>();           // לשחזור המחסנית
    bool uniform = true;
    if (!st.IsEmpty())
    {
        int parity = st.Top() % 2;                 // הזוגיות של האיבר העליון
        while (!st.IsEmpty())
        {
            int x = st.Pop();
            if (x % 2 != parity)                   // נמצא איבר בזוגיות אחרת
                uniform = false;
            temp.Push(x);
        }
        while (!temp.IsEmpty())                    // החזרת האיברים למקומם
            st.Push(temp.Pop());
    }
    return uniform;
}

דוגמה: עבור מחסנית שבה (מלמעלה למטה) 6, 8, 4, 2 - כל האיברים זוגיים והפעולה מחזירה true. עבור 4, 7, 5, 3 - לאיבר העליון 4 זוגיות שונה מזו של 7, והפעולה מחזירה false.

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

סעיף ב

תשובה:

O(n)O(n), כאשר nn מספר האיברים במחסנית.

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

1. כל פעולות המחסנית (`push`, `pop`, `top`, `isEmpty`) מתבצעות ב-O(1)O(1).

2. הלולאה הראשונה שולפת כל איבר פעם אחת ודוחפת אותו ל-`temp`: nn סיבובים, בכל אחד מספר קבוע של פעולות.

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

4. בסך הכול 2n2n סיבובים של עבודה קבועה, כלומר סיבוכיות לינארית.

תשובה: O(n)O(n).

שאלה 2 · הוצאת האיבר האחרון מתור

א.

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

לדוגמה:

עבור התור q הבא הפעולה תחזיר ערך 4

התור q אחרי זימון הפעולה:

(12 נקודות)
ב.

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

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

סעיף א

תשובה:

הפעולה removeLast שלהלן: מעבירה את כל האיברים חוץ מהאחרון לתור עזר, שומרת את האחרון ומחזירה את השאר לתור.

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

הנחה: התור אינו ריק (אחרת אין איבר אחרון להחזיר).

1. כל עוד `q` אינו ריק: מוציאים איבר `x`.

2. אם אחרי ההוצאה `q` ריק - `x` הוא האיבר האחרון: `last = x`.

3. אחרת מכניסים את `x` לתור העזר `temp`.

4. מעבירים את כל האיברים מ-`temp` חזרה ל-`q`, ומחזירים את `last`.

Java:

public static int removeLast(Queue<Integer> q)
{
    Queue<Integer> temp = new Queue<Integer>();
    int last = 0;
    while (!q.isEmpty())
    {
        int x = q.remove();
        if (q.isEmpty())          // x היה האיבר האחרון בתור
            last = x;
        else
            temp.insert(x);       // כל השאר נשמרים בתור העזר
    }
    while (!temp.isEmpty())       // החזרת האיברים לתור באותו הסדר
        q.insert(temp.remove());
    return last;
}

C#:

public static int RemoveLast(Queue<int> q)
{
    Queue<int> temp = new Queue<int>();
    int last = 0;
    while (!q.IsEmpty())
    {
        int x = q.Remove();
        if (q.IsEmpty())          // x היה האיבר האחרון בתור
            last = x;
        else
            temp.Insert(x);       // כל השאר נשמרים בתור העזר
    }
    while (!temp.IsEmpty())       // החזרת האיברים לתור באותו הסדר
        q.Insert(temp.Remove());
    return last;
}

בדיקה על הדוגמה: התור הוא (מהראש לסוף) 8, 10, 11, 2, 3, 16, 12, 4. שבעת האיברים הראשונים עוברים ל-`temp`; אחרי הוצאת 4 התור ריק, ולכן `last = 4`. בסוף `q` מכיל 8, 10, 11, 2, 3, 16, 12 והפעולה מחזירה 4.

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

סעיף ב

תשובה:

O(n)O(n), כאשר nn מספר האיברים בתור.

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

1. כל פעולות התור (`insert`, `remove`, `isEmpty`) מתבצעות ב-O(1)O(1).

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

3. הלולאה השנייה מחזירה n−1n-1 איברים לתור.

4. בסך הכול כ-2n2n פעולות קבועות.

תשובה: O(n)O(n).

שאלה 3 · שרשרת חוליות: ערכים שליליים ללא חזרות

א.

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

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

אם כן – הפעולה תחזיר ערך true, ולא – ערך false.

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

Java:

public static boolean uniqNeg(Node<Integer> chain)

C#:

public static bool UniqNeg(Node<int> chain)

לדוגמה: עבור שרשרת הבאה הפעולה תחזיר ערך true

עבור שרשרת הבאה הפעולה תחזיר ערך false כי ערך -3 מופיע פעמיים

(12 נקודות)
ב.

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

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

סעיף א

תשובה:

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

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

1. `p` מתחיל בחוליה הראשונה.

2. אם `p.getValue()` שלילי - עוברים עם `q` על כל החוליות מ-`p.getNext()` ועד הסוף. אם באחת מהן הערך שווה ל-xx - מצאנו חזרה, מחזירים false.

3. מקדמים את `p` לחוליה הבאה.

4. אם הגענו לסוף השרשרת בלי למצוא חזרה - מחזירים true.

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

Java:

public static boolean uniqNeg(Node<Integer> chain)
{
    Node<Integer> p = chain;
    while (p != null)
    {
        int x = p.getValue();
        if (x < 0)
        {
            // מחפשים את x בחוליות שאחרי p
            Node<Integer> q = p.getNext();
            while (q != null)
            {
                if (q.getValue() == x)
                    return false;     // הערך השלילי x מופיע פעמיים
                q = q.getNext();
            }
        }
        p = p.getNext();
    }
    return true;
}

C#:

public static bool UniqNeg(Node<int> chain)
{
    Node<int> p = chain;
    while (p != null)
    {
        int x = p.GetValue();
        if (x < 0)
        {
            // מחפשים את x בחוליות שאחרי p
            Node<int> q = p.GetNext();
            while (q != null)
            {
                if (q.GetValue() == x)
                    return false;     // הערך השלילי x מופיע פעמיים
                q = q.GetNext();
            }
        }
        p = p.GetNext();
    }
    return true;
}

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

•בשרשרת 10, -3, 10, 6, -2, -8, 7 הערכים השליליים -3, -2, -8 מופיעים כל אחד פעם אחת, והפעולה מחזירה true (החזרה של 10 אינה משנה, כי 10 חיובי).

•בשרשרת 10, -3, 10, -3, -2, -8, 7 - כש-`p` נמצא בחוליה הראשונה שערכה -3, החיפוש קדימה מוצא -3 בחוליה הרביעית, והפעולה מחזירה false.

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

סעיף ב

תשובה:

O(n2)O(n^2), כאשר nn מספר החוליות בשרשרת.

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

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

2. עבור חוליה במקום ii שערכה שלילי, הלולאה הפנימית עוברת על כל n−in-i החוליות שאחריה.

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

(n−1)+(n−2)+⋯+1=n(n−1)2(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}

4. זהו סדר גודל ריבועי.

תשובה: O(n2)O(n^2).

שאלה 4 · כתיבת מחלקת על לפי מחלקה יורשת ופלט

נתונות שתי המחלקות Child ו- Driver הבאות:

Java:

public class Child extends Parent {
  private int age;
  public Child( String fName, String lName, char gender,int age){
      super(fName, lName, gender);
      this.age = age;
  }

  public Child(){
    super("David","Cohen");
    this.age = 13;
    this.gender = 'm';
  }

  public int getBirthYear(){
     return Parent.year - this.age;
  }

  public void printDetails() {
     if(this.gender == 'f')System.out.print("Daughter ");
     else System.out.print("Son ");
     System.out.print(getName()+" was born at " + getBirthYear());
  }
}// end of class Child

public class Driver {
    public static void main(String[] args) {

           Parent.setYear(2020);

           Parent[] family = new Parent[5];
           family[0] = new Parent("Anna", "Blum");
           family[1] = new Parent("Moshe","Coehn",'m');
           family[2] = new Child();
           family[3] = new Child("Dorit","Levi",'f',24);
           family[4] = new Child("Eli","Coehn",'m',30);
           family[3].updateCity("Tel-Aviv");
           family[4].updateCity("Jerusalem");

           for(int i=0; i<family.length; i++)
           {
               family[i].printDetails();
               family[i].printCity();
           }
    }
}// end of class Driver

C#:

public class Child : Parent {
  private int age;
  public Child( String fName, String lName, char gender,int age):
                base(fName, lName, gender){
      this.age = age;
  }

  public Child() : base("David","Cohen"){
    this.age = 13;
    this.gender = 'm';
  }

  public int GetBirthYear(){
     return Parent.year - this.age;
  }

  public override void PrintDetails() {
     if(this.gender == 'f')Console.Write("Daughter ");
     else Console.Write ("Son ");
     Console.Write (GetName()+" was born at " + GetBirthYear());
  }
}// end of class Child

public class Driver {
    public static void Main(string[] args) {

           Parent.SetYear(2020);

           Parent[] family = new Parent[5];
           family[0] = new Parent("Anna", "Blum");
           family[1] = new Parent("Moshe","Coehn",'m');
           family[2] = new Child();
           family[3] = new Child("Dorit","Levi",'f',24);
           family[4] = new Child("Eli","Coehn",'m',30);
           family[3].UpdateCity("Tel-Aviv");
           family[4].UpdateCity("Jerusalem");

           for(int i=0; i<family.Length; i++)
           {
               family[i].PrintDetails();
               family[i].PrintCity();
           }
    }
}// end of class Driver

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

Mother Anna Blum lives in Beer-Sheva
Father Moshe Coehn lives in Beer-Sheva
Son David Cohen was born at 2007 lives in Beer-Sheva
Daughter Dorit Levi was born at 1996 lives in Tel-Aviv
Son Eli Coehn was born at 1990 lives in Jerusalem

כתבו את המחלקה המורישה Parent (מחלקת העל, super-class) של המחלקה Child.

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

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

אין לשנות את מחלקת Child.

◂ פתרון מלא לשאלה 4

פתרון

תשובה:

המחלקה Parent שלהלן: תכונות fName, lName, gender, city ותכונה סטטית year; שני בנאים (ברירת מחדל למגדר 'f'), setYear סטטית, getName, updateCity, printCity (עם ברירת מחדל Beer-Sheva) ו-printDetails (Mother/Father).

הרעיון: עוברים על המחלקות Child ו-Driver ואוספים כל תכונה וכל פעולה של Parent שהן משתמשות בהן. אחר כך משתמשים בפלט כדי להבין מה כל פעולה צריכה לעשות.

מה נדרש מהקוד:

1. `super(fName, lName, gender)` - בנאי עם שם פרטי, שם משפחה ותו של מגדר.

2. `super("David","Cohen")` ו-`new Parent("Anna", "Blum")` - בנאי עם שני פרמטרים בלבד.

3. `this.gender = 'm'` ו-`this.gender == 'f'` בתוך Child - התכונה `gender` מטיפוס `char` חייבת להיות נגישה למחלקה היורשת, ולכן `protected`.

4. `Parent.year` - תכונה סטטית (משותפת לכל העצמים) מטיפוס `int`, נגישה מ-Child.

5. `Parent.setYear(2020)` - פעולה סטטית שקובעת את `year`.

6. `getName()` - פעולה שמחזירה את השם המלא.

7. `updateCity(...)`, `printCity()` - עיר מגורים, ופעולה שמדפיסה אותה.

8. `printDetails()` - נקראת על כל איברי המערך `Parent[]`, ולכן חייבת להיות ב-Parent. ב-Child היא נדרסת, וההפעלה הפולימורפית בוחרת בגרסה של Child עבור עצמי Child (ב-C# החתימה ב-Child היא `override`, ולכן ב-Parent היא חייבת להיות `virtual`).

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

1. `Anna Blum` נבנתה בבנאי עם שני פרמטרים, והודפס עבורה `Mother` - ולכן בבנאי זה המגדר נקבע כברירת מחדל ל-`'f'`. (ב-`Child()` הבנאי הזה נקרא, ואחריו Child משנה את המגדר ל-`'m'` - ואכן מודפס `Son`.)

2. `Moshe Coehn` עם `'m'` מודפס `Father` - ולכן `printDetails` של Parent מדפיסה `Mother ` כאשר המגדר `'f'` ו-`Father ` אחרת, ואחר כך את השם.

3. `getName()` מחזירה את השם הפרטי, רווח ושם המשפחה: `David Cohen`.

4. מי שלא עדכן עיר מודפס `lives in Beer-Sheva` - ולכן העיר ההתחלתית בבנאי היא `"Beer-Sheva"`, ו-`updateCity` מחליפה אותה.

5. `printCity()` מודפסת מיד אחרי `printDetails()` באותה שורה, ומסיימת את השורה - ולכן היא מדפיסה `" lives in " + city` עם ירידת שורה (println / WriteLine), בעוד ש-`printDetails` משתמשת ב-print / Write בלי ירידת שורה.

6. שנות הלידה: 2020−13=20072020-13=2007, 2020−24=19962020-24=1996, 2020−30=19902020-30=1990 - מתאימות ל-`year = 2020`.

Java:

public class Parent
{
    protected String fName;
    protected String lName;
    protected char gender;
    protected String city;
    public static int year;          // שנה נוכחית, משותפת לכל העצמים

    public Parent(String fName, String lName, char gender)
    {
        this.fName = fName;
        this.lName = lName;
        this.gender = gender;
        this.city = "Beer-Sheva";    // עיר ברירת מחדל
    }

    public Parent(String fName, String lName)
    {
        this(fName, lName, 'f');     // ברירת מחדל: אישה
    }

    public static void setYear(int y)
    {
        year = y;
    }

    public String getName()
    {
        return this.fName + " " + this.lName;
    }

    public void updateCity(String city)
    {
        this.city = city;
    }

    public void printCity()
    {
        System.out.println(" lives in " + this.city);
    }

    public void printDetails()
    {
        if (this.gender == 'f')
            System.out.print("Mother ");
        else
            System.out.print("Father ");
        System.out.print(getName());
    }
}

C#:

public class Parent
{
    protected string fName;
    protected string lName;
    protected char gender;
    protected string city;
    public static int year;          // שנה נוכחית, משותפת לכל העצמים

    public Parent(string fName, string lName, char gender)
    {
        this.fName = fName;
        this.lName = lName;
        this.gender = gender;
        this.city = "Beer-Sheva";    // עיר ברירת מחדל
    }

    public Parent(string fName, string lName) : this(fName, lName, 'f')
    {
                                     // ברירת מחדל: אישה
    }

    public static void SetYear(int y)
    {
        year = y;
    }

    public string GetName()
    {
        return this.fName + " " + this.lName;
    }

    public void UpdateCity(string city)
    {
        this.city = city;
    }

    public void PrintCity()
    {
        Console.WriteLine(" lives in " + this.city);
    }

    public virtual void PrintDetails()
    {
        if (this.gender == 'f')
            Console.Write("Mother ");
        else
            Console.Write("Father ");
        Console.Write(GetName());
    }
}

בדיקה מול הפלט: עבור `family[2] = new Child()`: הבנאי של Parent קובע שם David Cohen, מגדר `'f'` ועיר Beer-Sheva; Child קובע גיל 13 ומגדר `'m'`. בלולאה נקראת `printDetails` של Child ומדפיסה `Son David Cohen was born at 2007`, ואחריה `printCity` של Parent מוסיפה ` lives in Beer-Sheva` ויורדת שורה. כך מתקבלות בדיוק חמש שורות הפלט הנתונות.

תשובה: המחלקה Parent שלמעלה.

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

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

Java:

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

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

C#:

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

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

נתונה מחסנית s

מה יהיה התוכן של המחסנית s אחרי זימון הפעולה what(s) עבור המחסנית s

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

(10 נקודות)
ב.

תנו דוגמה למחסנית s המכילה לפחות חמישה ערכים כך שתוכן המחסנית לא ישתנה אחרי זימון הפעולה what(s)

(3 נקודות)
ג.

מה מבצעת הפעולה what(s) עבור מחסנית של מספרים שלמים s?

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

סעיף א

תשובה:

מלמעלה למטה: 6, 4, 4, 1 (כלומר [6, 4, 4, 1], 6 בראש המחסנית).

מה הפעולה עושה בכל סיבוב: בכל סיבוב של הלולאה החיצונית שולפים את האיבר העליון `x`. אחר כך הלולאה הפנימית שולפת את כל שאר האיברים ל-`temp1` ובודקת אם יש ביניהם איבר גדול מ-`x` (`found`). הלולאה שאחריה מחזירה את כל האיברים מ-`temp1` ל-`s` (בסדר המקורי). אם לא נמצא איבר גדול מ-`x` - `x` נדחף ל-`temp2`; אחרת הוא נזרק. בסוף מעבירים את `temp2` ל-`s`.

המחסנית ההתחלתית (מלמעלה למטה): 4, 6, 3, 1, 4, 1, 4, 1.

טבלת מעקב (המחסניות רשומות מלמעלה למטה):

סיבובxהאיברים שמתחת ל-x ב-sfoundtemp2 אחרי הסיבוב
146, 3, 1, 4, 1, 4, 1true (6 > 4)ריקה
263, 1, 4, 1, 4, 1false6
331, 4, 1, 4, 1true (4 > 3)6
414, 1, 4, 1true6
541, 4, 1false (אין איבר גדול מ-4)4, 6
614, 1true4, 6
741false4, 4, 6
81(ריקה)false1, 4, 4, 6

אחרי הסיבוב השמיני `s` ריקה. הלולאה האחרונה שולפת מ-`temp2` את 1, 4, 4, 6 (בסדר זה) ודוחפת ל-`s`. האיבר שנדחף אחרון (6) נמצא בראש.

תשובה: תוכן המחסנית s (מלמעלה למטה): 6, 4, 4, 1.

סעיף ב

תשובה:

למשל (מלמעלה למטה) 5, 4, 3, 2, 1 - כל איבר גדול או שווה לכל האיברים שמתחתיו.

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

דוגמה: מחסנית שבה (מלמעלה למטה) 5, 4, 3, 2, 1 (1 בתחתית, 5 בראש). בכל סיבוב `x` הוא האיבר הגדול ביותר מבין הנותרים, ולכן `found` נשאר false וכל איבר נדחף ל-`temp2`. `temp2` מקבלת 5, 4, 3, 2, 1 בסדר הפוך, והעברתה ל-`s` מחזירה את 5 לראש.

תשובה: למשל s = (מלמעלה למטה) 5, 4, 3, 2, 1.

סעיף ג

תשובה:

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

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

לכן בסוף הערכים ב-`s` מסודרים כך שמהתחתית לראש הם לא יורדים (בראש נמצא המקסימום של המחסנית), כמו בסעיף א': 1, 4, 4, 6 מהתחתית לראש.

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

שאלה 6 · תורים: תור התחלתי ושכפול של תור

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

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

•אפשר להניח שקיימת פעולה `public static int size(Queue<Integer> q)` (ב-C#: `public static int Size(Queue<int> q)`) המחזירה מספר איברים בתור q.

א.

הגדרה: תור q1 נקרא "תור התחלתי" של תור q2 אם כל האיברים של q1 נמצאים בתחילת התור q2 באותו הסדר.

לדוגמה:

התור q1

הוא תור התחלתי של התור q2

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

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

Java:

public static boolean startWith(Queue<Integer> q1,
                                Queue<Integer> q2)

C#:

public static bool StartWith(Queue<int> q1,
                             Queue<int> q2)
(7 נקודות)
ב.

הגדרה: תור q2 נקרא "שכפול" של תור q1 אם כל האיברים של q1 נמצאים בתור q2 באותו הסדר כמה פעמים (התור q2 מורכב ממספר של תורים q1).

לדוגמה:

עבור התור q1

התור q2 הוא "שכפול" של התור q1

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

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

Java:

public static boolean duplication(Queue<Integer> q1,
                                  Queue<Integer> q2)

C#:

public static bool Duplication(Queue<int> q1,
                               Queue<int> q2)
(7 נקודות)
ג.

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

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

סעיף א

תשובה:

הפעולה startWith שלהלן: אם q1 ארוך מ-q2 - false; אחרת מסובבים את q2 סיבוב שלם, ובמקביל את q1, ומשווים את n1n_1 האיברים הראשונים.

הרעיון: q1 הוא תור התחלתי של q2 אם n1≤n2n_1\le n_2 (כאשר n1n_1, n2n_2 מספרי האיברים) ואם n1n_1 האיברים הראשונים של q2 שווים, לפי הסדר, לאיברי q1.

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

1. מחשבים `n1 = size(q1)` ו-`n2 = size(q2)`. אם n1>n2n_1>n_2 - q1 לא יכול להיות בתחילת q2, מחזירים false.

2. מבצעים n2n_2 סיבובים של q2. בסיבוב ii מוציאים את `x` מ-q2.

3. בסיבובים i<n1i<n_1 מסובבים גם את q1: מוציאים את `y`, משווים ל-`x`; אם הם שונים - `ok = false`. מכניסים את `y` חזרה לסוף q1.

4. מכניסים את `x` חזרה לסוף q2.

5. בסוף q1 סובב בדיוק n1n_1 פעמים ו-q2 בדיוק n2n_2 פעמים, ולכן שניהם חזרו למצבם המקורי. מחזירים את `ok`.

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

Java:

public static boolean startWith(Queue<Integer> q1,
                                Queue<Integer> q2)
{
    int n1 = size(q1);
    int n2 = size(q2);
    if (n1 > n2)                  // q1 ארוך מ-q2 - אינו יכול להיות בתחילתו
        return false;
    boolean ok = true;
    for (int i = 0; i < n2; i++)  // סיבוב שלם של q2
    {
        int x = q2.remove();
        if (i < n1)               // סיבוב שלם של q1 במקביל
        {
            int y = q1.remove();
            if (x != y)
                ok = false;
            q1.insert(y);
        }
        q2.insert(x);
    }
    return ok;
}

C#:

public static bool StartWith(Queue<int> q1,
                             Queue<int> q2)
{
    int n1 = Size(q1);
    int n2 = Size(q2);
    if (n1 > n2)                  // q1 ארוך מ-q2 - אינו יכול להיות בתחילתו
        return false;
    bool ok = true;
    for (int i = 0; i < n2; i++)  // סיבוב שלם של q2
    {
        int x = q2.Remove();
        if (i < n1)               // סיבוב שלם של q1 במקביל
        {
            int y = q1.Remove();
            if (x != y)
                ok = false;
            q1.Insert(y);
        }
        q2.Insert(x);
    }
    return ok;
}

בדיקה על הדוגמה: q1 = 2, 10, 12, 3 (n1=4n_1=4), q2 = 2, 10, 12, 3, 7, 4, 1 (n2=7n_2=7). בארבעת הסיבובים הראשונים מושווים 2=2, 10=10, 12=12, 3=3; בשלושת הבאים רק q2 מסתובב. התוצאה true, ושני התורים חוזרים לסדרם.

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

סעיף ב

תשובה:

הפעולה duplication שלהלן: בודקים ש-n2n_2 מתחלק ב-n1n_1, ואז מסובבים את q2 סיבוב שלם ואת q1 שוב ושוב במעגל, ומשווים איבר מול איבר.

הרעיון: q2 מורכב מכמה עותקים של q1 אם ורק אם:

•מספר האיברים n2n_2 הוא כפולה של n1n_1, וגם

•כל איבר במקום ii ב-q2 שווה לאיבר במקום i mod n1i \bmod n_1 ב-q1.

את התנאי השני בודקים בעזרת סיבובים: בכל צעד מוציאים איבר מ-q2 ואיבר מ-q1, משווים ומחזירים כל אחד לסוף התור שלו. כיוון ש-q1 "מסתובב" במעגל, אחרי כל n1n_1 צעדים הוא חוזר להתחלה ומשווים אותו לעותק הבא בתוך q2.

1. מחשבים `n1 = size(q1)`, `n2 = size(q2)`. אם q1 ריק או ש-n2n_2 אינו מתחלק ב-n1n_1 - מחזירים false (ההגנה n1=0n_1=0 מונעת גם חלוקה באפס).

2. מבצעים n2n_2 צעדים. בכל צעד: `x` מ-q2, `y` מ-q1; אם `x != y` - `ok = false`; מחזירים את `y` לסוף q1 ואת `x` לסוף q2.

3. q2 סובב n2n_2 פעמים ו-q1 סובב n2n_2 פעמים, שזו כפולה של n1n_1 - ולכן שניהם חוזרים בדיוק למצבם המקורי. מחזירים את `ok`.

Java:

public static boolean duplication(Queue<Integer> q1,
                                  Queue<Integer> q2)
{
    int n1 = size(q1);
    int n2 = size(q2);
    if (n1 == 0 || n2 % n1 != 0)  // אורך q2 חייב להיות כפולה של אורך q1
        return false;
    boolean ok = true;
    for (int i = 0; i < n2; i++)  // סיבוב שלם של q2
    {
        int x = q2.remove();
        int y = q1.remove();      // q1 מסתובב שוב ושוב במעגל
        if (x != y)
            ok = false;
        q1.insert(y);
        q2.insert(x);
    }
    return ok;
}

C#:

public static bool Duplication(Queue<int> q1,
                               Queue<int> q2)
{
    int n1 = Size(q1);
    int n2 = Size(q2);
    if (n1 == 0 || n2 % n1 != 0)  // אורך q2 חייב להיות כפולה של אורך q1
        return false;
    bool ok = true;
    for (int i = 0; i < n2; i++)  // סיבוב שלם של q2
    {
        int x = q2.Remove();
        int y = q1.Remove();      // q1 מסתובב שוב ושוב במעגל
        if (x != y)
            ok = false;
        q1.Insert(y);
        q2.Insert(x);
    }
    return ok;
}

בדיקה על הדוגמה: q1 = 3, 7, 4, 1 (n1=4n_1=4), q2 = 3, 7, 4, 1, 3, 7, 4, 1, 3, 7, 4, 1 (n2=12n_2=12). 12 mod 4=012 \bmod 4=0, ובכל אחד מ-12 הצעדים האיברים שווים, לכן התוצאה true. לעומת זאת, עבור q2 = 3, 7, 4, 1, 3, 7, 4 (n2=7n_2=7) - 7 אינו מתחלק ב-4 והתוצאה false.

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

סעיף ג

תשובה:

שתי הפעולות לינאריות: O(n1+n2)O(n_1+n_2), כלומר O(n)O(n).

נסמן ב-n1n_1 וב-n2n_2 את מספרי האיברים ב-q1 וב-q2. פעולות התור עצמן (`insert`, `remove`) הן O(1)O(1), והפעולה `size` עוברת על התור פעם אחת, כלומר O(n1)O(n_1) או O(n2)O(n_2).

1. startWith: שתי קריאות ל-`size` עולות O(n1+n2)O(n_1+n_2). אחריהן לולאה של n2n_2 סיבובים, ובכל סיבוב מספר קבוע של פעולות. סך הכול O(n1+n2)O(n_1+n_2) (וכיוון שמגיעים ללולאה רק כאשר n1≤n2n_1\le n_2, זה O(n2)O(n_2)).

2. duplication: שוב שתי קריאות ל-`size` (O(n1+n2)O(n_1+n_2)), ואחריהן לולאה של n2n_2 צעדים קבועים. סך הכול O(n1+n2)O(n_1+n_2).

תשובה: שתי הפעולות בסיבוכיות לינארית, O(n)O(n) (ליתר דיוק O(n1+n2)O(n_1+n_2)).

שאלה 7 · שרשרת חוליות: בדיקת סדרה עולה-יורדת

סדרת מספרים נקראת "עולה – יורדת" אם עד איבר מסוים המספרים הולכים וגדלים ומאיבר זה ואילך, הם הולכים וקטנים.

לדוגמה:

הסדרה הבאה היא סדרה "עולה – יורדת"

2, 5, 13, 19, 21, 18, 13, 6, 32,\ 5,\ 13,\ 19,\ \mathbf{21},\ 18,\ 13,\ 6,\ 3

א.

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

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

Java:

public static boolean isUpDown(Node<Integer> chain)

C#:

public static bool IsUpDown(Node<int> chain)
(14 נקודות)
ב.

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

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

סעיף א

תשובה:

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

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

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

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

אם אחרי שני השלבים הגענו לחוליה האחרונה - כל הסדרה עלתה ואחר כך ירדה. אם עצרנו לפני הסוף - יש איבר שמפר את הכלל (עלייה אחרי ירידה, או שני איברים שווים), והסדרה אינה "עולה – יורדת".

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

2. `p` מתקדם בשלב העלייה כל עוד `p.getValue() < p.getNext().getValue()`.

3. `p` ממשיך בשלב הירידה כל עוד `p.getValue() > p.getNext().getValue()`.

4. מחזירים `p.getNext() == null`.

הערה: סדרה שעולה עד סופה (השיא הוא האיבר האחרון והקטע היורד ריק) מתקבלת כ"עולה – יורדת" לפי פתרון זה; סדרה שיורדת כבר מתחילתה - לא.

Java:

public static boolean isUpDown(Node<Integer> chain)
{
    // צריך לפחות שני איברים, והצעד הראשון חייב להיות עלייה
    if (chain == null || chain.getNext() == null
            || chain.getValue() >= chain.getNext().getValue())
        return false;
    Node<Integer> p = chain;
    // שלב העלייה: מתקדמים כל עוד האיבר הבא גדול יותר
    while (p.getNext() != null && p.getValue() < p.getNext().getValue())
        p = p.getNext();
    // שלב הירידה: מתקדמים כל עוד האיבר הבא קטן יותר
    while (p.getNext() != null && p.getValue() > p.getNext().getValue())
        p = p.getNext();
    // הסדרה תקינה רק אם הגענו כך לסוף השרשרת
    return p.getNext() == null;
}

C#:

public static bool IsUpDown(Node<int> chain)
{
    // צריך לפחות שני איברים, והצעד הראשון חייב להיות עלייה
    if (chain == null || chain.GetNext() == null
            || chain.GetValue() >= chain.GetNext().GetValue())
        return false;
    Node<int> p = chain;
    // שלב העלייה: מתקדמים כל עוד האיבר הבא גדול יותר
    while (p.GetNext() != null && p.GetValue() < p.GetNext().GetValue())
        p = p.GetNext();
    // שלב הירידה: מתקדמים כל עוד האיבר הבא קטן יותר
    while (p.GetNext() != null && p.GetValue() > p.GetNext().GetValue())
        p = p.GetNext();
    // הסדרה תקינה רק אם הגענו כך לסוף השרשרת
    return p.GetNext() == null;
}

בדיקה על הדוגמה: 2, 5, 13, 19, 21, 18, 13, 6, 3: הצעד הראשון 2 < 5. בשלב העלייה `p` מגיע ל-21 (כי 21 > 18 עוצר את העלייה). בשלב הירידה 21 > 18 > 13 > 6 > 3, ו-`p` מגיע לחוליה האחרונה - הפעולה מחזירה true. עבור 1, 3, 2, 4: העלייה נעצרת ב-3, הירידה ב-2 (כי 2 < 4), ו-`p` אינו בסוף - false.

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

סעיף ב

תשובה:

O(n)O(n), כאשר nn מספר החוליות.

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

1. שתי הלולאות ממשיכות זו את זו עם אותו מצביע `p`, ו-`p` רק מתקדם. לכן בשתיהן יחד `p` עובר על כל חוליה לכל היותר פעם אחת: לכל היותר n−1n-1 צעדים.

2. בכל צעד מתבצעות השוואה אחת והתקדמות אחת - עבודה קבועה.

3. הבדיקות שלפני הלולאות ושאחריהן הן O(1)O(1).

תשובה: O(n)O(n).

שאלה 8 · עץ בינרי: הדפסת צמתים קטנים מהממוצע

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

לדוגמה:

עבור העץ הבא

הפעולה תדפיס 5, 2, 6, 4, 3

הערה: סדר ההדפסה לא חשוב.

◂ פתרון מלא לשאלה 8

פתרון

תשובה:

הפעולה printBelowAverage שלהלן: מחשבת ברקורסיה את סכום הערכים ואת מספר הצמתים, מחלקת לקבלת הממוצע, ובמעבר נוסף על העץ מדפיסה כל ערך קטן ממנו. בדוגמה: ממוצע 8.25, מודפסים 5 6 2 4 3.

הרעיון: אי אפשר לדעת אם ערך קטן מהממוצע לפני שמכירים את כל העץ, ולכן העבודה נעשית בשני שלבים:

1. חישוב הממוצע: פעולה רקורסיבית `sumTree` מחזירה את סכום הערכים בעץ (ערך השורש + סכום תת-העץ השמאלי + סכום תת-העץ הימני; לעץ ריק - 0), ופעולה רקורסיבית `countNodes` מחזירה את מספר הצמתים באותו אופן (1 + שני תתי-העצים). הממוצע הוא המנה ביניהם - כמספר ממשי (`double`), כדי לא לאבד את החלק השברי בחילוק שלמים.

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

הפעולה הראשית `printBelowAverage` מחשבת את הממוצע וקוראת ל-`printLess`. עבור עץ ריק אין מה להדפיס (וגם נמנעת חלוקה באפס).

Java:

// סכום כל הערכים בעץ
public static int sumTree(BinNode<Integer> t)
{
    if (t == null)
        return 0;
    return t.getValue() + sumTree(t.getLeft()) + sumTree(t.getRight());
}

// מספר הצמתים בעץ
public static int countNodes(BinNode<Integer> t)
{
    if (t == null)
        return 0;
    return 1 + countNodes(t.getLeft()) + countNodes(t.getRight());
}

// הדפסת כל הצמתים שערכם קטן מ-avg
public static void printLess(BinNode<Integer> t, double avg)
{
    if (t != null)
    {
        if (t.getValue() < avg)
            System.out.print(t.getValue() + " ");
        printLess(t.getLeft(), avg);
        printLess(t.getRight(), avg);
    }
}

public static void printBelowAverage(BinNode<Integer> bt)
{
    if (bt == null)
        return;
    double avg = (double) sumTree(bt) / countNodes(bt);
    printLess(bt, avg);
}

C#:

// סכום כל הערכים בעץ
public static int SumTree(BinNode<int> t)
{
    if (t == null)
        return 0;
    return t.GetValue() + SumTree(t.GetLeft()) + SumTree(t.GetRight());
}

// מספר הצמתים בעץ
public static int CountNodes(BinNode<int> t)
{
    if (t == null)
        return 0;
    return 1 + CountNodes(t.GetLeft()) + CountNodes(t.GetRight());
}

// הדפסת כל הצמתים שערכם קטן מ-avg
public static void PrintLess(BinNode<int> t, double avg)
{
    if (t != null)
    {
        if (t.GetValue() < avg)
            Console.Write(t.GetValue() + " ");
        PrintLess(t.GetLeft(), avg);
        PrintLess(t.GetRight(), avg);
    }
}

public static void PrintBelowAverage(BinNode<int> bt)
{
    if (bt == null)
        return;
    double avg = (double) SumTree(bt) / CountNodes(bt);
    PrintLess(bt, avg);
}

בדיקה על הדוגמה: בעץ 8 צמתים: 10, 5, 14, 6, 2, 22, 4, 3.

•סכום: 10+5+14+6+2+22+4+3=6610+5+14+6+2+22+4+3=66

•ממוצע: 668=8.25\frac{66}{8}=8.25

•הערכים הקטנים מ-8.25: 5, 6, 2, 4, 3. במעבר תחילי הם מודפסים בסדר 5 6 2 4 3 - אותם ערכים כמו בדוגמה (הסדר אינו חשוב).

סיבוכיות: שלושה מעברים על העץ, כל אחד O(n)O(n) - סך הכול O(n)O(n).

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

שאלה 9 · ירושה ופולימורפיזם: מעקב אחר עצמים במערך

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

Java:

public class One {
    protected int n1;
    public One ()
    {
        this.n1 = 1;
    }
    public One (int val)
    {
        this.n1 = val;
    }
    public void update(int k)
    {
        this.n1 = this.n1 * k;
    }
    public String toString()
    {
        return "One: n1=" + this.n1;
    }
}

public class Two extends One {
    protected int n2;
    public Two(int val)
    {
        this.n2 = val;
    }
    public Two (int val1,int val2)
    {
        super(val1);
        this.n2 = val2;
    }
    public void update(int k)
    {
        super.update(k);
        this.n2 = this.n2 * k;
    }

    public String toString()
    {
        return super.toString() + " Two: n2=" + this.n2;
    }
}

public class Test {
    public   static void main(String[] args){
        One[] arr = new One [6];
        arr [0] = new One (2);
        arr [1] = new Two(4);
        arr [2] = new Two(3, 6);
        arr [3] = arr [0];
        arr [4] = new Two(4);
        arr [5] = arr[1];

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

(*)     for(int i=0;i< arr.length;i++)
            arr [i].update(i+3);

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

C#:

public class One {
    protected int n1;
    public One ()
    {
        this.n1 = 1;
    }
    public One (int val)
    {
        this.n1 = val;
    }
    public virtual void Update(int k)
    {
        this.n1 = this.n1 * k;
    }
    public override string ToString()
    {
        return "One: n1=" + this.n1;
    }
}

public class Two : One {
    protected int n2;
    public Two(int val):base()
    {
        this.n2 = val;
    }
    public Two (int val1,int val2):base(val1)
    {
        this.n2 = val2;
    }
    public override void Update(int k)
    {
        base.Update(k);
        this.n2 = this.n2 * k;
    }

    public override string ToString()
    {
        return base.ToString() + " Two: n2=" + this.n2;
    }
}

public class Test {
    public   static void Main(string[] args){
        One[] arr = new One [6];
        arr [0] = new One (2);
        arr [1] = new Two(4);
        arr [2] = new Two(3, 6);
        arr [3] = arr [0];
        arr [4] = new Two(4);
        arr [5] = arr[1];

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

(*)     for(int i=0;i< arr.Length;i++)
            arr [i].Update(i+3);

(**)    for (int i = 0; i < arr.Length; i++)
            Console.WriteLine (arr[i]);
    }
}
א.

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

(12 נקודות)
ב.

שתי הלולאות (*) ו-() הוחלפו ללולאה הבא:

Java:

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

C#:

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

האם פלט של הפעולה הראשית השתנה? הסבירו את תשובתכם

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

סעיף א

תשובה:

One: n1=2 / One: n1=1 Two: n2=4 / One: n1=3 Two: n2=6 / One: n1=2 / One: n1=1 Two: n2=4 / One: n1=1 Two: n2=4 / One: n1=36 / One: n1=32 Two: n2=128 / One: n1=15 Two: n2=30 / One: n1=36 / One: n1=7 Two: n2=28 / One: n1=32 Two: n2=128

שלב 1 - יצירת העצמים. נותנים שם לכל עצם שנוצר ב-`new`:

עצםנוצר ב-n1n2הסבר
A`new One(2)`2-הבנאי עם פרמטר
B`new Two(4)`14הבנאי `Two(int val)` אינו קורא במפורש לבנאי של One, ולכן מופעל הבנאי בלי פרמטרים `One()` שקובע `n1 = 1`
C`new Two(3, 6)`36`super(val1)` / `base(val1)` קובע `n1 = 3`
D`new Two(4)`14כמו B, אבל עצם חדש ונפרד

השמות `arr[3] = arr[0]` ו-`arr[5] = arr[1]` אינן יוצרות עצמים חדשים - הן מעתיקות הפניות. לכן:

תא012345
העצםABCADB

שלב 2 - הלולאה הראשונה (הדפסה). `println(arr[i])` / `WriteLine(arr[i])` קוראת ל-`toString` של העצם בפועל (פולימורפיזם). ב-Two מודפס קודם החלק של One (`super.toString()`) ואחריו `Two: n2=...`:

One: n1=2
One: n1=1 Two: n2=4
One: n1=3 Two: n2=6
One: n1=2
One: n1=1 Two: n2=4
One: n1=1 Two: n2=4

שלב 3 - הלולאה (*): `arr[i].update(i+3)`. עבור עצם One מוכפל `n1` ב-k. עבור עצם Two מופעלת הגרסה הדורסת: `super.update(k)` מכפיל את `n1`, ואחר כך מוכפל `n2`:

סיבוב ik = i+3העצםn1n2
03A2⋅3=62\cdot3=6-
14B1⋅4=41\cdot4=44⋅4=164\cdot4=16
25C3⋅5=153\cdot5=156⋅5=306\cdot5=30
36A (שוב)6⋅6=366\cdot6=36-
47D1⋅7=71\cdot7=74⋅7=284\cdot7=28
58B (שוב)4⋅8=324\cdot8=3216⋅8=12816\cdot8=128

ערכי התכונות הסופיים: A: n1=36; B: n1=32, n2=128; C: n1=15, n2=30; D: n1=7, n2=28.

שלב 4 - הלולאה () (הדפסה). התאים 0 ו-3 מדפיסים את A, והתאים 1 ו-5 מדפיסים את B, בערכיהם הסופיים:

One: n1=36
One: n1=32 Two: n2=128
One: n1=15 Two: n2=30
One: n1=36
One: n1=7 Two: n2=28
One: n1=32 Two: n2=128

תשובה: הפלט המלא (12 שורות):

One: n1=2
One: n1=1 Two: n2=4
One: n1=3 Two: n2=6
One: n1=2
One: n1=1 Two: n2=4
One: n1=1 Two: n2=4
One: n1=36
One: n1=32 Two: n2=128
One: n1=15 Two: n2=30
One: n1=36
One: n1=7 Two: n2=28
One: n1=32 Two: n2=128

סעיף ב

תשובה:

כן. השורות 7 ו-8 משתנות ל-One: n1=6 ול-One: n1=4 Two: n2=16, כי A ו-B מודפסים מיד אחרי העדכון הראשון שלהם, לפני העדכון השני דרך arr[3] ו-arr[5].

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

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

סיבוב ikהעצםערכים אחרי העדכוןמודפס
03An1=6One: n1=6
14Bn1=4, n2=16One: n1=4 Two: n2=16
25Cn1=15, n2=30One: n1=15 Two: n2=30
36An1=36One: n1=36
47Dn1=7, n2=28One: n1=7 Two: n2=28
58Bn1=32, n2=128One: n1=32 Two: n2=128

ההשוואה לפלט המקורי: השורה השביעית הייתה `One: n1=36` וכעת `One: n1=6`; השורה השמינית הייתה `One: n1=32 Two: n2=128` וכעת `One: n1=4 Two: n2=16`. שאר השורות זהות (העצמים C ו-D מופיעים פעם אחת בלבד במערך, ותאים 3 ו-5 מודפסים אחרי העדכון האחרון של A ושל B).

תשובה: כן, הפלט משתנה: שש השורות האחרונות הן One: n1=6 / One: n1=4 Two: n2=16 / One: n1=15 Two: n2=30 / One: n1=36 / One: n1=7 Two: n2=28 / One: n1=32 Two: n2=128. הסיבה: arr[0], arr[3] ו-arr[1], arr[5] מפנים לאותם עצמים, ובלולאה החדשה הם מודפסים לפני העדכון השני שלהם.

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

לפניכם שתי הפעולות הרקורסיביות what ו-why. הפעולה what מקבלת הפניה לאחת מהחוליות בשרשרת חוליות של מספרים שלמים, והפעולה why מקבלת הפניה לחוליה ראשונה בשרשרת החוליות.

Java:

public static Node<Integer> what (Node<Integer> p1)
{
     if(p1.getNext() ==null)
          return p1;
     Node<Integer> p2 = what(p1.getNext());
     if(p1.getValue() < p2.getValue())
          return p1;
     return p2;
}


public static void why(Node<Integer> chain)
{
     if(chain.getNext()!=null)
     {
          Node<Integer>p = what(chain);
          int temp=p.getValue();
          p.setValue(chain.getValue());
          chain.setValue(temp);
          why(chain.getNext());
     }
}

C#:

public static Node<int> What (Node<int> p1)
{
     if(p1.GetNext() ==null)
          return p1;
     Node<int> p2 = What(p1.GetNext());
     if(p1.GetValue() < p2.GetValue())
          return p1;
     return p2;
}


public static void Why(Node<int> chain)
{
     if(chain.GetNext()!=null)
     {
          Node<int>p = What(chain);
          int temp=p.GetValue();
          p.SetValue(chain.GetValue());
          chain.SetValue(temp);
          Why(chain.GetNext());
     }
}

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

א.

מה יחזיר זימון הפעולה what(p1)? יש להראות מעקב אחר ביצוע הפעולה.

(6 נקודות)
ב.

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

(3 נקודות)
ג.

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

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

(6 נקודות)
ד.

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

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

סעיף א

תשובה:

הפניה לחוליה שערכה 5 (הרביעית בשרשרת), כלומר לשרשרת 5 → 8 → 6.

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

`p1` מפנה לחוליה שערכה 10, ואחריה 5, 8, 6.

ירידה ברקורסיה:

זימוןערך p1p1.getNext() == null?פעולה
what(10)10לאקורא ל-what(5)
what(5)5לאקורא ל-what(8)
what(8)8לאקורא ל-what(6)
what(6)6כןמחזיר את החוליה 6

חזרה מהרקורסיה:

זימוןערך p2 שהתקבלp1.getValue() < p2.getValue()?מחזיר
what(8)68 < 6 - לאהחוליה 6
what(5)65 < 6 - כןהחוליה 5
what(10)510 < 5 - לאהחוליה 5

תשובה: הזימון what(p1) מחזיר הפניה לחוליה שערכה 5 (ממנה ממשיכה השרשרת 5 → 8 → 6).

סעיף ב

תשובה:

מחזירה הפניה לחוליה בעלת הערך הקטן ביותר, מהחוליה שהתקבלה ועד סוף השרשרת.

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

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

סעיף ג

תשובה:

3 → 4 → 5 → 6 → 8 → 10

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

השרשרת בתחילה: 3, 4, 10, 5, 8, 6.

זימוןהחוליה הנוכחית (מקום, ערך)what מחזירה (מקום, ערך)החלפההשרשרת אחרי ההחלפה
11, ערך 31, ערך 3עם עצמה - אין שינוי3, 4, 10, 5, 8, 6
22, ערך 42, ערך 4עם עצמה - אין שינוי3, 4, 10, 5, 8, 6
33, ערך 104, ערך 510 ↔ 53, 4, 5, 10, 8, 6
44, ערך 106, ערך 610 ↔ 63, 4, 5, 6, 8, 10
55, ערך 85, ערך 8עם עצמה - אין שינוי3, 4, 5, 6, 8, 10
66, ערך 10-החוליה האחרונה: התנאי `getNext() != null` אינו מתקיים, הרקורסיה נעצרת3, 4, 5, 6, 8, 10

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

תשובה: אחרי הזימון השרשרת היא 3 → 4 → 5 → 6 → 8 → 10.

סעיף ד

תשובה:

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

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

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

שאלה 11 · מחלקות ציון וסטודנט: הממוצע הגבוה ביותר

במאגר הציונים של סטודנטים באוניברסיטה נשמרים עבור כל סטודנט הנתונים הבאים:

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

א.

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

•קוד מקצוע.

•ציון סמסטר א'.

•ציון סמסטר ב'.

(2 נקודות)
ב.

הגדירו מחלקה Student המתארת סטודנט באוניברסיטה. תכונות המחלקה:

•מספר תעודת הזהות של הסטודנט.

•רשימת ציונים (שרשרת חוליות מסוג Grade).

(2 נקודות)
ג.

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

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

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

הערה: אפשר להניח שבמחלקות Grade ו-Student קיימות פעולות get לכל התכונות.

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

סעיף א

תשובה:

מחלקה Grade עם התכונות code, gradeA, gradeB (שלמים), בנאי ופעולות get.

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

Java:

public class Grade
{
    private int code;        // קוד מקצוע
    private int gradeA;      // ציון סמסטר א'
    private int gradeB;      // ציון סמסטר ב'

    public Grade(int code, int gradeA, int gradeB)
    {
        this.code = code;
        this.gradeA = gradeA;
        this.gradeB = gradeB;
    }

    public int getCode() { return this.code; }
    public int getGradeA() { return this.gradeA; }
    public int getGradeB() { return this.gradeB; }
}

C#:

public class Grade
{
    private int code;        // קוד מקצוע
    private int gradeA;      // ציון סמסטר א'
    private int gradeB;      // ציון סמסטר ב'

    public Grade(int code, int gradeA, int gradeB)
    {
        this.code = code;
        this.gradeA = gradeA;
        this.gradeB = gradeB;
    }

    public int GetCode() { return this.code; }
    public int GetGradeA() { return this.gradeA; }
    public int GetGradeB() { return this.gradeB; }
}

תשובה: המחלקה Grade שלמעלה.

סעיף ב

תשובה:

מחלקה Student עם התכונות id (מחרוזת) ו-grades (Node<Grade>), בנאי ופעולות get.

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

Java:

public class Student
{
    private String id;               // מספר תעודת הזהות
    private Node<Grade> grades;      // רשימת הציונים

    public Student(String id, Node<Grade> grades)
    {
        this.id = id;
        this.grades = grades;
    }

    public String getId() { return this.id; }
    public Node<Grade> getGrades() { return this.grades; }
}

C#:

public class Student
{
    private string id;               // מספר תעודת הזהות
    private Node<Grade> grades;      // רשימת הציונים

    public Student(string id, Node<Grade> grades)
    {
        this.id = id;
        this.grades = grades;
    }

    public string GetId() { return this.id; }
    public Node<Grade> GetGrades() { return this.grades; }
}

תשובה: המחלקה Student שלמעלה.

סעיף ג

תשובה:

הפעולה bestStudent שלהלן (המאגר: שרשרת חוליות Node<Student>): מחשבת לכל סטודנט ממוצע של כל ציוניו בעזרת average ושומרת את תעודת הזהות של בעל הממוצע המקסימלי.

בחירת המבנה: נייצג את המאגר כשרשרת חוליות של סטודנטים, `Node<Student>`. כך אפשר לעבור על כל הסטודנטים בלי להוציא אותם מהמבנה ובלי לשנות אותו.

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

פעולת העזר average:

1. עוברים על שרשרת הציונים של הסטודנט.

2. לכל מקצוע מוסיפים לסכום את שני הציונים (סמסטר א' וסמסטר ב') ומגדילים את המונה ב-2 - כי הממוצע הוא של כל הציונים.

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

הפעולה הראשית bestStudent:

1. `bestAvg` מאותחל ל-1- (קטן מכל ממוצע אפשרי של ציונים), ו-`bestId` ל-null.

2. לכל סטודנט מחשבים `avg`. אם הוא גדול מ-`bestAvg` - מעדכנים את `bestAvg` ואת `bestId`.

3. בסוף מחזירים את `bestId`. לפי ההנחה בשאלה יש סטודנט יחיד עם הממוצע הגבוה ביותר, ולכן התשובה חד-משמעית.

Java:

public static double average(Node<Grade> grades)
{
    int sum = 0;
    int count = 0;
    while (grades != null)
    {
        Grade g = grades.getValue();
        sum += g.getGradeA() + g.getGradeB();   // שני ציוני המקצוע
        count += 2;
        grades = grades.getNext();
    }
    if (count == 0)
        return -1;                              // סטודנט בלי ציונים
    return (double) sum / count;
}

public static String bestStudent(Node<Student> students)
{
    String bestId = null;
    double bestAvg = -1;
    while (students != null)
    {
        Student st = students.getValue();
        double avg = average(st.getGrades());
        if (avg > bestAvg)                      // ממוצע גבוה יותר מכל הקודמים
        {
            bestAvg = avg;
            bestId = st.getId();
        }
        students = students.getNext();
    }
    return bestId;
}

C#:

public static double Average(Node<Grade> grades)
{
    int sum = 0;
    int count = 0;
    while (grades != null)
    {
        Grade g = grades.GetValue();
        sum += g.GetGradeA() + g.GetGradeB();   // שני ציוני המקצוע
        count += 2;
        grades = grades.GetNext();
    }
    if (count == 0)
        return -1;                              // סטודנט בלי ציונים
    return (double) sum / count;
}

public static string BestStudent(Node<Student> students)
{
    string bestId = null;
    double bestAvg = -1;
    while (students != null)
    {
        Student st = students.GetValue();
        double avg = Average(st.GetGrades());
        if (avg > bestAvg)                      // ממוצע גבוה יותר מכל הקודמים
        {
            bestAvg = avg;
            bestId = st.GetId();
        }
        students = students.GetNext();
    }
    return bestId;
}

דוגמה: סטודנט 111 עם ציונים (80, 90) ו-(70, 100): ממוצע 80+90+70+1004=85\frac{80+90+70+100}{4}=85. סטודנט 222 עם (95, 85): ממוצע 95+852=90\frac{95+85}{2}=90. הפעולה מחזירה "222".

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

תשובה: הפעולה bestStudent (עם פעולת העזר average) שלמעלה.

שאלה 12 · מחיקת כפולות מתוך שרשרת חוליות

נתונות שתי הפעולות what ו- where המקבלות הפניה לחוליה הראשונה של שרשרת חוליות:

Java:

public static Node<Integer> what(Node<Integer> chain, int x){
        while(chain!=null && chain.getValue()% x == 0){
            chain = chain.getNext();
        }
        if(chain == null)
                return null;

        Node<Integer> p = chain;
        Node<Integer> p1 = p.getNext();
        while(p1 != null){
            if(p1.getValue()% x == 0)
            {
                p.setNext(p1.getNext());
                p1.setNext(null);
                p1 = p.getNext();
            }
            else
            {
                p = p1;
                p1 = p1.getNext();
            }
        }
        return chain;
    }
public static void where(Node<Integer> chain){
        Node<Integer> p = chain;
        while(p != null) {
            p.setNext(what(p.getNext(),p.getValue()));
            p = p.getNext();
        }
    }

C#:

public static Node<int> What(Node<int> chain, int x){
        while(chain!=null && chain.GetValue()% x == 0){
            chain = chain.GetNext();
        }
        if(chain == null)
                return null;

        Node<int> p = chain;
        Node<int> p1 = p.GetNext();
        while(p1 != null){
            if(p1.GetValue()% x == 0)
            {
                p.SetNext(p1.GetNext());
                p1.SetNext(null);
                p1 = p.GetNext();
            }
            else
            {
                p = p1;
                p1 = p1.GetNext();
            }
        }
        return chain;
    }
public static void Where(Node<int> chain){
        Node<int> p = chain;
        while(p != null) {
            p.SetNext(What(p.GetNext(),p.GetValue()));
            p = p.GetNext();
        }
    }

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

א.

עקבו אחרי זימון הפעולה what(chain, 4) ורשמו מה תחזיר הפעולה.

(5 נקודות)
ב.

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

(2 נקודות)
ג.

עקבו אחרי זימון הפעולה where(chain) ורשמו איך תיראה השרשרת אחרי ביצוע. אין צורך במעקב אחרי זימון הפעולה what.

(5 נקודות)
ד.

האם אפשר לשנות סדר חוליות בשרשרת chain כך ששרשרת לא תשתנה אחרי זימון הפעולה where? אם כן – רשמו את השרשרת אחרי שינוי, אם לא – הסבירו למה אי אפשר לבצע שינוי כזה.

(2 נקודות)
ה.

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

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

סעיף א

תשובה:

הפניה לחוליה שערכה 5: השרשרת 5 → 7 → 6 → 18.

שלב 1 - הלולאה הראשונה: מדלגת על חוליות מתחילת השרשרת כל עוד הערך מתחלק ב-x=4x=4:

chain מפנה ל-ערך % 4פעולה
40מדלגים
200מדלגים
51עוצרים

כעת `chain` מפנה לחוליה 5 (אינו null).

שלב 2 - הלולאה השנייה: `p` היא החוליה האחרונה שנשארת, ו-`p1` החוליה שאחריה. אם ערך `p1` מתחלק ב-4 - מנתקים אותה (`p` מדלגת עליה); אחרת מתקדמים.

החוליה pp1p1 % 4פעולההשרשרת מ-chain
573מתקדמים: p = 75, 7, 8, 4, 6, 18
780מוחקים את 8: 7 מצביעה על 45, 7, 4, 6, 18
740מוחקים את 4: 7 מצביעה על 65, 7, 6, 18
762מתקדמים: p = 65, 7, 6, 18
6182מתקדמים: p = 185, 7, 6, 18
18null-סוף הלולאה5, 7, 6, 18

הפעולה מחזירה את `chain`, כלומר הפניה לחוליה 5.

תשובה: הפעולה מחזירה הפניה לשרשרת 5 → 7 → 6 → 18.

סעיף ב

תשובה:

מוחקת מהשרשרת את כל החוליות שערכן מתחלק ב-x ומחזירה הפניה לתחילת השרשרת שנותרה (null אם לא נותר דבר).

הלולאה הראשונה מדלגת על כל החוליות בתחילת השרשרת שערכן מתחלק ב-x, והלולאה השנייה מנתקת מהמשך השרשרת כל חוליה שערכה מתחלק ב-x. ההפניה המוחזרת היא לחוליה הראשונה שערכה אינו מתחלק ב-x.

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

סעיף ג

תשובה:

4 → 5 → 7 → 6

מה הפעולה עושה: עבור כל חוליה `p` (מההתחלה), קוראים ל-`what` על ההמשך שלה עם הערך של `p` - כלומר מוחקים מההמשך את כל הערכים שמתחלקים בערך של `p` - ומחברים את `p` לתוצאה. אחר כך מתקדמים לחוליה הבאה בשרשרת המעודכנת.

השרשרת בתחילה: 4, 20, 5, 7, 8, 4, 6, 18.

החוליה pההמשך לפנינמחקים (מתחלקים ב-p)ההמשך אחריהשרשרת כולה
420, 5, 7, 8, 4, 6, 1820, 8, 45, 7, 6, 184, 5, 7, 6, 18
57, 6, 18אין7, 6, 184, 5, 7, 6, 18
76, 18אין6, 184, 5, 7, 6, 18
61818null4, 5, 7, 6

אחרי החוליה 6 `p` מקבל null והלולאה מסתיימת.

תשובה: השרשרת אחרי הביצוע: 4 → 5 → 7 → 6.

סעיף ד

תשובה:

לא. בשרשרת יש שתי חוליות עם הערך 4; בכל סדר, ה-4 המאוחר מתחלק ב-4 המוקדם ויימחק.

השרשרת לא משתנה רק אם אף ערך אינו מתחלק בערך כלשהו שמופיע לפניו. אבל הערך 4 מופיע בשרשרת פעמיים. בכל סידור, אחד המופעים של 4 יהיה לפני השני, ו-4 mod 4=04 \bmod 4=0 - ולכן כשהפעולה תגיע ל-4 הראשון היא תמחק את 4 השני. כלומר השרשרת תשתנה בכל סדר.

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

סעיף ה

תשובה:

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

מהמעקב: לכל חוליה שנשארת בשרשרת, `where` מוחקת מכל ההמשך שלה את הערכים שמתחלקים בערך שלה. חוליה נמחקת אם יש לפניה (בין החוליות שנשארו) ערך שמחלק אותה; ואם חוליה נמחקה בגלל ערך שלפניה, כל מה שמתחלק בה מתחלק גם באותו ערך ולכן גם הוא נמחק.

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

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

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

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