מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - קיץ 2021 מועד א'
הנדסת תוכנה · סמל 97105 · 11 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, קיץ 2021 מועד א', כל 11 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 20)
בכל מבחן 11 שאלות.
שאלות 4-1: יש לענות על שלוש שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 8-5: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 11-9: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 12 נקודות.
נקודה אחת תינתן על הערכה.
חומר עזר: 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.
המחלקה 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).
כתבו פעולה `public int sortStore()`
(ב-C#: `public int SortStore()`)
הפעולה מסדרת את מערך המוצרים כך שבתחילת המערך יהיו מחשבי לוח בעלי מערכת הפעלה ווינדוס, אחר כך מכשירים בעלי מערכת הפעלה אנדרואיד ולבסוף מכשירים עם מערכת הפעלה iOS. הפעולה תחזיר את מספר המקומות הפנויים במחסן.
◂ פתרון מלא לשאלה 1
סעיף א
פעולה במחלקה Tablet שמחזירה את התנאי: השמות שווים (equals), הדגמים שווים והגדלים שווים.
הרעיון: הפעולה נכתבת בתוך המחלקה Tablet, ולכן מותר לה לגשת ישירות לתכונות הפרטיות גם של העצם other (הוא מאותה מחלקה).
1. את השם ואת הדגם (מחרוזות) משווים לפי התוכן: ב-Java בעזרת `equals` (האופרטור `==` היה משווה הפניות), וב-C# האופרטור `==` על string משווה תוכן.
2. את הגודל (double) משווים בעזרת `==`.
3. מחזירים את הגימום (וגם) של שלושת התנאים. מערכת ההפעלה והמחיר אינם משתתפים בהשוואה, כפי שנדרש.
public boolean isSame(Tablet other)
{
return this.name.equals(other.name)
&& this.kind.equals(other.kind)
&& this.size == other.size;
}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.
סיבוכיות: מעבר אחד על המוצרים, .
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;
}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 מוצרים, כלומר .
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;
}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 והפעולה תחזיר .
תשובה: המערך מסודר מחדש: קודם כל מחשבי ווינדוס, אחריהם אנדרואיד ובסוף 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 האיברים מבצעים ספירה של , ולכן בסך הכול .
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;
}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 עבור ספרים
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;}
}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 – מערך הפריטים למסירה.
כתבו את כותרת המחלקה ואת התכונות שלה. ציינו מהו סוג המערך שנבחר והסבירו את בחירתכם.
כתבו פעולה פנימית `public double sum()` המחזירה את הסכום הכולל של הפריטים במשלוח.
(ב-C#: `public double Sum()`)
הערה: אין להוסיף מחלקות או פעולות, אין לשנות את יחסי הירושה בין המחלקות.
◂ פתרון מלא לשאלה 3
סעיף א
המערך arr מוגדר מסוג Object[] (ב-C#: object[]), כי Clothes (ותתי-המחלקות שלה) ו-Book אינן חולקות מחלקת-על משותפת מלבד Object.
בחירת סוג המערך: המשלוח צריך להכיל גם בגדים (עצמים מסוג Clothes, Shirt, Dress) וגם ספרים (Book). Shirt ו-Dress יורשות מ-Clothes, ולכן מערך מסוג Clothes היה יכול להכיל את כל הבגדים - אבל לא ספרים, כי Book אינה יורשת מ-Clothes. מערך מסוג Book לא יכיל בגדים.
המחלקה המשותפת היחידה לכל המחלקות היא Object (כל מחלקה יורשת ממנה במישרין או בעקיפין), ואסור לנו להוסיף מחלקות או לשנות את יחסי הירושה. לכן המערך יהיה מסוג Object, וכל פריט - בגד או ספר - יכול להיות מוצב בו (המרה כלפי מעלה).
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; // 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(). בספר הפעולה מחזירה כבר את המחיר אחרי הנחה (), ואנחנו פשוט משתמשים בה.
5. תא ריק (null) אינו עובר אף אחת מהבדיקות (instanceof על null מחזיר false), ולכן אין צורך בבדיקה נפרדת.
6. מחזירים את total.
לדוגמה, משלוח עם חולצה במחיר 100, שמלה במחיר 200 וספר שמחירו 50 ייתן .
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;
}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:
public class A{
}
public class B extends A{
public B(){
System.out.println("B constructor");
}
}public class A{
}
public class B : A{
public B(){
Console.WriteLine("B constructor");
}
}לפניכם ארבעה היגדים. קבעו לגבי כל אחד מהם אם הוא נכון או אינו נכון ונמקו את קביעתכם.
הבנאי של B יקרא לבנאי הריק של A (בנאי ללא פרמטרים, בנאי ברירת מחדל, default constructor)
הבנאי הריק של Object לא ייקרא כי ל- A אין זימון מפורש של בנאי זה
הבנאי הריק של Object ייקרא לאחר הדפסת המחרוזת "B constructor"
הבנאי הריק של B יקרא לבנאי הריק של A ואז תודפס המחרוזת
נתונות שלוש מחלקות B, A ו- C, כאשר מחלקה B יורשת מהמחלקה A והמחלקה C יורשת מהמחלקה B.
כמו כן נתון שלמחלקה A מוגדרת התכונה value.
לפניכם ארבעה היגדים. קבעו לגבי כל אחד מהם אם הוא נכון או אינו נכון ונמקו את קביעתכם.
מתוך המחלקה C אין גישה לתכונה value של המחלקה A אפילו ש- value מוגדרות כ- protected מכיוון שמדובר בשתי רמות של ירושה.
מתוך המחלקה C יש גישה לתכונה value רק בתנאי שהתכונה value במחלקה A מוגדרת כ- protected.
מתוך המחלקה C יש גישה לתכונה value של המחלקה A באמצעות הפקודה super.super.value.
מתוך המחלקה C יש גישה לתכונה value מכיוון שהמחלקה C יורשת בעקיפין מהמחלקה A, בלי קשר להרשאת הגישה של התכונה.
נתונה הפקודה הבאה העוברת שלב קומפילציה (הידור):
((A)b).myFun();(ב-C#: `((A)b).MyFun();`)
כאשר b הוא מצביע מסוג המחלקה B.
לפניכם ארבעה היגדים. קבעו לגבי כל אחד מהם אם הוא נכון או אינו נכון ונמקו את קביעתכם.
הפעולה myFun מוגדרת במחלקה A.
B היא מחלקה היורשת את המחלקה A.
A היא מחלקה היורשת את המחלקה B.
הפעולה myFun מוגדרת גם במחלקה A וגם במחלקה B.
◂ פתרון מלא לשאלה 4
סעיף א
נכון.
בנאי של מחלקה יורשת תמיד מתחיל בזימון בנאי של מחלקת-העל. כשהבנאי של B אינו כותב זימון מפורש (`super(...)` ב-Java או `: base(...)` ב-C#), המהדר מוסיף זימון לבנאי הריק `super()`. ל-A לא נכתב שום בנאי, ולכן המהדר יצר לה בנאי ברירת מחדל ללא פרמטרים - ואותו מזמן הבנאי של B.
תשובה: נכון.
לא נכון - הבנאי של Object נקרא.
A יורשת במובלע מ-Object. גם בבנאי ברירת המחדל של A המהדר מוסיף זימון מובלע `super()` לבנאי של Object. אין צורך בזימון מפורש: כל יצירת עצם מפעילה את שרשרת הבנאים עד Object.
תשובה: לא נכון. הבנאי הריק של Object ייקרא (במובלע, מתוך הבנאי של A).
לא נכון - הוא נקרא ומסתיים לפני ההדפסה.
הזימון של בנאי מחלקת-העל הוא הפעולה הראשונה בבנאי. סדר הביצוע ב-`new B()`:
1. B() מזמן את A() לפני גוף הבנאי שלו.
2. A() מזמן את Object() לפני גוף הבנאי שלו.
3. Object() מתבצע ומסתיים, אחריו גוף A() (ריק), ורק אז גוף B() - שמדפיס "B constructor".
תשובה: לא נכון. הבנאי של Object מתבצע לפני הדפסת המחרוזת.
נכון.
כמו שהוסבר בהיגד 1 ובהיגד 3: הבנאי של B מזמן קודם את הבנאי הריק של A (שבתורו מזמן את Object), ורק אחרי שהזימון מסתיים מתבצעת שורת ההדפסה שבגוף הבנאי של B. הפלט של `new B()` הוא `B constructor`.
תשובה: נכון.
סעיף ב
לא נכון.
הרשאת protected פותחת את הגישה לכל המחלקות היורשות, בכל עומק של ירושה. C יורשת מ-B שיורשת מ-A, ולכן C היא צאצא של A ויכולה לגשת ל-value המוגדרת protected. מספר רמות הירושה אינו משנה.
תשובה: לא נכון.
לא נכון - גם אם value מוגדרת public יש גישה.
protected מספיק כדי לאפשר גישה מ-C, אבל הוא לא התנאי היחיד. אם value מוגדרת public, אפשר לגשת אליה מכל מחלקה, ובפרט מ-C. ב-Java יש גישה גם כש-value מוגדרת בלי מציין גישה (package), אם המחלקות באותה חבילה. רק כש-value מוגדרת private אין גישה ישירה מ-C. לכן המילה "רק" הופכת את ההיגד לשגוי.
תשובה: לא נכון.
לא נכון - הביטוי super.super אינו חוקי.
המילה super (ב-C#: base) מתייחסת רק למחלקת-העל הישירה, ואי אפשר לשרשר אותה: `super.super.value` היא שגיאת קומפילציה. אם יש גישה ל-value (למשל protected או public), פונים אליה פשוט כ-`value`, `this.value` או `super.value` - התכונה עוברת בירושה דרך B אל C.
תשובה: לא נכון.
לא נכון - אם value היא private אין גישה.
הרשאת הגישה קובעת. אם value מוגדרת private, היא נגישה רק בתוך המחלקה A עצמה. אף מחלקה יורשת - B או C - אינה יכולה לפנות אליה ישירות, גם אם העצם מסוג C מכיל אותה בזיכרון. במקרה כזה הגישה אפשרית רק דרך פעולות get/set ציבוריות של A.
תשובה: לא נכון.
סעיף ג
נכון.
בשלב הקומפילציה המהדר בודק את הזימון לפי הטיפוס הסטטי של הביטוי. אחרי ההמרה הטיפוס הוא A, ולכן הקוד עובר קומפילציה רק אם למחלקה A יש פעולה myFun - מוגדרת בה או עוברת אליה בירושה ממחלקת-על שלה. בכל מקרה הפעולה שייכת לממשק של A.
תשובה: נכון.
לא נכון (לא בהכרח).
ההמרה `(A)b` עוברת קומפילציה כש-A ו-B נמצאות על אותו קו ירושה, לא משנה באיזה כיוון:
•אם B יורשת מ-A - זו המרה כלפי מעלה (תמיד בטוחה).
•אם A יורשת מ-B - זו המרה כלפי מטה. היא עוברת קומפילציה, והתוצאה נבדקת רק בזמן ריצה.
רק המרה בין מחלקות שאין ביניהן קשר ירושה נכשלת בקומפילציה. לכן מכך שהפקודה עברה קומפילציה אי אפשר להסיק ש-B יורשת מ-A.
תשובה: לא נכון - לא בהכרח; ייתכן גם ש-A יורשת מ-B.
לא נכון (לא בהכרח).
מאותה סיבה כמו בהיגד 2: הקומפילציה מבטיחה רק שקיים קשר ירושה בין A ל-B, באחד משני הכיוונים. ייתכן ש-A יורשת מ-B (ואז ההמרה היא כלפי מטה), אבל ייתכן באותה מידה ש-B יורשת מ-A.
תשובה: לא נכון - לא בהכרח.
לא נכון (לא בהכרח).
כדי שהפקודה תעבור קומפילציה מספיק ש-myFun קיימת ב-A (היגד 1). אין דרישה שהיא תוגדר מחדש (תידרס) ב-B. אם B יורשת מ-A, היא יכולה לרשת את myFun בלי להגדיר אותה בעצמה.
תשובה: לא נכון - לא בהכרח.
שאלה 5 · מעקב: דריסת פעולות, super וקישור דינמי
נתונות שתי המחלקות הבאות:
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();
}
}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();
}
}נתון קטע הקוד הבא:
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();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();עקבו אחרי ביצוע קטע הקוד ורשמו מה יהיה הפלט.
האם אפשר להוסיף לקטע הקוד את שתי הפקודות הבאות?
a.superG();
((B)a).superG();(ב-C#: `a.SuperG();` ו-`((B)a).SuperG();`)
הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 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).
ההמרה `(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
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));
}
}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? הסבירו את תשובתכם.
נתונה המחלקה Program הבאה:
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);
*******
}
}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 שלעיל, לאחר ההצהרות על האובייקטים (במקום שמסומן בכוכביות *).
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));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));אם הוספתם פקודת קוד גורמת לשגיאה יש להסביר מהי השגיאה (שגיאת קומפילציה או שגיאת זמן ריצה).
◂ פתרון מלא לשאלה 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.
ב-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:
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;}
}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.
כאשר המעבד צריך להקצות זיכרון בגודל מסוים (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.
(שני המצבים, לפני הזימון ואחריו, מוצגים באיורים לסעיף ב.)
◂ פתרון מלא לשאלה 7
סעיף א
סורקים את השרשרת, סוכמים את גודל כל המקטעים ואת גודל המקטעים הפנויים, ומחזירים true אם free*10 < total.
הרעיון: "מצב מסוכן" פירושו שהזיכרון הפנוי קטן מ-10% מהזיכרון הכללי, כלומר , או בלי שברים: .
1. מאפסים שני צוברים: total (כל הזיכרון) ו-free (הזיכרון הפנוי).
2. עוברים על השרשרת מהחוליה start עד null. בכל חוליה מוסיפים את גודל המקטע ל-total, ואם המקטע פנוי (isFree) מוסיפים אותו גם ל-free.
3. מחזירים את תוצאת ההשוואה `free * 10 < total`. ההשוואה במספרים שלמים נמנעת משגיאות עיגול.
בדוגמה שבאיור: ו-. מתקיים , ולכן הזיכרון אינו במצב מסוכן והפעולה מחזירה false.
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;
}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% פנוי) ו-false אחרת.
סעיף ב
אם isDangerous() מחזירים false. אחרת סורקים עד המקטע הפנוי הראשון שגודלו לפחות num; הופכים אותו לתפוס בגודל num, ואם נשארה יתרה מוסיפים אחריו חוליה חדשה פנויה בגודל היתרה; מחזירים true. אם לא נמצא - false.
1. אם הזיכרון במצב מסוכן (הפעולה מסעיף א) - לא עושים דבר ומחזירים false.
2. סורקים את השרשרת מ-start. מחפשים את החוליה הראשונה שהמקטע שלה פנוי וגודלו לפחות num.
3. כשנמצאה חוליה כזו (בגודל size), מפצלים אותה לשניים:
•החוליה עצמה הופכת למקטע תפוס בגודל num: `setFree(false)` ו-`setSize(num)`.
•היתרה נשארת פנויה. אם , יוצרים חוליה חדשה עם `new Data(rest)` (הבנאי יוצר מקטע פנוי) ומשרשרים אותה מיד אחרי החוליה הנוכחית: הבא שלה הוא הבא הקודם של החוליה הנוכחית. אם , המקטע נתפס כולו ואין צורך בחוליה חדשה.
•מחזירים true.
4. אם הסריקה הגיעה לסוף השרשרת בלי למצוא מקטע מתאים - מחזירים false.
הכלל "אין שני מקטעים פנויים סמוכים" נשמר. המקטע שאחרי החוליה שפוצלה היה תפוס (כי המקטע המקורי היה פנוי), ולכן החוליה הפנויה החדשה גובלת מצד אחד במקטע התפוס החדש ומצד שני במקטע תפוס.
בדיקה מול הדוגמה, firstFit(142): הזיכרון אינו מסוכן (סעיף א). המקטע 137 פנוי אבל ; המקטע 97 תפוס; המקטע 342 פנוי ו-. הוא הופך ל"תפוס 142", ואחריו נוספת חוליה "פנוי ". מתקבל 137 פנוי, 97 תפוס, 142 תפוס, 200 פנוי, והפעולה מחזירה true, כמו בדוגמה.
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;
}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;
}סיבוכיות: , כאשר n הוא מספר החוליות (גם סעיף א וגם החיפוש הם מעבר אחד על השרשרת).
תשובה: firstFit מחזירה false במצב מסוכן או כשאין מקטע פנוי מספיק גדול. אחרת היא הופכת את המקטע הפנוי הראשון שגודלו לפחות num למקטע תפוס בגודל num, מוסיפה אחריו חוליה פנויה בגודל היתרה (אם היתרה חיובית) ומחזירה true.
שאלה 8 · רשימת מספרים: השוואת רישא והכלה
נתונה מחלקה IntList הבאה:
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;
}
}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:
IntList testList = new IntList();
testList.add(2); testList.add(3); testList.add(6);
testList.add(1); testList.add(4);
System.out.println(testList);IntList testList = new IntList();
testList.Add(2); testList.Add(3); testList.Add(6);
testList.Add(1); testList.Add(4);
Console.WriteLine(testList);מהו הפלט של קטע הקוד (אין צורך במעקב מפורט)?
בעבור עצם שנוצר בסעיף א' הביאו דוגמה של עצם אחר מטיפוס IntList בשם list הכולל ארבעה איברים לפחות, כך ש:
זימון testList.what1(list) יחזיר true והזימון testList.what2 (list) יחזיר true
אם אי אפשר להביא דוגמה כזו, ציינו זאת והסבירו מדוע.
זימון testList.what1(list) יחזיר true והזימון testList.what2 (list) יחזיר false
אם אי אפשר להביא דוגמה כזו, ציינו זאת והסבירו מדוע.
זימון testList.what1(list) יחזיר false והזימון testList.what2 (list) יחזיר true
אם אי אפשר להביא דוגמה כזו, ציינו זאת והסבירו מדוע.
זימון testList.what1(list) יחזיר false והזימון testList.what2 (list) יחזיר false
אם אי אפשר להביא דוגמה כזו, ציינו זאת והסבירו מדוע.
מה מבצעות הפעולות what1 ו- what2 באופן כללי?
◂ פתרון מלא לשאלה 8
סעיף א
{4,1,6,3,2}
הפעולה add יוצרת חוליה חדשה בראש הרשימה (`head = new Node(a, head)`), ולכן כל מספר חדש נכנס לפני כל הקודמים, והרשימה מתקבלת בסדר הפוך לסדר ההוספה:
toString מתחילה ב-"{", מוסיפה כל ערך ואחריו פסיק עד החוליה האחרונה, ואת הערך האחרון מוסיפה עם "}".
תשובה: הפלט הוא `{4,1,6,3,2}`.
סעיף ב
אפשר: 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).
אפשר: 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).
אפשר: list = {2,3,6,1,4} (נבנה ב-add(4), add(1), add(6), add(3), add(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).
אפשר: list = {7,8,9,10} (נבנה ב-add(10), add(9), add(8), add(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 באופן המתאים ביותר לעקרונות של תכנות מונחה עצמים.
לכל אחת מהמחלקות Employee, Nurse, Doctor, Supervisor כתבו:
•כותרת המחלקה.
•תכונות.
•פעולה בונה – הפעולה הבונה של כל מחלקה מקבלת את כל הפרמטרים הנדרשים.
יש לשים לב שמספר העובד הוא מספר ייחודי, שנוצר באופן אוטומטי, ואין להעבירו כפרמטר לפעולה בונה!
המחלקה AllEmployees מיועדת לנהל את כל העובדים בבית החולים. תכונות המחלקה:
•arr - מערך של כל אנשי הצוות. בבית חולים יכולים לעבוד לא יותר מ- 200 אנשי צוות.
•current - מספר אנשי הצוות בפועל, מטיפוס שלם, int.
כתבו את כותרת המחלקה ואת התכונות של המחלקה AllEmployees והוסיפו את הפעולות הפנימיות הבאות:
•פעולה בשם numSupervisor המחזירה את מספר ראשי כל הצוותים.
•פעולה בשם getNewNurse המקבלת את סוג האחות ומחזירה את האחות מהסוג הנדרש שהצטרפה אחרונה למאגר העובדים (מספר העובד שלה מקסימלי). אם אין אחות מהסוג הנדרש, הפעולה תחזיר null.
(ב-C#: NumSupervisor ו-GetNewNurse.)
הערה: הניחו שהפעולות get ו- set מוגדרות בעבור כל תכונה בכל אחת מהמחלקות.
◂ פתרון מלא לשאלה 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.
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;
}
}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`).
1. משתנה newest מאותחל ל-null (עדיין לא נמצאה אחות מתאימה).
2. עוברים על העובדים. אם העובד הוא אחות (instanceof Nurse), ממירים אותו ל-Nurse. ההמרה הכרחית, כי לטיפוס Employee אין פעולה getType.
3. אם סוג האחות שווה לסוג המבוקש (השוואת מחרוזות ב-equals) ומספר העובד שלה גדול ממספר העובד של newest (או ש-newest עדיין null), מעדכנים את newest.
4. מחזירים את newest. אם לא נמצאה אף אחות מהסוג הנדרש, מוחזר null.
מספר העובד גדל עם כל הצטרפות, ולכן האחות עם המספר המקסימלי היא זו שהצטרפה אחרונה.
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 ואת התכונות שלהן.
הערה: יש לבחור מבנה נתונים מתאים לשמירת אוסף נתונים לא מוגבל (תור, מחסנית, שרשרת חוליות).
ממשו במחלקה Student את הפעולה `int getCode()`.
(ב-C#: `int GetCode()`)
הפעולה מחזירה מספר המורכב משתי ספרות האמצעיות של מספר סטודנט (studentID).
__לדוגמה__: עבור המספר 12345678 הפעולה תחזיר 45.
לפניכם חלק מהפעולות במחלקה GradesFile. אין צורך לממש את הפעולות!
(ב-C#: GetStudent, IsEmpty, ListIsGood, ו-bool במקום boolean.)
ממשו את הפעולה `void moveStudent(int k, int j)`.
(ב-C#: `void MoveStudent(int k, int j)`)
במהלך הכנסת הנתונים למערכת קרתה תקלה, ובעקבות כך חל בלבול ולא כל הסטודנטים הוכנסו למקומות המתאימים לפי מספר הסטודנט שלהם.
כתבו __פעולה חיצונית__ המקבלת את מאגר המידע (הפניה לעצם מסוג GradesFile) ומעדכנת אותו כך שבכל תא במערך יהיה אוסף סטודנטים בעלי מספרי סטודנט המתאימים למספר התא במערך (על פי שיטת האחסון שתוארה בתחילה).
בפתרון של סעיף ד' יש להשתמש בפעולות הנתונות של המחלקות Student ו-GradesFile בלבד!
אין להשתמש בפעולות של מבנים אחרים ואין להניח על קיומן של הפעולות האחרות במחלקות Student ו- GradesFile.
◂ פתרון מלא לשאלה 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.
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>();
}
}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 ספרות , הספרות האמצעיות הן - הרביעית והחמישית משמאל.
1. חלוקה בשלמים ב-1000 מסירה את שלוש הספרות הימניות: .
2. שארית החלוקה ב-100 משאירה את שתי הספרות הימניות של התוצאה: .
public int getCode()
{
return (studentId / 1000) % 100;
}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 בודקים בנפרד: . אם אחד התנאים מתקיים - יוצאים בלי לעשות דבר.
2. העברה: מוציאים את הסטודנט מראש התור k (remove) ומכניסים אותו לסוף התור j (insert).
אם , הסטודנט עובר מראש התור לסופו של אותו תור (סיבוב). זה יהיה שימושי בסעיף ד.
public void moveStudent(int k, int j)
{
if (j < 0 || j >= arr.length || isEmpty(k))
return;
arr[j].insert(arr[k].remove());
}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)`:
•אם - הסטודנט נמצא במקום שגוי, והוא עובר לסוף האוסף הנכון שלו. מספר הסטודנטים השגויים באוסף k קטן ב-1.
•אם - הסטודנט במקום הנכון, וההעברה מעבירה אותו מראש האוסף לסופו (סיבוב). כך הסטודנט הבא מגיע לראש האוסף.
3. כשהאוסף k נעשה תקין (או ריק), עוברים ל-k הבא.
•סיום: כל עוד האוסף אינו תקין יש בו לפחות סטודנט שגוי אחד. סיבובים של סטודנטים תקינים מביאים אותו לראש האוסף אחרי לכל היותר (גודל האוסף) צעדים, ואז הוא מוצא מהאוסף. מספר הסטודנטים השגויים יורד עד 0, והלולאה מסתיימת.
•אוספים שכבר טופלו נשארים תקינים: אל אוסף c נכנסים רק סטודנטים שהקוד שלהם c, כלומר רק סטודנטים במקום הנכון. לכן גם אוסף שכבר תוקן לא מתקלקל, ואוסף פשוט יקבל סטודנט תקין שיישאר בו.
•אף סטודנט לא הולך לאיבוד: moveStudent רק מעבירה סטודנטים בין אוספים.
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
}
}
}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
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 Driverpublic 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):
מהו הפלט של הפעולה main?
(ב-C#: Main)
◂ פתרון מלא לשאלה 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: 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 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 (כל אחד בשורה נפרדת).