מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2024 מועד ב'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2024 מועד ב', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 12)
בכל מבחן עשר שאלות.
שאלות 1-5: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 6-10: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 11-12: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית מסודרת לפי זוגיות
מחסנית של מספרים שלמים וחיוביים נקראת "מסודרת לפי זוגיות" אם כל הערכים הזוגיים נמצאים בתחילת המחסנית, ואחריהם – כל הערכים האי-זוגיים. כתבו פעולה המקבלת מחסנית של מספרים שלמים ובודקת אם היא "מסודרת לפי זוגיות". כותרת הפעולה:
public static boolean isOrdered(Stack<Integer> st)public static bool IsOrdered(Stack<int> st)מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
מעבר על המחסנית עם דגל "נמצא אי-זוגי"; זוגי שמופיע אחרי אי-זוגי – false, אחרת true (המחסנית משוחזרת).
נתון: מחסנית `st` של מספרים שלמים וחיוביים. "תחילת המחסנית" היא הראש שלה (הערך שיוצא ראשון).
מבוקש: להחזיר true אם כל הזוגיים נמצאים מעל (לפני) כל האי-זוגיים.
הרעיון: מוציאים את האיברים מהראש כלפי מטה. כל עוד רואים זוגיים – הכול תקין. מהרגע שנראה המספר האי-זוגי הראשון, אסור שיופיע אחריו אף מספר זוגי. לכן מספיק דגל אחד `oddSeen` ("כבר ראינו אי-זוגי"):
1. מוציאים איבר `x` מהמחסנית ודוחפים אותו למחסנית עזר `temp` (כדי שנוכל לשחזר את המחסנית המקורית בסוף).
2. אם `x` אי-זוגי – מדליקים את `oddSeen`.
3. אם `x` זוגי ו-`oddSeen` כבר דלוק – מצאנו זוגי שנמצא אחרי אי-זוגי, והמחסנית אינה "מסודרת לפי זוגיות" (`ordered = false`).
4. בסוף מחזירים את כל האיברים מ-`temp` ל-`st` (הסדר חוזר להיות המקורי), ומחזירים את `ordered`.
מחסנית ריקה, מחסנית של זוגיים בלבד ומחסנית של אי-זוגיים בלבד – כולן מסודרות (התשובה true). למשל, עבור מחסנית שבראשה התשובה true, ועבור התשובה false (4 זוגי ונמצא אחרי 1).
public static boolean isOrdered(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
boolean ordered = true;
boolean oddSeen = false; // האם כבר נמצא מספר אי-זוגי
while (!st.isEmpty())
{
int x = st.pop();
temp.push(x);
if (x % 2 != 0)
oddSeen = true;
else if (oddSeen) // זוגי אחרי אי-זוגי
ordered = false;
}
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return ordered;
}public static bool IsOrdered(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
bool ordered = true;
bool oddSeen = false; // האם כבר נמצא מספר אי-זוגי
while (!st.IsEmpty())
{
int x = st.Pop();
temp.Push(x);
if (x % 2 != 0)
oddSeen = true;
else if (oddSeen) // זוגי אחרי אי-זוגי
ordered = false;
}
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return ordered;
}תשובה: מעבר אחד על המחסנית עם דגל "כבר ראינו אי-זוגי"; אם אחריו מופיע זוגי – מחזירים false, אחרת true. המחסנית משוחזרת בסוף.
סעיף ב
נסמן ב- את מספר האיברים במחסנית.
1. הלולאה הראשונה מוציאה כל איבר פעם אחת ודוחפת אותו ל-`temp` – סיבובים, ובכל סיבוב מספר קבוע של פעולות (pop, push, בדיקת זוגיות).
2. הלולאה השנייה מחזירה את האיברים – עוד סיבובים של .
3. סך הכול סיבובים, כלומר .
תשובה: – כל איבר מוצא ומוחזר פעם אחת בלבד.
שאלה 2 · מחיקת האיבר או האיברים האמצעיים בתור
כתבו פעולה המקבלת תור של מספרים שלמים וחיוביים. אם אורך התור אי-זוגי, הפעולה תמחק את האיבר האמצעי, ולא היא תמחק את שני האיברים האמצעיים. כל שאר איברי התור יישארו ללא שינוי.
לדוגמה:
עבור התור q הבא (איור א' לשאלה 2), התור q אחרי זימון הפעולה מוצג באיור ב' לשאלה 2.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
סופרים את האיברים בעזרת תור עזר ומחזירים אותם לתור בלי המקום (ובאורך זוגי גם בלי ); בדוגמה: .
נתון: תור `q` של מספרים שלמים וחיוביים.
מבוקש: למחוק את האיבר האמצעי (אורך אי-זוגי) או את שני האיברים האמצעיים (אורך זוגי), ושאר האיברים יישארו באותו סדר.
הרעיון: בתור אין גישה לפי מיקום, ולכן קודם צריך לדעת את האורך , ואז לעבור שוב ולדלג על האמצעיים.
1. מעבירים את כל האיברים מ-`q` לתור עזר `temp` וסופרים אותם – מקבלים .
2. ממספרים את האיברים מ-0 עד . האיבר האמצעי באורך אי-זוגי הוא במקום (חילוק שלמים). באורך זוגי שני האמצעיים הם במקומות ו-.
3. מעבירים את האיברים חזרה מ-`temp` ל-`q`, ומכניסים כל איבר חוץ מהאמצעיים. הסדר נשמר כי תור הוא FIFO.
בדיקה עם הדוגמה: (זוגי), ולכן נמחקים המקומות ו-, כלומר האיברים 2 ו-3 (המסומנים באפור). התור שמתקבל: .
(באיור התור שאחרי זימון הפעולה מופיעים רק – האיבר 4 שבסוף התור נשמט מהשרטוט; לפי ההגדרה "כל שאר איברי התור יישארו ללא שינוי" הוא נשאר בתור.)
עבור , למשל : נמחק המקום , כלומר 3, ומתקבל .
public static void removeMiddle(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int n = 0;
while (!q.isEmpty()) // העברה לתור עזר וספירה
{
temp.insert(q.remove());
n++;
}
int i = 0; // מיקום האיבר הנוכחי (מ-0)
while (!temp.isEmpty())
{
int x = temp.remove();
boolean middle = (i == n / 2) || (n % 2 == 0 && i == n / 2 - 1);
if (!middle)
q.insert(x);
i++;
}
}public static void RemoveMiddle(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int n = 0;
while (!q.IsEmpty()) // העברה לתור עזר וספירה
{
temp.Insert(q.Remove());
n++;
}
int i = 0; // מיקום האיבר הנוכחי (מ-0)
while (!temp.IsEmpty())
{
int x = temp.Remove();
bool middle = (i == n / 2) || (n % 2 == 0 && i == n / 2 - 1);
if (!middle)
q.Insert(x);
i++;
}
}תשובה: סופרים את האיברים בעזרת תור עזר, ובהחזרה לתור מדלגים על המקום (ובאורך זוגי גם על ). עבור הדוגמה מתקבל התור .
סעיף ב
נסמן ב- את מספר האיברים בתור.
1. הלולאה הראשונה מעבירה את האיברים לתור העזר – פעולות remove/insert של .
2. הלולאה השנייה מחזירה את האיברים (חוץ מאחד או שניים) – עוד סיבובים של .
3. סך הכול פעולות, כלומר .
תשובה: – שני מעברים על התור.
שאלה 3 · שרשרת פלא: אורך, קצוות ומינימום באמצע

שרשרת חוליות של מספרים שלמים נקראת "שרשרת פלא" אם היא עונה על שלושת התנאים הבאים:
•מספר החוליות בשרשרת אי-זוגי.
•הערך הראשון בשרשרת שווה לערך האחרון.
•הערך המינימלי בשרשרת נמצא בחוליה האמצעית.
כתבו פעולה המקבלת הפניה chain לחוליה הראשונה של שרשרת חוליות של מספרים שלמים.
הפעולה תבדוק אם השרשרת היא שרשרת פלא. אם כן – הפעולה תחזיר ערך true, ולא – ערך false.
כותרת הפעולה:
public static boolean isMiracle(Node<Integer> chain)public static bool IsMiracle(Node<int> chain)לדוגמה: עבור שרשרת הבאה (איור לשאלה 3) הפעולה תחזיר ערך true.
מהי סיבוכיות הפעולה isMiracle שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
מעבר אחד: מספר חוליות, מינימום וערך אחרון; true אם אי-זוגי, ראשון = אחרון וערך החוליה האמצעית = המינימום.
נתון: הפניה `chain` לחוליה הראשונה של שרשרת מספרים שלמים.
מבוקש: לבדוק שלושה תנאים: מספר החוליות אי-זוגי, הערך הראשון שווה לאחרון, והערך המינימלי נמצא בחוליה האמצעית.
הרעיון: מעבר אחד על השרשרת אוסף את כל מה שצריך – מספר החוליות , הערך המינימלי והערך האחרון. אחר כך בודקים את התנאים, ורק אם הם מתקיימים מתקדמים צעדים אל החוליה האמצעית.
1. מעבר על השרשרת: סופרים חוליות ב-`n`, מעדכנים `min`, ושומרים את ערך החוליה הנוכחית ב-`lastValue` (בסוף המעבר זה ערך החוליה האחרונה).
2. אם זוגי – התנאי הראשון לא מתקיים, מחזירים false.
3. אם הערך הראשון שונה מ-`lastValue` – מחזירים false.
4. מתקדמים חוליות מההתחלה (חילוק שלמים). עבור אי-זוגי זו בדיוק החוליה האמצעית (למשל עבור מתקדמים 3 צעדים לחוליה הרביעית). מחזירים האם ערכה שווה ל-`min`.
שרשרת ריקה (`null`) אינה שרשרת פלא – יש בה 0 חוליות, מספר זוגי.
בדיקה עם הדוגמה: : אי-זוגי, הראשון והאחרון 10, המינימום , והחוליה האמצעית (אחרי 3 צעדים) היא – הפעולה מחזירה true.
public static boolean isMiracle(Node<Integer> chain)
{
if (chain == null)
return false;
int n = 0;
int min = chain.getValue();
int lastValue = 0;
Node<Integer> p = chain;
while (p != null) // מעבר אחד: ספירה, מינימום, ערך אחרון
{
n++;
if (p.getValue() < min)
min = p.getValue();
lastValue = p.getValue();
p = p.getNext();
}
if (n % 2 == 0) // מספר חוליות זוגי
return false;
if (chain.getValue() != lastValue) // ראשון שונה מאחרון
return false;
Node<Integer> mid = chain;
for (int i = 0; i < n / 2; i++) // התקדמות לחוליה האמצעית
mid = mid.getNext();
return mid.getValue() == min;
}public static bool IsMiracle(Node<int> chain)
{
if (chain == null)
return false;
int n = 0;
int min = chain.GetValue();
int lastValue = 0;
Node<int> p = chain;
while (p != null) // מעבר אחד: ספירה, מינימום, ערך אחרון
{
n++;
if (p.GetValue() < min)
min = p.GetValue();
lastValue = p.GetValue();
p = p.GetNext();
}
if (n % 2 == 0) // מספר חוליות זוגי
return false;
if (chain.GetValue() != lastValue) // ראשון שונה מאחרון
return false;
Node<int> mid = chain;
for (int i = 0; i < n / 2; i++) // התקדמות לחוליה האמצעית
mid = mid.GetNext();
return mid.GetValue() == min;
}תשובה: מעבר אחד מחשב את מספר החוליות, המינימום והערך האחרון; מחזירים true רק אם אי-זוגי, הראשון שווה לאחרון וערך החוליה במקום שווה למינימום.
סעיף ב
נסמן ב- את מספר החוליות בשרשרת.
1. לולאת ה-while עוברת על כל החוליות, ובכל חוליה מספר קבוע של פעולות – .
2. הבדיקות של זוגיות ושל הראשון מול האחרון – .
3. לולאת ה-for מתקדמת צעדים – .
4. סך הכול צעדים, כלומר .
תשובה: – מעבר אחד מלא וחצי מעבר נוסף על השרשרת.
שאלה 4 · ירושה, המרות טיפוסים ושטח מקסימלי

נתון עץ הירושה הבא (איור לשאלה 4).
לפניכם קטע קוד מתוך הפעולה הראשית:
Shape s1 = new Shape();
Shape s2 = new Square();
Shape s3 = new Rectangle();
Square sq = new Rectangle();לפניכם שמונה קטעי קוד. עבור כל אחד מהסעיפים יש לציין, אם הקוד תקין או לא. אם הקוד אינו תקין – יש להסביר למה הוא אינו תקין ולציין את סוג השגיאה (שגיאת קומפילציה/הידור או שגיאת זמן ריצה).
1. Square sq1 = new Shape();
2. Square sq2 = s1;
3. Square sq3 = (Square)s2;
4. Square sq4 = (Square)s3;
5. Square sq5 = (Square) s1;
6.
Triangle t = new Triangle();
Shape s6 = t;
Square sq6 = (Square)s6;
7. Shape s7 = (Square)(new Rectangle());
8. Square sq8 = (Shape)(new Rectangle());רוצים לכתוב פעולה אשר מקבלת מערך של צורות (מערך הפניות לעצמים מטיפוס Shape) ומחזירה את סכום השטחים של כל המשולשים (Triangle) והמלבנים (Rectangle).
באיזו מחלקה או מחלקות יש להוסיף את הפעולה `double area()` (ב-C#: `double Area()`) המחשבת ומחזירה שטח?
כתבו פעולה המקבלת מערך צורות ומחזירה את המשולש ששטחו הוא הגדול ביותר. אם במערך אין אף משולש, הפעולה תחזיר null.
כותרת הפעולה:
public static Triangle maxArea(Shape[] arr)public static Triangle MaxArea(Shape[] arr)◂ פתרון מלא לשאלה 4
סעיף א
תקינים: 3, 4, 7; שגיאת הידור: 1, 2, 8; שגיאת זמן ריצה: 5, 6.
•השמה בלי המרה מותרת רק מטיפוס בן (או אותו טיפוס) אל טיפוס אב ("כל Rectangle הוא Square"). השמה מאב אל בן בלי המרה מפורשת היא שגיאת הידור.
•המרה מפורשת (casting) מאב אל בן עוברת הידור, אבל בזמן ריצה נבדק הטיפוס האמיתי של העצם: אם העצם אינו מהטיפוס שאליו ממירים (או מצאצא שלו) – שגיאת זמן ריצה (ב-Java `ClassCastException`, ב-C# `InvalidCastException`).
•לפי עץ הירושה: Square ו-Triangle ו-Circle יורשות מ-Shape, Rectangle יורשת מ-Square, Ellipse יורשת מ-Circle. העצמים: `s1` הוא Shape, `s2` הוא Square, `s3` הוא Rectangle (כולם בהפניה מטיפוס Shape).
תשובה: תקינים: 3, 4, 7. שגיאת הידור: 1, 2, 8. שגיאת זמן ריצה: 5, 6.
סעיף ב
במחלקות Triangle ו-Rectangle (כל אחת לפי התכונות שלה).
נתון: הפעולה מקבלת מערך הפניות מטיפוס Shape וסוכמת רק את שטחי המשולשים והמלבנים.
מבוקש: באילו מחלקות להוסיף את `area()`.
1. רק לעצמים מסוג Triangle ו-Rectangle צריך לחשב שטח, ולכל אחד מהם נוסחה אחרת שמשתמשת בתכונות שלו (משולש: , מלבן: רוחב כפול אורך). לכן את הפעולה `double area()` מוסיפים במחלקה Triangle ובמחלקה Rectangle.
2. בפעולת הסכום עוברים על המערך, בודקים את הטיפוס בעזרת `instanceof` (ב-C#: `is`), ממירים את ההפניה לטיפוס המתאים וקוראים ל-`area()`:
if (arr[i] instanceof Triangle)
sum += ((Triangle) arr[i]).area();
else if (arr[i] instanceof Rectangle)
sum += ((Rectangle) arr[i]).area();3. ההמרה נחוצה כי ההפניות במערך הן מטיפוס Shape, ולמחלקה Shape אין פעולה `area()`.
4. (אפשרות נוספת: להצהיר על `area()` גם במחלקה Shape – למשל כפעולה מופשטת או כפעולה שמחזירה 0 – ולדרוס אותה ב-Triangle וב-Rectangle. אז אפשר לקרוא ל-`arr[i].area()` בלי המרה, בזכות פולימורפיזם; עדיין צריך לבדוק את הטיפוס כדי לסכום רק משולשים ומלבנים.)
תשובה: במחלקות Triangle ו-Rectangle – רק להן מחשבים שטח, וכל אחת מחשבת אותו לפי התכונות שלה (אפשר להוסיף הצהרה גם ב-Shape כדי לקרוא לפעולה בלי המרה).
סעיף ג
חיפוש מקסימום על איברי המערך שהם Triangle, עם max שמאותחל ל-null.
נתון: מערך צורות `arr`.
מבוקש: להחזיר את המשולש בעל השטח הגדול ביותר, או null אם אין משולשים.
הרעיון: חיפוש מקסימום רגיל, רק על האיברים שהם משולשים. מחזיקים הפניה `max` למשולש הגדול ביותר עד כה, ומאתחלים אותה ל-null – כך, אם אין משולש במערך, היא נשארת null ומוחזרת כנדרש.
1. עוברים על המערך. אם `arr[i]` הוא Triangle (`instanceof` / `is`), ממירים אותו ל-Triangle.
2. אם `max` עדיין null (זה המשולש הראשון) או ששטחו גדול משטח `max` – מעדכנים את `max`.
3. בסוף מחזירים את `max`.
הפעולה `area()` נמצאת במחלקה Triangle (סעיף ב'). איבר null במערך אינו נחשב משולש (`instanceof` מחזיר עליו false).
public static Triangle maxArea(Shape[] arr)
{
Triangle max = null;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof Triangle)
{
Triangle t = (Triangle) arr[i];
if (max == null || t.area() > max.area())
max = t;
}
}
return max;
}public static Triangle MaxArea(Shape[] arr)
{
Triangle max = null;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is Triangle)
{
Triangle t = (Triangle) arr[i];
if (max == null || t.Area() > max.Area())
max = t;
}
}
return max;
}תשובה: חיפוש מקסימום על המשולשים בלבד, עם `max` שמאותחל ל-null; מוחזרת ההפניה למשולש הגדול ביותר או null.
שאלה 5 · מעקב: סיבוב ערכים וחוליות בשרשרת

נתונה הפעולה mystery הבאה:
public static Node<Integer> mystery (Node<Integer> chain)
{
Node<Integer> p = chain;
int x = p.getValue();
while(p.getNext() != null)
{
int y = p.getNext().getValue();
p.getNext().setValue(x);
x = y;
p = p.getNext();
}
chain.setValue(x);
return chain;
}public static Node<int> Mystery (Node<int> chain)
{
Node<int> p = chain;
int x = p.GetValue();
while(p.GetNext() != null)
{
int y = p.GetNext().GetValue();
p.GetNext().SetValue(x);
x = y;
p = p.GetNext();
}
chain.SetValue(x);
return chain;
}נתונה שרשרת חוליות הבאה (איור א' לשאלה 5).
איך תיראה השרשרת אחרי זימון הפעולה mystery(chain)?

נתונה הפעולה miracle הבאה:
public static Node<Integer> miracle(Node<Integer> n)
{
Node<Integer> p = n;
while(p.getNext() != null)
{
p = p.getNext();
}
p.setNext(n);
n = n.getNext();
p = p.getNext();
p.setNext(null);
return n;
}public static Node<int> Miracle(Node<int> n)
{
Node<int> p = n;
while(p.GetNext() != null)
{
p = p.GetNext();
}
p.SetNext(n);
n = n.GetNext();
p = p.GetNext();
p.SetNext(null);
return n;
}אחרי זימון הפעולה miracle(n) התקבלה השרשרת הבאה (איור ב' לשאלה 5).
איך נראתה השרשרת לפני זימון הפעולה?
מה מבצעות הפעולות miracle(n) ו- mystery(chain) כאשר הן מקבלות הפניות לחוליות הראשונות של שרשרות החוליות של מספרים שלמים?
◂ פתרון מלא לשאלה 5
סעיף א
הפעולה עוברת על השרשרת עם `p`. בכל סיבוב היא שומרת ב-`y` את ערך החוליה הבאה, כותבת בחוליה הבאה את `x` (הערך הקודם), ו-`x` מקבל את `y`. כך כל ערך "זז" חוליה אחת קדימה, ובסוף הלולאה `x` מחזיק את הערך של החוליה האחרונה, שנכתב בחוליה הראשונה.
מעקב (השרשרת ההתחלתית ; בהתחלה `p` מצביע על החוליה הראשונה ו-):
אחרי הסיבוב השישי `p` מצביע על החוליה האחרונה (`p.getNext()` הוא null) והלולאה נעצרת.
תשובה: השרשרת אחרי הזימון: (הערך האחרון עבר להתחלה וכל השאר זזו מקום אחד ימינה).
סעיף ב
1. הלולאה מביאה את `p` לחוליה האחרונה.
2. `p.setNext(n)` – החוליה האחרונה מצביעה על החוליה הראשונה (השרשרת נהיית מעגלית).
3. `n = n.getNext()` – `n` עובר לחוליה השנייה, שתהיה הראשונה החדשה.
4. `p = p.getNext()` – `p` עובר לחוליה הראשונה המקורית (שעכשיו נמצאת אחרי האחרונה).
5. `p.setNext(null)` – החוליה הראשונה המקורית נהיית האחרונה, והמעגל נשבר.
6. מוחזר `n` – הפניה לחוליה השנייה המקורית.
כלומר: החוליה הראשונה עוברת לסוף השרשרת, ומוחזרת הפניה לחוליה שהייתה שנייה.
חזרה אחורה: אחרי הזימון התקבלה . החוליה האחרונה (4) היא החוליה שהייתה ראשונה, והשאר שמרו על הסדר. לכן לפני הזימון השרשרת הייתה .
בדיקה במעקב על :
תשובה: לפני הזימון: .
סעיף ג
mystery: הערך האחרון עובר לחוליה הראשונה וכל ערך זז חוליה קדימה; miracle: החוליה הראשונה עוברת לסוף ומוחזרת הפניה לחוליה שהייתה שנייה.
1. mystery(chain) – מזיזה את הערכים מקום אחד קדימה באופן מעגלי: הערך של החוליה האחרונה עובר לחוליה הראשונה, וכל ערך אחר עובר לחוליה שאחריו (סיבוב ימינה של הערכים). החוליות עצמן לא זזות – רק הערכים מועתקים; מוחזרת ההפניה `chain` לאותה חוליה ראשונה.
2. miracle(n) – מזיזה את החוליה הראשונה לסוף השרשרת (סיבוב שמאלה) ומחזירה הפניה לחוליה הראשונה החדשה – זו שהייתה שנייה.
3. שתי הפעולות הפוכות זו לזו מבחינת סדר הערכים: mystery מעבירה את האחרון להתחלה, ו-miracle מעבירה את הראשון לסוף (כך גם רואים בסעיפים א' ו-ב').
תשובה: mystery מסובבת את הערכים צעד אחד ימינה (האחרון עובר להתחלה); miracle מעבירה את החוליה הראשונה לסוף ומחזירה הפניה לחוליה שהייתה שנייה.
שאלה 6 · מחסנית תחתית ותחתית משותפת
•אין להשתמש במבני נתונים נוספים פרט למחסנית או מחסניות נוספות.
•אין צורך בשמירת המחסניות.

הגדרה: מחסנית s1 נקראת "מחסנית תחתית" של מחסנית s2 אם כל האיברים של s1 נמצאים בתחתית s2 באותו הסדר.
לדוגמה: המחסנית s1 היא מחסנית תחתית של s2 (איור א' לשאלה 6).
כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים s1 ו- s2. הפעולה תבדוק אם s1 היא מחסנית תחתית של s2. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isBottomStack(Stack<Integer> s1,
Stack<Integer> s2)public static bool IsBottomStack(Stack<int> s1,
Stack<int> s2)
הגדרה: מחסנית נקראת "תחתית משותפת" של מחסניות s1 ו- s2 אם היא "מחסנית תחתית" גם ל- s1 וגם ל- s2.
לדוגמה: המחסניות s3, s4, s5 הן תחתית משותפת של המחסניות s1 ו- s2 (איור ב' לשאלה 6).
כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים s1 ו- s2. הפעולה תחזיר מחסנית חדשה שהיא "תחתית משותפת" הארוכה ביותר של s1 ו- s2.
כותרת הפעולה:
public static Stack<Integer> commonBottom(Stack<Integer> s1,
Stack<Integer> s2)public static Stack<int> CommonBottom(Stack<int> s1,
Stack<int> s2)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
הופכים את שתי המחסניות ומשווים מהתחתית; הבדל או s2 קצרה מדי – false, אחרת true.
נתון: שתי מחסניות `s1`, `s2`; מותר להשתמש רק במחסניות עזר, ואין צורך לשמור את המחסניות.
מבוקש: לבדוק אם כל איברי `s1` נמצאים בתחתית `s2`, באותו סדר.
הרעיון: ההשוואה צריכה להתחיל מהתחתית, אבל במחסנית אפשר לגשת רק לראש. לכן הופכים את שתי המחסניות: מעבירים כל אחת למחסנית עזר, ואז התחתית נמצאת בראש.
1. מעבירים את `s1` ל-`r1` ואת `s2` ל-`r2`. עכשיו בראש `r1` ובראש `r2` נמצאים האיברים התחתונים.
2. כל עוד `r1` לא ריקה: אם `r2` כבר ריקה – ב-`s1` יש יותר איברים מאשר ב-`s2`, ולכן false. אחרת מוציאים איבר מכל אחת; אם הם שונים – false.
3. אם `r1` התרוקנה בלי שנמצא הבדל – כל איברי `s1` מופיעים בתחתית `s2` באותו סדר: true.
בדיקה עם הדוגמה: מהתחתית למעלה `s2` = ו-`s1` = . ארבעת הזוגות הראשונים שווים ו-`r1` מתרוקנת – true.
(מחסנית `s1` ריקה היא מחסנית תחתית של כל מחסנית – הפעולה מחזירה true.)
public static boolean isBottomStack(Stack<Integer> s1, Stack<Integer> s2)
{
Stack<Integer> r1 = new Stack<Integer>();
Stack<Integer> r2 = new Stack<Integer>();
while (!s1.isEmpty()) // היפוך: התחתית עוברת לראש
r1.push(s1.pop());
while (!s2.isEmpty())
r2.push(s2.pop());
while (!r1.isEmpty())
{
if (r2.isEmpty()) // s1 ארוכה מ-s2
return false;
int a = r1.pop();
int b = r2.pop();
if (a != b)
return false;
}
return true;
}public static bool IsBottomStack(Stack<int> s1, Stack<int> s2)
{
Stack<int> r1 = new Stack<int>();
Stack<int> r2 = new Stack<int>();
while (!s1.IsEmpty()) // היפוך: התחתית עוברת לראש
r1.Push(s1.Pop());
while (!s2.IsEmpty())
r2.Push(s2.Pop());
while (!r1.IsEmpty())
{
if (r2.IsEmpty()) // s1 ארוכה מ-s2
return false;
int a = r1.Pop();
int b = r2.Pop();
if (a != b)
return false;
}
return true;
}תשובה: הופכים את שתי המחסניות למחסניות עזר ומשווים איבר-איבר מהתחתית; הבדל, או ש-s2 נגמרת לפני s1 – false, אחרת true.
סעיף ב
הופכים את שתי המחסניות ודוחפים לתוצאה כל עוד הזוגות שווים; בדוגמה מוחזרת (7 בראש).
נתון: שתי מחסניות `s1`, `s2`.
מבוקש: מחסנית חדשה – התחתית המשותפת הארוכה ביותר.
הרעיון: התחתית המשותפת הארוכה ביותר היא הרצף הארוך ביותר של איברים שווים, החל מהתחתית של שתי המחסניות. כמו בסעיף א', הופכים את שתיהן כך שהתחתיות יהיו בראש, ומוציאים זוגות כל עוד הם שווים.
1. מעבירים את `s1` ל-`r1` ואת `s2` ל-`r2`.
2. כל עוד שתיהן לא ריקות: מוציאים איבר מכל אחת. אם הם שונים – עוצרים. אם שווים – דוחפים את האיבר למחסנית התוצאה.
3. האיבר הראשון שנדחף הוא התחתון, ולכן מחסנית התוצאה בנויה בסדר הנכון: התחתית שלה זהה לתחתית של `s1` ושל `s2`.
4. אם כבר האיברים התחתונים שונים – מוחזרת מחסנית ריקה.
בדיקה עם הדוגמה: מהתחתית למעלה `s2` = ו-`s1` = . הזוגות שווים, והזוג החמישי (1 מול 6) שונה. מוחזרת המחסנית שבראשה 7: – בדיוק `s5`.
public static Stack<Integer> commonBottom(Stack<Integer> s1, Stack<Integer> s2)
{
Stack<Integer> r1 = new Stack<Integer>();
Stack<Integer> r2 = new Stack<Integer>();
while (!s1.isEmpty())
r1.push(s1.pop());
while (!s2.isEmpty())
r2.push(s2.pop());
Stack<Integer> result = new Stack<Integer>();
while (!r1.isEmpty() && !r2.isEmpty())
{
int a = r1.pop();
int b = r2.pop();
if (a != b)
break; // סוף החלק המשותף
result.push(a);
}
return result;
}public static Stack<int> CommonBottom(Stack<int> s1, Stack<int> s2)
{
Stack<int> r1 = new Stack<int>();
Stack<int> r2 = new Stack<int>();
while (!s1.IsEmpty())
r1.Push(s1.Pop());
while (!s2.IsEmpty())
r2.Push(s2.Pop());
Stack<int> result = new Stack<int>();
while (!r1.IsEmpty() && !r2.IsEmpty())
{
int a = r1.Pop();
int b = r2.Pop();
if (a != b)
break; // סוף החלק המשותף
result.Push(a);
}
return result;
}תשובה: הופכים את שתי המחסניות ודוחפים למחסנית חדשה את האיברים כל עוד הזוגות שווים; בדוגמה מוחזרת המחסנית (7 בראש).
סעיף ג
שתיהן
נסמן ב- את מספר האיברים ב-`s1` וב- את מספר האיברים ב-`s2`.
1. isBottomStack: היפוך `s1` – פעולות, היפוך `s2` – פעולות, ולולאת ההשוואה – לכל היותר סיבובים. כל פעולה , ולכן סך הכול .
2. commonBottom: אותם שני היפוכים – פעולות, ולולאת ההשוואה – לכל היותר סיבובים. סך הכול .
תשובה: שתי הפעולות – לינאריות בסכום גודלי המחסניות.
שאלה 7 · סדרת פיבונאצ'י בשרשרת חוליות
סדרת פיבונאצ'י (Fibonacci) היא הסדרה ששני איבריה הראשונים הם 1, 1 וכל איבר לאחר מכן שווה לסכום של שני קודמיו. בהתאם לכך, איבריה הראשונים של הסדרה הם:
כתבו פעולה המקבלת הפנייה לשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם ערכים של השרשרת הם סדרה פיבונאצ'י. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isFibonacci(Node<Integer> chain)public static bool IsFibonacci(Node<int> chain)
כתבו פעולה המקבלת מספר שלם וחיובי num ומחזירה הפניה לחוליה הראשונה של שרשרת חוליות שאבריה הם num המספרים הראשונים של סדרה פיבונאצ'י.
לדוגמה: עבור num=9 הפעולה תחזיר הפנייה לחוליה הראשונה של שרשרת החוליות הבאה (איור לשאלה 7).
מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
משווים כל חוליה לאיבר הבא בסדרה (; ); הבדל – false, סוף השרשרת – true.
נתון: הפניה לשרשרת חוליות של מספרים שלמים.
מבוקש: לבדוק אם ערכי השרשרת, מתחילתה, הם איברי סדרת פיבונאצ'י:
הרעיון: מייצרים את איברי הסדרה תוך כדי המעבר על השרשרת ומשווים. מחזיקים שני משתנים: `a` – האיבר הנוכחי של הסדרה, `b` – האיבר שאחריו. בהתחלה .
1. לכל חוליה: אם ערכה שונה מ-`a` – השרשרת אינה סדרת פיבונאצ'י, מחזירים false.
2. מתקדמים בסדרה: , , (כל איבר הוא סכום שני קודמיו), ומתקדמים לחוליה הבאה.
3. אם הגענו לסוף השרשרת בלי הבדל – מחזירים true.
כך נבדקים יחד גם שני האיברים הראשונים (1, 1) וגם הכלל "כל איבר שווה לסכום שני קודמיו". שרשרת ריקה (null) – אין בה ערכים, ולכן מחזירים false.
דוגמאות: – true; – false (4 במקום 3); – false (מתחילה ב-2).
public static boolean isFibonacci(Node<Integer> chain)
{
if (chain == null)
return false;
int a = 1, b = 1; // האיבר הנוכחי והבא בסדרה
Node<Integer> p = chain;
while (p != null)
{
if (p.getValue() != a)
return false;
int c = a + b;
a = b;
b = c;
p = p.getNext();
}
return true;
}public static bool IsFibonacci(Node<int> chain)
{
if (chain == null)
return false;
int a = 1, b = 1; // האיבר הנוכחי והבא בסדרה
Node<int> p = chain;
while (p != null)
{
if (p.GetValue() != a)
return false;
int c = a + b;
a = b;
b = c;
p = p.GetNext();
}
return true;
}תשובה: מייצרים את הסדרה (, ואז ) במקביל למעבר על השרשרת; ערך שונה – false, הגעה לסוף – true.
סעיף ב
בונים שרשרת עם הפניה לחוליה האחרונה ומוסיפים את איברי הסדרה; עבור : .
נתון: מספר שלם וחיובי `num`.
מבוקש: שרשרת של `num` האיברים הראשונים של סדרת פיבונאצ'י.
הרעיון: בונים את השרשרת מההתחלה לסוף ומחזיקים הפניה `last` לחוליה האחרונה, כדי שכל הוספה תהיה ב-.
1. יוצרים את החוליה הראשונה עם הערך 1 (`num` חיובי, ולכן יש לפחות איבר אחד). `first` ו-`last` מצביעים עליה.
2. `a` הוא הערך האחרון שנכנס ו-`b` הוא הבא בתור; בהתחלה .
3. לכל מ-2 עד `num`: מוסיפים אחרי `last` חוליה עם הערך `b`, מקדמים את `last`, ומחשבים את האיבר הבא: , , .
4. מחזירים את `first`.
בדיקה עם הדוגמה: עבור נוצרות החוליות .
public static Node<Integer> fibonacciChain(int num)
{
Node<Integer> first = new Node<Integer>(1);
Node<Integer> last = first;
int a = 1, b = 1; // הערך האחרון בשרשרת והערך הבא
for (int i = 2; i <= num; i++)
{
last.setNext(new Node<Integer>(b));
last = last.getNext();
int c = a + b;
a = b;
b = c;
}
return first;
}public static Node<int> FibonacciChain(int num)
{
Node<int> first = new Node<int>(1);
Node<int> last = first;
int a = 1, b = 1; // הערך האחרון בשרשרת והערך הבא
for (int i = 2; i <= num; i++)
{
last.SetNext(new Node<int>(b));
last = last.GetNext();
int c = a + b;
a = b;
b = c;
}
return first;
}תשובה: בונים שרשרת עם הפניה לחוליה האחרונה ומוסיפים בכל סיבוב את האיבר הבא בסדרה; עבור מתקבל .
סעיף ג
א' – ; ב' –
1. isFibonacci: נסמן ב- את מספר החוליות. הלולאה עוברת על כל חוליה לכל היותר פעם אחת, ובכל סיבוב מספר קבוע של פעולות. לכן .
2. fibonacciChain: הלולאה מבצעת סיבובים, ובכל אחד יצירת חוליה וחיבור אחרי `last` – (בזכות ההפניה לחוליה האחרונה לא צריך לעבור כל פעם עד סוף השרשרת). לכן .
תשובה: סעיף א' – ( – מספר החוליות); סעיף ב' – .
שאלה 8 · עץ בינרי יורד: שרטוט ובדיקה רקורסיבית
הגדרה: עץ יורד הוא עץ בינארי של מספרים שלמים העונה על הכלל הבא:
•לכל צומת פרט לעלים יש בדיוק שני בנים.
•הערך של צומת הבן קטן מהערך של צומת האב.
ציירו עץ "יורד" הכולל לפחות עשרה צמתים
כתבו פעולה המקבלת הפנייה לשורש של עץ בינרי של מספרים שלמים. הפעולה תבדוק אם העץ הוא "עץ יורד". אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
◂ פתרון מלא לשאלה 8
סעיף א
למשל: 100 (בנים 80, 90); 80 (50, 70); 90 (60, 85); 50 (10, 20); 70 (30, 40) – 11 צמתים.
הדרישות: לכל צומת שאינו עלה יש בדיוק שני בנים, וכל בן קטן מאביו.
איך בונים: בוחרים שורש גדול (100), ובכל רמה נותנים לכל צומת פנימי שני בנים קטנים ממנו. בעץ שבו לכל צומת פנימי שני בנים מספר הצמתים אי-זוגי (מספר העלים גדול באחד ממספר הצמתים הפנימיים), ולכן כדי להגיע ל"לפחות עשרה" צריך לפחות 11 צמתים: 5 צמתים פנימיים ו-6 עלים.
העלים: 10, 20, 30, 40, 60, 85. בכל שורה בטבלה שני הבנים קטנים מהאב, ולכל צומת פנימי שני בנים – העץ "יורד".
תשובה: למשל עץ בן 11 צמתים: שורש 100 עם הבנים 80 ו-90; ל-80 הבנים 50 ו-70; ל-90 הבנים 60 ו-85; ל-50 הבנים 10 ו-20; ל-70 הבנים 30 ו-40.
סעיף ב
רקורסיה: עלה – true; בן אחד או בן ≥ אב – false; אחרת בדיקה של שני תתי-העצים.
נתון: הפניה לשורש של עץ בינרי של מספרים שלמים.
מבוקש: true אם כל צומת הוא עלה או בעל שני בנים, וכל בן קטן מאביו.
הרעיון (רקורסיה): עץ הוא "יורד" אם השורש מקיים את הכללים מול בניו, ושני תתי-העצים הם "יורדים".
1. עץ ריק (null) – אין בו צומת שמפר את הכללים: true.
2. עלה (אין בן שמאלי ואין ימני) – true.
3. צומת עם בן אחד בלבד – מפר את הכלל "בדיוק שני בנים": false.
4. לצומת שני בנים: אם אחד הבנים גדול מהאב או שווה לו – false.
5. אחרת – מחזירים את התוצאה של הבדיקה הרקורסיבית על תת-העץ השמאלי וגם על הימני.
כותרת הפעולה לא נתונה בשאלה; נבחרה הכותרת שלמטה.
דוגמה: העץ מסעיף א' – true. צומת 5 עם בן שמאלי 3 בלבד – false (בן אחד). צומת 5 עם הבנים 3 ו-5 – false (בן שאינו קטן מהאב).
public static boolean isDescendingTree(BinNode<Integer> t)
{
if (t == null)
return true;
if (!t.hasLeft() && !t.hasRight()) // עלה
return true;
if (!t.hasLeft() || !t.hasRight()) // בן אחד בלבד
return false;
if (t.getLeft().getValue() >= t.getValue() ||
t.getRight().getValue() >= t.getValue())
return false;
return isDescendingTree(t.getLeft()) && isDescendingTree(t.getRight());
}public static bool IsDescendingTree(BinNode<int> t)
{
if (t == null)
return true;
if (!t.HasLeft() && !t.HasRight()) // עלה
return true;
if (!t.HasLeft() || !t.HasRight()) // בן אחד בלבד
return false;
if (t.GetLeft().GetValue() >= t.GetValue() ||
t.GetRight().GetValue() >= t.GetValue())
return false;
return IsDescendingTree(t.GetLeft()) && IsDescendingTree(t.GetRight());
}כל צומת נבדק פעם אחת, ולכן הסיבוכיות , כאשר מספר הצמתים.
תשובה: פעולה רקורסיבית: עלה או עץ ריק – true; בן אחד בלבד או בן שאינו קטן מהאב – false; אחרת – בדיקה של שני תתי-העצים.
שאלה 9 · הפרשים בין איברי תור
כתבו פעולה המקבלת תור של מספרים שלמים ומחזירה את ההפרש הגדול ביותר בין שני איברי התור.
כותרת הפעולה:
public static int maxDiff(Queue<Integer> q)public static int MaxDiff(Queue<int> q)כתבו פעולה המקבלת תור של מספרים שלמים ומספר שלם num. הפעולה תבדוק אם קיים בתור זוג איברים שהפרש שלהם שווה ל-num. אם כן, הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean existDiff(Queue<Integer> q, int num)public static bool ExistDiff(Queue<int> q, int num)מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו- ב'? הסבירו את תשובתכם
◂ פתרון מלא לשאלה 9
סעיף א
של איברי התור (מעבר אחד, התור משוחזר).
נתון: תור של מספרים שלמים (הנחה: התור אינו ריק).
מבוקש: ההפרש הגדול ביותר בין שני איברי התור.
הרעיון: ההפרש הגדול ביותר בין שני איברים מתקבל כשמחסירים את הקטן ביותר מהגדול ביותר: . לכן מספיק מעבר אחד שמוצא מקסימום ומינימום.
1. מאתחלים את `max` ואת `min` לאיבר שבראש התור.
2. מוציאים כל איבר, מכניסים אותו לתור עזר ומעדכנים את `max` ו-`min`.
3. מחזירים את האיברים מתור העזר לתור המקורי (הסדר נשמר).
4. מחזירים . (בתור עם איבר אחד מתקבל 0.)
דוגמה: עבור התור : , , וההפרש .
public static int maxDiff(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int max = q.head();
int min = q.head();
while (!q.isEmpty())
{
int x = q.remove();
temp.insert(x);
if (x > max)
max = x;
if (x < min)
min = x;
}
while (!temp.isEmpty()) // שחזור התור
q.insert(temp.remove());
return max - min;
}public static int MaxDiff(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int max = q.Head();
int min = q.Head();
while (!q.IsEmpty())
{
int x = q.Remove();
temp.Insert(x);
if (x > max)
max = x;
if (x < min)
min = x;
}
while (!temp.IsEmpty()) // שחזור התור
q.Insert(temp.Remove());
return max - min;
}תשובה: מוצאים במעבר אחד את המקסימום ואת המינימום ומחזירים (התור משוחזר).
סעיף ב
העתקה למערך ובדיקת כל הזוגות : אם – true.
נתון: תור `q` של מספרים שלמים ומספר שלם `num`.
מבוקש: האם יש שני איברים (במקומות שונים) שההפרש ביניהם שווה ל-`num`.
הרעיון: בתור אפשר לגשת רק לראש, ולכן כדי להשוות כל זוג נעתיק את איברי התור למערך, ואז נבדוק את כל הזוגות.
1. מעבירים את האיברים לתור עזר וסופרים אותם – .
2. יוצרים מערך בגודל , ומעבירים את האיברים מתור העזר גם למערך וגם חזרה ל-`q` (כך התור משוחזר).
3. לולאה כפולה על כל זוג מקומות : אם – מחזירים true. מכיוון ש- ו- עוברים על כל הסדרים, נבדקים גם וגם , ולכן הסדר של שני האיברים בתור אינו משנה.
4. אם לא נמצא זוג – false.
דוגמה: עבור התור : עבור – true (); עבור – true (); עבור – false (אין שני איברים שווים).
public static boolean existDiff(Queue<Integer> q, int num)
{
Queue<Integer> temp = new Queue<Integer>();
int n = 0;
while (!q.isEmpty()) // ספירת האיברים
{
temp.insert(q.remove());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור התור
{
arr[i] = temp.remove();
q.insert(arr[i]);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && arr[i] - arr[j] == num)
return true;
return false;
}public static bool ExistDiff(Queue<int> q, int num)
{
Queue<int> temp = new Queue<int>();
int n = 0;
while (!q.IsEmpty()) // ספירת האיברים
{
temp.Insert(q.Remove());
n++;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) // העתקה למערך ושחזור התור
{
arr[i] = temp.Remove();
q.Insert(arr[i]);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && arr[i] - arr[j] == num)
return true;
return false;
}תשובה: מעתיקים את התור למערך (ומשחזרים אותו) ובודקים את כל הזוגות ; אם – true, אחרת false.
סעיף ג
א' – ; ב' –
נסמן ב- את מספר האיברים בתור.
1. maxDiff: מעבר אחד להוצאת האיברים ועדכון מקסימום ומינימום ( סיבובים) ומעבר אחד לשחזור ( סיבובים), כל סיבוב . סך הכול .
2. existDiff: הספירה וההעתקה – . הלולאה הכפולה בודקת זוגות, כל בדיקה – . הגורם הדומיננטי הוא הלולאה הכפולה, ולכן (במקרה הגרוע, כשאין זוג מתאים).
תשובה: maxDiff – ; existDiff – .
שאלה 10 · בנאים בירושה ומערך עצמים מטיפוס יורש
לפניכם הכותרות של מחלקות One, Two והתכונות שלהן והמחלקה Test הכוללת פעולה ראשית:
public class One
{
protected int val;
….
}
public class Two extends One
{
private String s;
private One p;
…
}
public class Test
{
public static void main(String[] args)
{
One [] arr = new One [5];
arr[0] = new One (25);
arr[1] = new One ();
arr[2] = new Two ();
arr[3] = new Two (15, arr[0]);
arr[4] = new Two (2, "CCC", arr[1]);
}
}public class One
{
protected int val;
….
}
public class Two : One
{
private String s;
private One p;
…
}
public class Test
{
public static void main(String[] args)
{
One [] arr = new One [5];
arr[0] = new One (25);
arr[1] = new One ();
arr[2] = new Two ();
arr[3] = new Two (15, arr[0]);
arr[4] = new Two (2, "CCC", arr[1]);
}
}
הרצת הפעולה יצרה את העצמים הבאים (איור לשאלה 10).
כתבו במחלקות One ו-Two את הפעולות הבונות (constructors) הנדרשות לשם הרצת הפעולה הראשית כך שיתקבלו העצמים המתוארים.
כתבו פעולה המקבלת מערך arr של עצמים מסוג One ומחזירה מערך החדש הכולל עצמים מסוג Two אשר נמצאים ב-arr. אם במערך arr אין עצמים מסוג Two, הפעולה תחזיר null.
◂ פתרון מלא לשאלה 10
סעיף א
One(int val), One() עם val=10, ובנאי מעתיק One(One other); Two() עם val=10, s="AAA", p=null; Two(int val, One p) עם s="CCC" ו-p עותק חדש; Two(int val, String s, One p) עם p ההפניה שהתקבלה.
נתון: חמש פקודות יצירה בפעולה הראשית, והעצמים שנוצרו (איור לשאלה 10).
מבוקש: הבנאים של One ו-Two שיוצרים בדיוק את העצמים האלה.
1. `new One(25)` → `val = 25`: בנאי One עם פרמטר שלם, שמציב אותו ב-`val`.
2. `new One()` → `val = 10`: בנאי One בלי פרמטרים, שמציב ערך ברירת מחדל 10.
3. `new Two()` → `val = 10`, `s = "AAA"`, `p = null`: בנאי Two בלי פרמטרים. הוא מפעיל את הבנאי הריק של One (ומקבל 10), ומציב `"AAA"` ו-`null`.
4. `new Two(15, arr[0])` → `val = 15`, `s = "CCC"`, ו-`p` מפנה לעצם One חדש שערכו 25: באיור העצם הזה מצויר בנפרד, מתחת ל-`arr[3]`, ואינו העצם שבתא 0 (לעומת `arr[4]`, שהחץ שלו מוביל ישר לעצם שבתא 1). לכן הבנאי של Two עם מספר והפניה מעביר את המספר לבנאי One, מציב `"CCC"` כברירת מחדל, ויוצר עותק של העצם שהתקבל: עצם One חדש עם אותו `val`.
כדי ליצור את העותק מוסיפים ל-One בנאי מעתיק `One(One other)`, שמעתיק את `val` של העצם שהתקבל. זו פעולה בונה, ולכן היא מותרת לפי השאלה; בתוך המחלקה One מותר לגשת לתכונה `val` של עצם One אחר.
5. `new Two(2, "CCC", arr[1])` → `val = 2`, `s = "CCC"`, ו-`p` מפנה ל-`arr[1]` עצמו (החץ באיור מוביל לעצם שבתא 1): בנאי Two עם שלושה פרמטרים, ששומר את ההפניה כמו שהיא, בלי העתקה.
התכונה `val` מוגדרת ב-One, ולכן בבנאי של Two מאתחלים אותה דרך בנאי מחלקת האב (`super(...)` ב-Java, `: base(...)` ב-C#).
public class One
{
protected int val;
public One(int val)
{
this.val = val;
}
public One()
{
this.val = 10;
}
public One(One other) // בנאי מעתיק
{
this.val = other.val;
}
}
public class Two extends One
{
private String s;
private One p;
public Two()
{
super(); // val = 10
this.s = "AAA";
this.p = null;
}
public Two(int val, One p)
{
super(val);
this.s = "CCC";
this.p = new One(p); // עצם One חדש, עותק של p
}
public Two(int val, String s, One p)
{
super(val);
this.s = s;
this.p = p;
}
}public class One
{
protected int val;
public One(int val)
{
this.val = val;
}
public One()
{
this.val = 10;
}
public One(One other) // בנאי מעתיק
{
this.val = other.val;
}
}
public class Two : One
{
private string s;
private One p;
public Two() : base() // val = 10
{
this.s = "AAA";
this.p = null;
}
public Two(int val, One p) : base(val)
{
this.s = "CCC";
this.p = new One(p); // עצם One חדש, עותק של p
}
public Two(int val, string s, One p) : base(val)
{
this.s = s;
this.p = p;
}
}בדיקה מול האיור: `arr[3].p` מפנה לעצם One חדש שערכו 25 (עותק של `arr[0]`), ו-`arr[4].p` מפנה לעצם `arr[1]` עצמו – בדיוק כמו בשרטוט.
תשובה: ב-One: `One(int val)`, `One()` (val=10) ובנאי מעתיק `One(One other)`. ב-Two: `Two()` (val=10, s="AAA", p=null), `Two(int val, One p)` (s="CCC", p = עותק חדש של העצם שהתקבל) ו-`Two(int val, String s, One p)` (p = ההפניה שהתקבלה).
סעיף ב
ספירת העצמים מסוג Two; אם 0 – null; אחרת מערך Two[] בגודל המונה עם העצמים האלה.
נתון: מערך `arr` של הפניות מטיפוס One (חלקן לעצמים מטיפוס Two).
מבוקש: מערך חדש שבו רק העצמים מטיפוס Two, או null אם אין כאלה.
הרעיון: גודל המערך החדש צריך להיות ידוע מראש, ולכן עוברים פעמיים:
1. מעבר ראשון: סופרים כמה איברים הם מטיפוס Two (`instanceof` ב-Java, `is` ב-C#).
2. אם המונה 0 – מחזירים null.
3. יוצרים מערך `Two[]` בגודל המונה.
4. מעבר שני: כל איבר מטיפוס Two מומר ל-Two ומוכנס למקום הפנוי הבא (אינדקס `k`).
כותרת הפעולה לא נתונה בשאלה; נבחרה הכותרת שלמטה. עבור המערך מהפעולה הראשית יוחזר מערך באורך 3: `arr[2]`, `arr[3]`, `arr[4]`.
public static Two[] getTwos(One[] arr)
{
int count = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] instanceof Two)
count++;
if (count == 0)
return null;
Two[] result = new Two[count];
int k = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] instanceof Two)
{
result[k] = (Two) arr[i];
k++;
}
}
return result;
}public static Two[] GetTwos(One[] arr)
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
if (arr[i] is Two)
count++;
if (count == 0)
return null;
Two[] result = new Two[count];
int k = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] is Two)
{
result[k] = (Two) arr[i];
k++;
}
}
return result;
}תשובה: סופרים את האיברים מטיפוס Two; אם אין – null; אחרת יוצרים מערך Two[] בגודל המונה ומעתיקים אליו (עם המרה) את העצמים מטיפוס Two.
שאלה 11 · מאגר נהגים: מחלקות, מחיקה והשבתת רישיונות
משרד הרישוי מחזיק מאגר מידע של נהגי ישראל ושל עבירות התנועה בצורה ממוחשבת. עבור כל נהג נשמרים במשרד הרישוי נתונים הבאים:
•מספר תעודת הזהות (מחרוזת).
•שם (מחרוזת).
•מספר הרישיון (מחרוזת).
•תאריך הלידה (מחרוזת).
•מספר עבירות התנועה שעשה (מספר שלם).
•רישיון פעיל או מושבת (ערך בוליאני, true – פעיל, false – מושבת).
כתבו את כותרת המחלקה ואת התכונות עבור כל אחת מהמחלקות הבאות:
•Driver המתארת נהג.
•DriversData המתארת מידע על כל נהגי המדינה.
אפשר להניח שבמחלקה Driver קיימות בנאים, פעולות get ו- set לכל תכונה ופעולה toString המתארת נהג.
במחלקה Driver קיימת פעולה פנימית `int getAge()` המחזירה את גיל הנהג בשנים מלאות.
אפשר להניח שגיל נהג הוא מספר שלם בין 18 ל- 120 (כולל).
עקב תהליך משפטי, נשלחה בקשה רשמית למשרד הרישוי לבטל את הרישיון של נהג מסוים.
כתבו פעולה פנימית המקבלת מספר תעודת הזהות של הנהג ומוציאה אותו ממאגר.
כדי לצמצם את כמות העבירות הוחלט להשבית זמנית את רישיון הנהיגה לנהגים אשר מספר העבירות שעשו הוא הגבוה ביותר לגיל שלהם (אם יש כמה נהגים כאלו, משביתים את רישיון הנהיגה לכל הנהגים בעלי מספר התאונות הגבוה ביותר). שימו לב השבתת הרישיון היא עבור כול גיל בנפרד.
כתבו פעולה במחלקה DriversData המקבלת את גיל הנהג ומחזירה את מספר העבירות הגבוה ביותר שנעשו על-ידי נהג בגיל הזה.
כתבו פעולה במחלקה DriversData המדפיסה את פרטי הנהגים שרישיונם יושבת. הפעולה גם תעדכן את המאגר (אין צורך להוציא נהגים מהמאגר).
מהן סיבוכיות הפעולות שכתבתם בסעיף ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 11
סעיף א
Driver: id, name, licenseNum, birthDate (String), violations (int), active (boolean); DriversData: Node<Driver> drivers.
מה צריך לייצג: נהג אחד (Driver) עם שש התכונות שברשימה, ואת אוסף כל הנהגים (DriversData).
1. Driver: כל נתון ברשימה הופך לתכונה פרטית מהטיפוס שנכתב בסוגריים: ארבע מחרוזות, מספר שלם ומשתנה בוליאני.
2. DriversData: צריך אוסף שאפשר לעבור עליו שוב ושוב ולמחוק ממנו נהג מכל מקום (סעיף ב'). לכן נבחרה שרשרת חוליות `Node<Driver>` – מעבר עליה לא הורס אותה, ומחיקת חוליה היא שינוי הפניה אחת.
public class Driver
{
private String id; // מספר תעודת הזהות
private String name; // שם הנהג
private String licenseNum; // מספר הרישיון
private String birthDate; // תאריך הלידה
private int violations; // מספר עבירות התנועה שעשה
private boolean active; // true - רישיון פעיל, false - מושבת
...
}
public class DriversData
{
private Node<Driver> drivers; // שרשרת כל נהגי המדינה (הפניה לחוליה הראשונה)
...
}public class Driver
{
private string id; // מספר תעודת הזהות
private string name; // שם הנהג
private string licenseNum; // מספר הרישיון
private string birthDate; // תאריך הלידה
private int violations; // מספר עבירות התנועה שעשה
private bool active; // true - רישיון פעיל, false - מושבת
...
}
public class DriversData
{
private Node<Driver> drivers; // שרשרת כל נהגי המדינה (הפניה לחוליה הראשונה)
...
}בהמשך משתמשים בפעולות הקיימות לפי השאלה: `getId()`, `getViolations()`, `getActive()`, `setActive(...)`, `getAge()`, `toString()` (ב-C#: `GetId()` וכן הלאה).
תשובה: Driver – שש תכונות פרטיות (id, name, licenseNum, birthDate מסוג מחרוזת; violations שלם; active בוליאני); DriversData – תכונה אחת: שרשרת חוליות `Node<Driver> drivers`.
סעיף ב
מחיקת חוליה מהשרשרת: אם ראשונה – מקדמים את drivers, אחרת מדלגים עליה מהחוליה שלפניה.
נתון: מספר תעודת זהות `id`.
מבוקש: להוציא מהשרשרת את הנהג בעל תעודת זהות זו.
הרעיון: כדי למחוק חוליה משרשרת צריך הפניה לחוליה שלפניה, ולשנות את ה-next שלה כך שידלג על החוליה הנמחקת. החוליה הראשונה היא מקרה מיוחד – אין לפניה חוליה, ולכן פשוט מקדמים את `drivers`.
1. אם השרשרת ריקה – אין מה למחוק.
2. אם הנהג הראשון הוא המבוקש – `drivers` מצביע על החוליה השנייה, וסיימנו.
3. אחרת עוברים עם `p` ובודקים את החוליה הבאה: אם היא של הנהג המבוקש – `p.setNext(p.getNext().getNext())` ויוצאים (תעודת זהות ייחודית, ולכן יש לכל היותר נהג אחד כזה).
4. משווים מחרוזות עם `equals` (ב-C# אפשר `==`).
public void removeDriver(String id)
{
if (drivers == null)
return;
if (drivers.getValue().getId().equals(id)) // הנהג הראשון
{
drivers = drivers.getNext();
return;
}
Node<Driver> p = drivers;
while (p.getNext() != null)
{
if (p.getNext().getValue().getId().equals(id))
{
p.setNext(p.getNext().getNext()); // דילוג על החוליה
return;
}
p = p.getNext();
}
}public void RemoveDriver(string id)
{
if (drivers == null)
return;
if (drivers.GetValue().GetId() == id) // הנהג הראשון
{
drivers = drivers.GetNext();
return;
}
Node<Driver> p = drivers;
while (p.GetNext() != null)
{
if (p.GetNext().GetValue().GetId() == id)
{
p.SetNext(p.GetNext().GetNext()); // דילוג על החוליה
return;
}
p = p.GetNext();
}
}תשובה: פעולה פנימית ב-DriversData: אם הנהג בחוליה הראשונה – מקדמים את `drivers`; אחרת מוצאים את החוליה שלפניו ומדלגים עליו.
סעיף ג
מקסימום מספר העבירות של הנהגים הפעילים בגיל הנתון (0 אם אין).
נתון: גיל `age`.
מבוקש: מספר העבירות הגבוה ביותר של נהג בגיל זה, רק מבין הנהגים שהרישיון שלהם פעיל.
הרעיון: חיפוש מקסימום עם סינון.
1. מאתחלים `max = 0`. מספר עבירות אינו שלילי, ולכן אם אין בגיל הזה אף נהג פעיל עם עבירות – יוחזר 0, וזה בדיוק המקרה שבו לא משביתים (לפי ההערה בשאלה).
2. עוברים על כל הנהגים. נהג נלקח בחשבון רק אם `getAge() == age` וגם הרישיון שלו פעיל.
3. אם מספר העבירות שלו גדול מ-`max` – מעדכנים.
public int maxViolations(int age)
{
int max = 0;
Node<Driver> p = drivers;
while (p != null)
{
Driver d = p.getValue();
if (d.getAge() == age && d.getActive() && d.getViolations() > max)
max = d.getViolations();
p = p.getNext();
}
return max;
}public int MaxViolations(int age)
{
int max = 0;
Node<Driver> p = drivers;
while (p != null)
{
Driver d = p.GetValue();
if (d.GetAge() == age && d.GetActive() && d.GetViolations() > max)
max = d.GetViolations();
p = p.GetNext();
}
return max;
}תשובה: חיפוש מקסימום של מספר העבירות על הנהגים בגיל `age` שהרישיון שלהם פעיל; מוחזר 0 אם אין כאלה עם עבירות.
לכל גיל 18-120: אם המקסימום חיובי – setActive(false) והדפסה לכל נהג פעיל בגיל זה עם המקסימום.
מבוקש: לכל גיל בנפרד – להשבית את הרישיון של הנהגים הפעילים בעלי מספר העבירות הגבוה ביותר בגילם, להדפיס את פרטיהם ולעדכן את המאגר.
הרעיון: הגיל הוא מספר שלם בין 18 ל-120, ולכן עוברים על כל הגילים בלולאה.
1. לכל גיל מחשבים `max = maxViolations(age)` (סעיף 1). מחשבים אותו לפני שמשביתים מישהו, כך שגם כשיש כמה נהגים עם אותו מקסימום – כולם יושבתו.
2. אם `max == 0` – בגיל הזה אין עבירות (בין הנהגים הפעילים), ולא משביתים אף אחד.
3. אחרת עוברים על השרשרת; כל נהג בגיל הזה, עם רישיון פעיל ועם `max` עבירות – מעדכנים `setActive(false)` (זה עדכון המאגר; הנהג לא מוצא מהשרשרת) ומדפיסים את פרטיו (`toString`).
public void suspendDrivers()
{
for (int age = 18; age <= 120; age++)
{
int max = maxViolations(age);
if (max > 0) // בגיל זה יש עבירות
{
Node<Driver> p = drivers;
while (p != null)
{
Driver d = p.getValue();
if (d.getAge() == age && d.getActive() && d.getViolations() == max)
{
d.setActive(false); // השבתת הרישיון
System.out.println(d);
}
p = p.getNext();
}
}
}
}public void SuspendDrivers()
{
for (int age = 18; age <= 120; age++)
{
int max = MaxViolations(age);
if (max > 0) // בגיל זה יש עבירות
{
Node<Driver> p = drivers;
while (p != null)
{
Driver d = p.GetValue();
if (d.GetAge() == age && d.GetActive() && d.GetViolations() == max)
{
d.SetActive(false); // השבתת הרישיון
Console.WriteLine(d);
}
p = p.GetNext();
}
}
}
}דוגמה: בגיל 20 נהגים פעילים עם 3, 5, 5 עבירות ונהג מושבת עם 9 – המקסימום הוא 5, ושני הנהגים עם 5 עבירות מושבתים ומודפסים. בגיל 30 נהג יחיד עם 0 עבירות – לא מושבת.
תשובה: לכל גיל מ-18 עד 120: מחשבים את המקסימום מסעיף 1; אם הוא חיובי – משביתים (setActive(false)) ומדפיסים את כל הנהגים הפעילים בגיל זה עם מספר עבירות זה.
סעיף ד
שתיהן
נסמן ב- את מספר הנהגים במאגר.
1. maxViolations: מעבר אחד על השרשרת, לכל נהג (`getAge` היא פעולה קיימת שמחזירה גיל). לכן .
2. suspendDrivers: הלולאה החיצונית רצה על גילים – מספר קבוע שאינו תלוי ב-. בכל גיל: קריאה ל-maxViolations () ועוד מעבר על השרשרת (). סך הכול פעולות, כלומר .
תשובה: סעיף ג'1 – ; סעיף ג'2 – (קבוע של 103 גילים כפול מעברים לינאריים).
שאלה 12 · רקורסיה על מחסניות: הכנסה לתחתית והיפוך
נתונות שתי פעולות רקורסיביות הבאות:
public static void one(Stack<Integer> s, int x){
if(s.isEmpty())
s.push(x);
else
{
int temp=s.pop();
one(s,x);
s.push(temp);
}
}
public static void two(Stack<Integer> s){
if(!s.isEmpty())
{
int x = s.pop();
two(s);
one(s,x);
}
}public static void One(Stack<int> s, int x){
if(s.IsEmpty())
s.Push(x);
else
{
int temp=s.Pop();
One(s,x);
s.Push(temp);
}
}
public static void Two(Stack<int> s){
if(!s.IsEmpty())
{
int x = s.Pop();
Two(s);
One(s,x);
}
}(המחסנית s1 מוצגת באיור לשאלה 12.)

מה יהיה התוכן של המחסנית s1 אחרי זימון הפעולה one(s1,10)?
מה מבצעת הפעולה one(s,x) עבור מחסנית של מספרים שלמים s ומספר שלם x?
מה יהיה התוכן של המחסנית s1 אחרי זימון הפעולה two(s1)?
מה מבצעת הפעולה two(s) עבור מחסנית של מספרים שלמים s?
נתונה הפעולה הרקורסיבית three הבאה:
public static boolean three(Stack<Integer> s){
if(s.isEmpty())
return true;
int x = s.pop();
two(s);
if(s.isEmpty())
return true;
int y = s.pop();
if(x % y != 0)
return false;
two(s);
return three(s);
}public static bool Three(Stack<int> s){
if(s.IsEmpty())
return true;
int x = s.Pop();
Two(s);
if(s.IsEmpty())
return true;
int y = s.Pop();
if(x % y != 0)
return false;
Two(s);
return Three(s);
}(המחסנית s2 מוצגת באיור ה' לשאלה 12.)

מהי תוצאת זימון הפעולה three(s2)?
◂ פתרון מלא לשאלה 12
סעיף א
[3, -1, 7, 2, 10] (מהראש לתחתית)
`one` מוציאה את הראש, קוראת לעצמה על המחסנית הקטנה יותר, ואחרי החזרה מהרקורסיה מחזירה את הראש. רק כשהמחסנית התרוקנה לגמרי היא דוחפת את `x` – כלומר `x` נכנס לתחתית.
מעקב (המחסניות נכתבות מהראש לתחתית; `s1` = [3, -1, 7, 2]):
סדר החזרות הוא מלמטה למעלה בטבלה: one#5 דוחפת 10, אחריה one#4 דוחפת 2, וכן הלאה עד one#1 שדוחפת 3.
תשובה: `s1` = [3, -1, 7, 2, 10] – הראש 3, והערך 10 בתחתית.
סעיף ב
מכניסה את x לתחתית המחסנית s.
לפי המעקב בסעיף א': הפעולה מוציאה את כל האיברים בירידה ברקורסיה, דוחפת את `x` כשהמחסנית ריקה, ומחזירה את האיברים בסדר ההפוך להוצאתם – כלומר בדיוק למקומם.
תשובה: `one(s, x)` מכניסה את `x` לתחתית המחסנית `s`; שאר האיברים נשארים באותו סדר.
סעיף ג
[2, 7, -1, 3] (מהראש לתחתית)
`two` מוציאה את הראש `x`, הופכת (ברקורסיה) את שאר המחסנית, ואז מכניסה את `x` לתחתית בעזרת `one` (סעיף ב').
מעקב (`s1` = [3, -1, 7, 2], מהראש לתחתית):
החזרות מתבצעות מלמטה למעלה: two#4 מכניסה 2 לתחתית מחסנית ריקה, two#3 מכניסה 7 לתחתית – [2, 7], two#2 מכניסה -1 לתחתית – [2, 7, -1], ולבסוף two#1 מכניסה 3 לתחתית.
תשובה: `s1` = [2, 7, -1, 3] – הראש 2 והתחתית 3 (המחסנית התהפכה).
סעיף ד
הופכת את סדר איברי המחסנית.
לפי סעיף ג': האיבר העליון עובר לתחתית אחרי שכל השאר כבר הופכו, ולכן (באינדוקציה על גודל המחסנית) כל המחסנית מתהפכת.
תשובה: `two(s)` הופכת את סדר האיברים במחסנית: הראש עובר לתחתית והתחתית עוברת לראש.
סעיף ה
false
מה עושה סיבוב אחד של three: מוציאה את הראש `x`, `two` הופכת את השאר – כך שהאיבר שהיה בתחתית עולה לראש – ו-`y` הוא האיבר התחתון המקורי. אם `x` אינו מתחלק ב-`y` – false. אחרת `two` מחזירה את השאר לסדר המקורי, וממשיכים ברקורסיה עם המחסנית בלי הראש והתחתית. כלומר בודקים זוגות "ראש-תחתית" מבחוץ פנימה.
מעקב (`s2` = [3, 6, 14, 2, 6, 3, 1], מהראש לתחתית):
ב-three#3 השארית שונה מ-0, ולכן מוחזר false, והערך הזה עובר כמו שהוא דרך three#2 ו-three#1 (`return three(s)`).
תשובה: הזימון `three(s2)` מחזיר false (14 אינו מתחלק ב-6).