/
השאלות
בשאלון זה שני פרקים.
יש לענות על שאלות משני הפרקים, לפי ההוראות בכל פרק.
הערה: בכל שאלה שנדרשת בה קליטה, אין צורך לבדוק את תקינות הקלט .
לפותרים בשפת Java : בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner input = new Scanner (System.in);
שימו לב: בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית , עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן . |
פרק ראשון (50 נקודות)
ענו על שתיים מבין השאלות 1-3 (ערך כל שאלה – 25 נקודות)
שאלה 1
לפניכם הפעולות הבאות:
public static String what(BinNode<Integer> t) {
String output = "(";
if (t.getLeft()!= null)
output += what(t.getLeft());
output += t.getValue();
if (t.getRight()!= null)
output += what (t.getRight());
output += ")";
return output;
}
public static String why(BinNode<Integer> t) {
String output = "(";
output += t.getValue();
if (t.getLeft()!= null)
output += why(t.getLeft());
if (t.getRight()!= null)
output += why (t.getRight());
output += ")";
return output;
}
א. (6 נק') נתון העץ הבינארי bt הבא:
מה תהיה תוצאת זימון הפעולה (what(bt ? חובה להראות את המעקב !
ב. (6 נק') לפעולה what הועברה כפרמטר הפניה לשורש של עץ בינארי. המחרוזת שהוחזרה מהפעולה היא:
(((30) 20 ((50) 5)) 40 (10))
ציירו את העץ הבינארי שהועבר כפרמטר לפעולה. הסבירו תשובתכם.
ג. (3 נק') האם קיים עץ בינארי bt בעל שלושה צמתים (בעלי ערכים שונים) לפחות שעבורו תוצאת זימון הפעולה (what(bt תהיה זהה לתוצאת זימון הפעולה (why(bt ? אם כן – ציירו את העץ, אם לא – הסבירו מדוע .
ד. (10 נק') (אין קשר לסעיפים הקודמים)
ממשו את הפעולה החיצונית nextInTree.
הפעולה מקבלת עץ בינארי t שצמתיו הם תור של מספרים שלמים חיוביים. הפעולה מוצאת את הצומת הראשונה בסריקה תחילית אשר התור בה אינו ריק, ומחזירה את הערך מראש התור מבלי לשנות את התור.
אם כל התורים בעץ ריקים, הפעולה תחזיר 1-.
כותרת הפעולה:
public static int nextInTree(BinNode<Queue<Integer>> bt)
לדוגמא:
עבור העץ A - הפעולה תחזיר את המספר 23 מראש התור שבשורש (23-26-27), מבלי לשנות את התור.
עבור העץ B - הפעולה תחזיר את המספר 12 מראש התור שבצומת (12-13-14), מבלי לשנות את התור.
עבור העץ C - כל התורים בו ריקים, הפעולה תחזיר 1-.
שאלה 2
נתונה שרשרת חוליות המכילה מספרים שלמים. כל ערך בשרשרת יכול להופיע כמה פעמים .
נגדיר" מרחק" של ערך כלשהו בשרשרת כסכום המרחקים הקטנים ביותר של מופע של אותו מספר מקצוות השרשרת.
א. (10 נק') כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות ומספר num ומחזירה את ה "מרחק" של המספר num. אם num לא נמצא בשרשרת הפעולה תחזיר 1-.
כותרת הפעולה:
public static int distance(Node<Integer> lst, int num)
ב. (10 נק') כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות ומחזירה את המספר בעל ה"מרחק" הקטן ביותר.
עבור השרשרת הבאה הפעולה תחזיר 9 (ה"מרחק" של ה ערך 9 הוא הקטן ביותר).
כותרת הפעולה:
public static int minDistanceValue(Node<Integer> lst)
ג. (5 נק') מהן סיבוכיות זמן הריצה של הפעולות distance ו-minDistanceValue מסעיפים א' ו- ב'?
הסבירו את תשובתכם.
שאלה 3
תור רשימות מקושרות נקרא תור מושלם אם הוא עונה על שלושת התנאים הבאים:
- הערכים בכל רשימה הם סדרה עולה ( הערך הקטן ביותר נמצא בראש הרשימה).
- האורכים של הרשימות (מספר האיברים בכל רשימה ), הם בסדר עולה, הרשימה הקצרה ביותר נמצאת בראש התור.
- איבר הנמצא בראש כל רשימה שווה לאיבר הנמצא בסוף הרשימה הקודמת לה בתור .
לדוגמה: תור רשימות הבא הוא תור מושלם:
א. (20 נק') כתבו פעולה המקבלת תור של רשימות ובודקת אם הוא תור מושלם. אם כן – הפעולה תחזיר true, ואם לא – הפעולה תחזיר false. בסיום הפעולה מבנה הנתונים אינו משתנה.
כותרת הפעולה:
public static boolean isPerfect(Queue <Node<Integer>> q)
ב.(5 נק') מהי סיבוכיות הפעולה isPerfect?
הערה: אם כתבתם פעולות עזר חובה לתעד אותן (לציין פרמטרים שהפעולה מקבלת, הנחות, ותיאור של מה הפעולה מבצעת). כמו כן, יש לציין את הסיבוכיות של כל פעולת עזר שכתבתם.
פרק שני (50 נקודות)
ענו על שתיים מבין השאלות 4-6 (ערך כל שאלה – 25 נקודות)
שאלה 4
נתונות שתי המחלקות Fruit ו- Apple.
public class Fruit {
protected int weight;
public Fruit (int val) { weight = val; }
public int getWeight() { return weight; }
}
public class Apple extends Fruit {
private String color;
public Apple (int val, String col) {
super(val);
color=col;
}
public boolean validWeight(){
return weight > 80 && weight < 140;
}
}
א. (10 נק') לפניכם חמישה היגדים. קבעו לכל אחד מהם אם הוא נכון או אינו נכון ונמקו את קביעתכם.
- המחלקה Fruit יורשת את הפעולה ()validWeight מהמחלקה Apple.
- המחלקה Apple יורשת את כל התכונות ואת כל הפעולות של המחלקה Fruit.
- המחלקה Apple יכולה לגשת ישירות לתכונה weight של המחלקה Fruit.
- המחלקה Fruit יכולה לגשת לתכונה color של המחלקה Apple.
- למחלקה Apple אין פעולה ( ) toString
ב. (10 נק') לפניכם קטע קוד מהפעולה הראשית ( main ) של המחלקה TestFruit:
Fruit first = new Apple (100, "RED");
Fruit second = new Fruit (90);
Apple third = new Apple(100, "RED");
בעבור כל אחת מההוראות שלפניכם קבעו אם היא תקינה או אינה תקינה. אם היא אינה תקינה, כתבו אם זו שגיאת ריצה או שגיאת הידור (קומפילציה).
1. boolean b = first.validWeight();
2. boolean b = second.validWeight();
3. boolean b = ((Apple)first).validWeight();
4. boolean b = ((Apple)second).validWeight();
5. boolean b = ((Apple)first).color.equals(third.color);
ג. (5 נק') כתבו במחלקה הראשית פעולה חיצונית המקבלת מערך עצמים מטיפוס Object. הפעולה תדפיס כמה עצמים הם מטיפוס Apple, כמה עצמים מטיפוס Fruit ואינו מטיפוס Apple וכמה עצמים הם לא מטיפוס Fruit.
שאלה 5
נתונות שלושת המחלקות הבאות:
|
public class Test { public static void main(String[] args){ A a1 = new B(4, 2); System.out.println(a1); A a2 = new A(4, 2); System.out.println(a2); B a3 = new B(4, 2); System.out.println(a3); A b1 = new A(); System.out.println(b1); A c1 = new B("something"); System.out.println(c1); } } |
public class B extends A { private int y ; public B (int x) { super(x, x); this.y = x; } public B(int x, int y) { this(x * y); } public B(String s) { System.out.println (s+"%"+ this.y); } public String toString() { return this.x + " " + this.y ; } } |
public class A { protected int x; public A(){ this.x = 5; } public A(int x) { this.x = x;} public A(int x, int y) { this(x + y); } public int method (int i) { return x + i; } public String toString() { return this.x + " * "; } } |
א . (10 נק') עקבו אחרי ביצוע פעולה הראשית main ורשמו מה יהיה הפלט. יש להראות את העצמים שנוצרו ואת ערכי התכונות שלהם.
ב. (7.5 נק') לכל אחת מהפעולות הבאות קבעו אם אפשר להוסיף אותה במחלקה A, וציינו את האפשרות המתאימה מבין האפשרויות הבאות:
- שגיאת קומפילציה.
- קוד תקין, דריסה (overriding).
- קוד תקין, העמסה (overloading).
- public int method () { return 1; }
- public double method (int i){ return i; }
- public void method (double i){ System.out.print(i); }
ג. (7.5 נק') אין קשר לסעיף ב'.
לכל אחת מהפעולות הבאות קבעו אם אפשר להגדיר אותה במחלקה B וציינו את האפשרות המתאימה מבין האפשרויות הבאות:
- שגיאת קומפילציה.
- קוד תקין, דריסה (overriding)
- קוד תקין, העמסה (overloading)
- public int method () { return 10; }
- public int method (int i){ return i*10; }
- public void method (int i){ System.out.print(10*i); }
שאלה 6
נתונות שלושת המחלקות הבאות: One, Two, Tester :
|
public class Tester { for(int i=0; i < arr.length; i++) { arr[i].f(num); } } public static void what(One[] arr) { int k=0; for(int i = 0; i < arr.length; i++) { if(arr[i] instanceof Two) k++; } k = arr.length - k; System.out.println("k = "+ k); } |
public class One { protected int x; public One(){ this.x = 1; } public One(int x){ this.x = x; } public void f(int x){ this.x += x; } public String toString(){ return "x=" + this.x; } } // end of One |
|
public static void print(One[] arr){ for(int i=0; i < arr.length; i++) { System.out.println(i+" "+arr[i]); } } public static void main(String [] args) { One[] arr = new One[6]; arr[0]= new One(); arr[1]= new One(3); arr[2] = new Two(); arr[3] = new Two(2); arr[4] = new Two(5); arr[5] = arr[1]; Tester.print(arr); Tester.doF(arr, 2); Tester.print(arr); Tester.what(arr); } } |
public class Two extends One { public Two() { super(3); }
public Two(int x) { super.f(x); f(x); } public void f(int x) { this.x -= x; super.f(x); } }// end of Two |
א. (20 נק') עקבו אחרי ביצוע הפעולה הראשית ורשמו מה יהיה הפלט של הפעולה. יש להציג את כל העצמים שנוצרו ואת השינויים בערכי התכונות שלהם במהלך הביצוע .
ב . (5 נק') מה מבצעת הפעולה what?
עמוד מתוך 18