מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2025 מועד ב'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2025 מועד ב', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב-C# (עמוד 2)
מבחן ב-JAVA (עמוד 14)
בכל מבחן 12 שאלות.
שאלות 1–5: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 6–10: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 11–12: יש לענות על שאלה אחת בלבד. ערך השאלה 16 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית ייחודית – בדיקת חלוקה בין איברים
מחסנית של מספרים שלמים נקראת "מחסנית ייחודית" אם היא מחסנית ריקה או מחסנית שכל אחד מהאיברים בה אינו מתחלק בשום איבר אחר.
כתבו פעולה המקבלת מחסנית S שאיבריה מספרים שלמים וחיוביים. אם המחסנית היא מחסנית ייחודית הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
לכל איבר בודקים אם הוא מחלק או מתחלק באחד האיברים שמתחתיו; אם כן – false, אחרת true (המחסנית משוחזרת).
נתון: מחסנית `s` של מספרים שלמים וחיוביים.
מבוקש: להחזיר true אם אף איבר במחסנית אינו מתחלק באיבר אחר שלה (מחסנית ריקה – true).
הרעיון: צריך לבדוק כל זוג איברים. מספיק לבדוק כל זוג פעם אחת, אבל בשני הכיוונים: מתחלק ב- (`x % y == 0`) או מתחלק ב- (`y % x == 0`).
1. מוציאים מהמחסנית את האיבר העליון `x` (הוא עובר למחסנית העזר `temp1`).
2. משווים את `x` לכל האיברים שנשארו מתחתיו: מוציאים אותם אחד-אחד למחסנית עזר `temp2`, ובודקים את תנאי החלוקה בשני הכיוונים. אם אחד מהם מתקיים – המחסנית אינה ייחודית (`unique = false`).
3. מחזירים את האיברים מ-`temp2` ל-`s` (הסדר חוזר להיות המקורי), וממשיכים לאיבר הבא – כך כל זוג נבדק פעם אחת בדיוק.
4. כשנמצא זוג "אסור" אין טעם להמשיך, ולכן הלולאה החיצונית רצה רק כל עוד `unique` אמת.
5. בסוף מחזירים את כל האיברים מ-`temp1` ל-`s`, כך שהמחסנית חוזרת למצבה המקורי, ומחזירים את `unique`.
•שני איברים שווים מתחלקים זה בזה, ולכן מחסנית עם ערך כפול אינה ייחודית.
•מחסנית ריקה או מחסנית עם איבר אחד – הלולאה לא מוצאת זוג "אסור", והתשובה true.
•דוגמאות: עבור התשובה true; עבור התשובה false (12 מתחלק ב-4 וב-6).
כותרת הפעולה לא ניתנה בשאלה, ולכן נבחרה הכותרת שבקוד.
public static bool IsUnique(Stack<int> s)
{
Stack<int> temp1 = new Stack<int>();
bool unique = true;
while (!s.IsEmpty() && unique)
{
int x = s.Pop();
Stack<int> temp2 = new Stack<int>();
while (!s.IsEmpty()) // השוואת x לכל האיברים שמתחתיו
{
int y = s.Pop();
if (x % y == 0 || y % x == 0)
unique = false;
temp2.Push(y);
}
while (!temp2.IsEmpty()) // החזרת האיברים שמתחת ל-x
s.Push(temp2.Pop());
temp1.Push(x);
}
while (!temp1.IsEmpty()) // שחזור המחסנית
s.Push(temp1.Pop());
return unique;
}public static boolean isUnique(Stack<Integer> s)
{
Stack<Integer> temp1 = new Stack<Integer>();
boolean unique = true;
while (!s.isEmpty() && unique)
{
int x = s.pop();
Stack<Integer> temp2 = new Stack<Integer>();
while (!s.isEmpty()) // השוואת x לכל האיברים שמתחתיו
{
int y = s.pop();
if (x % y == 0 || y % x == 0)
unique = false;
temp2.push(y);
}
while (!temp2.isEmpty()) // החזרת האיברים שמתחת ל-x
s.push(temp2.pop());
temp1.push(x);
}
while (!temp1.isEmpty()) // שחזור המחסנית
s.push(temp1.pop());
return unique;
}תשובה: לכל איבר בודקים את כל האיברים שמתחתיו – אם אחד מהם מחלק אותו או מתחלק בו, מחזירים false; אחרת true. המחסנית משוחזרת בסוף.
סעיף ב
נסמן ב- את מספר האיברים במחסנית.
1. האיבר העליון מושווה ל- האיברים שמתחתיו, והם מוצאים ומוחזרים: בערך פעולות .
2. האיבר הבא מושווה ל- איברים, וכן הלאה עד 0.
3. סך הכול: השוואות (ופי 2 פעולות הוצאה/החזרה), כלומר .
4. השחזור הסופי מ-`temp1` הוא עוד פעולות – , שאינו משנה את הסדר.
במקרה הטוב (זוג "אסור" נמצא כבר בסיבוב הראשון) מספיק סיבוב אחד, ; במקרה הגרוע (מחסנית ייחודית) – .
תשובה: – כל זוג איברים נבדק פעם אחת.
שאלה 2 · תור שווה סכומים
תור "שווה סכומים", הוא תור של מספרים שלמים המכיל מספר זוגי של איברים כך שסכומם של כל שני איברים קיצוניים (ראשון + אחרון, שני + לפני אחרון וכו') זהה.
התור הבא הוא "תור שווה סכומים"
(האיבר הראשון והאיבר האחרון)
(האיבר השני והאיבר שלפני אחרון)
כתבו פעולה בשם EqualSums המקבלת תור של מספרים שלמים. אם התור הוא תור "שווה סכומים" הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר false.
מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
מעבר ראשון – העתקה לתור עזר ולמחסנית וספירה; מעבר שני – השוואת סכומי הזוגות הקיצוניים לסכום הזוג הראשון; true רק אם זוגי וכל הסכומים שווים.
נתון: תור `q` של מספרים שלמים.
מבוקש: להחזיר true אם מספר האיברים זוגי, וכל זוג איברים "קיצוניים" (ראשון + אחרון, שני + לפני אחרון וכו') נותן אותו סכום.
הרעיון: בתור אפשר לגשת רק לאיבר הראשון, ולכן צריך מבנה עזר שייתן את האיברים מהסוף להתחלה – מחסנית. אם נכניס את כל האיברים למחסנית, ה-pop הראשון ייתן את האיבר האחרון, השני – את האיבר שלפני האחרון, וכן הלאה.
1. מעבר ראשון: מוציאים כל איבר מ-`q`, מכניסים אותו לתור עזר `temp` (כדי לשחזר את `q`), דוחפים אותו גם למחסנית `st`, וסופרים את האיברים – .
2. אם אי-זוגי – התור אינו "שווה סכומים" (`ok = false`), אבל ממשיכים כדי לשחזר את התור.
3. מעבר שני: מוציאים את האיברים מ-`temp` לפי הסדר () ומחזירים כל אחד ל-`q`. בחצי הראשון () שולפים במקביל איבר מ-`st` – זה בדיוק "בן הזוג" מהסוף.
4. הסכום של הזוג הראשון () הוא הסכום הקובע `sum`; כל זוג אחר שסכומו שונה ממנו – `ok = false`.
5. בסוף `q` מכיל שוב את כל האיברים באותו סדר, ומחזירים את `ok`.
בדיקה עם הדוגמה: , והזוגות: , , , , – כולם 25, ולכן מוחזר true.
תור ריק – יש בו 0 איברים (מספר זוגי) ואין זוג שמפר את התנאי, ולכן מוחזר true.
public static bool EqualSums(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
Stack<int> st = new Stack<int>();
int n = 0;
while (!q.IsEmpty()) // מעבר ראשון: העתקה וספירה
{
int x = q.Remove();
temp.Insert(x);
st.Push(x);
n++;
}
bool ok = (n % 2 == 0);
int sum = 0;
for (int i = 0; i < n; i++) // מעבר שני: השוואה ושחזור
{
int x = temp.Remove();
q.Insert(x);
if (i < n / 2)
{
int y = st.Pop(); // האיבר המתאים מסוף התור
if (i == 0)
sum = x + y;
else if (x + y != sum)
ok = false;
}
}
return ok;
}public static boolean equalSums(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
Stack<Integer> st = new Stack<Integer>();
int n = 0;
while (!q.isEmpty()) // מעבר ראשון: העתקה וספירה
{
int x = q.remove();
temp.insert(x);
st.push(x);
n++;
}
boolean ok = (n % 2 == 0);
int sum = 0;
for (int i = 0; i < n; i++) // מעבר שני: השוואה ושחזור
{
int x = temp.remove();
q.insert(x);
if (i < n / 2)
{
int y = st.pop(); // האיבר המתאים מסוף התור
if (i == 0)
sum = x + y;
else if (x + y != sum)
ok = false;
}
}
return ok;
}תשובה: מעתיקים את התור למחסנית (שנותנת את האיברים מהסוף), משווים את סכומי הזוגות הקיצוניים לסכום הזוג הראשון, ובודקים שמספר האיברים זוגי; התור משוחזר.
סעיף ב
נסמן ב- את מספר האיברים בתור.
1. המעבר הראשון: סיבובים, ובכל אחד מספר קבוע של פעולות (remove, insert, push).
2. המעבר השני: עוד סיבובים של (remove, insert, ולכל היותר pop אחד והשוואה).
3. סך הכול סיבובים, כלומר .
תשובה: – שני מעברים על התור.
שאלה 3 · שרשרת מושלמת K
שרשרת חוליות של מספרים שלמים נקראת "שרשרת מושלמת K" אם כל ערך בה מופיע בדיוק K פעמים. כתבו פעולה המקבלת הפניה לחוליה הראשונה בשרשרת חוליות ומספר שלם וחיובי K. הפעולה תבדוק אם השרשרת היא "שרשרת מושלמת K". אם כן – הפעולה תחזיר ערך true, אם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static bool PerfectListK(Node<int> chain, int k)public static boolean perfectListK(Node<Integer> chain, int k)מהי סיבוכיות הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
לכל חוליה סופרים את מופעי הערך שלה בכל השרשרת; מונה שונה מ-K – false, אחרת true.
נתון: הפניה `chain` לחוליה הראשונה של שרשרת מספרים שלמים, ומספר שלם וחיובי `k`.
מבוקש: להחזיר true אם כל ערך בשרשרת מופיע בה בדיוק פעמים.
הרעיון: עוברים על החוליות אחת-אחת. לכל חוליה `p` סופרים, במעבר נוסף על כל השרשרת (מההתחלה), כמה פעמים מופיע הערך שלה. אם עבור ערך כלשהו המונה שונה מ- – אפשר לעצור ולהחזיר false. אם עברנו על כל החוליות ולא מצאנו ערך כזה – מחזירים true.
1. `p` עובר על כל חוליות השרשרת.
2. לכל `p`: `r` עובר על כל השרשרת מההתחלה, ו-`count` סופר את החוליות שערכן שווה לערך של `p`.
3. אם `count != k` – מחזירים false.
4. בסוף הלולאה – מחזירים true. (שרשרת ריקה: אין אף ערך שמפר את התנאי, ולכן true.)
השרשרת אינה משתנה – רק קוראים את הערכים.
דוגמה: עבור ו- – כל ערך מופיע 3 פעמים, ומוחזר true; עבור – הערך 3 מופיע פעמיים בלבד, ומוחזר false.
public static bool PerfectListK(Node<int> chain, int k)
{
Node<int> p = chain;
while (p != null)
{
int count = 0;
Node<int> r = chain;
while (r != null) // ספירת המופעים של הערך של p
{
if (r.GetValue() == p.GetValue())
count++;
r = r.GetNext();
}
if (count != k)
return false;
p = p.GetNext();
}
return true;
}public static boolean perfectListK(Node<Integer> chain, int k)
{
Node<Integer> p = chain;
while (p != null)
{
int count = 0;
Node<Integer> r = chain;
while (r != null) // ספירת המופעים של הערך של p
{
if (r.getValue().equals(p.getValue()))
count++;
r = r.getNext();
}
if (count != k)
return false;
p = p.getNext();
}
return true;
}(ב-Java משווים ערכים מטיפוס `Integer` בעזרת `equals`, כדי להשוות את הערכים ולא את ההפניות.)
תשובה: לכל חוליה סופרים את מספר המופעים של הערך שלה בכל השרשרת; אם מונה כלשהו שונה מ- – false, אחרת true.
סעיף ב
נסמן ב- את מספר החוליות בשרשרת.
1. הלולאה החיצונית עוברת על חוליות.
2. לכל אחת מהן הלולאה הפנימית עוברת על כל החוליות, ובכל צעד פעולה (השוואה וקידום).
3. סך הכול צעדים (במקרה הגרוע – כשהשרשרת "מושלמת K" ואין עצירה מוקדמת), כלומר .
תשובה: – לכל חוליה מעבר מלא על השרשרת.
שאלה 4 · המרות טיפוסים, Equals והעמסה
נתונות שתי המחלקות Car, Motorcycle. למחלקות יש תכונה אחת – מהירות מרבית.
public class Car {
private int speed;
public Car (int s) {
speed = s;
}
public int GetSpeed () {
return speed;
}
public bool Equals(Car other) {
return (other!=null) && (speed == other.speed);
}
}
public class Motorcycle {
private int speed;
public Motorcycle (int s) {
speed = s;
}
public int GetSpeed () {
return speed;
}
public bool Equals (Object other) {
return ((other != null) &&
(other is Motorcycle) &&
(speed == ((Motorcycle)other).speed));
}
}public class Car {
private int speed;
public Car (int s) {
speed = s;
}
public int getSpeed () {
return speed;
}
public boolean equals(Car other) {
return (other!=null) && (speed == other.speed);
}
}
public class Motorcycle {
private int speed;
public Motorcycle (int s) {
speed = s;
}
public int getSpeed () {
return speed;
}
public boolean equals (Object other) {
return ((other != null) &&
(other instanceof Motorcycle) &&
(speed == ((Motorcycle)other).speed));
}
}כתבו פעולה המקבלת מערך הפניות לעצמים מסוג Object. הפעולה תחזיר מספר אופנועים (עצמים מסוג Motorcycle) שמהירותם המרבית היא בין 180 ל-250 קמ"ש.
כותרת הפעולה:
public static int CountCars(Object[] vehicles)public static int countCars(Object[] vehicles)נתונה המחלקה Drive:
public class Drive {
public static void Main (string[] args) {
Car c1 = new Car (180);
Object c2 = new Car (180);
Motorcycle m1 = new Motorcycle (180);
Object m2 = new Motorcycle (180);
// ******
}
}public class Drive {
public static void main (String[] args) {
Car c1 = new Car (180);
Object c2 = new Car (180);
Motorcycle m1 = new Motorcycle (180);
Object m2 = new Motorcycle (180);
// ******
}
}בהתייחס לכל אחת מהשורות שלפניכם, כתבו מה יקרה בעקבות הוספתה לשיטה Main שלעיל, לאחר ההצהרות על האובייקטים (במקום שמסומן בכוכביות *).
אם הוספת פקודת קוד גורמת לשגיאה יש להסביר מהי השגיאה (שגיאת קומפילציה או שגיאת זמן ריצה).
(1) Console.WriteLine(c1.speed);
(2) Console.WriteLine(((Motorcycle)c2).GetSpeed());
(3) Console.WriteLine(c1.Equals(c2));
(4) Console.WriteLine(c2.Equals(c1));
(5) Console.WriteLine(m1.Equals(m2));
(6) Console.WriteLine(m2.Equals(m1));
(7) Console.WriteLine(c1.Equals((Motorcycle)m2));
(8) Console.WriteLine(c1.Equals((Car)c2));
(9) Console.WriteLine(m1.Equals((Car)c2));
(10) Console.WriteLine(m1.Equals((Motorcycle)c2));(11) System.out.println (c1.speed);
(12) System.out.println (((Motorcycle)c2).getSpeed());
(13) System.out.println (c1.equals(c2));
(14) System.out.println (c2.equals(c1));
(15) System.out.println (m1.equals(m2));
(16) System.out.println (m2.equals(m1));
(17) System.out.println (c1.equals((Motorcycle)m2));
(18) System.out.println (c1.equals((Car)c2));
(19) System.out.println (m1.equals((Car)c2));
(20) System.out.println (m1.equals((Motorcycle)c2));◂ פתרון מלא לשאלה 4
סעיף א
מעבר על המערך; לכל תא שהוא Motorcycle (is / instanceof) עם מהירות מגדילים מונה.
נתון: מערך `vehicles` של הפניות מטיפוס `Object` (בתאים יכולים להיות עצמים מסוגים שונים, וגם null).
מבוקש: מספר האופנועים (עצמים מסוג `Motorcycle`) שמהירותם המרבית בין 180 ל-250 קמ"ש (כולל הקצוות).
הרעיון: עוברים על כל תאי המערך. לכל תא בודקים קודם אם העצם הוא באמת `Motorcycle` (`is` ב-C#, `instanceof` ב-Java). רק אז מותר להמיר (casting) את ההפניה ל-`Motorcycle` ולזמן את `GetSpeed` – דרך הפניה מטיפוס `Object` אי אפשר לזמן אותה. אם המהירות בטווח – מגדילים את המונה.
•תא שמכיל null או עצם מסוג אחר (למשל `Car`) – הבדיקה מחזירה false והתא מדולג, כך שאין שגיאת המרה.
•שם הפעולה בכותרת הוא `CountCars`, אבל לפי הנוסח סופרים אופנועים.
public static int CountCars(Object[] vehicles)
{
int count = 0;
for (int i = 0; i < vehicles.Length; i++)
{
if (vehicles[i] is Motorcycle)
{
int s = ((Motorcycle)vehicles[i]).GetSpeed();
if (s >= 180 && s <= 250)
count++;
}
}
return count;
}public static int countCars(Object[] vehicles)
{
int count = 0;
for (int i = 0; i < vehicles.length; i++)
{
if (vehicles[i] instanceof Motorcycle)
{
int s = ((Motorcycle) vehicles[i]).getSpeed();
if (s >= 180 && s <= 250)
count++;
}
}
return count;
}תשובה: סופרים את התאים שהעצם בהם הוא `Motorcycle` (בדיקת טיפוס ואז המרה) ומהירותו בין 180 ל-250.
סעיף ב
1 – שגיאת קומפילציה; 2 – שגיאת זמן ריצה; 3 – false; 4 – false; 5 – true; 6 – Java: true, C#: False; 7 – false; 8 – true; 9 – false; 10 – שגיאת זמן ריצה.
נתון: ארבעה עצמים, כולם עם מהירות 180:
•`c1` – הפניה מטיפוס `Car` לעצם `Car`;
•`c2` – הפניה מטיפוס `Object` לעצם `Car`;
•`m1` – הפניה מטיפוס `Motorcycle` לעצם `Motorcycle`;
•`m2` – הפניה מטיפוס `Object` לעצם `Motorcycle`.
1. בזמן קומפילציה הקומפיילר מכיר רק את טיפוס ההפניה: הוא בודק הרשאות גישה (private), ובוחר איזו גרסה של פעולה (overload) מתאימה לטיפוס של הארגומנט.
2. המרה (casting) מ-`Object` לטיפוס אחר תמיד עוברת קומפילציה, אבל בזמן ריצה נבדק טיפוס העצם עצמו; אם העצם אינו מהטיפוס המבוקש – שגיאת זמן ריצה (`InvalidCastException` ב-C#, `ClassCastException` ב-Java).
3. ב-`Car` יש `Equals(Car)` – זו העמסה (overload) ולא דריסה של `Equals(Object)` של `Object`. היא נבחרת רק כשהארגומנט מטיפוס `Car`. אחרת נבחרת `Equals(Object)` של `Object`, שמשווה הפניות (האם זה אותו עצם).
4. ב-`Motorcycle` הפעולה היא `Equals(Object)` – אותה חתימה כמו של `Object`:
•ב-Java זו דריסה (override), ולכן גם דרך הפניה מטיפוס `Object` תופעל הגרסה של `Motorcycle` (קישור דינמי).
•ב-C# הפעולה הוגדרה בלי `override`, ולכן היא מסתירה את `Object.Equals` (הקומפיילר נותן אזהרה בלבד, לא שגיאה). דרך הפניה מטיפוס `Object` תופעל `Object.Equals` – השוואת הפניות.
מה קורה בכל שורה (C# – שורות 1-10, Java – שורות 11-20 באותו סדר):
(ב-C# ערך בוליאני מודפס כ-True / False, וב-Java כ-true / false.)
תשובה: 1 – שגיאת קומפילציה (private); 2, 10 – שגיאת זמן ריצה (המרה לא חוקית); 3 – false; 4 – false; 5 – true; 6 – ב-Java true, ב-C# False; 7 – false; 8 – true; 9 – false.
שאלה 5 · מעקב אחר פעולה על מחסנית
נתונה הפעולה:
public static void What(Stack<int> st, bool flag)
{
int x, y;
bool found;
Stack<int> temp1 = new Stack<int>();
Stack<int> temp2 = new Stack<int>();
while(!st.IsEmpty())
{
x = st.Pop();
found = false;
while(!st.IsEmpty())
{
y = st.Pop();
if(x > y == flag)
found = true;
temp1.Push(y);
}
while(!temp1.IsEmpty())
st.Push(temp1.Pop());
if(!found)
temp2.Push(x);
}
while(!temp2.IsEmpty())
st.Push(temp2.Pop());
}public static void what(Stack<Integer> st, boolean flag)
{
int x, y;
boolean found;
Stack<Integer> temp1 = new Stack<Integer>();
Stack<Integer> temp2 = new Stack<Integer>();
while(!st.isEmpty())
{
x = st.pop();
found = false;
while(!st.isEmpty())
{
y = st.pop();
if(x > y == flag)
found = true;
temp1.push(y);
}
while(!temp1.isEmpty())
st.push(temp1.pop());
if(!found)
temp2.push(x);
}
while(!temp2.isEmpty())
st.push(temp2.pop());
}
נתונה המחסנית st (8 נמצא בראש המחסנית):
מה יהיה התוכן של המחסנית st אחרי זימון הפעולה `What(st, true)` עבור המחסנית st?
תנו דוגמה למחסנית st המכילה לפחות חמישה ערכים שונים כך שתוכן המחסנית לא ישתנה אחרי זימון הפעולה `What(st, true)`.
אם לא ניתן ליצור מחסנית כזו, יש להסביר מדוע.
תנו דוגמה למחסנית st המכילה לפחות חמישה ערכים שונים כך שאחרי זימון הפעולה `What(st, false)` במחסנית יישאר רק ערך אחד.
אם לא ניתן ליצור מחסנית כזו, יש להסביר מדוע.
מה מבצעת הפעולה `What(Stack<int> st, bool flag)` באופן כללי?
◂ פתרון מלא לשאלה 5
סעיף א
מהראש לתחתית: 2, 3, 7, 10
הבנת הפעולה: בכל סיבוב של הלולאה החיצונית מוציאים את האיבר העליון `x`. הלולאה הפנימית עוברת על כל האיברים שמתחתיו (ומחזירה אותם למקומם דרך `temp1`), ומדליקה את `found` אם קיים מתחתיו `y` שעבורו `(x > y) == flag`.
•עם `flag = true`: `found` נדלק אם יש מתחת ל-`x` איבר קטן ממנו.
•אם `found` נשאר false – `x` נשמר ב-`temp2`; אחרת הוא נזרק.
בסוף מעבירים את `temp2` חזרה ל-`st`. האיברים נכנסו ל-`temp2` מהעליון לתחתון, ולכן אחרי ההעברה הם חוזרים באותו סדר יחסי כמו במחסנית המקורית.
מעקב – המחסנית מהראש לתחתית: , ו-`flag = true`:
אחרי הלולאה `temp2` מכילה (מהראש לתחתית) . מעבירים אותה ל-`st`, והסדר מתהפך שוב.
תשובה: המחסנית `st` מהראש לתחתית: (2 בראש המחסנית).
סעיף ב
אפשרי: מחסנית ממוינת בסדר עולה מהראש, למשל 1, 2, 3, 4, 5 (1 בראש).
עם `flag = true` איבר `x` נשאר רק אם אין מתחתיו איבר קטן ממנו, כלומר הוא קטן או שווה לכל האיברים שמתחתיו.
כדי שהמחסנית לא תשתנה, כל האיברים צריכים לקיים את התנאי, כלומר המחסנית צריכה להיות ממוינת בסדר עולה מהראש לתחתית (הקטן ביותר בראש).
דוגמה: המחסנית מהראש לתחתית (1 בראש המחסנית).
- 1: מתחתיו 2, 3, 4, 5 – אין קטן ממנו, נשאר.
- 2: מתחתיו 3, 4, 5 – נשאר. כך גם 3 ו-4.
- 5: אין מתחתיו איברים – נשאר.
כל האיברים נשמרים, ו-`temp2` מחזירה אותם באותו סדר.
תשובה: אפשרי – למשל מהראש לתחתית (מחסנית ממוינת בסדר עולה מהראש).
סעיף ג
אפשרי: מחסנית שהגדול ביותר בתחתיתה, למשל 3, 1, 4, 2, 9 מהראש (נשאר 9).
עם `flag = false` התנאי `(x > y) == false` פירושו . לכן `found` נדלק אם יש מתחת ל-`x` איבר גדול ממנו או שווה לו, ו-`x` נשאר רק אם הוא גדול מכל האיברים שמתחתיו.
•האיבר שבתחתית תמיד נשאר (אין מתחתיו איברים, `found` נשאר false).
•כדי שיישאר רק הוא, כל איבר אחר צריך שיהיה מתחתיו איבר גדול ממנו. זה מתקיים אם האיבר הגדול ביותר נמצא בתחתית – הוא מתחת לכל האחרים.
דוגמה: המחסנית מהראש לתחתית (3 בראש, 9 בתחתית).
- 3, 1, 4, 2 – לכל אחד מהם 9 נמצא מתחתיו וגדול ממנו, ולכן כולם נזרקים.
- 9 – אין מתחתיו איברים, נשאר.
תשובה: אפשרי – למשל מהראש לתחתית; אחרי `What(st, false)` נשאר רק 9 (כל מחסנית שהמקסימום שלה בתחתית מתאימה).
סעיף ד
מוחקת כל איבר שיש מתחתיו איבר קטן ממנו (flag אמת) או גדול/שווה לו (flag שקר); סדר הנותרים נשמר.
הפעולה עוברת על איברי המחסנית מהראש לתחתית, ולכל איבר משווה אותו לכל האיברים שמתחתיו:
•`flag = true`: נשארים רק האיברים שקטנים או שווים לכל האיברים שמתחתיהם; כל איבר שיש מתחתיו איבר קטן ממנו – נמחק.
•`flag = false`: נשארים רק האיברים שגדולים ממש מכל האיברים שמתחתיהם; כל איבר שיש מתחתיו איבר גדול ממנו או שווה לו – נמחק.
האיברים שנשארים שומרים על הסדר היחסי שלהם במחסנית, והאיבר שבתחתית נשאר תמיד. מהתחתית כלפי הראש מתקבלת סדרה יורדת, לא בהכרח ממש (כש-flag אמת) או עולה ממש (כש-flag שקר).
תשובה: הפעולה מוחקת מהמחסנית כל איבר שיש מתחתיו איבר קטן ממנו (flag = true) או איבר גדול ממנו או שווה לו (flag = false), ושומרת על סדר האיברים שנשארו.
שאלה 6 · מיקומים ומרחק בין איברים זהים בתור
•אין להשתמש במבני נתונים נוספים פרט לתור/תורים.
•יש לשמור את התור במצב מקורי בסיום הפעולה.
•אפשר להניח שקיימת הפעולה Clone המחזירה העתק של התור. כותרת הפעולה:
public static Queue<int> Clone(Queue<int> q)public static Queue<Integer> clone(Queue<Integer> q)סיבוכיות של הפעולה Clone היא כאשר n = מספר האיברים בתור.
כתבו פעולה המקבלת תור של מספרים שלמים q ומספר שלם num. הפעולה תחזיר את מיקומו הראשון של num בתוך התור. אם num לא מופיע בתור, הפעולה תחזיר ערך .
עבור התור q הבא והמספר num=3
הפעולה תחזיר 2.
כותרת הפעולה:
public static int FirstPosition(Queue<int>q, int num)public static int firstPosition(Queue<Integer>q, int num)כתבו פעולה המקבלת תור של מספרים שלמים q ומספר שלם num. הפעולה תחזיר את מיקומו האחרון של num בתוך התור. אם num לא מופיע בתור, הפעולה תחזיר ערך .
עבור התור q הבא והמספר num=3
הפעולה תחזיר 10.
כותרת הפעולה:
public static int LastPosition(Queue<int>q, int num)public static int lastPosition(Queue<Integer>q, int num)כתבו פעולה המקבלת מספר שלם וחיובי K ותור של מספרים שלמים, כל מספר בתור מופיע פעמיים בדיוק. הפעולה תבדוק אם קיים בתור זוג איברים זהים שמרחק ביניהם שווה ל-K.
המרחק בין שני איברים בתור הוא כמות האיברים הנמצאים ביניהם.
עבור התור הבא ו-K=4 הפעולה תחזיר true כי מרחק בין שני מספרים זהים (2 ו-2) הוא 4.
כותרת הפעולה:
public static bool IsDistanceK(Queue<int> q, int k)public static boolean isDistanceK(Queue<Integer> q, int k)מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א'–ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
מעבר על העתק (Clone) עם מונה מיקום; מוחזר מיקום המופע הראשון, או .
נתון: תור `q` ומספר `num`. המיקומים נספרים מ-1 מראש התור (בדוגמה: 18 במיקום 1, ה-3 המסומן במיקום 2).
מבוקש: המיקום הראשון של `num` בתור, או אם הוא לא מופיע; התור המקורי לא משתנה.
הרעיון: כדי לא לפגוע בתור המקורי עובדים על העתק שלו שמתקבל מ-`Clone` (מותר – זה תור, ואין צורך במבנה נתונים אחר). מוציאים איברים מההעתק ומונים את המיקום; בפעם הראשונה שיוצא `num` – מחזירים את המיקום. אם ההעתק התרוקן – מחזירים .
בדיקה עם הדוגמה: 18 (מיקום 1) – לא; 3 (מיקום 2) – כן, מוחזר 2.
public static int FirstPosition(Queue<int> q, int num)
{
Queue<int> copy = Clone(q); // התור המקורי לא משתנה
int pos = 1;
while (!copy.IsEmpty())
{
if (copy.Remove() == num)
return pos;
pos++;
}
return -1;
}public static int firstPosition(Queue<Integer> q, int num)
{
Queue<Integer> copy = clone(q); // התור המקורי לא משתנה
int pos = 1;
while (!copy.isEmpty())
{
if (copy.remove() == num)
return pos;
pos++;
}
return -1;
}תשובה: מעבר על העתק של התור עם מונה מיקום; מחזירים את המיקום של המופע הראשון של num, או .
סעיף ב
מעבר מלא על העתק, שמירת מיקום המופע האחרון (התחלה מ-).
נתון: תור `q` ומספר `num` (מיקומים מ-1 מראש התור).
מבוקש: המיקום האחרון של `num` בתור, או .
הרעיון: כמו בסעיף א', עובדים על העתק של התור. הפעם אי אפשר לעצור במופע הראשון – צריך לעבור על כל התור ולזכור במשתנה `last` את המיקום של המופע האחרון שנמצא עד כה. `last` מאותחל ל-, כך שאם `num` לא הופיע – זה מה שיוחזר.
בדיקה עם הדוגמה: – 3 מופיע במיקומים 2, 5, 10; אחרי המעבר `last = 10`, ומוחזר 10.
public static int LastPosition(Queue<int> q, int num)
{
Queue<int> copy = Clone(q);
int pos = 1;
int last = -1;
while (!copy.IsEmpty())
{
if (copy.Remove() == num)
last = pos; // המופע האחרון עד כה
pos++;
}
return last;
}public static int lastPosition(Queue<Integer> q, int num)
{
Queue<Integer> copy = clone(q);
int pos = 1;
int last = -1;
while (!copy.isEmpty())
{
if (copy.remove() == num)
last = pos; // המופע האחרון עד כה
pos++;
}
return last;
}תשובה: מעבר מלא על העתק של התור, שמירת המיקום של המופע האחרון של num (התחלה מ-).
סעיף ג
לכל איבר x שמוצא מהעתק – FirstPosition(copy, x) נותנת את המופע הבא; אם מחזירים true, אחרת בסוף false.
נתון: תור שכל מספר מופיע בו פעמיים בדיוק, ומספר חיובי `k`.
מבוקש: true אם יש מספר ששני המופעים שלו רחוקים זה מזה בדיוק (יש ביניהם בדיוק איברים).
הרעיון: משתמשים בפעולה מסעיף א'.
1. עובדים על העתק `copy` של התור (מ-`Clone`).
2. מוציאים מ-`copy` את האיבר הראשון `x`. עכשיו `copy` מכיל רק את האיברים שאחרי `x`.
3. `FirstPosition(copy, x)` מחזירה את המיקום של המופע הבא של `x` בתוך מה שנשאר (והיא לא משנה את `copy`). אם המיקום הוא , אז בין שני המופעים יש בדיוק איברים.
4. אם – מחזירים true. אם `x` הוא המופע השני של המספר, `FirstPosition` מחזירה ומדלגים.
5. אם עברנו על כל האיברים – מחזירים false.
לא נעשה שימוש במבנה נתונים מלבד תורים, והתור המקורי לא משתנה.
בדיקה עם הדוגמה: התור ו-:
• (מיקום 1): במה שנשאר 4 מופיע במיקום 4, מרחק .
•: מיקום 7 במה שנשאר, מרחק 6.
•: מה שנשאר הוא – 2 במיקום 5, מרחק , מוחזר true.
public static bool IsDistanceK(Queue<int> q, int k)
{
Queue<int> copy = Clone(q);
while (!copy.IsEmpty())
{
int x = copy.Remove(); // copy מכיל עכשיו את מה שאחרי x
int pos = FirstPosition(copy, x); // המופע הבא של x
if (pos != -1 && pos - 1 == k)
return true;
}
return false;
}public static boolean isDistanceK(Queue<Integer> q, int k)
{
Queue<Integer> copy = clone(q);
while (!copy.isEmpty())
{
int x = copy.remove(); // copy מכיל עכשיו את מה שאחרי x
int pos = firstPosition(copy, x); // המופע הבא של x
if (pos != -1 && pos - 1 == k)
return true;
}
return false;
}תשובה: לכל איבר מוצאים בעזרת FirstPosition את המופע הבא שלו בהמשך התור; אם מספר האיברים ביניהם () שווה ל-K – true, אחרת false.
סעיף ד
א' – ; ב' – ; ג' –
נסמן ב- את מספר האיברים בתור. נתון ש-`Clone` היא .
1. סעיף א' (FirstPosition): `Clone` – , ועוד מעבר אחד לכל היותר על ההעתק – . סך הכול .
2. סעיף ב' (LastPosition): `Clone` – , ומעבר מלא על ההעתק – . סך הכול .
3. סעיף ג' (IsDistanceK): הלולאה רצה פעמים (במקרה הגרוע). בכל סיבוב מזמנים את `FirstPosition` על התור שנשאר, שגודלו לכל היותר – . סך הכול (בפירוט: ).
תשובה: א' – ; ב' – ; ג' – .
שאלה 7 · סכום בין חוליות ורצף בעל סכום נתון

כתבו פעולה המקבלת שתי הפניות לחוליות שונות בשרשרת חוליות של מספרים שלמים. הפעולה תחזיר את סכום ערכי החוליות הנמצאות בין ההפניות שהתקבלו.
לדוגמה: עבור השרשרת שלפניכם הפעולה תחזיר 23.
כותרת הפעולה:
public static int GetSum(Node<int> p1, Node<int> p2)public static int getSum(Node<Integer> p1, Node<Integer> p2)אפשר להניח ש-p1 מצביע על חוליה שנמצאת לפני החוליה ש-p2 מצביע עליה.

כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות של מספרים שלמים חיוביים ומספר שלם חיובי num. הפעולה תבדוק אם קיים רצף חוליות שסכום הערכים שלהן שווה ל-num. אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static bool IsAmount(Node<int> ch, int num)public static boolean isAmount(Node<Integer> ch, int num)לדוגמה:
עבור השרשרת הבאה ו-num=23 או num=37 הפעולה תחזיר true,
עבור num=26 או num=19 הפעולה תחזיר false.
מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א'–ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
סכימת הערכים מ-p1 עד p2 כולל שתיהן (בדוגמה 23).
נתון: שתי הפניות `p1`, `p2` לחוליות באותה שרשרת, ו-`p1` לפני `p2`.
מבוקש: סכום הערכים של החוליות מ-`p1` עד `p2`.
הבנת הדוגמה: בשרשרת – `p1` מצביע על 6 ו-`p2` על 3. הסכום , כלומר שתי החוליות הקצוות נכללות בסכום.
הרעיון: מתקדמים עם הפניה `p` מ-`p1` ומוסיפים לסכום את הערך של כל חוליה, עד שמגיעים ל-`p2` (משווים הפניות, לא ערכים – ערכים יכולים לחזור על עצמם). בסוף מוסיפים גם את הערך של `p2`.
public static int GetSum(Node<int> p1, Node<int> p2)
{
int sum = 0;
Node<int> p = p1;
while (p != p2) // עד החוליה ש-p2 מצביע עליה
{
sum += p.GetValue();
p = p.GetNext();
}
sum += p2.GetValue(); // גם p2 נכללת בסכום
return sum;
}public static int getSum(Node<Integer> p1, Node<Integer> p2)
{
int sum = 0;
Node<Integer> p = p1;
while (p != p2) // עד החוליה ש-p2 מצביע עליה
{
sum += p.getValue();
p = p.getNext();
}
sum += p2.getValue(); // גם p2 נכללת בסכום
return sum;
}תשובה: מעבר מ-p1 עד p2 (כולל שתיהן) וסכימת הערכים; בדוגמה .
סעיף ב
מכל נקודת התחלה מצטברים ערכים כל עוד הסכום קטן מ-num; סכום שווה בדיוק ל-num – true, אחרת false.
נתון: שרשרת של מספרים שלמים חיוביים ומספר חיובי `num`.
מבוקש: true אם יש רצף חוליות צמודות שסכום ערכיו בדיוק `num`.
הרעיון: בודקים כל נקודת התחלה אפשרית `start`. מכל התחלה מוסיפים חוליות אחת אחרי השנייה לסכום. כיוון שכל המספרים חיוביים, הסכום רק גדל – ולכן ברגע שהסכום הגיע ל-`num` או עבר אותו אין טעם להמשיך מאותה התחלה:
1. `start` עובר על כל חוליות השרשרת.
2. מ-`start` מוסיפים ערכים ל-`sum` כל עוד יש חוליות ו-`sum < num`.
3. אם בסוף `sum == num` – נמצא רצף מתאים, מחזירים true.
4. אחרת עוברים להתחלה הבאה. אם אף התחלה לא הצליחה – false.
בדיקה עם הדוגמה ():
•`num = 23`: מההתחלה 6: – true.
•`num = 37`: מההתחלה 6: – true.
•`num = 26`: מכל התחלה הסכום "מדלג" מעל 26 (למשל , ; , ; , , ; ; , ) – false.
•`num = 19`: גם כאן אין רצף מתאים (למשל , , , ) – false.
public static bool IsAmount(Node<int> ch, int num)
{
Node<int> start = ch;
while (start != null)
{
int sum = 0;
Node<int> p = start;
while (p != null && sum < num) // מספרים חיוביים: הסכום רק גדל
{
sum += p.GetValue();
p = p.GetNext();
}
if (sum == num)
return true;
start = start.GetNext();
}
return false;
}public static boolean isAmount(Node<Integer> ch, int num)
{
Node<Integer> start = ch;
while (start != null)
{
int sum = 0;
Node<Integer> p = start;
while (p != null && sum < num) // מספרים חיוביים: הסכום רק גדל
{
sum += p.getValue();
p = p.getNext();
}
if (sum == num)
return true;
start = start.getNext();
}
return false;
}תשובה: לכל חוליה כנקודת התחלה מצטברים ערכים עד שהסכום מגיע ל-num או עובר אותו; אם התקבל בדיוק num – true, אחרת false.
סעיף ג
א' – ; ב' –
נסמן ב- את מספר החוליות בשרשרת.
1. סעיף א' (GetSum): מעבר אחד על החוליות שבין `p1` ל-`p2`; מספרן לכל היותר , ובכל צעד . לכן .
2. סעיף ב' (IsAmount): יש עד נקודות התחלה, ומכל אחת הלולאה הפנימית עוברת במקרה הגרוע עד סוף השרשרת – עד צעדים. סך הכול , כלומר .
תשובה: א' – ; ב' – .
שאלה 8 · סכום, תחתית מחסנית ושרשרת מחסניות
כתבו פעולה המקבלת מחסנית של מספרים שלמים ומחזירה את סכום האיברים הנמצאים במחסנית.
כותרת הפעולה:
public static int GetSumOfStack(Stack<int> st)public static int getSumOfStack(Stack<Integer> st)כתבו פעולה המקבלת מחסנית של מספרים שלמים ומחזירה את הערך של המספר האחרון שנמצא במחסנית (את הערך הנמצא בתחתית המחסנית).
כותרת הפעולה:
public static int GetStackLastValue(Stack<int> st)public static int getStackLastValue(Stack<Integer> st)שרשרת מחסניות היא שרשרת חוליות מסוג `Node<Stack<int>>` (ב-Java: `Node<Stack<Integer>>`). כלומר, הערך (value) של כל חוליה הוא הפניה למחסנית של מספרים שלמים.

כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת מחסניות.
הפעולה תחזיר תור של מספרים שלמים באופן הזה:
עבור כל מחסנית הנמצאת בשרשרת מחסניות שהאורך שלה זוגי, יוכנס לתור ערך השווה לסכום האיברים במחסנית, ואילו עבור כל מחסנית שהאורך שלה הוא אי-זוגי הפעולה תכניס לתור את הערך הנמצא בתחתית המחסנית.
עבור שרשרת המחסניות שלפניכם:
הפעולה תחזיר תור חדש: 22, 3, 15, 7
•עבור החוליה הראשונה יתקבל סכום של איברים כי אורך המחסנית זוגי.
הסכום הוא
•עבור החוליה השנייה יתקבל מספר בתחתית המחסנית (3) כי אורך המחסנית אי-זוגי.
•עבור החוליה השלישית יתקבל סכום של איברים כי אורך המחסנית זוגי.
הסכום הוא .
•עבור החוליה הרביעית יתקבל מספר בתחתית המחסנית (7) כי אורך המחסנית אי-זוגי.
כותרת הפעולה:
public static Queue<int> DoIt(Node<Stack<int>> chain)public static Queue<Integer> doIt(Node<Stack<Integer>> chain)מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף ג'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
סכימת האיברים תוך העברה למחסנית עזר ושחזור המחסנית.
מבוקש: סכום איברי המחסנית, בלי לשנות אותה.
הרעיון: מוציאים את כל האיברים, מוסיפים כל אחד לסכום ומעבירים אותו למחסנית עזר; בסוף מחזירים את האיברים מהעזר למחסנית המקורית (הסדר חוזר להיות המקורי).
public static int GetSumOfStack(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
int sum = 0;
while (!st.IsEmpty())
{
int x = st.Pop();
sum += x;
temp.Push(x);
}
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return sum;
}public static int getSumOfStack(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
int sum = 0;
while (!st.isEmpty())
{
int x = st.pop();
sum += x;
temp.push(x);
}
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return sum;
}תשובה: מעבר על המחסנית דרך מחסנית עזר, סכימת האיברים ושחזור המחסנית.
סעיף ב
העברה למחסנית עזר, קריאת הראש שלה (התחתית המקורית) ושחזור.
מבוקש: הערך שבתחתית המחסנית, בלי לשנות אותה. (מניחים שהמחסנית אינה ריקה – אחרת אין "ערך אחרון".)
הרעיון: מעבירים את כל האיברים למחסנית עזר. כך הסדר מתהפך, והאיבר שהיה בתחתית נמצא עכשיו בראש מחסנית העזר – קוראים אותו עם `Top`. אחר כך מחזירים את כל האיברים למחסנית המקורית.
public static int GetStackLastValue(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
while (!st.IsEmpty())
temp.Push(st.Pop());
int last = temp.Top(); // התחתית של st נמצאת בראש temp
while (!temp.IsEmpty()) // שחזור המחסנית
st.Push(temp.Pop());
return last;
}public static int getStackLastValue(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
while (!st.isEmpty())
temp.push(st.pop());
int last = temp.top(); // התחתית של st נמצאת בראש temp
while (!temp.isEmpty()) // שחזור המחסנית
st.push(temp.pop());
return last;
}תשובה: העברת כל האיברים למחסנית עזר, קריאת הראש שלה (התחתית המקורית) ושחזור המחסנית.
סעיף ג
לכל חוליה: אורך המחסנית זוגי – לתור נכנס סכום איבריה, אי-זוגי – הערך שבתחתיתה (בדוגמה 22, 3, 15, 7).
נתון: הפניה `chain` לחוליה הראשונה של שרשרת שבכל חוליה שלה יש מחסנית.
מבוקש: תור חדש: לכל מחסנית באורך זוגי – סכום איבריה, ולכל מחסנית באורך אי-זוגי – הערך שבתחתיתה, לפי סדר החוליות.
הרעיון: עוברים על החוליות לפי הסדר. לכל מחסנית צריך לדעת את האורך שלה – לשם כך כותבים פעולת עזר `Size` שסופרת את האיברים ומשחזרת את המחסנית. לפי זוגיות האורך מכניסים לתור את התוצאה של `GetSumOfStack` (סעיף א') או של `GetStackLastValue` (סעיף ב'). כל הפעולות משחזרות את המחסניות, כך שהשרשרת לא משתנה.
התור המוחזר: – כמו בדוגמה.
(מחסנית ריקה – אורכה 0, זוגי, ונכנס לתור הסכום 0.)
public static int Size(Stack<int> st)
{
Stack<int> temp = new Stack<int>();
int count = 0;
while (!st.IsEmpty())
{
temp.Push(st.Pop());
count++;
}
while (!temp.IsEmpty())
st.Push(temp.Pop());
return count;
}
public static Queue<int> DoIt(Node<Stack<int>> chain)
{
Queue<int> result = new Queue<int>();
Node<Stack<int>> p = chain;
while (p != null)
{
Stack<int> st = p.GetValue();
if (Size(st) % 2 == 0)
result.Insert(GetSumOfStack(st)); // אורך זוגי: הסכום
else
result.Insert(GetStackLastValue(st)); // אורך אי-זוגי: התחתית
p = p.GetNext();
}
return result;
}public static int size(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>();
int count = 0;
while (!st.isEmpty())
{
temp.push(st.pop());
count++;
}
while (!temp.isEmpty())
st.push(temp.pop());
return count;
}
public static Queue<Integer> doIt(Node<Stack<Integer>> chain)
{
Queue<Integer> result = new Queue<Integer>();
Node<Stack<Integer>> p = chain;
while (p != null)
{
Stack<Integer> st = p.getValue();
if (size(st) % 2 == 0)
result.insert(getSumOfStack(st)); // אורך זוגי: הסכום
else
result.insert(getStackLastValue(st)); // אורך אי-זוגי: התחתית
p = p.getNext();
}
return result;
}תשובה: לכל חוליה מחשבים את אורך המחסנית; אורך זוגי – מכניסים לתור את סכום האיברים, אי-זוגי – את הערך שבתחתית. בדוגמה מתקבל התור 22, 3, 15, 7.
סעיף ד
– N מספר כל האיברים במחסניות, m מספר החוליות.
נסמן ב- את מספר החוליות בשרשרת, ב- את גודל המחסנית בחוליה ה-, וב- את מספר כל האיברים בכל המחסניות.
1. לכל חוליה: `Size` מוציאה ומחזירה כל איבר – ; אחריה `GetSumOfStack` או `GetStackLastValue` – עוד ; והכנסה לתור – .
2. לכן חוליה עולה .
3. סך הכול: .
תשובה: – כל איבר בכל מחסנית מטופל מספר קבוע של פעמים, וכל חוליה פעם אחת.
שאלה 9 · מסלולים מהשורש לעלים בעץ בינרי
נתונה הפעולה Mystery. הפעולה מקבלת הפניה לשורש עץ בינרי של מספרים שלמים חיוביים bt.
public static void Mystery(BinNode<int> bt)
{
Mystery(bt, "");
}
private static void Mystery(BinNode<int> bt, string st)
{
st = st + " " + bt.GetValue();
if (bt.GetLeft()==null && bt.GetRight()==null)
{
Console.WriteLine(st);
}
else
{
if (bt.GetLeft() != null)
Mystery (bt.GetLeft(), st);
if (bt.GetRight() != null)
Mystery (bt.GetRight(), st);
}
}public static void mystery(BinNode<Integer>bt)
{
mystery(bt, "");
}
private static void mystery(BinNode<Integer> bt, String st)
{
st = st + " " + bt.getValue();
if (bt.getLeft()==null && bt.getRight()==null)
{
System.out.println(st);
}
else
{
if (bt.getLeft() != null)
mystery (bt.getLeft(), st);
if (bt.getRight() != null)
mystery (bt.getRight(), st);
}
}נתון העץ הבינרי bt1 הבא:

מה תהיה תוצאת זימון הפעולה Mystery(bt1)?
לפעולה Mystery הועבר כפרמטר הפניה לשורש של עץ בינרי bt2.
הפלט שהתקבל לאחר זימון הפעולה Mystery(bt2) היה בדיוק בסדר זה (משמאל לימין):
70 20 50 40 30
70 20 50 60
70 100 120ציירו את העץ הבינרי bt2 שהועבר כפרמטר לפעולה.
לפעולה Mystery הועבר כפרמטר הפניה לשורש של עץ חיפוש בינרי bt3.
האם ייתכן שהפלט שהתקבל אחרי זימון הפעולה Mystery(bt3) יהיה זהה לפלט שהתקבל אחרי הזימון Mystery(bt2)? אם כן – ציירו עץ חיפוש בינרי bt3. אם הדבר בלתי אפשרי – הסבירו מדוע.
מה מבצעת הפעולה Mystery באופן כללי?
◂ פתרון מלא לשאלה 9
סעיף א
שלוש שורות: " 18 6 1 3", " 18 20 17 1", " 18 20 13".
הבנת הפעולה: הפעולה עוברת על העץ בסדר תחילי (צומת, תת-עץ שמאלי, תת-עץ ימני). המחרוזת `st` צוברת את ערכי הצמתים מהשורש עד הצומת הנוכחי, כשלפני כל ערך יש רווח. כשמגיעים לעלה (אין בנים) – מדפיסים את המחרוזת. כל זימון מקבל עותק משלו של המחרוזת, ולכן אחרי החזרה מענף אחד ההמשך לענף השני מתחיל מהמסלול הנכון.
העץ bt1: 18 בשורש; בניו 6 (שמאלי) ו-20 (ימני); ל-6 בן שמאלי 1, ול-1 בן ימני 3; ל-20 בן שמאלי 17 ובן ימני 13; ל-17 בן שמאלי 1.
תשובה: יודפסו שלוש שורות (בתחילת כל שורה רווח):
18 6 1 3
18 20 17 1
18 20 13סעיף ב
70: שמאל 20, ימין 100; 20 – בן יחיד 50; 50: שמאל 40, ימין 60; 40 – בן יחיד 30; 100 – בן יחיד 120.
1. כל שורה בפלט היא מסלול מהשורש לעלה. לכן השורש הוא 70, ויש שלושה עלים: 30, 60, 120.
2. המסלולים ו- משותפים עד 50, ולכן ל-50 יש שני בנים: 40 ו-60.
3. המסלול השלישי מתפצל כבר בשורש: ל-70 שני בנים – 20 ו-100.
4. הפעולה מבקרת קודם בתת-העץ השמאלי ואחר כך בימני, ולכן העלים מודפסים משמאל לימין:
•מסלולי 20 הודפסו לפני מסלול 100, ולכן 20 הוא הבן השמאלי של 70 ו-100 הבן הימני.
•המסלול דרך 40 הודפס לפני המסלול של 60, ולכן 40 הוא הבן השמאלי של 50 ו-60 הבן הימני.
5. לצמתים 20, 40, 100 יש בן אחד בלבד (50, 30, 120). הפלט אינו קובע אם הבן הזה שמאלי או ימני – כל בחירה נותנת אותו פלט. בציור בחרנו: 50 בן ימני של 20, 30 בן שמאלי של 40, 120 בן ימני של 100.
70
/ \
20 100
\ \
50 120
/ \
40 60
/
30תשובה: השורש 70 עם בן שמאלי 20 ובן ימני 100; ל-20 בן יחיד 50; ל-50 בן שמאלי 40 ובן ימני 60; ל-40 בן יחיד 30; ל-100 בן יחיד 120 (הצד של בן יחיד אינו נקבע מהפלט).
סעיף ג
כן: 70 (20, 100); 50 בן ימני של 20; 50 (40, 60); 30 בן שמאלי של 40; 120 בן ימני של 100.
כן, זה אפשרי. צריך לבדוק שאפשר לבחור את הצדדים של הבנים היחידים כך שהעץ מסעיף ב' יהיה עץ חיפוש בינרי (בכל צומת: כל הערכים בתת-העץ השמאלי קטנים ממנו, וכל הערכים בתת-העץ הימני גדולים ממנו).
1. השורש 70: תת-העץ השמאלי – כולם קטנים מ-70; תת-העץ הימני – גדולים מ-70. מתאים (וזה גם הסדר שהפלט מחייב).
2. 20: הבן היחיד 50 גדול מ-20, ולכן חייב להיות בן ימני; כל תת-העץ שלו גדול מ-20.
3. 50: 40 בן שמאלי () ו-60 בן ימני () – בדיוק הסדר שהפלט מחייב.
4. 40: הבן היחיד 30 קטן מ-40, ולכן בן שמאלי; וגם , כנדרש מצומת שנמצא בתת-העץ הימני של 20.
5. 100: הבן היחיד 120 גדול מ-100, ולכן בן ימני.
6. גם 60 מתאים לכל אבותיו: , , .
כל התנאים מתקיימים, ולכן עץ החיפוש bt3 הוא בדיוק העץ שצויר בסעיף ב' (ובעץ חיפוש הצדדים נקבעים באופן יחיד):
70
/ \
20 100
\ \
50 120
/ \
40 60
/
30זה אותו עץ כמו bt2, ולכן גם המעבר עליו זהה: העלים 30, 60, 120 מודפסים באותו סדר, והפלט זהה לפלט של bt2.
תשובה: כן – עץ החיפוש: 70 (שמאל 20, ימין 100); 20 – בן ימני 50; 50 – שמאל 40, ימין 60; 40 – בן שמאלי 30; 100 – בן ימני 120.
סעיף ד
מדפיסה את כל המסלולים מהשורש לעלים, כל מסלול בשורה, לפי סדר העלים משמאל לימין.
הפעולה עוברת על העץ בסדר תחילי ושומרת את המסלול מהשורש לצומת הנוכחי. בכל פעם שהיא מגיעה לעלה היא מדפיסה בשורה נפרדת את המסלול – כל הערכים מהשורש עד העלה (לפני כל ערך רווח). העלים מטופלים משמאל לימין.
תשובה: הפעולה מדפיסה את כל המסלולים מהשורש לעלים של העץ, כל מסלול בשורה נפרדת, לפי סדר העלים משמאל לימין.
שאלה 10 · ירושה, בנאי מעתיק והפניות משותפות
בבית החולים, לכל רופא מתמחה הוצמד רופא ותיק מנוסה. כדי לנהל את תהליך ההתמחות פותחו המחלקות האלה: Doctor, Intern, Test.
המחלקה Doctor מתארת רופא:
public class Doctor {
protected string name;// שם
protected string specialization;// התמחות
protected int numOfPatients; // מספר חולים
public Doctor(string name, string spec) {
this.name = name;
this.specialization = spec;
this.numOfPatients = 0;
}
public Doctor(string name, string spec, int num) {
this.name = name;
this.specialization = spec;
this.numOfPatients = num;
}
public Doctor(Doctor other) {
this.name = other.name;
this.specialization = other.specialization;
this.numOfPatients = other.numOfPatients;
}
public void AddPatients(int num)
{
if(numOfPatients + num >=0)
this.numOfPatients += num;
}
public string ToString(){
return "Doctor:" + name + ", " + specialization+ ","
+numOfPatients;
}
}public class Doctor {
protected String name;// שם
protected String specialization;// התמחות
protected int numOfPatients; // מספר חולים
public Doctor(String name, String spec) {
this.name = name;
this.specialization = spec;
this.numOfPatients = 0;
}
public Doctor(String name, String spec, int num) {
this.name = name;
this.specialization = spec;
this.numOfPatients = num;
}
public Doctor(Doctor other) {
this.name = other.name;
this.specialization = other.specialization;
this.numOfPatients = other.numOfPatients;
}
public void addPatients(int num)
{
if(numOfPatients + num >=0)
this.numOfPatients += num;
}
public String toString(){
return "Doctor:" + name + ", " + specialization+ ","
+numOfPatients;
}
}במחלקה הוגדרו גם פעולות set/Get לכל התכונות.
המחלקה Intern מתארת מתמחה:
public class Intern : Doctor {
private Doctor mentor;
public Intern(string name, string spec, Doctor mentor):
base(name, spec){
this.mentor = mentor;
this.numOfPatients = mentor.numOfPatients/2;
}
public Doctor GetMentor(){return mentor;}
public string ToString() {
return "Intern: " + name + ", " + specialization +
", Mentor: " + mentor.name +", " +
mentor.numOfPatients +"," + numOfPatients;
}
}public class Intern extends Doctor {
private Doctor mentor;
public Intern(String name, String spec, Doctor mentor) {
super(name, spec);
this.mentor = mentor;
this.numOfPatients = mentor.numOfPatients/2;
}
public Doctor getMentor(){return mentor;}
public String toString() {
return "Intern: " + name + ", " + specialization +
", Mentor: " + mentor.name +", " +
mentor.numOfPatients +"," + numOfPatients;
}
}נתונה הפעולה הראשית main אשר נמצאת במחלקה Test. עקבו אחרי הביצוע של הפעולה main ורשמו מה יהיו ערכי התכונות של כל עצם שנוצר במהלך הביצוע.
public static void Main(string[] args) {
Doctor[] d = new Doctor[9];
d[0] = new Doctor("Dr. Cohen", "Cardiology",12);
d[1] = new Doctor("Dr. Levy", "Neurology");
d[2] = new Doctor("Dr. Sharon", "Pediatrics",8);
d[3] = new Intern("Dani", "Cardiology", new Doctor(d[0]));
d[4] = new Intern("Yael", "Surgery", d[0]);
d[5] = new Intern("Avi", "Pediatrics", new Doctor(d[2]));
d[6] = new Intern("Ruth", "Oncology", d[2]);
d[7] = new Intern("Noam", "Cardiology", new Doctor(d[1]));
d[8] = new Intern("Maya", "Neurology", new Doctor(d[0]));
for (int i=0; I < d.Length; i++) {
Console.WriteLine(d[i]);
}
d[0] = new Doctor("Dr. Goldman","Neurology",20);
d[2].SetName("Dr. Galper");
d[2].AddPatients(100);
d[3].AddPatients(200);
d[5].AddPatients(100);
Console.WriteLine("After change:");
for (int i=0; i < d.Length; i++) {
Console.WriteLine(d[i]);
}
}public static void main(String[] args) {
Doctor[] d = new Doctor[9];
d[0] = new Doctor("Dr. Cohen", "Cardiology",12);
d[1] = new Doctor("Dr. Levy", "Neurology");
d[2] = new Doctor("Dr. Sharon", "Pediatrics",8);
d[3] = new Intern("Dani", "Cardiology", new Doctor(d[0]));
d[4] = new Intern("Yael", "Surgery", d[0]);
d[5] = new Intern("Avi", "Pediatrics", new Doctor(d[2]));
d[6] = new Intern("Ruth", "Oncology", d[2]);
d[7] = new Intern("Noam", "Cardiology", new Doctor(d[1]));
d[8] = new Intern("Maya", "Neurology", new Doctor(d[0]));
for (int i=0; i<d.length; i++) {
System.out.println(d [i]);
}
d[0] = new Doctor("Dr. Goldman","Neurology",20);
d[2].setName("Dr. Galper");
d[2].addPatients(100);
d[3].addPatients(200);
d[5].addPatients(100);
System.out.println("After change:");
for (int i=0; i<d.length; i++) {
System.out.println(d[i]);
}
}מהו הפלט של הפעולה Main?
כתבו פעולה חיצונית המקבלת מערך רופאים ומדפיסה את שמותיהם של כל המתמחים אשר ההתמחות שלהם שונה מההתמחות של המנחים שלהם.
כותרת הפעולה:
public static void PrintNotSameSpec(Doctor[] d)public static void printNotSameSpec(Doctor[] d)◂ פתרון מלא לשאלה 10
סעיף א
14 עצמים (טבלה בפתרון); בסוף: C = Dr. Galper עם 108, Dani – 206, Avi – 104, d[0] = Dr. Goldman (Neurology, 20).
1. `new Doctor(d[0])` – בנאי מעתיק: נוצר עצם חדש עם אותם ערכים. שינוי מאוחר של העצם המקורי לא משפיע על העותק.
2. `new Intern(..., d[0])` – המנחה הוא אותו עצם ש-`d[0]` מפנה אליו (הפניה משותפת), ולכן שינוי בו נראה גם דרך המתמחה.
3. בבנאי של `Intern` הבנאי של `Doctor` מאפס את `numOfPatients`, ואז הוא נקבע ל-`mentor.numOfPatients/2` (חילוק שלמים).
4. `d[0] = new Doctor(...)` משנה רק את התא במערך – העצם הקודם ממשיך להתקיים, ומתמחים שמפנים אליו עדיין מפנים אליו.
5. `AddPatients(num)` מוסיפה רק אם התוצאה אינה שלילית – כאן כל ההוספות חיוביות.
נסמן את העצמים באותיות. הערכים מוצגים בזמן היצירה ובסוף הביצוע:
1. `d[0]` מפנה לעצם חדש K (Dr. Goldman, Neurology, 20). העצם A לא השתנה, ו-F (Yael) עדיין מפנה אליו.
2. `d[2].SetName("Dr. Galper")` – משנה את C. גם H (Ruth) רואה את השינוי, כי המנחה שלה הוא C עצמו; G (Avi) לא – המנחה שלו הוא העותק D2.
3. `d[2].AddPatients(100)` – ב-C: .
4. `d[3].AddPatients(200)` – ב-E (Dani): .
5. `d[5].AddPatients(100)` – ב-G (Avi): .
תשובה: נוצרו 14 עצמים: 9 עצמים במערך, 4 עותקים של רופאים (D1-D4) ו-Dr. Goldman. ערכי כל עצם מופיעים בטבלה. בסוף: C – Dr. Galper עם 108 חולים, Dani עם 206 חולים, Avi עם 104 חולים, ו-`d[0]` הוא Dr. Goldman.
סעיף ב
9 שורות לפני "After change:" ו-9 אחריה, כמפורט בפתרון (למשל Intern: Ruth, Oncology, Mentor: Dr. Galper, 108,4).
מדפיסים כל תא לפי `ToString` של העצם (קישור דינמי: עצם `Intern` מודפס לפי `ToString` של `Intern`).
•תבנית רופא: `Doctor:` + שם + `, ` + התמחות + `,` + מספר חולים.
•תבנית מתמחה: `Intern: ` + שם + `, ` + התמחות + `, Mentor: ` + שם המנחה + `, ` + חולי המנחה + `,` + חולי המתמחה.
ההדפסה הראשונה – לפי ערכי היצירה בטבלה של סעיף א'.
ההדפסה השנייה – אחרי השינויים:
•שורה 1: `d[0]` הוא Dr. Goldman.
•שורה 3: C – השם Dr. Galper ו-108 חולים.
•שורה 4: Dani – 206 חולים; המנחה שלו הוא העותק D1 (Dr. Cohen, 12) – לא השתנה.
•שורה 5: Yael – המנחה A (Dr. Cohen, 12) – לא השתנה, למרות ש-`d[0]` מפנה עכשיו לעצם אחר.
•שורה 6: Avi – 104 חולים; המנחה העותק D2 – עדיין Dr. Sharon, 8.
•שורה 7: Ruth – המנחה הוא C עצמו, ולכן מודפס Dr. Galper, 108.
הערה לנוסח C#: כדי שהקוד יעבור הידור ויפעל לפי הכוונה, צריך לתקן שלושה דברים. בלולאה הראשונה נכתב `I` (אות גדולה) במקום `i`. ב-C# מחלקה יורשת אינה רשאית לגשת לתכונה protected דרך הפניה מטיפוס `Doctor` (`mentor.numOfPatients`, `mentor.name`), ולכן צריך להשתמש בפעולות Get. כמו כן, `ToString` צריכה להיות מוגדרת עם `override` כדי ש-`Console.WriteLine` תפעיל אותה. הפלט שלהלן הוא לפי הכוונה, והוא זהה לפלט של נוסח Java.
Doctor:Dr. Cohen, Cardiology,12
Doctor:Dr. Levy, Neurology,0
Doctor:Dr. Sharon, Pediatrics,8
Intern: Dani, Cardiology, Mentor: Dr. Cohen, 12,6
Intern: Yael, Surgery, Mentor: Dr. Cohen, 12,6
Intern: Avi, Pediatrics, Mentor: Dr. Sharon, 8,4
Intern: Ruth, Oncology, Mentor: Dr. Sharon, 8,4
Intern: Noam, Cardiology, Mentor: Dr. Levy, 0,0
Intern: Maya, Neurology, Mentor: Dr. Cohen, 12,6
After change:
Doctor:Dr. Goldman, Neurology,20
Doctor:Dr. Levy, Neurology,0
Doctor:Dr. Galper, Pediatrics,108
Intern: Dani, Cardiology, Mentor: Dr. Cohen, 12,206
Intern: Yael, Surgery, Mentor: Dr. Cohen, 12,6
Intern: Avi, Pediatrics, Mentor: Dr. Sharon, 8,104
Intern: Ruth, Oncology, Mentor: Dr. Galper, 108,4
Intern: Noam, Cardiology, Mentor: Dr. Levy, 0,0
Intern: Maya, Neurology, Mentor: Dr. Cohen, 12,6סעיף ג
לכל Intern במערך: אם ההתמחות שלו שונה מזו של המנחה – מדפיסים את שמו (במערך מהשאלה: Yael, Ruth, Noam, Maya).
הרעיון: עוברים על המערך. רק לתאים שהעצם בהם הוא מתמחה (`is Intern` ב-C#, `instanceof Intern` ב-Java) יש מנחה, ולכן בודקים קודם את הטיפוס ורק אז ממירים ל-`Intern`. משווים את ההתמחות של המתמחה להתמחות של המנחה (בעזרת פעולות ה-Get, כי התכונות protected), ואם הן שונות – מדפיסים את שם המתמחה. תא null או רופא רגיל – מדלגים.
בדיקה עם המערך מהסעיף הקודם: Dani – Cardiology כמו המנחה (לא מודפס); Yael – Surgery מול Cardiology (מודפס); Avi – Pediatrics כמו המנחה (לא); Ruth – Oncology מול Pediatrics (מודפס); Noam – Cardiology מול Neurology (מודפס); Maya – Neurology מול Cardiology (מודפס). יודפסו: Yael, Ruth, Noam, Maya.
public static void PrintNotSameSpec(Doctor[] d)
{
for (int i = 0; i < d.Length; i++)
{
if (d[i] is Intern)
{
Intern intern = (Intern)d[i];
string mentorSpec = intern.GetMentor().GetSpecialization();
if (!intern.GetSpecialization().Equals(mentorSpec))
Console.WriteLine(intern.GetName());
}
}
}public static void printNotSameSpec(Doctor[] d)
{
for (int i = 0; i < d.length; i++)
{
if (d[i] instanceof Intern)
{
Intern intern = (Intern) d[i];
String mentorSpec = intern.getMentor().getSpecialization();
if (!intern.getSpecialization().equals(mentorSpec))
System.out.println(intern.getName());
}
}
}תשובה: לכל תא שהוא Intern משווים את ההתמחות שלו להתמחות של המנחה ומדפיסים את שמו אם הן שונות (במערך מהשאלה: Yael, Ruth, Noam, Maya).
שאלה 11 · מוקד חירום – רשימות קריאות לפי סוג
מוקד החירום העירוני מקבל קריאות לעזרה בעקבות מצבי חירום שונים. בעת קבלת הקריאה נקבעת רמת הדחיפות של האירוע (1 – גבוהה, 2 – בינונית, 3 – נמוכה) וסוג האירוע (1 – שריפה, 2 – תאונה, 3 – חילוץ, 4 – פלילי, 5 – ביטחוני).
המחלקה Call מייצגת קריאה לעזרה.
תכונות המחלקה:
private int type; // סוג אירוע חירום
private string location; // אזור
private string description; // תיאור
private string callerName; // שם המתקשר
private int priority; // רמת הדחיפותprivate int type; // סוג אירוע חירום
private String location; // אזור
private String description; // תיאור
private String callerName; // שם המתקשר
private int priority; // רמת הדחיפותבמחלקה הוגדרה פעולה בונה (constructor) המקבלת פרמטרים לכל תכונה וכן פעולות Get/Set.
המחלקה EmergencyList מייצגת רשימת קריאות לאירועי חירום.
כתבו את כותרת המחלקה EmergencyList ואת התכונות שלה.
המחלקה EmergencyCenter מייצגת את מוקד החירום. למחלקה תכונה אחת – מערך של רשימות הקריאות לפי סוג אירוע החירום:
private EmergencyList[] arr = new EmergencyList[6];(השורה זהה בשתי השפות.)
התא 0 מיועד לרשימת קריאות שהטיפול בהן הסתיים.
כתבו במחלקה EmergencyCenter פעולה המקבלת את הפרטים של הקריאה ומוסיפה אותה לרשימת קריאות <u>בהתאם לסוג האירוע</u> שלה.
כותרת הפעולה:
public void AddCall(int type, string location, string
description, string callerName, int priority)public void addCall(int type, String location, String
description, String callerName, int priority)כתבו במחלקה EmergencyCenter פעולה המקבלת סוג אירוע type ומחזירה קריאה לאירוע הדחוף ביותר מסוג זה. הפעולה גם תמחק את הקריאה מרשימת הקריאות ותעביר אותה לרשימת הקריאות שהטיפול בהן הסתיים.
אם יש מספר קריאות באותה רמת הדחיפות (הגבוהה ביותר), יש להחזיר את הקריאה שהתקבלה ראשונה. אם אין שום קריאה מסוג type, הפעולה תחזיר null.
כותרת הפעולה:
public Call MostUrgentCall(int type)public Call mostUrgentCall(int type)כתבו במחלקה EmergencyCenter פעולה המקבלת אזור בעיר (location) ומדפיסה עבור כל סוג אירוע את מספר הקריאות באזור זה.
◂ פתרון מלא לשאלה 11
סעיף א
`public class EmergencyList` עם התכונה `Queue<Call> calls` – הקריאות לפי סדר קבלתן.
הבחירה: את הרשימה מייצגים בעזרת תור של קריאות: קריאה חדשה נכנסת לסוף התור, ולכן הקריאות שמורות לפי סדר קבלתן – הקריאה שהתקבלה ראשונה נמצאת בראש התור. זה חשוב לסעיף ג', שבו בין קריאות באותה רמת דחיפות בוחרים את זו שהתקבלה ראשונה.
התכונה היחידה הנחוצה היא התור. נוסיף בנאי שיוצר תור ריק, פעולה שמחזירה את התור ופעולה להוספת קריאה – בהן ישתמשו הפעולות של `EmergencyCenter`.
public class EmergencyList
{
private Queue<Call> calls; // הקריאות לפי סדר קבלתן (הראשונה שהתקבלה – בראש התור)
public EmergencyList()
{
calls = new Queue<Call>();
}
public Queue<Call> GetCalls()
{
return calls;
}
public void Add(Call c) // הוספת קריאה לסוף הרשימה
{
calls.Insert(c);
}
}public class EmergencyList
{
private Queue<Call> calls; // הקריאות לפי סדר קבלתן (הראשונה שהתקבלה – בראש התור)
public EmergencyList()
{
calls = new Queue<Call>();
}
public Queue<Call> getCalls()
{
return calls;
}
public void add(Call c) // הוספת קריאה לסוף הרשימה
{
calls.insert(c);
}
}תשובה: `public class EmergencyList` עם התכונה `private Queue<Call> calls` – תור הקריאות לפי סדר קבלתן (ובנוסף בנאי, GetCalls ו-Add).
סעיף ב
יצירת `new Call(...)` והוספתה לרשימה `arr[type]`.
הרעיון: יוצרים עצם `Call` חדש מהפרטים שהתקבלו (בבנאי שמקבל פרמטר לכל תכונה, לפי סדר התכונות במחלקה), ומוסיפים אותו לרשימה שבתא `arr[type]` – התא של סוג האירוע (1-5).
המערך נוצר עם `new EmergencyList[6]`, ולכן בהתחלה כל התאים null. בבנאי של `EmergencyCenter` יוצרים בכל תא רשימה ריקה, כדי שאפשר יהיה להוסיף אליה.
public class EmergencyCenter
{
private EmergencyList[] arr = new EmergencyList[6];
public EmergencyCenter()
{
for (int i = 0; i < arr.Length; i++)
arr[i] = new EmergencyList();
}
public void AddCall(int type, string location, string
description, string callerName, int priority)
{
Call c = new Call(type, location, description, callerName, priority);
arr[type].Add(c);
}
}public class EmergencyCenter
{
private EmergencyList[] arr = new EmergencyList[6];
public EmergencyCenter()
{
for (int i = 0; i < arr.length; i++)
arr[i] = new EmergencyList();
}
public void addCall(int type, String location, String
description, String callerName, int priority)
{
Call c = new Call(type, location, description, callerName, priority);
arr[type].add(c);
}
}תשובה: יוצרים `new Call(type, location, description, callerName, priority)` ומוסיפים לסוף הרשימה `arr[type]` (הרשימות נוצרות בבנאי של EmergencyCenter).
סעיף ג
מציאת הקריאה עם priority מינימלי (הראשונה בשוויון) בתור של arr[type], הוצאתה והעברתה ל-arr[0]; null אם אין.
נתון: סוג אירוע `type`.
מבוקש: להחזיר את הקריאה הדחופה ביותר מסוג זה (רמת דחיפות 1 היא הגבוהה ביותר, כלומר הערך הקטן ביותר של `priority`), ובשוויון – את זו שהתקבלה ראשונה. הקריאה נמחקת מהרשימה `arr[type]` ומועברת לרשימה `arr[0]`. אם אין קריאות – מחזירים null.
הרעיון: שני מעברים על התור של `arr[type]`:
1. מעבר ראשון – חיפוש: מעבירים את כל הקריאות לתור עזר `temp`, ושומרים ב-`best` את הקריאה עם ה-`priority` הקטן ביותר. מחליפים את `best` רק כשנמצאת קריאה עם ערך קטן ממש – כך בשוויון נשארת הקריאה הראשונה (הקריאות עוברות לפי סדר קבלתן).
2. מעבר שני – מחיקה: מחזירים את הקריאות מ-`temp` לתור המקורי, חוץ מהעצם `best` עצמו (השוואת הפניות). סדר שאר הקריאות נשמר.
3. אם נמצאה קריאה – מוסיפים אותה לרשימה `arr[0]` (טיפול הסתיים) ומחזירים אותה. אם התור היה ריק, `best` נשאר null ומוחזר null.
public Call MostUrgentCall(int type)
{
Queue<Call> q = arr[type].GetCalls();
Queue<Call> temp = new Queue<Call>();
Call best = null;
while (!q.IsEmpty()) // מעבר ראשון: מציאת הדחופה ביותר
{
Call c = q.Remove();
if (best == null || c.GetPriority() < best.GetPriority())
best = c;
temp.Insert(c);
}
while (!temp.IsEmpty()) // מעבר שני: החזרה בלי best
{
Call c = temp.Remove();
if (c != best)
q.Insert(c);
}
if (best != null)
arr[0].Add(best); // מעבר לרשימת הקריאות שטופלו
return best;
}public Call mostUrgentCall(int type)
{
Queue<Call> q = arr[type].getCalls();
Queue<Call> temp = new Queue<Call>();
Call best = null;
while (!q.isEmpty()) // מעבר ראשון: מציאת הדחופה ביותר
{
Call c = q.remove();
if (best == null || c.getPriority() < best.getPriority())
best = c;
temp.insert(c);
}
while (!temp.isEmpty()) // מעבר שני: החזרה בלי best
{
Call c = temp.remove();
if (c != best)
q.insert(c);
}
if (best != null)
arr[0].add(best); // מעבר לרשימת הקריאות שטופלו
return best;
}דוגמה: אם ברשימת השריפות (סוג 1) התקבלו לפי הסדר קריאות עם דחיפות 2, 1, 1 – תוחזר הקריאה השנייה (הראשונה מבין שתי הקריאות בדחיפות 1), והיא תעבור ל-`arr[0]`.
תשובה: מעבר על תור הקריאות של `arr[type]` ומציאת הקריאה עם ה-priority הקטן ביותר (הראשונה בשוויון), הוצאתה מהתור והוספתה ל-`arr[0]`; אם אין קריאות – null.
סעיף ד
לכל סוג 1-5: ספירת הקריאות בתור של arr[t] שהאזור שלהן location (עם שחזור) והדפסת המונה.
נתון: אזור `location`.
מבוקש: לכל סוג אירוע (1 עד 5) להדפיס כמה קריאות מהאזור הזה יש ברשימה שלו.
הרעיון: לכל תא `t` מ-1 עד 5 עוברים על תור הקריאות של `arr[t]` דרך תור עזר (כדי לשחזר אותו), וסופרים קריאות שהאזור שלהן שווה ל-`location` (השוואת מחרוזות לפי תוכן). אחרי כל סוג מדפיסים את המונה. התא 0 (קריאות שהטיפול בהן הסתיים) אינו שייך לסוג אירוע מסוים, ולכן לא נספר.
כותרת הפעולה לא ניתנה בשאלה, ולכן נבחרה הכותרת שבקוד.
public void PrintCallsInLocation(string location)
{
for (int t = 1; t < arr.Length; t++)
{
Queue<Call> q = arr[t].GetCalls();
Queue<Call> temp = new Queue<Call>();
int count = 0;
while (!q.IsEmpty())
{
Call c = q.Remove();
if (c.GetLocation().Equals(location))
count++;
temp.Insert(c);
}
while (!temp.IsEmpty()) // שחזור הרשימה
q.Insert(temp.Remove());
Console.WriteLine("Type " + t + ": " + count);
}
}public void printCallsInLocation(String location)
{
for (int t = 1; t < arr.length; t++)
{
Queue<Call> q = arr[t].getCalls();
Queue<Call> temp = new Queue<Call>();
int count = 0;
while (!q.isEmpty())
{
Call c = q.remove();
if (c.getLocation().equals(location))
count++;
temp.insert(c);
}
while (!temp.isEmpty()) // שחזור הרשימה
q.insert(temp.remove());
System.out.println("Type " + t + ": " + count);
}
}תשובה: לכל סוג אירוע 1-5 סופרים בתור שלו את הקריאות שהאזור שלהן הוא location (תוך שחזור התור) ומדפיסים את המונה.
שאלה 12 · רקורסיה על שרשרת: מחיקה וספירת מופעים
נתונה השרשרת הבאה:

נתונות שתי הפעולות הרקורסיביות הבאות:
public static int One(Node<int> ch, int num)
{
if(ch.GetNext()!= null)
{
if(ch.GetNext().GetValue() == num)
{
ch.SetNext(ch.GetNext().GetNext());
return 1 + One(ch, num);
}
else
{
ch = ch.GetNext();
return One(ch, num);
}
}
else
return 0;
}
public static void Two(Node<int> ch)
{
if(ch != null)
{
int x = One(ch, ch.GetValue());
ch.SetNext(new Node<int> (x+1, ch.GetNext()));
ch = ch.GetNext();
Two(ch.GetNext());
}
}public static int one(Node<Integer> ch, int num)
{
if(ch.getNext()!= null)
{
if(ch.getNext().getValue() == num)
{
ch.setNext(ch.getNext().getNext());
return 1 + one(ch, num);
}
else
{
ch = ch.getNext();
return one(ch, num);
}
}
else
return 0;
}
public static void two(Node<Integer> ch)
{
if(ch != null)
{
int x = one(ch, ch.getValue());
ch.setNext(new Node<Integer> (x+1, ch.getNext()));
ch = ch.getNext();
two(ch.getNext());
}
}מה תהיה תוצאת זימון הפעולה One(ch1, 14)?
מה מבצעת הפעולה One באופן כללי?
עקבו אחרי זימון הפעולה Two(ch1) ורשמו איך תיראה השרשרת אחרי זימון.
מה מבצעת הפעולה Two באופן כללי?
◂ פתרון מלא לשאלה 12
סעיף א
3; השרשרת אחרי הזימון: 10, 12, 12, 10, 12.
הבנת הפעולה: `One` בודקת תמיד את החוליה שאחרי `ch`:
•אם הערך שלה שווה ל-`num` – "מדלגים" עליה (`ch.SetNext(...)`), כלומר מוחקים אותה מהשרשרת, ומזמנים שוב מאותה חוליה `ch` (כי עכשיו יש אחריה חוליה אחרת) ומוסיפים 1.
•אחרת מתקדמים לחוליה הבאה בלי להוסיף.
•כשאין חוליה הבאה – מחזירים 0.
השרשרת בהתחלה: . כדי להבחין בין חוליות עם אותו ערך נסמן אותן לפי מיקומן: .
הערכים חוזרים מלמטה למעלה: .
תשובה: הפעולה מחזירה 3, והשרשרת אחרי הזימון: (נמחקו שלוש החוליות עם הערך 14).
סעיף ב
מוחקת אחרי ch את כל החוליות שערכן num ומחזירה את מספר החוליות שנמחקו.
הפעולה עוברת על השרשרת מהחוליה שאחרי `ch` ועד סופה, מוחקת ממנה כל חוליה שהערך שלה שווה ל-`num`, ומחזירה את מספר החוליות שנמחקו. החוליה `ch` עצמה לא נבדקת ולא נמחקת.
תשובה: One מוחקת מהשרשרת (אחרי החוליה ch) את כל החוליות שערכן num ומחזירה כמה חוליות נמחקו.
סעיף ג
10, 2, 14, 3, 12, 3
הבנת הפעולה: בכל זימון של `Two` עם חוליה `ch`:
1. `One(ch, ch.GetValue())` מוחקת את כל החוליות שאחרי `ch` עם אותו ערך כמו `ch`, ומחזירה כמה נמחקו – `x`.
2. מוסיפים מיד אחרי `ch` חוליה חדשה עם הערך `x+1` – זה מספר המופעים של הערך בשרשרת המקורית (המופע של `ch` עצמה ועוד `x` שנמחקו).
3. `ch` מתקדם לחוליה החדשה, והזימון הרקורסיבי ממשיך מהחוליה שאחריה – החוליה הבאה מהשרשרת המקורית.
השרשרת בהתחלה: .
תשובה: אחרי `Two(ch1)` השרשרת היא .
סעיף ד
משאירה כל ערך שונה פעם אחת (לפי סדר ההופעה) ואחריו חוליה עם מספר מופעיו בשרשרת.
הפעולה משאירה בשרשרת רק את המופע הראשון של כל ערך (לפי סדר ההופעה), ומיד אחריו מוסיפה חוליה שהערך שלה הוא מספר הפעמים שהערך הופיע בשרשרת המקורית. בדוגמה: 10 הופיע פעמיים, 14 – שלוש פעמים, 12 – שלוש פעמים, ולכן התקבל .
תשובה: Two הופכת את השרשרת לרשימת זוגות "ערך, מספר המופעים שלו" – כל ערך שונה מופיע פעם אחת, לפי סדר ההופעה הראשונה, ואחריו מספר הפעמים שהופיע.