מבחן מה"ט מבנה נתונים ותכנות מונחה עצמים 97105 - אביב 2024 מועד א'
הנדסת תוכנה · סמל 97105 · 12 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט במבנה נתונים ותכנות מונחה עצמים, אביב 2024 מועד א', כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 12)
בכל מבחן 12 שאלות.
שאלות 5-1: יש לענות על שלוש שאלות בלבד. ערך כל שאלה 16 נקודות.
שאלות 10-6: יש לענות על שתי שאלות בלבד. ערך כל שאלה 18 נקודות.
שאלות 12-11: יש לענות על אחת בלבד. ערך שאלה 16 נקודות.
נקודה אחת תינתן על הערכה.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מחסנית אחידה: בדיקת זוגיות כל הערכים
מחסנית של מספרים שלמים וחיוביים נקראת "מחסנית אחידה" אם כל הערכים שנמצאים בה הם מספרים זוגיים או כל הערכים שנמצאים בה הם מספרים אי-זוגיים.
כתבו פעולה המקבלת מחסנית של מספרים שלמים ובודקת אם היא "מחסנית אחידה".
כותרת הפעולה:
public static boolean isUniform(Stack<Integer> st)public static bool IsUniform(Stack<int> st)מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 1
סעיף א
הפעולה isUniform שלהלן: משווה את הזוגיות של כל איבר לזוגיות של האיבר העליון, ומשחזרת את המחסנית בעזרת מחסנית עזר.
הרעיון: מחסנית היא אחידה אם לכל האיברים בה אותה זוגיות. לכן מספיק לקבוע את הזוגיות של איבר אחד (העליון) ולבדוק שלכל שאר האיברים אותה זוגיות. כדי לעבור על המחסנית צריך לשלוף ממנה איברים, ולכן נעביר אותם למחסנית עזר ובסוף נחזיר אותם, כך שהמחסנית המקורית לא תשתנה.
1. אם המחסנית ריקה - אין בה איבר שמפר את התנאי, והיא נחשבת אחידה (מחזירים true).
2. שומרים את `parity = st.top() % 2` - הזוגיות של האיבר העליון (0 לזוגי, 1 לאי-זוגי; המספרים חיוביים ולכן השארית אינה שלילית).
3. שולפים את האיברים אחד אחד. לכל איבר `x` בודקים אם `x % 2` שונה מ-`parity`; אם כן - המחסנית אינה אחידה (`uniform = false`). כל איבר שנשלף נדחף למחסנית העזר `temp`.
4. בסוף מחזירים את האיברים מ-`temp` ל-`st`. מאחר שמחסנית הופכת סדר פעמיים, הסדר המקורי משוחזר.
5. מחזירים את `uniform`.
public static boolean isUniform(Stack<Integer> st)
{
Stack<Integer> temp = new Stack<Integer>(); // לשחזור המחסנית
boolean uniform = true;
if (!st.isEmpty())
{
int parity = st.top() % 2; // הזוגיות של האיבר העליון
while (!st.isEmpty())
{
int x = st.pop();
if (x % 2 != parity) // נמצא איבר בזוגיות אחרת
uniform = false;
temp.push(x);
}
while (!temp.isEmpty()) // החזרת האיברים למקומם
st.push(temp.pop());
}
return uniform;
}public static bool IsUniform(Stack<int> st)
{
Stack<int> temp = new Stack<int>(); // לשחזור המחסנית
bool uniform = true;
if (!st.IsEmpty())
{
int parity = st.Top() % 2; // הזוגיות של האיבר העליון
while (!st.IsEmpty())
{
int x = st.Pop();
if (x % 2 != parity) // נמצא איבר בזוגיות אחרת
uniform = false;
temp.Push(x);
}
while (!temp.IsEmpty()) // החזרת האיברים למקומם
st.Push(temp.Pop());
}
return uniform;
}דוגמה: עבור מחסנית שבה (מלמעלה למטה) 6, 8, 4, 2 - כל האיברים זוגיים והפעולה מחזירה true. עבור 4, 7, 5, 3 - לאיבר העליון 4 זוגיות שונה מזו של 7, והפעולה מחזירה false.
תשובה: הפעולה isUniform שלמעלה.
סעיף ב
, כאשר מספר האיברים במחסנית.
נסמן ב- את מספר האיברים במחסנית.
1. כל פעולות המחסנית (`push`, `pop`, `top`, `isEmpty`) מתבצעות ב-.
2. הלולאה הראשונה שולפת כל איבר פעם אחת ודוחפת אותו ל-`temp`: סיבובים, בכל אחד מספר קבוע של פעולות.
3. הלולאה השנייה מחזירה כל איבר פעם אחת: עוד סיבובים.
4. בסך הכול סיבובים של עבודה קבועה, כלומר סיבוכיות לינארית.
תשובה: .
שאלה 2 · הוצאת האיבר האחרון מתור
כתבו פעולה המקבלת תור של מספרים שלמים. הפעולה תחזיר את האיבר הנמצא בסוף התור ותוציא אותו מהתור. כל שאר איברי התור יישארו ללא שינוי.
לדוגמה:
עבור התור q הבא הפעולה תחזיר ערך 4
התור q אחרי זימון הפעולה:
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 2
סעיף א
הפעולה removeLast שלהלן: מעבירה את כל האיברים חוץ מהאחרון לתור עזר, שומרת את האחרון ומחזירה את השאר לתור.
הרעיון: בתור אפשר להוציא איברים רק מראשו, ולכן כדי להגיע לאיבר האחרון צריך להוציא את כל האיברים. נוציא אותם אחד אחד; איבר שאחרי הוצאתו התור נשאר ריק הוא האיבר האחרון - אותו נשמור ולא נחזיר. את כל שאר האיברים נכניס לתור עזר, ובסוף נחזיר אותם לתור המקורי. כך הם חוזרים באותו סדר בדיוק (תור שומר על הסדר).
הנחה: התור אינו ריק (אחרת אין איבר אחרון להחזיר).
1. כל עוד `q` אינו ריק: מוציאים איבר `x`.
2. אם אחרי ההוצאה `q` ריק - `x` הוא האיבר האחרון: `last = x`.
3. אחרת מכניסים את `x` לתור העזר `temp`.
4. מעבירים את כל האיברים מ-`temp` חזרה ל-`q`, ומחזירים את `last`.
public static int removeLast(Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>();
int last = 0;
while (!q.isEmpty())
{
int x = q.remove();
if (q.isEmpty()) // x היה האיבר האחרון בתור
last = x;
else
temp.insert(x); // כל השאר נשמרים בתור העזר
}
while (!temp.isEmpty()) // החזרת האיברים לתור באותו הסדר
q.insert(temp.remove());
return last;
}public static int RemoveLast(Queue<int> q)
{
Queue<int> temp = new Queue<int>();
int last = 0;
while (!q.IsEmpty())
{
int x = q.Remove();
if (q.IsEmpty()) // x היה האיבר האחרון בתור
last = x;
else
temp.Insert(x); // כל השאר נשמרים בתור העזר
}
while (!temp.IsEmpty()) // החזרת האיברים לתור באותו הסדר
q.Insert(temp.Remove());
return last;
}בדיקה על הדוגמה: התור הוא (מהראש לסוף) 8, 10, 11, 2, 3, 16, 12, 4. שבעת האיברים הראשונים עוברים ל-`temp`; אחרי הוצאת 4 התור ריק, ולכן `last = 4`. בסוף `q` מכיל 8, 10, 11, 2, 3, 16, 12 והפעולה מחזירה 4.
תשובה: הפעולה removeLast שלמעלה.
סעיף ב
, כאשר מספר האיברים בתור.
נסמן ב- את מספר האיברים בתור.
1. כל פעולות התור (`insert`, `remove`, `isEmpty`) מתבצעות ב-.
2. הלולאה הראשונה מוציאה כל איבר פעם אחת: סיבובים.
3. הלולאה השנייה מחזירה איברים לתור.
4. בסך הכול כ- פעולות קבועות.
תשובה: .
שאלה 3 · שרשרת חוליות: ערכים שליליים ללא חזרות


כתבו פעולה המקבלת הפניה chain לחוליה הראשונה של שרשרת חוליות של מספרים שלמים.
הפעולה תבדוק אם אין חזרות של מספרים שליליים (כלומר, כל ערך שלילי מופיע פעם אחת בלבד).
אם כן – הפעולה תחזיר ערך true, ולא – ערך false.
כותרת הפעולה:
public static boolean uniqNeg(Node<Integer> chain)public static bool UniqNeg(Node<int> chain)לדוגמה: עבור שרשרת הבאה הפעולה תחזיר ערך true
עבור שרשרת הבאה הפעולה תחזיר ערך false כי ערך -3 מופיע פעמיים
מהי סיבוכיות הפעולה uniqNeg שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 3
סעיף א
הפעולה uniqNeg שלהלן: לכל ערך שלילי מחפשים אותו בהמשך השרשרת; אם נמצא - false, אחרת בסוף true.
הרעיון: ערך שלילי מופיע יותר מפעם אחת אם ורק אם קיימת חוליה עם ערך שלילי שאחריה (בהמשך השרשרת) יש עוד חוליה עם אותו ערך . לכן נעבור על השרשרת עם מצביע `p`, ולכל חוליה שערכה שלילי נחפש את אותו ערך בחוליות שאחריה בעזרת מצביע שני `q`. מספיק לחפש רק קדימה: אם הערך הופיע גם לפני `p`, החזרה כבר נמצאה כשעברנו על המופע הקודם.
1. `p` מתחיל בחוליה הראשונה.
2. אם `p.getValue()` שלילי - עוברים עם `q` על כל החוליות מ-`p.getNext()` ועד הסוף. אם באחת מהן הערך שווה ל- - מצאנו חזרה, מחזירים false.
3. מקדמים את `p` לחוליה הבאה.
4. אם הגענו לסוף השרשרת בלי למצוא חזרה - מחזירים true.
הפעולה רק קוראת ערכים ומזיזה מצביעים מקומיים, ולכן השרשרת אינה משתנה.
public static boolean uniqNeg(Node<Integer> chain)
{
Node<Integer> p = chain;
while (p != null)
{
int x = p.getValue();
if (x < 0)
{
// מחפשים את x בחוליות שאחרי p
Node<Integer> q = p.getNext();
while (q != null)
{
if (q.getValue() == x)
return false; // הערך השלילי x מופיע פעמיים
q = q.getNext();
}
}
p = p.getNext();
}
return true;
}public static bool UniqNeg(Node<int> chain)
{
Node<int> p = chain;
while (p != null)
{
int x = p.GetValue();
if (x < 0)
{
// מחפשים את x בחוליות שאחרי p
Node<int> q = p.GetNext();
while (q != null)
{
if (q.GetValue() == x)
return false; // הערך השלילי x מופיע פעמיים
q = q.GetNext();
}
}
p = p.GetNext();
}
return true;
}•בשרשרת 10, -3, 10, 6, -2, -8, 7 הערכים השליליים -3, -2, -8 מופיעים כל אחד פעם אחת, והפעולה מחזירה true (החזרה של 10 אינה משנה, כי 10 חיובי).
•בשרשרת 10, -3, 10, -3, -2, -8, 7 - כש-`p` נמצא בחוליה הראשונה שערכה -3, החיפוש קדימה מוצא -3 בחוליה הרביעית, והפעולה מחזירה false.
תשובה: הפעולה uniqNeg שלמעלה.
סעיף ב
, כאשר מספר החוליות בשרשרת.
נסמן ב- את מספר החוליות בשרשרת.
1. הלולאה החיצונית עוברת על כל החוליות.
2. עבור חוליה במקום שערכה שלילי, הלולאה הפנימית עוברת על כל החוליות שאחריה.
3. במקרה הגרוע (כל הערכים שליליים ושונים זה מזה) מספר ההשוואות הוא
4. זהו סדר גודל ריבועי.
תשובה: .
שאלה 4 · כתיבת מחלקת על לפי מחלקה יורשת ופלט
נתונות שתי המחלקות Child ו- Driver הבאות:
public class Child extends Parent {
private int age;
public Child( String fName, String lName, char gender,int age){
super(fName, lName, gender);
this.age = age;
}
public Child(){
super("David","Cohen");
this.age = 13;
this.gender = 'm';
}
public int getBirthYear(){
return Parent.year - this.age;
}
public void printDetails() {
if(this.gender == 'f')System.out.print("Daughter ");
else System.out.print("Son ");
System.out.print(getName()+" was born at " + getBirthYear());
}
}// end of class Child
public class Driver {
public static void main(String[] args) {
Parent.setYear(2020);
Parent[] family = new Parent[5];
family[0] = new Parent("Anna", "Blum");
family[1] = new Parent("Moshe","Coehn",'m');
family[2] = new Child();
family[3] = new Child("Dorit","Levi",'f',24);
family[4] = new Child("Eli","Coehn",'m',30);
family[3].updateCity("Tel-Aviv");
family[4].updateCity("Jerusalem");
for(int i=0; i<family.length; i++)
{
family[i].printDetails();
family[i].printCity();
}
}
}// end of class Driverpublic class Child : Parent {
private int age;
public Child( String fName, String lName, char gender,int age):
base(fName, lName, gender){
this.age = age;
}
public Child() : base("David","Cohen"){
this.age = 13;
this.gender = 'm';
}
public int GetBirthYear(){
return Parent.year - this.age;
}
public override void PrintDetails() {
if(this.gender == 'f')Console.Write("Daughter ");
else Console.Write ("Son ");
Console.Write (GetName()+" was born at " + GetBirthYear());
}
}// end of class Child
public class Driver {
public static void Main(string[] args) {
Parent.SetYear(2020);
Parent[] family = new Parent[5];
family[0] = new Parent("Anna", "Blum");
family[1] = new Parent("Moshe","Coehn",'m');
family[2] = new Child();
family[3] = new Child("Dorit","Levi",'f',24);
family[4] = new Child("Eli","Coehn",'m',30);
family[3].UpdateCity("Tel-Aviv");
family[4].UpdateCity("Jerusalem");
for(int i=0; i<family.Length; i++)
{
family[i].PrintDetails();
family[i].PrintCity();
}
}
}// end of class Driverעקב ביצוע הפעולה הראשית של המחלקה Driver התקבל פלט הבא:
Mother Anna Blum lives in Beer-Sheva
Father Moshe Coehn lives in Beer-Sheva
Son David Cohen was born at 2007 lives in Beer-Sheva
Daughter Dorit Levi was born at 1996 lives in Tel-Aviv
Son Eli Coehn was born at 1990 lives in Jerusalemכתבו את המחלקה המורישה Parent (מחלקת העל, super-class) של המחלקה Child.
מחלקת העל צריכה להכיל את כל התכונות והפעולות המתחייבות ממחלקת Child.
◂ פתרון מלא לשאלה 4
פתרון
המחלקה Parent שלהלן: תכונות fName, lName, gender, city ותכונה סטטית year; שני בנאים (ברירת מחדל למגדר 'f'), setYear סטטית, getName, updateCity, printCity (עם ברירת מחדל Beer-Sheva) ו-printDetails (Mother/Father).
הרעיון: עוברים על המחלקות Child ו-Driver ואוספים כל תכונה וכל פעולה של Parent שהן משתמשות בהן. אחר כך משתמשים בפלט כדי להבין מה כל פעולה צריכה לעשות.
1. `super(fName, lName, gender)` - בנאי עם שם פרטי, שם משפחה ותו של מגדר.
2. `super("David","Cohen")` ו-`new Parent("Anna", "Blum")` - בנאי עם שני פרמטרים בלבד.
3. `this.gender = 'm'` ו-`this.gender == 'f'` בתוך Child - התכונה `gender` מטיפוס `char` חייבת להיות נגישה למחלקה היורשת, ולכן `protected`.
4. `Parent.year` - תכונה סטטית (משותפת לכל העצמים) מטיפוס `int`, נגישה מ-Child.
5. `Parent.setYear(2020)` - פעולה סטטית שקובעת את `year`.
6. `getName()` - פעולה שמחזירה את השם המלא.
7. `updateCity(...)`, `printCity()` - עיר מגורים, ופעולה שמדפיסה אותה.
8. `printDetails()` - נקראת על כל איברי המערך `Parent[]`, ולכן חייבת להיות ב-Parent. ב-Child היא נדרסת, וההפעלה הפולימורפית בוחרת בגרסה של Child עבור עצמי Child (ב-C# החתימה ב-Child היא `override`, ולכן ב-Parent היא חייבת להיות `virtual`).
1. `Anna Blum` נבנתה בבנאי עם שני פרמטרים, והודפס עבורה `Mother` - ולכן בבנאי זה המגדר נקבע כברירת מחדל ל-`'f'`. (ב-`Child()` הבנאי הזה נקרא, ואחריו Child משנה את המגדר ל-`'m'` - ואכן מודפס `Son`.)
2. `Moshe Coehn` עם `'m'` מודפס `Father` - ולכן `printDetails` של Parent מדפיסה `Mother ` כאשר המגדר `'f'` ו-`Father ` אחרת, ואחר כך את השם.
3. `getName()` מחזירה את השם הפרטי, רווח ושם המשפחה: `David Cohen`.
4. מי שלא עדכן עיר מודפס `lives in Beer-Sheva` - ולכן העיר ההתחלתית בבנאי היא `"Beer-Sheva"`, ו-`updateCity` מחליפה אותה.
5. `printCity()` מודפסת מיד אחרי `printDetails()` באותה שורה, ומסיימת את השורה - ולכן היא מדפיסה `" lives in " + city` עם ירידת שורה (println / WriteLine), בעוד ש-`printDetails` משתמשת ב-print / Write בלי ירידת שורה.
6. שנות הלידה: , , - מתאימות ל-`year = 2020`.
public class Parent
{
protected String fName;
protected String lName;
protected char gender;
protected String city;
public static int year; // שנה נוכחית, משותפת לכל העצמים
public Parent(String fName, String lName, char gender)
{
this.fName = fName;
this.lName = lName;
this.gender = gender;
this.city = "Beer-Sheva"; // עיר ברירת מחדל
}
public Parent(String fName, String lName)
{
this(fName, lName, 'f'); // ברירת מחדל: אישה
}
public static void setYear(int y)
{
year = y;
}
public String getName()
{
return this.fName + " " + this.lName;
}
public void updateCity(String city)
{
this.city = city;
}
public void printCity()
{
System.out.println(" lives in " + this.city);
}
public void printDetails()
{
if (this.gender == 'f')
System.out.print("Mother ");
else
System.out.print("Father ");
System.out.print(getName());
}
}public class Parent
{
protected string fName;
protected string lName;
protected char gender;
protected string city;
public static int year; // שנה נוכחית, משותפת לכל העצמים
public Parent(string fName, string lName, char gender)
{
this.fName = fName;
this.lName = lName;
this.gender = gender;
this.city = "Beer-Sheva"; // עיר ברירת מחדל
}
public Parent(string fName, string lName) : this(fName, lName, 'f')
{
// ברירת מחדל: אישה
}
public static void SetYear(int y)
{
year = y;
}
public string GetName()
{
return this.fName + " " + this.lName;
}
public void UpdateCity(string city)
{
this.city = city;
}
public void PrintCity()
{
Console.WriteLine(" lives in " + this.city);
}
public virtual void PrintDetails()
{
if (this.gender == 'f')
Console.Write("Mother ");
else
Console.Write("Father ");
Console.Write(GetName());
}
}בדיקה מול הפלט: עבור `family[2] = new Child()`: הבנאי של Parent קובע שם David Cohen, מגדר `'f'` ועיר Beer-Sheva; Child קובע גיל 13 ומגדר `'m'`. בלולאה נקראת `printDetails` של Child ומדפיסה `Son David Cohen was born at 2007`, ואחריה `printCity` של Parent מוסיפה ` lives in Beer-Sheva` ויורדת שורה. כך מתקבלות בדיוק חמש שורות הפלט הנתונות.
תשובה: המחלקה Parent שלמעלה.
שאלה 5 · מעקב אחר פעולה על מחסנית
נתונה הפעולה הבאה:
public static void what(Stack<Integer> s)
{
Stack<Integer> temp1 = new Stack<Integer>();
Stack<Integer> temp2 = new Stack<Integer>();
while(!s.isEmpty())
{
int x = s.pop();
boolean found = false;
while(!s.isEmpty())
{
int y =s.pop();
if(x < y)
found = true;
temp1.push(y);
}
while(!temp1.isEmpty())
s.push(temp1.pop());
if(!found)
temp2.push(x);
}
while(!temp2.isEmpty())
s.push(temp2.pop());
}
}public static void What(Stack<int> s)
{
Stack<int> temp1 = new Stack<int>();
Stack<int> temp2 = new Stack<int>();
while(!s.IsEmpty())
{
int x = s.Pop();
bool found = false;
while(!s.IsEmpty())
{
int y =s.Pop();
if(x < y)
found = true;
temp1.Push(y);
}
while(!temp1.IsEmpty())
s.Push(temp1.Pop());
if(!found)
temp2.Push(x);
}
while(!temp2.IsEmpty())
s.Push(temp2.Pop());
}
}
נתונה מחסנית s
מה יהיה התוכן של המחסנית s אחרי זימון הפעולה what(s) עבור המחסנית s
תנו דוגמה למחסנית s המכילה לפחות חמישה ערכים כך שתוכן המחסנית לא ישתנה אחרי זימון הפעולה what(s)
מה מבצעת הפעולה what(s) עבור מחסנית של מספרים שלמים s?
◂ פתרון מלא לשאלה 5
סעיף א
מלמעלה למטה: 6, 4, 4, 1 (כלומר [6, 4, 4, 1], 6 בראש המחסנית).
מה הפעולה עושה בכל סיבוב: בכל סיבוב של הלולאה החיצונית שולפים את האיבר העליון `x`. אחר כך הלולאה הפנימית שולפת את כל שאר האיברים ל-`temp1` ובודקת אם יש ביניהם איבר גדול מ-`x` (`found`). הלולאה שאחריה מחזירה את כל האיברים מ-`temp1` ל-`s` (בסדר המקורי). אם לא נמצא איבר גדול מ-`x` - `x` נדחף ל-`temp2`; אחרת הוא נזרק. בסוף מעבירים את `temp2` ל-`s`.
המחסנית ההתחלתית (מלמעלה למטה): 4, 6, 3, 1, 4, 1, 4, 1.
טבלת מעקב (המחסניות רשומות מלמעלה למטה):
אחרי הסיבוב השמיני `s` ריקה. הלולאה האחרונה שולפת מ-`temp2` את 1, 4, 4, 6 (בסדר זה) ודוחפת ל-`s`. האיבר שנדחף אחרון (6) נמצא בראש.
תשובה: תוכן המחסנית s (מלמעלה למטה): 6, 4, 4, 1.
סעיף ב
למשל (מלמעלה למטה) 5, 4, 3, 2, 1 - כל איבר גדול או שווה לכל האיברים שמתחתיו.
מהמעקב בסעיף א': איבר נשאר במחסנית אם ורק אם אין מתחתיו איבר גדול ממנו, והאיברים שנשארים חוזרים באותו סדר יחסי. לכן המחסנית לא תשתנה אם כל איבר גדול או שווה לכל האיברים שמתחתיו, כלומר הערכים אינם יורדים מתחתית המחסנית לראשה.
דוגמה: מחסנית שבה (מלמעלה למטה) 5, 4, 3, 2, 1 (1 בתחתית, 5 בראש). בכל סיבוב `x` הוא האיבר הגדול ביותר מבין הנותרים, ולכן `found` נשאר false וכל איבר נדחף ל-`temp2`. `temp2` מקבלת 5, 4, 3, 2, 1 בסדר הפוך, והעברתה ל-`s` מחזירה את 5 לראש.
תשובה: למשל s = (מלמעלה למטה) 5, 4, 3, 2, 1.
סעיף ג
משאירה במחסנית רק את האיברים שאין מתחתיהם איבר גדול מהם (באותו סדר), ומוחקת את כל השאר; המחסנית שמתקבלת אינה יורדת מהתחתית לראש.
מהמעקב: איבר `x` נשמר (ב-`temp2`) רק אם אף אחד מהאיברים שמתחתיו אינו גדול ממנו, כלומר `x` גדול או שווה לכל האיברים שמתחתיו. כל איבר אחר נמחק. האיברים שנשמרו מוחזרים ל-`s` באותו סדר שבו היו.
לכן בסוף הערכים ב-`s` מסודרים כך שמהתחתית לראש הם לא יורדים (בראש נמצא המקסימום של המחסנית), כמו בסעיף א': 1, 4, 4, 6 מהתחתית לראש.
תשובה: הפעולה מוחקת מהמחסנית כל איבר שיש מתחתיו איבר גדול ממנו, ומשאירה את שאר האיברים בסדרם המקורי; התוצאה היא מחסנית ממוינת בסדר עולה מהתחתית לראש (המקסימום בראש).
שאלה 6 · תורים: תור התחלתי ושכפול של תור
•אין להשתמש במבני נתונים נוספים פרט לתור או תורים נוספים.
•אפשר להניח שקיימת פעולה `public static int size(Queue<Integer> q)` (ב-C#: `public static int Size(Queue<int> q)`) המחזירה מספר איברים בתור q.
הגדרה: תור q1 נקרא "תור התחלתי" של תור q2 אם כל האיברים של q1 נמצאים בתחילת התור q2 באותו הסדר.
לדוגמה:
התור q1
הוא תור התחלתי של התור q2
כתבו פעולה המקבלת שני תורים של מספרים שלמים q1 ו- q2. הפעולה תבדוק אם q1 הוא תור התחלתי של q2. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean startWith(Queue<Integer> q1,
Queue<Integer> q2)public static bool StartWith(Queue<int> q1,
Queue<int> q2)הגדרה: תור q2 נקרא "שכפול" של תור q1 אם כל האיברים של q1 נמצאים בתור q2 באותו הסדר כמה פעמים (התור q2 מורכב ממספר של תורים q1).
לדוגמה:
עבור התור q1
התור q2 הוא "שכפול" של התור q1
כתבו פעולה המקבלת שני תורים של מספרים שלמים q1 ו- q2. הפעולה תבדוק אם q2 הוא "שכפול" של q1. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean duplication(Queue<Integer> q1,
Queue<Integer> q2)public static bool Duplication(Queue<int> q1,
Queue<int> q2)מהן סיבוכיות של הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 6
סעיף א
הפעולה startWith שלהלן: אם q1 ארוך מ-q2 - false; אחרת מסובבים את q2 סיבוב שלם, ובמקביל את q1, ומשווים את האיברים הראשונים.
הרעיון: q1 הוא תור התחלתי של q2 אם (כאשר , מספרי האיברים) ואם האיברים הראשונים של q2 שווים, לפי הסדר, לאיברי q1.
כדי לא להרוס את התורים ולא להשתמש במבנה נוסף, נשתמש ב"סיבוב": מוציאים איבר מראש התור ומכניסים אותו מיד לסופו. אחרי סיבובים כאלה תור בגודל חוזר בדיוק למצבו המקורי.
1. מחשבים `n1 = size(q1)` ו-`n2 = size(q2)`. אם - q1 לא יכול להיות בתחילת q2, מחזירים false.
2. מבצעים סיבובים של q2. בסיבוב מוציאים את `x` מ-q2.
3. בסיבובים מסובבים גם את q1: מוציאים את `y`, משווים ל-`x`; אם הם שונים - `ok = false`. מכניסים את `y` חזרה לסוף q1.
4. מכניסים את `x` חזרה לסוף q2.
5. בסוף q1 סובב בדיוק פעמים ו-q2 בדיוק פעמים, ולכן שניהם חזרו למצבם המקורי. מחזירים את `ok`.
(ממשיכים לסובב גם אחרי שנמצא הבדל, כדי שהתורים יחזרו לסדרם.)
public static boolean startWith(Queue<Integer> q1,
Queue<Integer> q2)
{
int n1 = size(q1);
int n2 = size(q2);
if (n1 > n2) // q1 ארוך מ-q2 - אינו יכול להיות בתחילתו
return false;
boolean ok = true;
for (int i = 0; i < n2; i++) // סיבוב שלם של q2
{
int x = q2.remove();
if (i < n1) // סיבוב שלם של q1 במקביל
{
int y = q1.remove();
if (x != y)
ok = false;
q1.insert(y);
}
q2.insert(x);
}
return ok;
}public static bool StartWith(Queue<int> q1,
Queue<int> q2)
{
int n1 = Size(q1);
int n2 = Size(q2);
if (n1 > n2) // q1 ארוך מ-q2 - אינו יכול להיות בתחילתו
return false;
bool ok = true;
for (int i = 0; i < n2; i++) // סיבוב שלם של q2
{
int x = q2.Remove();
if (i < n1) // סיבוב שלם של q1 במקביל
{
int y = q1.Remove();
if (x != y)
ok = false;
q1.Insert(y);
}
q2.Insert(x);
}
return ok;
}בדיקה על הדוגמה: q1 = 2, 10, 12, 3 (), q2 = 2, 10, 12, 3, 7, 4, 1 (). בארבעת הסיבובים הראשונים מושווים 2=2, 10=10, 12=12, 3=3; בשלושת הבאים רק q2 מסתובב. התוצאה true, ושני התורים חוזרים לסדרם.
תשובה: הפעולה startWith שלמעלה.
סעיף ב
הפעולה duplication שלהלן: בודקים ש- מתחלק ב-, ואז מסובבים את q2 סיבוב שלם ואת q1 שוב ושוב במעגל, ומשווים איבר מול איבר.
הרעיון: q2 מורכב מכמה עותקים של q1 אם ורק אם:
•מספר האיברים הוא כפולה של , וגם
•כל איבר במקום ב-q2 שווה לאיבר במקום ב-q1.
את התנאי השני בודקים בעזרת סיבובים: בכל צעד מוציאים איבר מ-q2 ואיבר מ-q1, משווים ומחזירים כל אחד לסוף התור שלו. כיוון ש-q1 "מסתובב" במעגל, אחרי כל צעדים הוא חוזר להתחלה ומשווים אותו לעותק הבא בתוך q2.
1. מחשבים `n1 = size(q1)`, `n2 = size(q2)`. אם q1 ריק או ש- אינו מתחלק ב- - מחזירים false (ההגנה מונעת גם חלוקה באפס).
2. מבצעים צעדים. בכל צעד: `x` מ-q2, `y` מ-q1; אם `x != y` - `ok = false`; מחזירים את `y` לסוף q1 ואת `x` לסוף q2.
3. q2 סובב פעמים ו-q1 סובב פעמים, שזו כפולה של - ולכן שניהם חוזרים בדיוק למצבם המקורי. מחזירים את `ok`.
public static boolean duplication(Queue<Integer> q1,
Queue<Integer> q2)
{
int n1 = size(q1);
int n2 = size(q2);
if (n1 == 0 || n2 % n1 != 0) // אורך q2 חייב להיות כפולה של אורך q1
return false;
boolean ok = true;
for (int i = 0; i < n2; i++) // סיבוב שלם של q2
{
int x = q2.remove();
int y = q1.remove(); // q1 מסתובב שוב ושוב במעגל
if (x != y)
ok = false;
q1.insert(y);
q2.insert(x);
}
return ok;
}public static bool Duplication(Queue<int> q1,
Queue<int> q2)
{
int n1 = Size(q1);
int n2 = Size(q2);
if (n1 == 0 || n2 % n1 != 0) // אורך q2 חייב להיות כפולה של אורך q1
return false;
bool ok = true;
for (int i = 0; i < n2; i++) // סיבוב שלם של q2
{
int x = q2.Remove();
int y = q1.Remove(); // q1 מסתובב שוב ושוב במעגל
if (x != y)
ok = false;
q1.Insert(y);
q2.Insert(x);
}
return ok;
}בדיקה על הדוגמה: q1 = 3, 7, 4, 1 (), q2 = 3, 7, 4, 1, 3, 7, 4, 1, 3, 7, 4, 1 (). , ובכל אחד מ-12 הצעדים האיברים שווים, לכן התוצאה true. לעומת זאת, עבור q2 = 3, 7, 4, 1, 3, 7, 4 () - 7 אינו מתחלק ב-4 והתוצאה false.
תשובה: הפעולה duplication שלמעלה.
סעיף ג
שתי הפעולות לינאריות: , כלומר .
נסמן ב- וב- את מספרי האיברים ב-q1 וב-q2. פעולות התור עצמן (`insert`, `remove`) הן , והפעולה `size` עוברת על התור פעם אחת, כלומר או .
1. startWith: שתי קריאות ל-`size` עולות . אחריהן לולאה של סיבובים, ובכל סיבוב מספר קבוע של פעולות. סך הכול (וכיוון שמגיעים ללולאה רק כאשר , זה ).
2. duplication: שוב שתי קריאות ל-`size` (), ואחריהן לולאה של צעדים קבועים. סך הכול .
תשובה: שתי הפעולות בסיבוכיות לינארית, (ליתר דיוק ).
שאלה 7 · שרשרת חוליות: בדיקת סדרה עולה-יורדת
סדרת מספרים נקראת "עולה – יורדת" אם עד איבר מסוים המספרים הולכים וגדלים ומאיבר זה ואילך, הם הולכים וקטנים.
לדוגמה:
הסדרה הבאה היא סדרה "עולה – יורדת"
כתבו פעולה המקבלת הפנייה לשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם ערכים של השרשרת מהווים סדרה "עולה - יורדת". אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isUpDown(Node<Integer> chain)public static bool IsUpDown(Node<int> chain)מהי סיבוכיות של הפעולות שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 7
סעיף א
הפעולה isUpDown שלהלן: מוודאים שהצעד הראשון עולה, מתקדמים כל עוד הסדרה עולה ממש, אחר כך כל עוד היא יורדת ממש, ומחזירים true רק אם הגענו כך לסוף השרשרת.
הרעיון: סדרה "עולה – יורדת" בנויה משני קטעים רצופים: קטע עולה ממש עד איבר השיא, ואחריו קטע יורד ממש. לכן נעבור על השרשרת פעם אחת בשני שלבים:
•שלב העלייה: מתקדמים כל עוד האיבר הבא גדול מהנוכחי. עוצרים בשיא.
•שלב הירידה: מהשיא מתקדמים כל עוד האיבר הבא קטן מהנוכחי.
אם אחרי שני השלבים הגענו לחוליה האחרונה - כל הסדרה עלתה ואחר כך ירדה. אם עצרנו לפני הסוף - יש איבר שמפר את הכלל (עלייה אחרי ירידה, או שני איברים שווים), והסדרה אינה "עולה – יורדת".
1. מקרי קצה: שרשרת ריקה או עם חוליה אחת אינה סדרה כזו. כמו כן הסדרה חייבת להתחיל בעלייה, ולכן אם האיבר השני אינו גדול מהראשון - מחזירים false.
2. `p` מתקדם בשלב העלייה כל עוד `p.getValue() < p.getNext().getValue()`.
3. `p` ממשיך בשלב הירידה כל עוד `p.getValue() > p.getNext().getValue()`.
4. מחזירים `p.getNext() == null`.
הערה: סדרה שעולה עד סופה (השיא הוא האיבר האחרון והקטע היורד ריק) מתקבלת כ"עולה – יורדת" לפי פתרון זה; סדרה שיורדת כבר מתחילתה - לא.
public static boolean isUpDown(Node<Integer> chain)
{
// צריך לפחות שני איברים, והצעד הראשון חייב להיות עלייה
if (chain == null || chain.getNext() == null
|| chain.getValue() >= chain.getNext().getValue())
return false;
Node<Integer> p = chain;
// שלב העלייה: מתקדמים כל עוד האיבר הבא גדול יותר
while (p.getNext() != null && p.getValue() < p.getNext().getValue())
p = p.getNext();
// שלב הירידה: מתקדמים כל עוד האיבר הבא קטן יותר
while (p.getNext() != null && p.getValue() > p.getNext().getValue())
p = p.getNext();
// הסדרה תקינה רק אם הגענו כך לסוף השרשרת
return p.getNext() == null;
}public static bool IsUpDown(Node<int> chain)
{
// צריך לפחות שני איברים, והצעד הראשון חייב להיות עלייה
if (chain == null || chain.GetNext() == null
|| chain.GetValue() >= chain.GetNext().GetValue())
return false;
Node<int> p = chain;
// שלב העלייה: מתקדמים כל עוד האיבר הבא גדול יותר
while (p.GetNext() != null && p.GetValue() < p.GetNext().GetValue())
p = p.GetNext();
// שלב הירידה: מתקדמים כל עוד האיבר הבא קטן יותר
while (p.GetNext() != null && p.GetValue() > p.GetNext().GetValue())
p = p.GetNext();
// הסדרה תקינה רק אם הגענו כך לסוף השרשרת
return p.GetNext() == null;
}בדיקה על הדוגמה: 2, 5, 13, 19, 21, 18, 13, 6, 3: הצעד הראשון 2 < 5. בשלב העלייה `p` מגיע ל-21 (כי 21 > 18 עוצר את העלייה). בשלב הירידה 21 > 18 > 13 > 6 > 3, ו-`p` מגיע לחוליה האחרונה - הפעולה מחזירה true. עבור 1, 3, 2, 4: העלייה נעצרת ב-3, הירידה ב-2 (כי 2 < 4), ו-`p` אינו בסוף - false.
תשובה: הפעולה isUpDown שלמעלה.
סעיף ב
, כאשר מספר החוליות.
נסמן ב- את מספר החוליות בשרשרת.
1. שתי הלולאות ממשיכות זו את זו עם אותו מצביע `p`, ו-`p` רק מתקדם. לכן בשתיהן יחד `p` עובר על כל חוליה לכל היותר פעם אחת: לכל היותר צעדים.
2. בכל צעד מתבצעות השוואה אחת והתקדמות אחת - עבודה קבועה.
3. הבדיקות שלפני הלולאות ושאחריהן הן .
תשובה: .
שאלה 8 · עץ בינרי: הדפסת צמתים קטנים מהממוצע
כתבו פעולה המקבלת הפנייה לשורש של עץ בינרי של מספרים שלמים. הפעולה תדפיס את כל הצמתים שהערך שלהם קטן מהממוצע של כל הצמתים.
לדוגמה:
עבור העץ הבא

הפעולה תדפיס 5, 2, 6, 4, 3
◂ פתרון מלא לשאלה 8
פתרון
הפעולה printBelowAverage שלהלן: מחשבת ברקורסיה את סכום הערכים ואת מספר הצמתים, מחלקת לקבלת הממוצע, ובמעבר נוסף על העץ מדפיסה כל ערך קטן ממנו. בדוגמה: ממוצע 8.25, מודפסים 5 6 2 4 3.
הרעיון: אי אפשר לדעת אם ערך קטן מהממוצע לפני שמכירים את כל העץ, ולכן העבודה נעשית בשני שלבים:
1. חישוב הממוצע: פעולה רקורסיבית `sumTree` מחזירה את סכום הערכים בעץ (ערך השורש + סכום תת-העץ השמאלי + סכום תת-העץ הימני; לעץ ריק - 0), ופעולה רקורסיבית `countNodes` מחזירה את מספר הצמתים באותו אופן (1 + שני תתי-העצים). הממוצע הוא המנה ביניהם - כמספר ממשי (`double`), כדי לא לאבד את החלק השברי בחילוק שלמים.
2. הדפסה: פעולה רקורסיבית `printLess` עוברת על כל הצמתים (בסדר תחילי: שורש, שמאל, ימין) ומדפיסה כל ערך הקטן מהממוצע.
הפעולה הראשית `printBelowAverage` מחשבת את הממוצע וקוראת ל-`printLess`. עבור עץ ריק אין מה להדפיס (וגם נמנעת חלוקה באפס).
// סכום כל הערכים בעץ
public static int sumTree(BinNode<Integer> t)
{
if (t == null)
return 0;
return t.getValue() + sumTree(t.getLeft()) + sumTree(t.getRight());
}
// מספר הצמתים בעץ
public static int countNodes(BinNode<Integer> t)
{
if (t == null)
return 0;
return 1 + countNodes(t.getLeft()) + countNodes(t.getRight());
}
// הדפסת כל הצמתים שערכם קטן מ-avg
public static void printLess(BinNode<Integer> t, double avg)
{
if (t != null)
{
if (t.getValue() < avg)
System.out.print(t.getValue() + " ");
printLess(t.getLeft(), avg);
printLess(t.getRight(), avg);
}
}
public static void printBelowAverage(BinNode<Integer> bt)
{
if (bt == null)
return;
double avg = (double) sumTree(bt) / countNodes(bt);
printLess(bt, avg);
}// סכום כל הערכים בעץ
public static int SumTree(BinNode<int> t)
{
if (t == null)
return 0;
return t.GetValue() + SumTree(t.GetLeft()) + SumTree(t.GetRight());
}
// מספר הצמתים בעץ
public static int CountNodes(BinNode<int> t)
{
if (t == null)
return 0;
return 1 + CountNodes(t.GetLeft()) + CountNodes(t.GetRight());
}
// הדפסת כל הצמתים שערכם קטן מ-avg
public static void PrintLess(BinNode<int> t, double avg)
{
if (t != null)
{
if (t.GetValue() < avg)
Console.Write(t.GetValue() + " ");
PrintLess(t.GetLeft(), avg);
PrintLess(t.GetRight(), avg);
}
}
public static void PrintBelowAverage(BinNode<int> bt)
{
if (bt == null)
return;
double avg = (double) SumTree(bt) / CountNodes(bt);
PrintLess(bt, avg);
}בדיקה על הדוגמה: בעץ 8 צמתים: 10, 5, 14, 6, 2, 22, 4, 3.
•סכום:
•ממוצע:
•הערכים הקטנים מ-8.25: 5, 6, 2, 4, 3. במעבר תחילי הם מודפסים בסדר 5 6 2 4 3 - אותם ערכים כמו בדוגמה (הסדר אינו חשוב).
סיבוכיות: שלושה מעברים על העץ, כל אחד - סך הכול .
תשובה: הפעולה printBelowAverage שלמעלה.
שאלה 9 · ירושה ופולימורפיזם: מעקב אחר עצמים במערך
נתונות שלוש המחלקות הבאות:
public class One {
protected int n1;
public One ()
{
this.n1 = 1;
}
public One (int val)
{
this.n1 = val;
}
public void update(int k)
{
this.n1 = this.n1 * k;
}
public String toString()
{
return "One: n1=" + this.n1;
}
}
public class Two extends One {
protected int n2;
public Two(int val)
{
this.n2 = val;
}
public Two (int val1,int val2)
{
super(val1);
this.n2 = val2;
}
public void update(int k)
{
super.update(k);
this.n2 = this.n2 * k;
}
public String toString()
{
return super.toString() + " Two: n2=" + this.n2;
}
}
public class Test {
public static void main(String[] args){
One[] arr = new One [6];
arr [0] = new One (2);
arr [1] = new Two(4);
arr [2] = new Two(3, 6);
arr [3] = arr [0];
arr [4] = new Two(4);
arr [5] = arr[1];
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
(*) for(int i=0;i< arr.length;i++)
arr [i].update(i+3);
(**) for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
}
}public class One {
protected int n1;
public One ()
{
this.n1 = 1;
}
public One (int val)
{
this.n1 = val;
}
public virtual void Update(int k)
{
this.n1 = this.n1 * k;
}
public override string ToString()
{
return "One: n1=" + this.n1;
}
}
public class Two : One {
protected int n2;
public Two(int val):base()
{
this.n2 = val;
}
public Two (int val1,int val2):base(val1)
{
this.n2 = val2;
}
public override void Update(int k)
{
base.Update(k);
this.n2 = this.n2 * k;
}
public override string ToString()
{
return base.ToString() + " Two: n2=" + this.n2;
}
}
public class Test {
public static void Main(string[] args){
One[] arr = new One [6];
arr [0] = new One (2);
arr [1] = new Two(4);
arr [2] = new Two(3, 6);
arr [3] = arr [0];
arr [4] = new Two(4);
arr [5] = arr[1];
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);
(*) for(int i=0;i< arr.Length;i++)
arr [i].Update(i+3);
(**) for (int i = 0; i < arr.Length; i++)
Console.WriteLine (arr[i]);
}
}עקבו אחרי ביצוע פעולה הראשית (main) של המחלקה Test ורשמו מה יהיה הפלט של הפעולה הראשית. חובה להציג עבור כל עצם שנוצר בפעולה את ערכי התכונות שלו.
שתי הלולאות (*) ו-() הוחלפו ללולאה הבא:
for(int i=0;i< arr.length;i++) {
arr [i].update(i+3);
System.out.println(arr[i]);
}for(int i=0;i< arr.Length;i++) {
arr [i].Update(i+3);
Console.WriteLine(arr[i]);
}האם פלט של הפעולה הראשית השתנה? הסבירו את תשובתכם
◂ פתרון מלא לשאלה 9
סעיף א
One: n1=2 / One: n1=1 Two: n2=4 / One: n1=3 Two: n2=6 / One: n1=2 / One: n1=1 Two: n2=4 / One: n1=1 Two: n2=4 / One: n1=36 / One: n1=32 Two: n2=128 / One: n1=15 Two: n2=30 / One: n1=36 / One: n1=7 Two: n2=28 / One: n1=32 Two: n2=128
שלב 1 - יצירת העצמים. נותנים שם לכל עצם שנוצר ב-`new`:
השמות `arr[3] = arr[0]` ו-`arr[5] = arr[1]` אינן יוצרות עצמים חדשים - הן מעתיקות הפניות. לכן:
שלב 2 - הלולאה הראשונה (הדפסה). `println(arr[i])` / `WriteLine(arr[i])` קוראת ל-`toString` של העצם בפועל (פולימורפיזם). ב-Two מודפס קודם החלק של One (`super.toString()`) ואחריו `Two: n2=...`:
One: n1=2
One: n1=1 Two: n2=4
One: n1=3 Two: n2=6
One: n1=2
One: n1=1 Two: n2=4
One: n1=1 Two: n2=4שלב 3 - הלולאה (*): `arr[i].update(i+3)`. עבור עצם One מוכפל `n1` ב-k. עבור עצם Two מופעלת הגרסה הדורסת: `super.update(k)` מכפיל את `n1`, ואחר כך מוכפל `n2`:
ערכי התכונות הסופיים: A: n1=36; B: n1=32, n2=128; C: n1=15, n2=30; D: n1=7, n2=28.
שלב 4 - הלולאה () (הדפסה). התאים 0 ו-3 מדפיסים את A, והתאים 1 ו-5 מדפיסים את B, בערכיהם הסופיים:
One: n1=36
One: n1=32 Two: n2=128
One: n1=15 Two: n2=30
One: n1=36
One: n1=7 Two: n2=28
One: n1=32 Two: n2=128תשובה: הפלט המלא (12 שורות):
One: n1=2
One: n1=1 Two: n2=4
One: n1=3 Two: n2=6
One: n1=2
One: n1=1 Two: n2=4
One: n1=1 Two: n2=4
One: n1=36
One: n1=32 Two: n2=128
One: n1=15 Two: n2=30
One: n1=36
One: n1=7 Two: n2=28
One: n1=32 Two: n2=128סעיף ב
כן. השורות 7 ו-8 משתנות ל-One: n1=6 ול-One: n1=4 Two: n2=16, כי A ו-B מודפסים מיד אחרי העדכון הראשון שלהם, לפני העדכון השני דרך arr[3] ו-arr[5].
הרעיון: במערך יש שתי הפניות לעצם A (תאים 0 ו-3) ושתי הפניות לעצם B (תאים 1 ו-5). בקוד המקורי מדפיסים רק אחרי שכל העדכונים הסתיימו, ולכן גם בתא 0 וגם בתא 3 מודפס הערך הסופי של A (וכך גם עבור B). בלולאה החדשה כל תא מודפס מיד אחרי העדכון שלו - ועבור תאים 0 ו-1 זה לפני העדכון השני של אותו עצם.
שש השורות הראשונות (הלולאה הראשונה) אינן משתנות. מעקב אחרי הלולאה החדשה:
ההשוואה לפלט המקורי: השורה השביעית הייתה `One: n1=36` וכעת `One: n1=6`; השורה השמינית הייתה `One: n1=32 Two: n2=128` וכעת `One: n1=4 Two: n2=16`. שאר השורות זהות (העצמים C ו-D מופיעים פעם אחת בלבד במערך, ותאים 3 ו-5 מודפסים אחרי העדכון האחרון של A ושל B).
תשובה: כן, הפלט משתנה: שש השורות האחרונות הן One: n1=6 / One: n1=4 Two: n2=16 / One: n1=15 Two: n2=30 / One: n1=36 / One: n1=7 Two: n2=28 / One: n1=32 Two: n2=128. הסיבה: arr[0], arr[3] ו-arr[1], arr[5] מפנים לאותם עצמים, ובלולאה החדשה הם מודפסים לפני העדכון השני שלהם.
שאלה 10 · רקורסיה על שרשרת: מינימום ומיון בחירה
לפניכם שתי הפעולות הרקורסיביות what ו-why. הפעולה what מקבלת הפניה לאחת מהחוליות בשרשרת חוליות של מספרים שלמים, והפעולה why מקבלת הפניה לחוליה ראשונה בשרשרת החוליות.
public static Node<Integer> what (Node<Integer> p1)
{
if(p1.getNext() ==null)
return p1;
Node<Integer> p2 = what(p1.getNext());
if(p1.getValue() < p2.getValue())
return p1;
return p2;
}
public static void why(Node<Integer> chain)
{
if(chain.getNext()!=null)
{
Node<Integer>p = what(chain);
int temp=p.getValue();
p.setValue(chain.getValue());
chain.setValue(temp);
why(chain.getNext());
}
}public static Node<int> What (Node<int> p1)
{
if(p1.GetNext() ==null)
return p1;
Node<int> p2 = What(p1.GetNext());
if(p1.GetValue() < p2.GetValue())
return p1;
return p2;
}
public static void Why(Node<int> chain)
{
if(chain.GetNext()!=null)
{
Node<int>p = What(chain);
int temp=p.GetValue();
p.SetValue(chain.GetValue());
chain.SetValue(temp);
Why(chain.GetNext());
}
}נתונה שרשרת חוליות הבאה:

מה יחזיר זימון הפעולה what(p1)? יש להראות מעקב אחר ביצוע הפעולה.
מה מבצעת הפעולה what באופן כללי?
עקבו אחרי זימון הפעולה why(chain) ורשמו איך תיראה השרשרת אחרי זימון.
יש להראות מעקב אחרי ביצוע הפעולה why, אין צורך במעקב אחרי הזימונים של what.
מה מבצע הפעולה why באופן כללי?
◂ פתרון מלא לשאלה 10
סעיף א
הפניה לחוליה שערכה 5 (הרביעית בשרשרת), כלומר לשרשרת 5 → 8 → 6.
מה הפעולה עושה: אם `p1` היא החוליה האחרונה - מחזירים אותה. אחרת קוראים ברקורסיה על החוליה הבאה ומקבלים `p2`, ומחזירים את מי מהשתיים שערכה קטן יותר (`p1` רק אם ערכה קטן ממש מערכה של `p2`).
`p1` מפנה לחוליה שערכה 10, ואחריה 5, 8, 6.
תשובה: הזימון what(p1) מחזיר הפניה לחוליה שערכה 5 (ממנה ממשיכה השרשרת 5 → 8 → 6).
סעיף ב
מחזירה הפניה לחוליה בעלת הערך הקטן ביותר, מהחוליה שהתקבלה ועד סוף השרשרת.
מהמעקב: בכל רמה של הרקורסיה משווים את ערך החוליה הנוכחית לחוליה המינימלית שנמצאה בהמשך השרשרת, ומחזירים את הקטנה מביניהן. לכן הפעולה מחזירה את החוליה המינימלית בקטע שמ-`p1` ועד הסוף. (אם הערך המינימלי מופיע כמה פעמים, מוחזרת החוליה האחרונה מביניהן, כי `p1` מוחזרת רק כשערכה קטן ממש.)
תשובה: הפעולה מחזירה הפניה לחוליה שערכה הוא הקטן ביותר בשרשרת, החל מהחוליה שהתקבלה ועד סוף השרשרת.
סעיף ג
3 → 4 → 5 → 6 → 8 → 10
מה הפעולה עושה: אם החוליה הנוכחית אינה האחרונה, מוצאים בעזרת `what` את החוליה המינימלית מהחוליה הנוכחית ועד הסוף, מחליפים בין הערך שלה לבין הערך של החוליה הנוכחית, וקוראים ברקורסיה על החוליה הבאה.
השרשרת בתחילה: 3, 4, 10, 5, 8, 6.
רק הערכים מוחלפים; מבנה השרשרת (ההפניות בין החוליות) אינו משתנה.
תשובה: אחרי הזימון השרשרת היא 3 → 4 → 5 → 6 → 8 → 10.
סעיף ד
ממיינת את ערכי השרשרת בסדר עולה (מיון בחירה).
בכל זימון מועבר למקום הנוכחי הערך הקטן ביותר מבין הערכים שמהמקום הזה ועד הסוף, ואז ממשיכים לחוליה הבאה. אחרי הזימון ה-, החוליות הראשונות מכילות את הערכים הקטנים ביותר לפי הסדר. זהו מיון בחירה (Selection Sort) שמבוצע ברקורסיה.
תשובה: הפעולה why ממיינת את ערכי השרשרת בסדר עולה (מיון בחירה), בלי לשנות את סדר החוליות עצמן - רק את הערכים שבהן.
שאלה 11 · מחלקות ציון וסטודנט: הממוצע הגבוה ביותר
במאגר הציונים של סטודנטים באוניברסיטה נשמרים עבור כל סטודנט הנתונים הבאים:
מספר תעודת הזהות ורשימת כל ציונים שלו. לכל ציון נשמר קוד מקצוע ושני ציונים (ציון של סמסטר א' וציון של סמסטר ב')
הגדירו מחלקה Grade המתארת ציון במקצוע. תכונות של המחלקה:
•קוד מקצוע.
•ציון סמסטר א'.
•ציון סמסטר ב'.
הגדירו מחלקה Student המתארת סטודנט באוניברסיטה. תכונות המחלקה:
•מספר תעודת הזהות של הסטודנט.
•רשימת ציונים (שרשרת חוליות מסוג Grade).
כתבו פעולה המקבלת מאגר (אוסף נתונים) של סטודנטים ומחזירה מספר תעודת הזהות של סטודנט בעל ממוצע (של כל הציונים בכל המקצועות שהוא למד) הגבוה ביותר.
אפשר להניח שקיים רק סטודנט אחד עם ממוצע הגבוה ביותר.
אפשר להשתמש לייצוג האוסף בכל מבנה הנתונים הנלמד (תור, מחסנית, שרשרת חוליות)
הערה: אפשר להניח שבמחלקות Grade ו-Student קיימות פעולות get לכל התכונות.
◂ פתרון מלא לשאלה 11
סעיף א
מחלקה Grade עם התכונות code, gradeA, gradeB (שלמים), בנאי ופעולות get.
מגדירים שלוש תכונות פרטיות מטיפוס `int`: קוד המקצוע ושני הציונים. בנאי מקבל את שלושתם, ופעולות get מאפשרות לקרוא אותם מחוץ למחלקה (נצטרך אותן בסעיף ג').
public class Grade
{
private int code; // קוד מקצוע
private int gradeA; // ציון סמסטר א'
private int gradeB; // ציון סמסטר ב'
public Grade(int code, int gradeA, int gradeB)
{
this.code = code;
this.gradeA = gradeA;
this.gradeB = gradeB;
}
public int getCode() { return this.code; }
public int getGradeA() { return this.gradeA; }
public int getGradeB() { return this.gradeB; }
}public class Grade
{
private int code; // קוד מקצוע
private int gradeA; // ציון סמסטר א'
private int gradeB; // ציון סמסטר ב'
public Grade(int code, int gradeA, int gradeB)
{
this.code = code;
this.gradeA = gradeA;
this.gradeB = gradeB;
}
public int GetCode() { return this.code; }
public int GetGradeA() { return this.gradeA; }
public int GetGradeB() { return this.gradeB; }
}תשובה: המחלקה Grade שלמעלה.
סעיף ב
מחלקה Student עם התכונות id (מחרוזת) ו-grades (Node<Grade>), בנאי ופעולות get.
מספר תעודת הזהות נשמר כמחרוזת (הוא מזהה ולא מספר שמחשבים איתו, וכך נשמרים גם אפסים מובילים). רשימת הציונים היא הפניה לחוליה הראשונה בשרשרת חוליות שבכל חוליה עצם Grade.
public class Student
{
private String id; // מספר תעודת הזהות
private Node<Grade> grades; // רשימת הציונים
public Student(String id, Node<Grade> grades)
{
this.id = id;
this.grades = grades;
}
public String getId() { return this.id; }
public Node<Grade> getGrades() { return this.grades; }
}public class Student
{
private string id; // מספר תעודת הזהות
private Node<Grade> grades; // רשימת הציונים
public Student(string id, Node<Grade> grades)
{
this.id = id;
this.grades = grades;
}
public string GetId() { return this.id; }
public Node<Grade> GetGrades() { return this.grades; }
}תשובה: המחלקה Student שלמעלה.
סעיף ג
הפעולה bestStudent שלהלן (המאגר: שרשרת חוליות Node<Student>): מחשבת לכל סטודנט ממוצע של כל ציוניו בעזרת average ושומרת את תעודת הזהות של בעל הממוצע המקסימלי.
בחירת המבנה: נייצג את המאגר כשרשרת חוליות של סטודנטים, `Node<Student>`. כך אפשר לעבור על כל הסטודנטים בלי להוציא אותם מהמבנה ובלי לשנות אותו.
הרעיון: זו בעיית מציאת מקסימום. נכתוב פעולת עזר `average` שמחשבת ממוצע של סטודנט אחד, ובפעולה הראשית נעבור על כל הסטודנטים ונשמור את הממוצע הגבוה ביותר שנמצא עד כה ואת תעודת הזהות של בעליו.
1. עוברים על שרשרת הציונים של הסטודנט.
2. לכל מקצוע מוסיפים לסכום את שני הציונים (סמסטר א' וסמסטר ב') ומגדילים את המונה ב-2 - כי הממוצע הוא של כל הציונים.
3. מחזירים סכום חלקי מונה כמספר ממשי. לסטודנט בלי ציונים מחזירים -1 (כך הוא לא ייבחר, ונמנעת חלוקה באפס).
1. `bestAvg` מאותחל ל-1- (קטן מכל ממוצע אפשרי של ציונים), ו-`bestId` ל-null.
2. לכל סטודנט מחשבים `avg`. אם הוא גדול מ-`bestAvg` - מעדכנים את `bestAvg` ואת `bestId`.
3. בסוף מחזירים את `bestId`. לפי ההנחה בשאלה יש סטודנט יחיד עם הממוצע הגבוה ביותר, ולכן התשובה חד-משמעית.
public static double average(Node<Grade> grades)
{
int sum = 0;
int count = 0;
while (grades != null)
{
Grade g = grades.getValue();
sum += g.getGradeA() + g.getGradeB(); // שני ציוני המקצוע
count += 2;
grades = grades.getNext();
}
if (count == 0)
return -1; // סטודנט בלי ציונים
return (double) sum / count;
}
public static String bestStudent(Node<Student> students)
{
String bestId = null;
double bestAvg = -1;
while (students != null)
{
Student st = students.getValue();
double avg = average(st.getGrades());
if (avg > bestAvg) // ממוצע גבוה יותר מכל הקודמים
{
bestAvg = avg;
bestId = st.getId();
}
students = students.getNext();
}
return bestId;
}public static double Average(Node<Grade> grades)
{
int sum = 0;
int count = 0;
while (grades != null)
{
Grade g = grades.GetValue();
sum += g.GetGradeA() + g.GetGradeB(); // שני ציוני המקצוע
count += 2;
grades = grades.GetNext();
}
if (count == 0)
return -1; // סטודנט בלי ציונים
return (double) sum / count;
}
public static string BestStudent(Node<Student> students)
{
string bestId = null;
double bestAvg = -1;
while (students != null)
{
Student st = students.GetValue();
double avg = Average(st.GetGrades());
if (avg > bestAvg) // ממוצע גבוה יותר מכל הקודמים
{
bestAvg = avg;
bestId = st.GetId();
}
students = students.GetNext();
}
return bestId;
}דוגמה: סטודנט 111 עם ציונים (80, 90) ו-(70, 100): ממוצע . סטודנט 222 עם (95, 85): ממוצע . הפעולה מחזירה "222".
סיבוכיות: כל ציון של כל סטודנט נקרא פעם אחת - , כאשר מספר הציונים הכולל במאגר (ועוד מספר הסטודנטים).
תשובה: הפעולה bestStudent (עם פעולת העזר average) שלמעלה.
שאלה 12 · מחיקת כפולות מתוך שרשרת חוליות
נתונות שתי הפעולות what ו- where המקבלות הפניה לחוליה הראשונה של שרשרת חוליות:
public static Node<Integer> what(Node<Integer> chain, int x){
while(chain!=null && chain.getValue()% x == 0){
chain = chain.getNext();
}
if(chain == null)
return null;
Node<Integer> p = chain;
Node<Integer> p1 = p.getNext();
while(p1 != null){
if(p1.getValue()% x == 0)
{
p.setNext(p1.getNext());
p1.setNext(null);
p1 = p.getNext();
}
else
{
p = p1;
p1 = p1.getNext();
}
}
return chain;
}
public static void where(Node<Integer> chain){
Node<Integer> p = chain;
while(p != null) {
p.setNext(what(p.getNext(),p.getValue()));
p = p.getNext();
}
}public static Node<int> What(Node<int> chain, int x){
while(chain!=null && chain.GetValue()% x == 0){
chain = chain.GetNext();
}
if(chain == null)
return null;
Node<int> p = chain;
Node<int> p1 = p.GetNext();
while(p1 != null){
if(p1.GetValue()% x == 0)
{
p.SetNext(p1.GetNext());
p1.SetNext(null);
p1 = p.GetNext();
}
else
{
p = p1;
p1 = p1.GetNext();
}
}
return chain;
}
public static void Where(Node<int> chain){
Node<int> p = chain;
while(p != null) {
p.SetNext(What(p.GetNext(),p.GetValue()));
p = p.GetNext();
}
}נתונה שרשרת חוליות הבא:

עקבו אחרי זימון הפעולה what(chain, 4) ורשמו מה תחזיר הפעולה.
מה מבצעת הפעולה what באופן כללי?
עקבו אחרי זימון הפעולה where(chain) ורשמו איך תיראה השרשרת אחרי ביצוע. אין צורך במעקב אחרי זימון הפעולה what.
האם אפשר לשנות סדר חוליות בשרשרת chain כך ששרשרת לא תשתנה אחרי זימון הפעולה where? אם כן – רשמו את השרשרת אחרי שינוי, אם לא – הסבירו למה אי אפשר לבצע שינוי כזה.
מה מבצעת הפעולה where באופן כללי?
◂ פתרון מלא לשאלה 12
סעיף א
הפניה לחוליה שערכה 5: השרשרת 5 → 7 → 6 → 18.
שלב 1 - הלולאה הראשונה: מדלגת על חוליות מתחילת השרשרת כל עוד הערך מתחלק ב-:
כעת `chain` מפנה לחוליה 5 (אינו null).
שלב 2 - הלולאה השנייה: `p` היא החוליה האחרונה שנשארת, ו-`p1` החוליה שאחריה. אם ערך `p1` מתחלק ב-4 - מנתקים אותה (`p` מדלגת עליה); אחרת מתקדמים.
הפעולה מחזירה את `chain`, כלומר הפניה לחוליה 5.
תשובה: הפעולה מחזירה הפניה לשרשרת 5 → 7 → 6 → 18.
סעיף ב
מוחקת מהשרשרת את כל החוליות שערכן מתחלק ב-x ומחזירה הפניה לתחילת השרשרת שנותרה (null אם לא נותר דבר).
הלולאה הראשונה מדלגת על כל החוליות בתחילת השרשרת שערכן מתחלק ב-x, והלולאה השנייה מנתקת מהמשך השרשרת כל חוליה שערכה מתחלק ב-x. ההפניה המוחזרת היא לחוליה הראשונה שערכה אינו מתחלק ב-x.
תשובה: הפעולה מסירה מהשרשרת את כל החוליות שהערך שלהן מתחלק ב-x, ומחזירה הפניה לחוליה הראשונה של השרשרת שנשארה (או null אם כל הערכים מתחלקים ב-x).
סעיף ג
4 → 5 → 7 → 6
מה הפעולה עושה: עבור כל חוליה `p` (מההתחלה), קוראים ל-`what` על ההמשך שלה עם הערך של `p` - כלומר מוחקים מההמשך את כל הערכים שמתחלקים בערך של `p` - ומחברים את `p` לתוצאה. אחר כך מתקדמים לחוליה הבאה בשרשרת המעודכנת.
השרשרת בתחילה: 4, 20, 5, 7, 8, 4, 6, 18.
אחרי החוליה 6 `p` מקבל null והלולאה מסתיימת.
תשובה: השרשרת אחרי הביצוע: 4 → 5 → 7 → 6.
סעיף ד
לא. בשרשרת יש שתי חוליות עם הערך 4; בכל סדר, ה-4 המאוחר מתחלק ב-4 המוקדם ויימחק.
השרשרת לא משתנה רק אם אף ערך אינו מתחלק בערך כלשהו שמופיע לפניו. אבל הערך 4 מופיע בשרשרת פעמיים. בכל סידור, אחד המופעים של 4 יהיה לפני השני, ו- - ולכן כשהפעולה תגיע ל-4 הראשון היא תמחק את 4 השני. כלומר השרשרת תשתנה בכל סדר.
תשובה: לא, אי אפשר: הערך 4 מופיע פעמיים, וכל מספר מתחלק בעצמו - ולכן בכל סדר המופע השני של 4 יימחק.
סעיף ה
מוחקת מהשרשרת כל חוליה שערכה מתחלק בערך של חוליה כלשהי שלפניה; בסוף אף ערך אינו מחלק ערך שאחריו.
מהמעקב: לכל חוליה שנשארת בשרשרת, `where` מוחקת מכל ההמשך שלה את הערכים שמתחלקים בערך שלה. חוליה נמחקת אם יש לפניה (בין החוליות שנשארו) ערך שמחלק אותה; ואם חוליה נמחקה בגלל ערך שלפניה, כל מה שמתחלק בה מתחלק גם באותו ערך ולכן גם הוא נמחק.
תשובה: הפעולה עוברת על כל החוליות ומוחקת מהשרשרת כל ערך שמתחלק בערך שמופיע לפניו; בשרשרת שמתקבלת אף ערך אינו מחלק ערך שבא אחריו (נשארים רק המופע הראשון של כל ערך, ורק ערכים שאינם כפולה של ערך קודם).