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

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

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

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

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

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

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

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

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

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

חלק א' - 45 נקודות

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

חלק ב' - 30 נקודות

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

חלק ג' - 25 נקודות

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

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

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

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

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

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

שאלה 1 · מחלקות מחשב לוח ומחסן: השוואה, הוספה ומיון

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

המחלקה Tablet המייצגת מחשב הלוח. תכונות המחלקה:

•name - שם חברה המייצרת, מסוג מחרוזת, String

•kind – דגם, מסוג מחרוזת, String

•system – מערכת הפעלה מסוג תו, char ('W' – ווינדוס, 'A' – אנדרואיד, 'I' – iOS)

•size – גודל, מסוג מספר ממשי, double

•price – מחיר, מסוג מספר ממשי, double

אפשר להניח שבמחלקה הוגדר בנאי (constructor) המקבל פרמטרים לכל התכונות, פעולות get/set ופעולת toString. אין צורך לממש את הפעולות.

(בגרסת C# הטיפוס של name ו-kind הוא string.)

א.

כתבו פעולה `public boolean isSame(Tablet other)`

(ב-C#: `public bool IsSame(Tablet other)`)

הפעולה מחזירה true אם השם, הדגם והגודל של העצם המפעיל את הפעולה זהים להשם, הדגם והגודל של other. ולא הפעולה תחזיר false.

(3 נקודות)

המחלקה Store מייצגת מחסן. תכונות המחלקה:

•tablets – מערך עצמים מסוג Tablet. גודל המערך 1000.

•systems – מערך מספרים שלמים. בכל תא במערך נשמר מספר סוגי המחשבים שחנות מציעה, לפי מערכת הפעלה: מספר המכשירים בעלי מערכת ווינדוס, מספר המכשירים בעלי מערכת ההפעלה אנדרואיד ומספר המכשירים בעלי מערכת ההפעלה iOS.

public class Store {
private Tablet[] tablets;
private int[] systems;
public Store()
{
 tablets = new Tablet[1000];
 systems = new int[3];
}
….
}
public class Store {
private Tablet[] tablets;
private int[] systems;
public Store()
{
 tablets = new Tablet[1000];
 systems = new int[3];
}
….
}
ב.

כתבו פעולה `public boolean addTablet(Tablet tab)`

(ב-C#: `public bool AddTablet(Tablet tab)`)

הפעולה מקבלת מחשב לוח tab ומוסיפה אותו למחסן.

•אם אין מקום להוסיף מוצר חדש, הפעולה תחזיר false.

•אם כבר קיים מוצר בעל אותו שם, דגם וגודל, הפעולה תעדכן את המחיר למחיר הגבוה בין המחיר של המוצר הקיים ובין המוצר שמתקבל כפרמטר ותחזיר true.

•אם לא קיים מוצר כמו tab, הפעולה תוסיף אותו למערך מוצרים, תעדכן את מספר המוצרים במחסן ותחזיר true.

שימו לב: עצמים במערך צריכים להיות ברצף ללא "חורים" (תאים עם ערך null).

(6 נקודות)
ג.

כתבו פעולה `public int sortStore()`

(ב-C#: `public int SortStore()`)

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

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

סעיף א

תשובה:

פעולה במחלקה Tablet שמחזירה את התנאי: השמות שווים (equals), הדגמים שווים והגדלים שווים.

הרעיון: הפעולה נכתבת בתוך המחלקה Tablet, ולכן מותר לה לגשת ישירות לתכונות הפרטיות גם של העצם other (הוא מאותה מחלקה).

1. את השם ואת הדגם (מחרוזות) משווים לפי התוכן: ב-Java בעזרת `equals` (האופרטור `==` היה משווה הפניות), וב-C# האופרטור `==` על string משווה תוכן.

2. את הגודל (double) משווים בעזרת `==`.

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

Java:

public boolean isSame(Tablet other)
{
    return this.name.equals(other.name)
        && this.kind.equals(other.kind)
        && this.size == other.size;
}

C#:

public bool IsSame(Tablet other)
{
    return this.name == other.name
        && this.kind == other.kind
        && this.size == other.size;
}

תשובה: הפעולה מחזירה true רק כאשר name, kind ו-size של שני העצמים שווים, ואחרת false.

סעיף ב

תשובה:

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

הרעיון:

1. כמה מוצרים יש במחסן? במערך systems נשמר מספר סוגי המחשבים לכל מערכת הפעלה, ולכן סכום שלושת התאים הוא מספר המוצרים n במערך. מכיוון שהמוצרים שמורים ברצף, הם נמצאים בתאים 0 עד n-1, והתא הפנוי הבא הוא tablets[n]. נגדיר פעולת עזר פרטית count שמחזירה את הסכום, ופעולת עזר sysIndex שממירה את תו מערכת ההפעלה לאינדקס במערך systems: 'W' ← 0, 'A' ← 1, 'I' ← 2.

2. מוצר קיים: עוברים על התאים 0 עד n-1. אם נמצא מוצר שעבורו `isSame(tab)` מחזירה true, מעדכנים את מחירו למחיר הגבוה מבין שני המחירים ומחזירים true. במקרה זה לא נוסף סוג מחשב חדש, ולכן systems לא משתנה.

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

4. הוספה: מכניסים את tab לתא tablets[n] - כך המערך נשאר רציף בלי "חורים" - ומגדילים ב-1 את המונה של מערכת ההפעלה שלו ב-systems (זה העדכון של מספר המוצרים במחסן). מחזירים true.

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

Java:

private int sysIndex(char s)
{
    if (s == 'W') return 0;
    if (s == 'A') return 1;
    return 2;                    // 'I'
}

private int count()
{
    return systems[0] + systems[1] + systems[2];
}

public boolean addTablet(Tablet tab)
{
    int n = count();
    for (int i = 0; i < n; i++)
    {
        if (tablets[i].isSame(tab))
        {
            if (tab.getPrice() > tablets[i].getPrice())
                tablets[i].setPrice(tab.getPrice());
            return true;
        }
    }
    if (n == tablets.length)
        return false;
    tablets[n] = tab;
    systems[sysIndex(tab.getSystem())]++;
    return true;
}

C#:

private int SysIndex(char s)
{
    if (s == 'W') return 0;
    if (s == 'A') return 1;
    return 2;                    // 'I'
}

private int Count()
{
    return systems[0] + systems[1] + systems[2];
}

public bool AddTablet(Tablet tab)
{
    int n = Count();
    for (int i = 0; i < n; i++)
    {
        if (tablets[i].IsSame(tab))
        {
            if (tab.GetPrice() > tablets[i].GetPrice())
                tablets[i].SetPrice(tab.GetPrice());
            return true;
        }
    }
    if (n == tablets.Length)
        return false;
    tablets[n] = tab;
    systems[SysIndex(tab.GetSystem())]++;
    return true;
}

תשובה: מוצר זהה קיים - מעדכנים את מחירו למחיר הגבוה ומחזירים true; המחסן מלא - false; אחרת מוסיפים את tab בתא tablets[n], מגדילים את המונה המתאים ב-systems ומחזירים true.

סעיף ג

תשובה:

בונים מערך חדש בגודל 1000 ומעתיקים אליו בשלושה מעברים את מחשבי 'W', אחריהם 'A' ואחריהם 'I'; מציבים אותו ב-tablets ומחזירים 1000 פחות מספר המוצרים.

הרעיון: יש רק שלושה ערכים אפשריים למערכת ההפעלה, ולכן אין צורך באלגוריתם מיון כללי. מספיקים שלושה מעברים:

1. n = מספר המוצרים (סכום התאים של systems, כמו בסעיף ב).

2. יוצרים מערך עזר sorted בגודל של tablets, ומונה k של המקום הפנוי הבא בו.

3. במעבר הראשון מעתיקים ל-sorted (לפי הסדר) את כל המחשבים שמערכת ההפעלה שלהם 'W', במעבר השני את כל מחשבי 'A' ובמעבר השלישי את כל מחשבי 'I'. עוברים על התווים בעזרת מערך order = {'W','A','I'}.

4. מציבים את sorted במקום tablets. המוצרים עדיין רציפים בתאים 0 עד n-1 וכל השאר null.

5. מספר המקומות הפנויים הוא גודל המערך פחות מספר המוצרים: tablets.length - n.

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

Java:

public int sortStore()
{
    int n = count();
    Tablet[] sorted = new Tablet[tablets.length];
    char[] order = {'W', 'A', 'I'};
    int k = 0;
    for (int j = 0; j < order.length; j++)
        for (int i = 0; i < n; i++)
            if (tablets[i].getSystem() == order[j])
            {
                sorted[k] = tablets[i];
                k++;
            }
    tablets = sorted;
    return tablets.length - n;
}

C#:

public int SortStore()
{
    int n = Count();
    Tablet[] sorted = new Tablet[tablets.Length];
    char[] order = {'W', 'A', 'I'};
    int k = 0;
    for (int j = 0; j < order.Length; j++)
        for (int i = 0; i < n; i++)
            if (tablets[i].GetSystem() == order[j])
            {
                sorted[k] = tablets[i];
                k++;
            }
    tablets = sorted;
    return tablets.Length - n;
}

לדוגמה, אם במחסן 5 מוצרים בסדר I, A, W, A, W, אחרי המיון הסדר יהיה W, W, A, A, I והפעולה תחזיר 1000−5=9951000-5=995.

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

שאלה 2 · תור חדש של איברים המופיעים יותר מפעמיים

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

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

לדוגמה:

עבור תור q1 הבא: [2,5,5,7,2,4,1,3,2,5,5,1] הפעולה תחזיר תור חדש [2,5].

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

פתרון

תשובה:

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

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

1. פעולת עזר count(q, x): מוציאה את כל איברי q אחד-אחד, סופרת כמה מהם שווים ל-x ומכניסה כל איבר לתור עזר temp. בסוף מחזירה את כל האיברים מ-temp ל-q באותו סדר. כך q נשאר כפי שהיה, והפעולה מחזירה את מספר המופעים של x.

2. עותק: בפעולה הראשית מעבירים את איברי q לשני תורים: copy (עליו נעבור) ו-temp, ואחר כך מחזירים מ-temp ל-q. כך q המקורי משוחזר.

3. מעבר על העותק: מוציאים מ-copy איבר x. אם `count(q, x) > 2` ("יותר מפעמיים", כלומר לפחות 3 מופעים) וגם x עדיין לא נמצא בתור התוצאה (`count(result, x) == 0`) - מכניסים אותו ל-result. הבדיקה השנייה מונעת הכנסה חוזרת של אותו ערך (למשל 5 מופיע ארבע פעמים, אבל יוכנס פעם אחת).

4. מחזירים את result. האיברים בו מופיעים לפי סדר המופע הראשון שלהם ב-q.

בדיקה בדוגמה: 2 מופיע 3 פעמים, 5 מופיע 4 פעמים, 1 מופיע פעמיים בלבד ושאר האיברים פעם אחת. לכן התוצאה היא [2,5], ו-q1 נשאר ללא שינוי.

סיבוכיות: לכל אחד מ-n האיברים מבצעים ספירה של O(n)O(n), ולכן בסך הכול O(n2)O(n^2).

Java:

public static int count(Queue<Integer> q, int x)
{
    Queue<Integer> temp = new Queue<Integer>();
    int c = 0;
    while (!q.isEmpty())
    {
        int y = q.remove();
        if (y == x)
            c++;
        temp.insert(y);
    }
    while (!temp.isEmpty())        // restore q
        q.insert(temp.remove());
    return c;
}

public static Queue<Integer> moreThanTwice(Queue<Integer> q)
{
    Queue<Integer> result = new Queue<Integer>();
    Queue<Integer> copy = new Queue<Integer>();
    Queue<Integer> temp = new Queue<Integer>();
    while (!q.isEmpty())
    {
        int x = q.remove();
        copy.insert(x);
        temp.insert(x);
    }
    while (!temp.isEmpty())        // restore q
        q.insert(temp.remove());

    while (!copy.isEmpty())
    {
        int x = copy.remove();
        if (count(q, x) > 2 && count(result, x) == 0)
            result.insert(x);
    }
    return result;
}

C#:

public static int Count(Queue<int> q, int x)
{
    Queue<int> temp = new Queue<int>();
    int c = 0;
    while (!q.IsEmpty())
    {
        int y = q.Remove();
        if (y == x)
            c++;
        temp.Insert(y);
    }
    while (!temp.IsEmpty())        // restore q
        q.Insert(temp.Remove());
    return c;
}

public static Queue<int> MoreThanTwice(Queue<int> q)
{
    Queue<int> result = new Queue<int>();
    Queue<int> copy = new Queue<int>();
    Queue<int> temp = new Queue<int>();
    while (!q.IsEmpty())
    {
        int x = q.Remove();
        copy.Insert(x);
        temp.Insert(x);
    }
    while (!temp.IsEmpty())        // restore q
        q.Insert(temp.Remove());

    while (!copy.IsEmpty())
    {
        int x = copy.Remove();
        if (Count(q, x) > 2 && Count(result, x) == 0)
            result.Insert(x);
    }
    return result;
}

תשובה: הפעולה moreThanTwice מחזירה תור חדש של הערכים שמופיעים 3 פעמים או יותר, כל ערך פעם אחת, והתור המקורי נשאר ללא שינוי. בדוגמה מוחזר [2,5].

שאלה 3 · משלוח פריטים מסוגים שונים: מערך Object

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

לשם כך הוחלט ליצור פרויקט הכולל מחלקות הבאות:

•המחלקה Clothes עבור בגדים

•המחלקה Shirt עבור חולצות

•המחלקה Dress עבור שמלות

•המחלקה Book עבור ספרים

Java:

public class Clothes {
    private String fabric;  // סוג בד
    private String color; // צבע
    private double price; // מחיר
    public double getPrice(){ return this.price;   }
}
public class Shirt extends Clothes {
    private String size; // (L, X,XL,XXL)מידה
}
public class Dress extends Clothes {
    private double length; // אורך בסמ'
    private int size; // מידה
}
public class Book {
    private String name; // שם ספר
    private String author; // מחבר
    private double price; // מחיר
    public double getPrice(){return 0.9*this.price;}
}

C#:

public class Clothes {
    private string fabric;  // סוג בד
    private string color; // צבע
    private double price; // מחיר
    public double GetPrice(){ return this.price;   }
}
public class Shirt : Clothes {
    private string size; // (L, X,XL,XXL)מידה
}
public class Dress : Clothes {
    private double length; // אורך בסמ'
    private int size; // מידה
}
public class Book {
    private string name; // שם ספר
    private string author; // מחבר
    private double price; // מחיר
    public double GetPrice(){return 0.9*this.price;}
}
א.

המחלקה Shipping מתארת משלוח. למחלקה יש שתי תכונות:

•address – כתובת משלוח מסוג מחרוזת, String

•arr – מערך הפריטים למסירה.

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

(5 נקודות)
ב.

כתבו פעולה פנימית `public double sum()` המחזירה את הסכום הכולל של הפריטים במשלוח.

(ב-C#: `public double Sum()`)

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

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

סעיף א

תשובה:

המערך arr מוגדר מסוג Object[] (ב-C#: object[]), כי Clothes (ותתי-המחלקות שלה) ו-Book אינן חולקות מחלקת-על משותפת מלבד Object.

בחירת סוג המערך: המשלוח צריך להכיל גם בגדים (עצמים מסוג Clothes, Shirt, Dress) וגם ספרים (Book). Shirt ו-Dress יורשות מ-Clothes, ולכן מערך מסוג Clothes היה יכול להכיל את כל הבגדים - אבל לא ספרים, כי Book אינה יורשת מ-Clothes. מערך מסוג Book לא יכיל בגדים.

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

Java:

public class Shipping
{
    private String address;    // shipping address
    private Object[] arr;      // items to deliver: Clothes, Shirt, Dress or Book
}

C#:

public class Shipping
{
    private string address;    // shipping address
    private object[] arr;      // items to deliver: Clothes, Shirt, Dress or Book
}

תשובה: `public class Shipping` עם התכונות `private String address;` ו-`private Object[] arr;` - המערך מסוג Object כי זו מחלקת-העל המשותפת היחידה לבגדים ולספרים.

סעיף ב

תשובה:

עוברים על arr; לכל תא שאינו null בודקים אם הוא Clothes (instanceof / is) או Book, ממירים אליו ומוסיפים getPrice() לסכום.

הרעיון: הטיפוס הסטטי של כל תא הוא Object, ול-Object אין פעולה getPrice, ולכן אי אפשר לכתוב `arr[i].getPrice()`. צריך לבדוק בזמן ריצה מה הטיפוס האמיתי של העצם ולהמיר אליו (המרה כלפי מטה):

1. מאפסים צובר total.

2. עוברים על כל תאי המערך.

3. אם `arr[i] instanceof Clothes` (ב-C#: `arr[i] is Clothes`) - העצם הוא בגד: Clothes, Shirt או Dress (גם חולצה ושמלה הן Clothes בזכות הירושה). ממירים ל-Clothes ומוסיפים את getPrice().

4. אחרת, אם `arr[i] instanceof Book` - ממירים ל-Book ומוסיפים את getPrice(). בספר הפעולה מחזירה כבר את המחיר אחרי הנחה (0.9⋅price0.9\cdot price), ואנחנו פשוט משתמשים בה.

5. תא ריק (null) אינו עובר אף אחת מהבדיקות (instanceof על null מחזיר false), ולכן אין צורך בבדיקה נפרדת.

6. מחזירים את total.

לדוגמה, משלוח עם חולצה במחיר 100, שמלה במחיר 200 וספר שמחירו 50 ייתן 100+200+0.9⋅50=345100+200+0.9\cdot 50=345.

Java:

public double sum()
{
    double total = 0;
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] instanceof Clothes)
            total += ((Clothes) arr[i]).getPrice();
        else if (arr[i] instanceof Book)
            total += ((Book) arr[i]).getPrice();
    }
    return total;
}

C#:

public double Sum()
{
    double total = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] is Clothes)
            total += ((Clothes) arr[i]).GetPrice();
        else if (arr[i] is Book)
            total += ((Book) arr[i]).GetPrice();
    }
    return total;
}

תשובה: הפעולה סורקת את המערך, מזהה כל פריט בעזרת instanceof (ב-C#: is), ממירה אותו ל-Clothes או ל-Book, מוסיפה את getPrice() שלו לסכום ומחזירה את הסכום.

שאלה 4 · בנאים, הרשאות גישה והמרת טיפוסים בירושה

הערה: בשאלה זו אין קשר בין הסעיפים!

א.

נתונות שתי מחלקות B, A:

Java:

public class A{
}
public class B extends A{
  public B(){
    System.out.println("B constructor");
  }
}

C#:

public class A{
}
public class B : A{
 public B(){
    Console.WriteLine("B constructor");
  }
}

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

(1)

הבנאי של B יקרא לבנאי הריק של A (בנאי ללא פרמטרים, בנאי ברירת מחדל, default constructor)

(2)

הבנאי הריק של Object לא ייקרא כי ל- A אין זימון מפורש של בנאי זה

(3)

הבנאי הריק של Object ייקרא לאחר הדפסת המחרוזת "B constructor"

(4)

הבנאי הריק של B יקרא לבנאי הריק של A ואז תודפס המחרוזת

(5 נקודות)
ב.

נתונות שלוש מחלקות B, A ו- C, כאשר מחלקה B יורשת מהמחלקה A והמחלקה C יורשת מהמחלקה B.

כמו כן נתון שלמחלקה A מוגדרת התכונה value.

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

(1)

מתוך המחלקה C אין גישה לתכונה value של המחלקה A אפילו ש- value מוגדרות כ- protected מכיוון שמדובר בשתי רמות של ירושה.

(2)

מתוך המחלקה C יש גישה לתכונה value רק בתנאי שהתכונה value במחלקה A מוגדרת כ- protected.

(3)

מתוך המחלקה C יש גישה לתכונה value של המחלקה A באמצעות הפקודה super.super.value.

(4)

מתוך המחלקה C יש גישה לתכונה value מכיוון שהמחלקה C יורשת בעקיפין מהמחלקה A, בלי קשר להרשאת הגישה של התכונה.

(5 נקודות)
ג.

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

((A)b).myFun();

(ב-C#: `((A)b).MyFun();`)

כאשר b הוא מצביע מסוג המחלקה B.

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

(1)

הפעולה myFun מוגדרת במחלקה A.

(2)

B היא מחלקה היורשת את המחלקה A.

(3)

A היא מחלקה היורשת את המחלקה B.

(4)

הפעולה myFun מוגדרת גם במחלקה A וגם במחלקה B.

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

סעיף א

(1)
תשובה:

נכון.

בנאי של מחלקה יורשת תמיד מתחיל בזימון בנאי של מחלקת-העל. כשהבנאי של B אינו כותב זימון מפורש (`super(...)` ב-Java או `: base(...)` ב-C#), המהדר מוסיף זימון לבנאי הריק `super()`. ל-A לא נכתב שום בנאי, ולכן המהדר יצר לה בנאי ברירת מחדל ללא פרמטרים - ואותו מזמן הבנאי של B.

תשובה: נכון.

(2)
תשובה:

לא נכון - הבנאי של Object נקרא.

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

תשובה: לא נכון. הבנאי הריק של Object ייקרא (במובלע, מתוך הבנאי של A).

(3)
תשובה:

לא נכון - הוא נקרא ומסתיים לפני ההדפסה.

הזימון של בנאי מחלקת-העל הוא הפעולה הראשונה בבנאי. סדר הביצוע ב-`new B()`:

1. B() מזמן את A() לפני גוף הבנאי שלו.

2. A() מזמן את Object() לפני גוף הבנאי שלו.

3. Object() מתבצע ומסתיים, אחריו גוף A() (ריק), ורק אז גוף B() - שמדפיס "B constructor".

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

(4)
תשובה:

נכון.

כמו שהוסבר בהיגד 1 ובהיגד 3: הבנאי של B מזמן קודם את הבנאי הריק של A (שבתורו מזמן את Object), ורק אחרי שהזימון מסתיים מתבצעת שורת ההדפסה שבגוף הבנאי של B. הפלט של `new B()` הוא `B constructor`.

תשובה: נכון.

סעיף ב

(1)
תשובה:

לא נכון.

הרשאת protected פותחת את הגישה לכל המחלקות היורשות, בכל עומק של ירושה. C יורשת מ-B שיורשת מ-A, ולכן C היא צאצא של A ויכולה לגשת ל-value המוגדרת protected. מספר רמות הירושה אינו משנה.

תשובה: לא נכון.

(2)
תשובה:

לא נכון - גם אם value מוגדרת public יש גישה.

protected מספיק כדי לאפשר גישה מ-C, אבל הוא לא התנאי היחיד. אם value מוגדרת public, אפשר לגשת אליה מכל מחלקה, ובפרט מ-C. ב-Java יש גישה גם כש-value מוגדרת בלי מציין גישה (package), אם המחלקות באותה חבילה. רק כש-value מוגדרת private אין גישה ישירה מ-C. לכן המילה "רק" הופכת את ההיגד לשגוי.

תשובה: לא נכון.

(3)
תשובה:

לא נכון - הביטוי super.super אינו חוקי.

המילה super (ב-C#: base) מתייחסת רק למחלקת-העל הישירה, ואי אפשר לשרשר אותה: `super.super.value` היא שגיאת קומפילציה. אם יש גישה ל-value (למשל protected או public), פונים אליה פשוט כ-`value`, `this.value` או `super.value` - התכונה עוברת בירושה דרך B אל C.

תשובה: לא נכון.

(4)
תשובה:

לא נכון - אם value היא private אין גישה.

הרשאת הגישה קובעת. אם value מוגדרת private, היא נגישה רק בתוך המחלקה A עצמה. אף מחלקה יורשת - B או C - אינה יכולה לפנות אליה ישירות, גם אם העצם מסוג C מכיל אותה בזיכרון. במקרה כזה הגישה אפשרית רק דרך פעולות get/set ציבוריות של A.

תשובה: לא נכון.

סעיף ג

(1)
תשובה:

נכון.

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

תשובה: נכון.

(2)
תשובה:

לא נכון (לא בהכרח).

ההמרה `(A)b` עוברת קומפילציה כש-A ו-B נמצאות על אותו קו ירושה, לא משנה באיזה כיוון:

•אם B יורשת מ-A - זו המרה כלפי מעלה (תמיד בטוחה).

•אם A יורשת מ-B - זו המרה כלפי מטה. היא עוברת קומפילציה, והתוצאה נבדקת רק בזמן ריצה.

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

תשובה: לא נכון - לא בהכרח; ייתכן גם ש-A יורשת מ-B.

(3)
תשובה:

לא נכון (לא בהכרח).

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

תשובה: לא נכון - לא בהכרח.

(4)
תשובה:

לא נכון (לא בהכרח).

כדי שהפקודה תעבור קומפילציה מספיק ש-myFun קיימת ב-A (היגד 1). אין דרישה שהיא תוגדר מחדש (תידרס) ב-B. אם B יורשת מ-A, היא יכולה לרשת את myFun בלי להגדיר אותה בעצמה.

תשובה: לא נכון - לא בהכרח.

שאלה 5 · מעקב: דריסת פעולות, super וקישור דינמי

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

Java:

class A{
    public void f() {
        System.out.println("A.f");
    }
    public void g() {
        f();
    }
}
public class B extends A{
    public void f(){
        System.out.println("B.f");
    }
    public void g() {
        System.out.println("B.g");
    }
    public void superG() {
        super.g();
    }
}

C#:

class A{
    public virtual void F() {
        Console.WriteLine("A.F");
    }
    public virtual void G() {
        F();
    }
}
public class B : A{
    public override void F(){
        Console.WriteLine("B.F");
    }
    public override void G() {
        Console.WriteLine("B.G");
    }
    public void SuperG() {
        base.G();
    }
}

נתון קטע הקוד הבא:

Java:

A a = new A();
B b = new B();
A ab = new B();
a.f();
ab.f();
b.f();
a.g();
ab.g();
b.g();
((B)(ab)).superG();
b.superG();

C#:

A a = new A();
B b = new B();
A ab = new B();
a.F();
ab.F();
b.F();
a.G();
ab.G();
b.G();
((B)(ab)).SuperG();
b.SuperG();
א.

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

(8 נקודות)
ב.

האם אפשר להוסיף לקטע הקוד את שתי הפקודות הבאות?

a.superG();
((B)a).superG();

(ב-C#: `a.SuperG();` ו-`((B)a).SuperG();`)

הסבירו את תשובתכם.

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

סעיף א

תשובה:

Java: A.f, B.f, B.f, A.f, B.g, B.g, B.f, B.f (כל אחד בשורה). C#: A.F, B.F, B.F, A.F, B.G, B.G, B.F, B.F.

העיקרון: בזימון פעולה של מופע, הגרסה שמתבצעת נקבעת לפי הטיפוס האמיתי של העצם בזמן ריצה (קישור דינמי), ולא לפי טיפוס המשתנה. ב-Java כל פעולת מופע נדרסת כך; ב-C# זה קורה כי הפעולות מוגדרות virtual ב-A ו-override ב-B. לעומת זאת, `super.g()` (ב-C#: `base.G()`) מפעיל במפורש את הגרסה של מחלקת-העל. אבל בתוך הגרסה הזו הזימון `f()` הוא שוב זימון דינמי על העצם הנוכחי (this).

העצמים: a הוא עצם A, ואילו b ו-ab הם עצמי B (ab רק מוגדר כמשתנה מסוג A).

פקודהטיפוס העצםמה מתבצעפלט
a.f()AA.fA.f
ab.f()BB.f (דריסה)B.f
b.f()BB.fB.f
a.g()AA.g מזמנת f() של העצם, שהוא AA.f
ab.g()BB.g (דריסה)B.g
b.g()BB.gB.g
((B)(ab)).superG()BsuperG מזמנת super.g() = A.g, שמזמנת f() על עצם B, כלומר B.fB.f
b.superG()Bאותו דבר: A.g ואחריה B.fB.f

ההמרה `(B)(ab)` הכרחית: superG מוגדרת רק ב-B. ההמרה מצליחה בזמן ריצה כי ab מצביע על עצם B.

הפלט ב-Java:

A.f
B.f
B.f
A.f
B.g
B.g
B.f
B.f

ב-C# הפלט זהה, באותיות גדולות: A.F, B.F, B.F, A.F, B.G, B.G, B.F, B.F (כל אחד בשורה נפרדת).

הערה לגרסת C#: כפי שהודפסה, A מוגדרת בלי מציין גישה (internal), ו-B היא public. C# אינו מתיר מחלקה ציבורית שיורשת ממחלקה פחות נגישה. אנו מניחים ששתי המחלקות באותה רמת גישה (למשל שתיהן public), כפי שהשאלה מתכוונת.

תשובה: A.f, B.f, B.f, A.f, B.g, B.g, B.f, B.f (בשורות נפרדות; ב-C# עם F ו-G גדולות).

סעיף ב

תשובה:

לא. a.superG() היא שגיאת קומפילציה (ל-A אין superG). ((B)a).superG() עוברת קומפילציה אבל נכשלת בזמן ריצה: ClassCastException ב-Java, InvalidCastException ב-C#, כי a הוא עצם A.

הפקודה `a.superG();`: המהדר בודק זימון לפי הטיפוס הסטטי של המשתנה. a מוגדר מסוג A, ובמחלקה A אין פעולה superG (היא מוגדרת רק ב-B). לכן זו שגיאת קומפילציה, והתוכנית לא תעבור הידור.

הפקודה `((B)a).superG();`: ההמרה מ-A ל-B היא המרה כלפי מטה. B יורשת מ-A, ולכן המהדר מתיר אותה, ואחרי ההמרה הטיפוס הוא B שיש לו superG. הפקודה עוברת קומפילציה.

אבל בזמן ריצה נבדק הטיפוס האמיתי של העצם: a מצביע על עצם שנוצר ב-`new A()`, וזה אינו עצם B. לכן ההמרה נכשלת ונזרקת שגיאת זמן ריצה: ClassCastException ב-Java, InvalidCastException ב-C#.

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

שאלה 6 · העמסה ודריסה של equals והמרות טיפוסים

נתונות שתי המחלקות הבאות: Apple ו- Banana

Java:

public class Apple {
      private int weight;
      public Apple (int w) {
            weight = w;
      }
      public int getWeight () {
            return weight;
      }
      public boolean equals(Apple other) {
            return ((other!=null) &&
                   (weight == other.weight));
      }
}

public class Banana {
      private int weight;
      public Banana (int w) {
            weight = w;
      }
      public int getWeight () {
            return weight;
      }
      public boolean equals (Object other) {
            return ((other != null) &&
                   (other instanceof Banana) &&
                   (weight == ((Banana)other).weight));
      }
}

C#:

public class Apple {
     private int weight;
     public Apple (int w) {
          weight = w;
     }
     public int GetWeight () {
          return weight;
     }
     public bool Equals(Apple other) {
          return ((other!=null) &&
                 (weight == other.weight));
     }
}

public class Banana {
     private int weight;
     public Banana (int w) {
          weight = w;
     }
     public int GetWeight () {
          return weight;
     }
     public override bool Equals (Object other) {
          return ((other != null) &&
                 (other is Banana) &&
                 (weight == ((Banana)other).weight));
     }
}
א.

האם קיימת העמסה (Overloading) או דריסה (Overriding) של הפעולה equals במחלקות Apple ו- Banana? הסבירו את תשובתכם.

(5 נקודות)
ב.

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

Java:

public class Program {
     public static void main (String[] args) {
          System.out.println ("************");
          Apple a1 = new Apple (10);
          Object a2 = new Apple (10);
          Banana b1 = new Banana (10);
          Object b2 = new Banana (10);
          *******
  }
}

C#:

public class Program {
     public static void main (string[] args) {
          Console.WriteLine ("************");
          Apple a1 = new Apple (10);
          Object a2 = new Apple (10);
          Banana b1 = new Banana (10);
          Object b2 = new Banana (10);
          *******
  }
}

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

Java:

1.   System.out.println (a1.weight);
2.   System.out.println (((Banana)a2).getWeight());
3.   System.out.println (a1.equals(a2));
4.   System.out.println (a2.equals(a1));
5.   System.out.println (b1.equals(b2));
6.   System.out.println (b2.equals(b1));
7.   System.out.println (a1.equals((Banana)b2));
8.   System.out.println (a1.equals((Apple)a2));
9.   System.out.println (b1.equals((Apple)a2));
10.  System.out.println (b1.equals((Banana)a2));

C#:

1.   Console.WriteLine (a1.weight);
2.   Console.WriteLine (((Banana)a2).GetWeight());
3.   Console.WriteLine (a1.Equals(a2));
4.   Console.WriteLine (a2.Equals(a1));
5.   Console.WriteLine (b1.Equals(b2));
6.   Console.WriteLine (b2.Equals(b1));
7.   Console.WriteLine (a1.Equals((Banana)b2));
8.   Console.WriteLine (a1.Equals((Apple)a2));
9.   Console.WriteLine (b1.Equals((Apple)a2));
10.  Console.WriteLine (b1.Equals((Banana)a2));

הערה:

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

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

סעיף א

תשובה:

ב-Apple יש העמסה: equals(Apple) מקבלת פרמטר מטיפוס שונה מ-equals(Object) שעוברת בירושה מ-Object. ב-Banana יש דריסה: equals(Object) באותה חתימה בדיוק (ב-C#: override).

כל מחלקה יורשת מ-Object את הפעולה `equals(Object)` (ב-C#: `Equals(object)`, מוגדרת virtual), שמשווה הפניות.

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

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

Apple: `equals(Apple other)` - הפרמטר מטיפוס Apple ולא Object, ולכן זו העמסה. במחלקה קיימות שתי פעולות: equals(Apple) החדשה ו-equals(Object) שעברה בירושה מ-Object ולא שונתה. ב-C# אין לפעולה override, ולכן גם שם זו העמסה.

Banana: `equals(Object other)` - אותה חתימה כמו ב-Object, ולכן זו דריסה. ב-C# זה מסומן במפורש ב-`override`. הגרסה של Banana מחליפה את זו של Object, גם כשמזמנים אותה דרך משתנה מטיפוס Object.

תשובה: במחלקה Apple קיימת העמסה של equals, ובמחלקה Banana קיימת דריסה של equals.

סעיף ב

תשובה:

1 - שגיאת קומפילציה (weight פרטית); 2 - שגיאת זמן ריצה (המרה לא חוקית); 3 - false; 4 - false; 5 - true; 6 - true; 7 - false; 8 - true; 9 - false; 10 - שגיאת זמן ריצה. ב-C# הערכים מודפסים True/False.

כללים:

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

•המרה (cast) כלפי מטה מ-Object עוברת קומפילציה, אבל נכשלת בזמן ריצה אם העצם אינו מהטיפוס המבוקש.

•ב-Apple לא נדרסה equals(Object), ולכן זימון שלה מפעיל את הגרסה של Object, שמשווה הפניות. a1 ו-a2 הם שני עצמים שונים, ולכן התוצאה false.

שורהניתוחתוצאה
1weight מוגדרת private ב-Apple, ואי אפשר לגשת אליה מהמחלקה Programשגיאת קומפילציה
2ההמרה (Banana)a2 עוברת הידור (a2 מטיפוס Object), אבל בזמן ריצה a2 הוא Appleשגיאת זמן ריצה: ClassCastException (ב-C#: InvalidCastException)
3הארגומנט a2 מטיפוס סטטי Object, ולכן נבחרת equals(Object) של Object: השוואת הפניות של שני עצמים שוניםfalse
4a2 מטיפוס Object, ולכן נבחרת equals(Object). בזמן ריצה a2 הוא Apple, אבל Apple לא דרסה אותה, ולכן מתבצעת הגרסה של Object: השוואת הפניותfalse
5Banana.equals(Object): b2 אינו null, הוא Banana, והמשקלים 10 ו-10 שוויםtrue
6b2 מטיפוס סטטי Object, אבל בזמן ריצה מתבצעת הדריסה של Banana (b2 הוא Banana); b1 הוא Banana עם אותו משקלtrue
7(Banana)b2 מצליחה. ל-Apple אין equals(Banana); equals(Apple) אינה מתאימה (Banana אינה Apple), ולכן נבחרת equals(Object) של Object: השוואת הפניותfalse
8(Apple)a2 מצליחה (a2 הוא Apple), ונבחרת equals(Apple): המשקלים 10 ו-10 שוויםtrue
9(Apple)a2 מצליחה, ונבחרת Banana.equals(Object). הארגומנט אינו Banana, ולכן הבדיקה instanceof (ב-C#: is) נכשלתfalse
10(Banana)a2 - a2 הוא Apple, ולכן ההמרה נכשלת עוד לפני הזימוןשגיאת זמן ריצה: ClassCastException (ב-C#: InvalidCastException)

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

תשובה: 1 - שגיאת קומפילציה; 2 - שגיאת זמן ריצה; 3 - false; 4 - false; 5 - true; 6 - true; 7 - false; 8 - true; 9 - false; 10 - שגיאת זמן ריצה.

שאלה 7 · ייצוג זיכרון ברשימה מקושרת והקצאת First Fit

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

Java:

public class Data{
  private boolean free;
  private int size;
  //constructor
  public Data (int size) {
     this.free = true;
     this.size = size;
    }
  public boolean isFree(){ return free; }
  public int getSize()     { return size; }
  public void setFree(boolean free){this.free = free; }
  public void setSize(int size){ this.size = size;}
}

C#:

public class Data{
  private bool free;
  private int size;
  //constructor
  public Data (int size) {
     this.free = true;
     this.size = size;
    }
  public bool IsFree()   { return free; }
  public int GetSize()     { return size; }
  public void SetFree(bool free)   {this.free = free; }
  public void SetSize(int size){ this.size = size;}
}

הזיכרון כולו מיוצג באמצעות האובייקט הבא:

public class Memory {
  private Node<Data> start;
  public Memory(int totalSize) {
      this.start = new Node<Data>(new Data(totalSize));
   }
}

(בגרסת C# קוד המחלקה Memory זהה.)

להלן דוגמה לזיכרון שיש בו מקטע פנוי בגודל 137, אחריו מקטע תפוס בגודל 97 ולבסוף מקטע פנוי בגודל 342 (איור לשאלה 7).

הערה: לא ייתכן שיהיו שני איברים סמוכים במצב true. אבל זה כן ייתכן לגבי מצב false.

זיכרון מחשב נמצא ב"מצב מסוכן" (Dangerous State) אם כמות הזיכרון הפנוי יורדת מתחת 10% מכמות זיכרון הכללי.

א.

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

(5 נקודות)

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

אם הזיכרון נמצא ב"מצב מסוכן" האלגוריתם אינו מבצע דבר.

ב.

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

`boolean firstFit(int num)`

(ב-C#: `bool FirstFit(int num)`)

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

לדוגמה:

אם לפני הזימון של הפעולה מצב הזיכרון הוא: מקטע פנוי (true) בגודל 137, מקטע תפוס (false) בגודל 97, מקטע פנוי (true) בגודל 342,

אז אחרי הזימון firstFit(142) מצב הזיכרון ישתנה למצב הבא: פנוי 137, תפוס 97, תפוס 142, פנוי 200, והפעולה תחזיר true.

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

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

סעיף א

תשובה:

סורקים את השרשרת, סוכמים את גודל כל המקטעים ואת גודל המקטעים הפנויים, ומחזירים true אם free*10 < total.

הרעיון: "מצב מסוכן" פירושו שהזיכרון הפנוי קטן מ-10% מהזיכרון הכללי, כלומר free<0.1⋅totalfree<0.1\cdot total, או בלי שברים: 10⋅free<total10\cdot free<total.

1. מאפסים שני צוברים: total (כל הזיכרון) ו-free (הזיכרון הפנוי).

2. עוברים על השרשרת מהחוליה start עד null. בכל חוליה מוסיפים את גודל המקטע ל-total, ואם המקטע פנוי (isFree) מוסיפים אותו גם ל-free.

3. מחזירים את תוצאת ההשוואה `free * 10 < total`. ההשוואה במספרים שלמים נמנעת משגיאות עיגול.

בדוגמה שבאיור: total=137+97+342=576total=137+97+342=576 ו-free=137+342=479free=137+342=479. מתקיים 479⋅10=4790≥576479\cdot 10=4790\ge 576, ולכן הזיכרון אינו במצב מסוכן והפעולה מחזירה false.

Java:

public boolean isDangerous()
{
    int total = 0, free = 0;
    Node<Data> p = start;
    while (p != null)
    {
        total += p.getValue().getSize();
        if (p.getValue().isFree())
            free += p.getValue().getSize();
        p = p.getNext();
    }
    return free * 10 < total;
}

C#:

public bool IsDangerous()
{
    int total = 0, free = 0;
    Node<Data> p = start;
    while (p != null)
    {
        total += p.GetValue().GetSize();
        if (p.GetValue().IsFree())
            free += p.GetValue().GetSize();
        p = p.GetNext();
    }
    return free * 10 < total;
}

תשובה: הפעולה isDangerous סוכמת את הזיכרון הכולל ואת הזיכרון הפנוי, ומחזירה true אם 10⋅free<total10\cdot free<total (פחות מ-10% פנוי) ו-false אחרת.

סעיף ב

תשובה:

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

הרעיון:

1. אם הזיכרון במצב מסוכן (הפעולה מסעיף א) - לא עושים דבר ומחזירים false.

2. סורקים את השרשרת מ-start. מחפשים את החוליה הראשונה שהמקטע שלה פנוי וגודלו לפחות num.

3. כשנמצאה חוליה כזו (בגודל size), מפצלים אותה לשניים:

•החוליה עצמה הופכת למקטע תפוס בגודל num: `setFree(false)` ו-`setSize(num)`.

•היתרה rest=size−numrest=size-num נשארת פנויה. אם rest>0rest>0, יוצרים חוליה חדשה עם `new Data(rest)` (הבנאי יוצר מקטע פנוי) ומשרשרים אותה מיד אחרי החוליה הנוכחית: הבא שלה הוא הבא הקודם של החוליה הנוכחית. אם rest=0rest=0, המקטע נתפס כולו ואין צורך בחוליה חדשה.

•מחזירים true.

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

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

בדיקה מול הדוגמה, firstFit(142): הזיכרון אינו מסוכן (סעיף א). המקטע 137 פנוי אבל 137<142137<142; המקטע 97 תפוס; המקטע 342 פנוי ו-342≥142342\ge 142. הוא הופך ל"תפוס 142", ואחריו נוספת חוליה "פנוי 342−142=200342-142=200". מתקבל 137 פנוי, 97 תפוס, 142 תפוס, 200 פנוי, והפעולה מחזירה true, כמו בדוגמה.

Java:

public boolean firstFit(int num)
{
    if (isDangerous())
        return false;
    Node<Data> p = start;
    while (p != null)
    {
        Data d = p.getValue();
        if (d.isFree() && d.getSize() >= num)
        {
            int rest = d.getSize() - num;
            d.setFree(false);
            d.setSize(num);
            if (rest > 0)
            {
                Node<Data> part = new Node<Data>(new Data(rest), p.getNext());
                p.setNext(part);
            }
            return true;
        }
        p = p.getNext();
    }
    return false;
}

C#:

public bool FirstFit(int num)
{
    if (IsDangerous())
        return false;
    Node<Data> p = start;
    while (p != null)
    {
        Data d = p.GetValue();
        if (d.IsFree() && d.GetSize() >= num)
        {
            int rest = d.GetSize() - num;
            d.SetFree(false);
            d.SetSize(num);
            if (rest > 0)
            {
                Node<Data> part = new Node<Data>(new Data(rest), p.GetNext());
                p.SetNext(part);
            }
            return true;
        }
        p = p.GetNext();
    }
    return false;
}

סיבוכיות: O(n)O(n), כאשר n הוא מספר החוליות (גם סעיף א וגם החיפוש הם מעבר אחד על השרשרת).

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

שאלה 8 · רשימת מספרים: השוואת רישא והכלה

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

Java:

public class IntList {
    private Node<Integer> head;
    public IntList( ) {
        head = null;
    }
    public void add(int a) {
       head = new Node<Integer> (a, head);
    }
    public String toString(){
        String s = "{";
        Node<Integer> h = head;
        while(h.getNext()!= null){
            s += h.getValue()+",";
            h = h.getNext();
        }
        return s + h.getValue()+"}";
    }
    public  boolean what1 (IntList list) {
        Node<Integer> h1 = head;
        Node<Integer> h2 = list.head;
        while ((h1 != null) && (h2 != null))  {
            if (h1.getValue()!= h2.getValue())
                return false;
            h1 = h1.getNext();
            h2 = h2.getNext();
        }
        return true;
    }
    public boolean what2 (IntList list) {
        Node<Integer> h1 = head;
        while (h1 != null) {
            boolean found = false;
            Node<Integer> h2 = list.head;
            while ((h2 != null) && (!found)) {
                if (h1.getValue()== h2.getValue())
                    found = true;
                h2 = h2.getNext();
            }
            if (!found)
                return false;
            h1 = h1.getNext();
        }
        return true;
    }
}

C#:

public class IntList {
    private Node<int> head;
    public IntList( ) {
        head = null;
    }
    public void Add(int a) {
       head = new Node<int> (a, head);
    }
    public override string ToString(){
        string s = "{";
        Node<int> h = head;
        while(h.GetNext()!= null){
            s += h.GetValue()+",";
            h = h.GetNext();
        }
        return s + h.GetValue()+"}";
    }
    public  bool What1 (IntList list) {
        Node<int> h1 = head;
        Node<int> h2 = list.head;
        while ((h1 != null) && (h2 != null))  {
            if (h1.GetValue()!= h2.GetValue())
                return false;
            h1 = h1.GetNext();
            h2 = h2.GetNext();
        }
        return true;
    }
    public bool What2 (IntList list) {
        Node<int> h1 = head;
        while (h1 != null) {
            bool found = false;
            Node<int> h2 = list.head;
            while ((h2 != null) && (!found)) {
                if (h1.GetValue()== h2.GetValue())
                    found = true;
                h2 = h2.GetNext();
            }
            if (!found)
                return false;
            h1 = h1.GetNext();
        }
        return true;
    }
}

נתון קטע קוד של הפעולה main במחלקה Program:

Java:

IntList testList = new IntList();
testList.add(2); testList.add(3); testList.add(6);
testList.add(1); testList.add(4);
System.out.println(testList);

C#:

IntList testList = new IntList();
testList.Add(2); testList.Add(3); testList.Add(6);
testList.Add(1); testList.Add(4);
Console.WriteLine(testList);
א.

מהו הפלט של קטע הקוד (אין צורך במעקב מפורט)?

(3 נקודות)
ב.

בעבור עצם שנוצר בסעיף א' הביאו דוגמה של עצם אחר מטיפוס IntList בשם list הכולל ארבעה איברים לפחות, כך ש:

(1)

זימון testList.what1(list) יחזיר true והזימון testList.what2 (list) יחזיר true

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

(2)

זימון testList.what1(list) יחזיר true והזימון testList.what2 (list) יחזיר false

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

(3)

זימון testList.what1(list) יחזיר false והזימון testList.what2 (list) יחזיר true

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

(4)

זימון testList.what1(list) יחזיר false והזימון testList.what2 (list) יחזיר false

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

(8 נקודות)
ג.

מה מבצעות הפעולות what1 ו- what2 באופן כללי?

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

סעיף א

תשובה:

{4,1,6,3,2}

הפעולה add יוצרת חוליה חדשה בראש הרשימה (`head = new Node(a, head)`), ולכן כל מספר חדש נכנס לפני כל הקודמים, והרשימה מתקבלת בסדר הפוך לסדר ההוספה:

אחרי הפקודההרשימה מ-head
add(2)2
add(3)3, 2
add(6)6, 3, 2
add(1)1, 6, 3, 2
add(4)4, 1, 6, 3, 2

toString מתחילה ב-"{", מוסיפה כל ערך ואחריו פסיק עד החוליה האחרונה, ואת הערך האחרון מוסיפה עם "}".

תשובה: הפלט הוא `{4,1,6,3,2}`.

סעיף ב

(1)
תשובה:

אפשר: list = {4,1,6,3,2} (נבנה ב-add(2), add(3), add(6), add(1), add(4)).

what1 מחזירה true אם בכל המקומות המשותפים לשתי הרשימות הערכים שווים, כלומר אחת הרשימות היא רישא (התחלה) של השנייה. what2 מחזירה true אם כל ערך של testList נמצא ב-list.

רשימה זהה ל-testList מקיימת את שני התנאים: כל האיברים שווים במקום, וכל ערך של testList נמצא בה (גם {4,1,6,3,2,9} מתאימה).

תשובה: list = {4,1,6,3,2}, כלומר הרשימה שנבנית בזימונים add(2), add(3), add(6), add(1), add(4).

(2)
תשובה:

אפשר: list = {4,1,6,3} (נבנה ב-add(3), add(6), add(1), add(4)).

ב-what1 משווים רק כל עוד שתי הרשימות לא נגמרו: 4=4, 1=1, 6=6, 3=3, ואז list נגמרת והפעולה מחזירה true.

ב-what2 הערך 2 של testList אינו נמצא ב-list, ולכן היא מחזירה false.

תשובה: list = {4,1,6,3}, כלומר הרשימה שנבנית בזימונים add(3), add(6), add(1), add(4).

(3)
תשובה:

אפשר: list = {2,3,6,1,4} (נבנה ב-add(4), add(1), add(6), add(3), add(2)).

אותם ערכים בסדר אחר: כבר במקום הראשון 4≠24\ne 2, ולכן what1 מחזירה false. כל ערך של testList (4, 1, 6, 3, 2) נמצא ב-list, ולכן what2 מחזירה true.

תשובה: list = {2,3,6,1,4}, כלומר הרשימה שנבנית בזימונים add(4), add(1), add(6), add(3), add(2).

(4)
תשובה:

אפשר: list = {7,8,9,10} (נבנה ב-add(10), add(9), add(8), add(7)).

במקום הראשון 4≠74\ne 7, ולכן what1 מחזירה false. הערך 4 של testList אינו מופיע ב-list, ולכן what2 מחזירה false.

תשובה: list = {7,8,9,10}, כלומר הרשימה שנבנית בזימונים add(10), add(9), add(8), add(7).

סעיף ג

תשובה:

what1 בודקת אם אחת הרשימות היא רישא (התחלה) של השנייה, כלומר הרשימות שוות בכל המקומות המשותפים. what2 בודקת אם כל ערך ברשימה הנוכחית מופיע גם ב-list (הכלה).

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

what2: לכל איבר h1 ברשימה הנוכחית (this) מחפשת ב-list איבר שווה. אם יש איבר שלא נמצא - מחזירה false. אם כל האיברים נמצאו - true. כלומר היא בודקת שכל ערכי הרשימה הנוכחית מופיעים ב-list (קבוצת הערכים של this מוכלת בקבוצת הערכים של list), בלי להתחשב בסדר ובמספר החזרות.

הערה ל-Java: הערכים שמורים כ-Integer, והביטויים `!=` ו-`==` משווים הפניות של עצמים. עבור מספרים קטנים (בין -128 ל-127, כמו בשאלה) Java משתמשת בעצמים שמורים משותפים, ולכן ההשוואה עובדת כמו השוואת ערכים. ב-C# הטיפוס הוא int וההשוואה היא תמיד של ערכים.

תשובה: what1 - בודקת אם רשימה אחת היא התחלה של השנייה (שוות בכל המקומות המשותפים). what2 - בודקת אם כל ערך ברשימה הנוכחית מופיע ברשימה list.

שאלה 9 · צוות רפואי: היררכיית מחלקות, מספר עובד אוטומטי

בבית חולים מסוים פותח פרויקט לניהול הצוות הרפואי. לכל עובד (Employee) בביה"ח יש שם ומספר עובד. מספר העובד הוא מספר ייחודי הניתן באופן אוטומטי עם הוספת עובד חדש למאגר העובדים כך שהעובד הראשון יקבל את המספר 1, העובד השני 2 וכך הלאה.

לאחות (Nurse) יש את התכונות:

•num - מספר עובד, מטיפוס שלם, int.

•name - שם, מטיפוס מחרוזת, String.

•type - סוג (מעשית, מוסמכת), מטיפוס מחרוזת, String.

לרופא (Doctor) יש את התכונות:

•num - מספר עובד, מטיפוס שלם, int.

•name - שם, מטיפוס מחרוזת, String.

•specialization - התמחות (רופא לב, רופא מרדים, רופא מנתח וכו'), מטיפוס מחרוזת, String.

ראש צוות (Supervisor) - ראש צוות הוא רופא שאחראי על צוות של __עד עשרה__ רופאים ואחיות:

•arr - מערך של אנשי הצוות הכפופים לראש הצוות.

•current - מספר אנשי הצוות בפועל, מטיפוס שלם, int.

(בגרסת C# הטיפוס של המחרוזות הוא string.)

א.

שרטטו תרשים UML המתאר את הקשר בין המחלקות Employee, Nurse, Doctor, Supervisor באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.

(2 נקודות)
ב.

לכל אחת מהמחלקות Employee, Nurse, Doctor, Supervisor כתבו:

•כותרת המחלקה.

•תכונות.

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

הערה:

יש לשים לב שמספר העובד הוא מספר ייחודי, שנוצר באופן אוטומטי, ואין להעבירו כפרמטר לפעולה בונה!

(4 נקודות)

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

•arr - מערך של כל אנשי הצוות. בבית חולים יכולים לעבוד לא יותר מ- 200 אנשי צוות.

•current - מספר אנשי הצוות בפועל, מטיפוס שלם, int.

ג.

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

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

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

(ב-C#: NumSupervisor ו-GetNewNurse.)

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

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

סעיף א

תשובה:

Employee (מופשטת: num, name, מונה סטטי) היא מחלקת-העל; Nurse ו-Doctor יורשות ממנה; Supervisor יורשת מ-Doctor ומכילה מערך של עד 10 עצמי Employee (הכלה/צבירה).

ניתוח:

1. לאחות ולרופא יש תכונות משותפות - num ו-name. כדי לא לשכפל קוד מעבירים אותן למחלקת-על Employee, וגם את מנגנון מספור העובדים האוטומטי (מונה סטטי counter). Employee מופשטת (abstract), כי כל עובד בפועל הוא אחות או רופא.

2. Nurse יורשת מ-Employee ומוסיפה את type. Doctor יורשת מ-Employee ומוסיפה את specialization.

3. ראש צוות הוא רופא (קשר is-a), ולכן Supervisor יורשת מ-Doctor ומקבלת ממנו גם num, name ו-specialization.

4. ראש הצוות מכיל צוות של עד 10 אנשים - רופאים ואחיות. לכן המערך שלו מטיפוס Employee (הוא יכול להכיל גם Nurse וגם Doctor). זה קשר הכלה (צבירה, has-a) בין Supervisor ל-Employee, עם ריבוי 0..10.

התרשים:

                +---------------------------+
                |   <<abstract>> Employee   |
                +---------------------------+
                | - counter : int  {static} |
                | - num : int               |
                | - name : String           |
                +---------------------------+
                | + Employee(name)          |
                | + getNum() : int          |
                | + getName() : String      |
                +---------------------------+
                     ^                 ^
                     | (inherits)      | (inherits)
   +------------------------+    +------------------------------+
   |         Nurse          |    |            Doctor            |
   +------------------------+    +------------------------------+
   | - type : String        |    | - specialization : String    |
   +------------------------+    +------------------------------+
   | + Nurse(name, type)    |    | + Doctor(name, spec.)        |
   +------------------------+    +------------------------------+
                                               ^
                                               | (inherits)
                                 +------------------------------+
                                 |          Supervisor          |
                                 +------------------------------+
                                 | - arr : Employee[10]         |
                                 | - current : int              |
                                 +------------------------------+
                                 | + Supervisor(name, spec.)    |
                                 +------------------------------+
                                      <>  0..10
                                      +-----------> Employee

החצים עם המשולש (^) מסמנים ירושה. המעוין (<>) מסמן ש-Supervisor מכיל (צובר) 0 עד 10 עצמים מסוג Employee.

תשובה: Employee היא מחלקת-העל (מופשטת) עם num, name ומונה סטטי; Nurse ו-Doctor יורשות ממנה; Supervisor יורשת מ-Doctor ומכילה מערך Employee של עד 10 אנשי צוות.

סעיף ב

תשובה:

Employee: static counter, num, name; הבנאי Employee(name) מגדיל את counter ומציב אותו ב-num. Nurse(name, type) ו-Doctor(name, specialization) מזמנים את בנאי Employee. Supervisor(name, specialization) מזמן את בנאי Doctor ויוצר arr = new Employee[10], current = 0.

הרעיון של המספור האוטומטי: תכונה סטטית (משותפת לכל העצמים של המחלקה) `counter` שומרת כמה עובדים נוצרו עד כה. הבנאי של Employee מגדיל אותה ב-1 ומציב את הערך החדש ב-num של העובד. כך העובד הראשון יקבל 1, השני 2 וכן הלאה, ואין צורך להעביר את המספר כפרמטר.

כל בנאי של מחלקה יורשת מזמן את הבנאי של מחלקת-העל שלו (`super(...)`, ב-C#: `: base(...)`), ולכן כל עובד מכל סוג עובר דרך הבנאי של Employee ומקבל מספר. הבנאי של Supervisor יוצר מערך ריק של 10 אנשי צוות, ומספר אנשי הצוות בפועל הוא 0.

Java:

public abstract class Employee
{
    private static int counter = 0;   // how many employees were created
    private int num;
    private String name;

    public Employee(String name)
    {
        counter++;
        this.num = counter;
        this.name = name;
    }
}

public class Nurse extends Employee
{
    private String type;

    public Nurse(String name, String type)
    {
        super(name);
        this.type = type;
    }
}

public class Doctor extends Employee
{
    private String specialization;

    public Doctor(String name, String specialization)
    {
        super(name);
        this.specialization = specialization;
    }
}

public class Supervisor extends Doctor
{
    private Employee[] arr;
    private int current;

    public Supervisor(String name, String specialization)
    {
        super(name, specialization);
        this.arr = new Employee[10];
        this.current = 0;
    }
}

C#:

public abstract class Employee
{
    private static int counter = 0;   // how many employees were created
    private int num;
    private string name;

    public Employee(string name)
    {
        counter++;
        this.num = counter;
        this.name = name;
    }
}

public class Nurse : Employee
{
    private string type;

    public Nurse(string name, string type) : base(name)
    {
        this.type = type;
    }
}

public class Doctor : Employee
{
    private string specialization;

    public Doctor(string name, string specialization) : base(name)
    {
        this.specialization = specialization;
    }
}

public class Supervisor : Doctor
{
    private Employee[] arr;
    private int current;

    public Supervisor(string name, string specialization) : base(name, specialization)
    {
        this.arr = new Employee[10];
        this.current = 0;
    }
}

תשובה: ארבע המחלקות כמתואר: Employee עם מונה סטטי שמעניק את num בבנאי, Nurse ו-Doctor מרחיבות אותה, ו-Supervisor מרחיבה את Doctor עם מערך Employee בגודל 10 ומונה current.

סעיף ג

תשובה:

arr מסוג Employee[200] ו-current. numSupervisor סופרת את התאים 0..current-1 שהם instanceof Supervisor. getNewNurse עוברת על העובדים, ולכל Nurse (בהמרה) מהסוג המבוקש שומרת את זו עם getNum() המקסימלי; מחזירה אותה או null.

התכונות: המערך מטיפוס Employee, כדי שיוכל להכיל אחיות, רופאים וראשי צוותים (כולם Employee). גודלו 200, ו-current מציין כמה תאים בתחילתו (0 עד current-1) תפוסים.

numSupervisor: עוברים על העובדים הקיימים וסופרים את אלה שהטיפוס האמיתי שלהם Supervisor, בעזרת `instanceof` (ב-C#: `is`).

getNewNurse(type):

1. משתנה newest מאותחל ל-null (עדיין לא נמצאה אחות מתאימה).

2. עוברים על העובדים. אם העובד הוא אחות (instanceof Nurse), ממירים אותו ל-Nurse. ההמרה הכרחית, כי לטיפוס Employee אין פעולה getType.

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

4. מחזירים את newest. אם לא נמצאה אף אחות מהסוג הנדרש, מוחזר null.

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

Java:

public class AllEmployees
{
    private Employee[] arr;
    private int current;

    public AllEmployees()
    {
        arr = new Employee[200];
        current = 0;
    }

    public int numSupervisor()
    {
        int count = 0;
        for (int i = 0; i < current; i++)
            if (arr[i] instanceof Supervisor)
                count++;
        return count;
    }

    public Nurse getNewNurse(String type)
    {
        Nurse newest = null;
        for (int i = 0; i < current; i++)
        {
            if (arr[i] instanceof Nurse)
            {
                Nurse n = (Nurse) arr[i];
                if (n.getType().equals(type)
                        && (newest == null || n.getNum() > newest.getNum()))
                    newest = n;
            }
        }
        return newest;
    }
}

C#: ב-C# לכל עצם יש כבר פעולה GetType() שעוברת בירושה מ-object, ולכן את פעולת ה-get של התכונה type נקרא כאן GetNurseType().

public class AllEmployees
{
    private Employee[] arr;
    private int current;

    public AllEmployees()
    {
        arr = new Employee[200];
        current = 0;
    }

    public int NumSupervisor()
    {
        int count = 0;
        for (int i = 0; i < current; i++)
            if (arr[i] is Supervisor)
                count++;
        return count;
    }

    public Nurse GetNewNurse(string type)
    {
        Nurse newest = null;
        for (int i = 0; i < current; i++)
        {
            if (arr[i] is Nurse)
            {
                Nurse n = (Nurse) arr[i];
                if (n.GetNurseType() == type
                        && (newest == null || n.GetNum() > newest.GetNum()))
                    newest = n;
            }
        }
        return newest;
    }
}

תשובה: AllEmployees עם `Employee[] arr` (200 תאים) ו-`int current`. numSupervisor סופרת את העובדים מטיפוס Supervisor, ו-getNewNurse מחזירה את האחות מהסוג המבוקש שמספר העובד שלה הגדול ביותר, או null אם אין כזו.

שאלה 10 · מאגר ציונים: מערך של תורים לפי ספרות אמצעיות

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

לשם כך הוגדרו המחלקות Student ו- GradesFile.

כל סטודנט מאופיין באמצעות מספר סטודנט (studentId) שמורכב משמונה ספרות וציון (grade).

מכיוון שמרחב מספרי הסטודנטים גדול, הוחלט שהציונים יישמרו ב- 100 רשימות, כדי לאפשר חיפוש מהיר.

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

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

לוקחים את שתי __הספרות האמצעיות__ של מספר הסטודנט. אלה יוצרות מספר K בין 0 ל- 99. מוסיפים את הסטודנט למאגר לאוסף הנמצא במקום K במערך.

לדוגמה:

אם מספר הסטודנט הוא 12345678 הסטודנט ייכנס למאגר לרשימה במקום 45 במערך.

המבנה ייראה כך (איור לשאלה 10):

א.

כתבו את כותרת המחלקות Student ו- GradesFile ואת התכונות שלהן.

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

(2 נקודות)
ב.

ממשו במחלקה Student את הפעולה `int getCode()`.

(ב-C#: `int GetCode()`)

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

__לדוגמה__: עבור המספר 12345678 הפעולה תחזיר 45.

(2 נקודות)

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

פעולהתיאור
`Student getStudent(int k)`הפעולה מחזירה את הסטודנט הראשון באוסף במקום ה- k במערך. אם אוסף במקום k ריק או k לא נמצא בגבולות המערך, הפעולה תחזיר null.
`boolean isEmpty(int k)`הפעולה מחזירה "אמת" אם אוסף הסטודנטים במקום ה- k ריק, ו"שקר" אם לא. אם k לא נמצא בגבולות המערך, הפעולה מחזירה "אמת".
`boolean listIsGood (int k)`הפעולה מחזירה "אמת" אם כל הסטודנטים הנמצאים באוסף במקום ה- k במערך, מתאימים למקום זה על פי ה- studentId, ו"שקר" אם לא. אם k לא נמצא בגבולות המערך או האוסף במקום ה- k ריק, הפעולה מחזירה "אמת".

(ב-C#: GetStudent, IsEmpty, ListIsGood, ו-bool במקום boolean.)

ג.

ממשו את הפעולה `void moveStudent(int k, int j)`.

(ב-C#: `void MoveStudent(int k, int j)`)

פעולהתיאור
`void moveStudent(int k, int j)`הפעולה מעבירה את הסטודנט הראשון באוסף שמיקומו k במערך להיות סטודנט אחרון באוסף שמיקומו j במערך. אם האוסף במקום ה- k ריק או k או j לא נמצאים בגבולות המערך, הפעולה לא מבצעת דבר.
(4 נקודות)
ד.

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

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

הערה:

בפתרון של סעיף ד' יש להשתמש בפעולות הנתונות של המחלקות Student ו-GradesFile בלבד!

אין להשתמש בפעולות של מבנים אחרים ואין להניח על קיומן של הפעולות האחרות במחלקות Student ו- GradesFile.

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

סעיף א

תשובה:

Student: int studentId, double grade. GradesFile: מערך של 100 תורים, Queue<Student>[] arr (תור מתאים כי נדרש 'הסטודנט הראשון' והוספה 'כסטודנט אחרון').

Student: מספר סטודנט בן 8 ספרות נכנס בטיפוס int (הערך הגדול ביותר, 99,999,999, קטן מהמקסימום של int). הציון הוא ממוצע משוקלל, ולכן double.

GradesFile: מערך בגודל 100, ובכל תא אוסף בגודל לא מוגבל של סטודנטים. בחרנו בתור (Queue<Student>):

•הפעולות של המחלקה מדברות על "הסטודנט הראשון באוסף" (getStudent) ועל העברה "להיות סטודנט אחרון באוסף" (moveStudent). אלה בדיוק הפעולות של תור: head/remove מראש התור ו-insert לסופו.

•גודל התור אינו מוגבל, כנדרש.

בבנאי יוצרים 100 תורים ריקים. באיור תא ריק מסומן כ-null; אצלנו תא ריק הוא תור ריק, והבדיקה נעשית ב-isEmpty.

Java:

public class Student
{
    private int studentId;     // 8 digits
    private double grade;      // final weighted average
}

public class GradesFile
{
    private Queue<Student>[] arr;

    public GradesFile()
    {
        arr = new Queue[100];
        for (int i = 0; i < arr.length; i++)
            arr[i] = new Queue<Student>();
    }
}

C#:

public class Student
{
    private int studentId;     // 8 digits
    private double grade;      // final weighted average
}

public class GradesFile
{
    private Queue<Student>[] arr;

    public GradesFile()
    {
        arr = new Queue<Student>[100];
        for (int i = 0; i < arr.Length; i++)
            arr[i] = new Queue<Student>();
    }
}

תשובה: Student - `int studentId`, `double grade`; GradesFile - מערך של 100 תורים `Queue<Student>[] arr`.

סעיף ב

תשובה:

return (studentId / 1000) % 100;

הרעיון: במספר בן 8 ספרות d1d2d3d4d5d6d7d8d_1d_2d_3d_4d_5d_6d_7d_8, הספרות האמצעיות הן d4d5d_4d_5 - הרביעית והחמישית משמאל.

1. חלוקה בשלמים ב-1000 מסירה את שלוש הספרות הימניות: 12345678/1000=1234512345678/1000=12345.

2. שארית החלוקה ב-100 משאירה את שתי הספרות הימניות של התוצאה: 12345 mod 100=4512345 \bmod 100=45.

Java:

public int getCode()
{
    return (studentId / 1000) % 100;
}

C#:

public int GetCode()
{
    return (studentId / 1000) % 100;
}

הערך המוחזר תמיד בין 0 ל-99, ולכן הוא אינדקס חוקי במערך (למשל עבור 10000078 מתקבל 0).

תשובה: `return (studentId / 1000) % 100;` - עבור 12345678 מוחזר 45.

סעיף ג

תשובה:

אם j מחוץ לגבולות או isEmpty(k) (מכסה גם k מחוץ לגבולות) - לא עושים דבר; אחרת arr[j].insert(arr[k].remove()).

הרעיון: כל אוסף הוא תור, ולכן "הסטודנט הראשון באוסף k" הוא ראש התור arr[k], ו"להיות סטודנט אחרון באוסף j" פירושו הכנסה לסוף התור arr[j].

1. בדיקת תקינות: הפעולה isEmpty(k) הנתונה מחזירה true גם כש-k מחוץ לגבולות המערך, ולכן הבדיקה `isEmpty(k)` מכסה את שני המקרים "האוסף k ריק" ו-"k לא בגבולות". את j בודקים בנפרד: 0≤j<1000\le j<100. אם אחד התנאים מתקיים - יוצאים בלי לעשות דבר.

2. העברה: מוציאים את הסטודנט מראש התור k (remove) ומכניסים אותו לסוף התור j (insert).

אם j=kj=k, הסטודנט עובר מראש התור לסופו של אותו תור (סיבוב). זה יהיה שימושי בסעיף ד.

Java:

public void moveStudent(int k, int j)
{
    if (j < 0 || j >= arr.length || isEmpty(k))
        return;
    arr[j].insert(arr[k].remove());
}

C#:

public void MoveStudent(int k, int j)
{
    if (j < 0 || j >= arr.Length || IsEmpty(k))
        return;
    arr[j].Insert(arr[k].Remove());
}

תשובה: אם האוסף k ריק או ש-k/j מחוץ לגבולות - לא מבצעים דבר; אחרת `arr[j].insert(arr[k].remove())`.

סעיף ד

תשובה:

לכל k מ-0 עד 99: כל עוד !listIsGood(k): code = getStudent(k).getCode(); moveStudent(k, code). סטודנט במקום הלא נכון עובר לאוסף שלו, וסטודנט במקום הנכון (code==k) מסתובב לסוף אותו אוסף.

הרעיון: מטפלים באוספים אחד אחרי השני, k = 0, 1, ..., 99. מותר להשתמש רק בפעולות getStudent, isEmpty, listIsGood, moveStudent ו-getCode.

1. כל עוד האוסף k אינו תקין (`!listIsGood(k)`), מסתכלים על הסטודנט הראשון בו (`getStudent(k)`) ומחשבים את מקומו הנכון `code = getCode()`.

2. מזמנים `moveStudent(k, code)`:

•אם code≠kcode\ne k - הסטודנט נמצא במקום שגוי, והוא עובר לסוף האוסף הנכון שלו. מספר הסטודנטים השגויים באוסף k קטן ב-1.

•אם code=kcode=k - הסטודנט במקום הנכון, וההעברה מעבירה אותו מראש האוסף לסופו (סיבוב). כך הסטודנט הבא מגיע לראש האוסף.

3. כשהאוסף k נעשה תקין (או ריק), עוברים ל-k הבא.

למה זה נכון ומסתיים?

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

•אוספים שכבר טופלו נשארים תקינים: אל אוסף c נכנסים רק סטודנטים שהקוד שלהם c, כלומר רק סטודנטים במקום הנכון. לכן גם אוסף c<kc<k שכבר תוקן לא מתקלקל, ואוסף c>kc>k פשוט יקבל סטודנט תקין שיישאר בו.

•אף סטודנט לא הולך לאיבוד: moveStudent רק מעבירה סטודנטים בין אוספים.

Java:

public static void fixFile(GradesFile gf)
{
    for (int k = 0; k < 100; k++)
    {
        while (!gf.listIsGood(k))
        {
            int code = gf.getStudent(k).getCode();
            gf.moveStudent(k, code);    // wrong place: to its list; right place: to the end
        }
    }
}

C#:

public static void FixFile(GradesFile gf)
{
    for (int k = 0; k < 100; k++)
    {
        while (!gf.ListIsGood(k))
        {
            int code = gf.GetStudent(k).GetCode();
            gf.MoveStudent(k, code);    // wrong place: to its list; right place: to the end
        }
    }
}

תשובה: הפעולה החיצונית fixFile עוברת על k = 0..99, וכל עוד listIsGood(k) מחזירה false היא מזמנת `moveStudent(k, getStudent(k).getCode())`. בסוף כל סטודנט נמצא באוסף שמספרו הוא שתי הספרות האמצעיות של מספר הסטודנט שלו.

שאלה 11 · מעקב: בנאים, בנאי העתקה וירושה עם הכלה

נתונות שלוש מחלקות הבאות: One, Two, Driver

Java:

public class One {
    private int num;
    private char ch;
    public One()  {num = 2;   ch = 'G'; }
    public One(int n)  {  num = n;  ch = 'M'; }
    public One(int n, char c)  {  num = n; ch = c;  }
    public One(One other){
        num = other.num;
        ch = other.ch;
    }
    public int getNum()    { return num;  }
    public char getCh()    { return ch; }
    public void inc(){ num ++; ch ++; }
    public String toString(){
        String s = "";
        for (int i = 0; i < num; i++)
            s += ch;
        return s;
    }
}// end of a class One

public class Two extends One {
  private One first;
  public Two()    {  super();  first = new One();}
  public Two(int n) {  super(n);  first = new One(); }
  public Two(One other) {
    super(); first = new One(other);
  }
  public Two(One other, int n) {
    super(other); first = new One(n);
   }
  public void inc(){ first.inc(); }
  private int what (int n, int m) {
    if(n > m )return n;
    return m;
   }
  private char what (char ch1, char ch2){
   if(ch1<ch2) return ch1;
   return ch2;
  }
  public One makeOne(){
   return
      new One(what(first.getNum(),getNum()),
              what(first.getCh(), getCh()));
  }
  public String toString(){ return first.toString();}
}// end of a class Two
public class Driver{
    public static void main(String[] args){
        One x1 = new One(4, 'E');
        One x2 = new One(3);
        Two y1 = new Two(x1);
        One x3 = new Two(5);
        System.out.println("x1 before "+x1);
        x1.inc();
        System.out.println("x1 after "+x1);
        System.out.println("x2 " + x2);
        System.out.println("y1 " + y1);
        System.out.println("x3 " + x3);
        Two y2 = new Two(y1, 1);
        System.out.println("y2 " + y2);
        One x4 = y2.makeOne();
        System.out.println("x4 " + x4);
    }
}// end of a class Driver

C#:

public class One {
    private int num;
    private char ch;
    public One()  {num = 2;   ch = 'G'; }
    public One(int n)  {  num = n;  ch = 'M'; }
    public One(int n, char c)  {  num = n; ch = c;  }
    public One(One other){
        num = other.num;
        ch = other.ch;
    }
    public int GetNum()    { return num;  }
    public char GetCh()    { return ch; }
    public virtual void Inc(){ num ++; ch ++; }
    public override string ToString(){
        string s = "";
        for (int i = 0; i < num; i++)
            s += ch;
        return s;
    }
}// end of a class One

public class Two : One {
  private One first;
  public Two(): base()    { first = new One(); }
  public Two(int n): base(n) { first = new One(); }
  public Two(One other): base() {
    first = new One(other);
  }
  public Two(One other, int n): base(other) {
    first = new One(n);
   }
  public override void Inc(){ first.Inc(); }
  private int What (int n, int m) {
    if(n > m )return n;
    return m;
   }
  private char What (char ch1, char ch2){
   if(ch1<ch2) return ch1;
   return ch2;
  }
  public One MakeOne(){
   return
      new One(What(first.GetNum(),GetNum()),
              What(first.GetCh(), GetCh()));
  }
  public override string ToString(){ return first.ToString();}
}// end of a class Two
public class Driver{
    public static void Main(string[] args){
        One x1 = new One(4, 'E');
        One x2 = new One(3);
        Two y1 = new Two(x1);
        One x3 = new Two(5);
        Console.WriteLine("x1 before "+x1);
        x1.Inc();
        Console.WriteLine("x1 after "+x1);
        Console.WriteLine("x2 " + x2);
        Console.WriteLine("y1 " + y1);
        Console.WriteLine("x3 " + x3);
        Two y2 = new Two(y1, 1);
        Console.WriteLine("y2 " + y2);
        One x4 = y2.MakeOne();
        Console.WriteLine("x4 " + x4);
    }
}// end of a class Driver
א.

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

יש להשתמש באיורים הבאים להצגת העצמים (איור לשאלה 11):

(5 נקודות)
ב.

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

(ב-C#: Main)

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

סעיף א

תשובה:

x1: num=5, ch='F' (לפני inc: 4,'E'); x2: 3,'M'; y1: 2,'G', first→(4,'E'); x3: 5,'M', first→(2,'G'); y2: 2,'G', first→(1,'M'); x4: 2,'G'.

נעקוב אחרי כל פקודה ב-main ונרשום את התכונות של העצמים שנוצרים. עצם Two מכיל את התכונות num ו-ch (שעברו בירושה מ-One) וגם הפניה first לעצם One נפרד.

פקודהמה קורההעצם שנוצר / משתנה
`One x1 = new One(4,'E')`הבנאי עם int ו-charx1: num=4, ch='E'
`One x2 = new One(3)`הבנאי עם int: ch='M'x2: num=3, ch='M'
`Two y1 = new Two(x1)`super() נותן num=2, ch='G'; first = new One(x1) יוצר עותק של x1y1: num=2, ch='G'; first: num=4, ch='E'
`One x3 = new Two(5)`super(5) נותן num=5, ch='M'; first = new One()x3: num=5, ch='M'; first: num=2, ch='G'
`x1.inc()`x1 הוא עצם One: num++ ו-ch++ (אחרי 'E' בא 'F')x1: num=5, ch='F'. העותק ב-y1.first לא משתנה
`Two y2 = new Two(y1, 1)`super(other) מעתיק את num ו-ch של y1 (2,'G'); first = new One(1)y2: num=2, ch='G'; first: num=1, ch='M'
`One x4 = y2.makeOne()`what(1, 2) מחזירה את הגדול: 2; what('M','G') מחזירה את הקטן: 'G' (כי 'G'<'M')x4: num=2, ch='G'

ערכי התכונות בסוף הביצוע (בפורמט האיורים):

•One x1: num = 5, ch = 'F'

•One x2: num = 3, ch = 'M'

•Two y1: num = 2, ch = 'G', first ← (num = 4, ch = 'E')

•Two x3 (משתנה מטיפוס One שמצביע על עצם Two): num = 5, ch = 'M', first ← (num = 2, ch = 'G')

•Two y2: num = 2, ch = 'G', first ← (num = 1, ch = 'M')

•One x4: num = 2, ch = 'G'

תשובה: x1 (5,'F'), x2 (3,'M'), y1 (2,'G' ו-first (4,'E')), x3 (5,'M' ו-first (2,'G')), y2 (2,'G' ו-first (1,'M')), x4 (2,'G').

סעיף ב

תשובה:

x1 before EEEE / x1 after FFFFF / x2 MMM / y1 EEEE / x3 GG / y2 M / x4 GG

toString של One מחזירה את התו ch משורשר num פעמים. ב-Two הפעולה דורסת את toString ומחזירה `first.toString()` - כלומר את המחרוזת של העצם הפנימי first, ולא של num ו-ch של העצם עצמו. השרשור `"..." + x` מזמן את toString של הטיפוס האמיתי של העצם (קישור דינמי), ולכן גם x3, שמוגדר כמשתנה מטיפוס One, מודפס לפי Two.

הדפסהחישובפלט
x1 beforex1 = (4,'E'), ארבע פעמים Ex1 before EEEE
x1 afterאחרי inc: x1 = (5,'F')x1 after FFFFF
x2(3,'M')x2 MMM
y1Two, ולכן first = (4,'E') - עותק שלא הושפע מ-inc של x1y1 EEEE
x3עצם Two, ולכן first = (2,'G')x3 GG
y2first = (1,'M')y2 M
x4עצם One = (2,'G')x4 GG
x1 before EEEE
x1 after FFFFF
x2 MMM
y1 EEEE
x3 GG
y2 M
x4 GG

הפלט זהה ב-Java וב-C#. ב-C# הפעולה Inc מוגדרת virtual ונדרסת ב-Two, אבל x1 הוא עצם One, ולכן מתבצעת הגרסה של One.

תשובה: x1 before EEEE, x1 after FFFFF, x2 MMM, y1 EEEE, x3 GG, y2 M, x4 GG (כל אחד בשורה נפרדת).

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

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

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