מה"ט מבני נתונים ותכנות מונחה עצמים — הנדסאי תוכנה — קיץ 2025 מועד א' (97105)

public static void addToProperQueue(Queue<String> q, String s)

כתבו פעולה המקבלת תור של מחרוזות "תקין" q ומחרוזת s. הפעולה תוסיף את המחרוזת לתור כך שהוא יישאר תקין.

public static boolean isProperQueue(Queue<String> q)

כתבו פעולה המקבלת תור של מחרוזות. הפעולה תבדוק אם התור הוא "תור תקין". אם כן – הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

public static void fixIt(Queue<String> q)

כתבו פעולה המקבלת תור של מחרוזות. הפעולה תבדוק אם התור הוא "תור תקין" ואם לא, הפעולה תשנה את סדר המחרוזות בתור כך שהוא יהיה "תקין".

מהי סיבוכיות הפעולות שכתבתם בסעיפים א'-ג'? הסבירו את תשובתכם.

public static boolean isSequenceK(Node<Integer> p1, Node<Integer> p2)

כתבו פעולה המקבלת שתי הפניות p1 ו-p2 לחוליות שונות בשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם החוליות בין p1 (כולל) ל-p2 (לא כולל) מהוות "רצף K". אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

example: descriptionHebrew: לדוגמה, עבור השרשרת שלפניכם תחזיר הפעולה ערך true: p1 מצביע על החוליה השלישית (4), p2 מצביע על החוליה השביעית (14).

chainValues: [10, 14, 4, 4, 4, 4, 14, 14]

p1Index: 2

p2Index: 6

confidence: MEDIUM — figure is a box-and-pointer diagram; index positions transcribed visually, re-verify against source before use as a solve-oracle input.

public static boolean isSequenceList(Node<Integer> chain)

שרשרת חוליות נקראת "שרשרת רצפים" אם היא מורכבת מכמה "רצפי K". כתבו פעולה המקבלת הפניה לחוליה הראשונה של שרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם השרשרת היא "שרשרת רצפים". אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

example: descriptionHebrew: לדוגמה, השרשרת שלפניכם היא "שרשרת רצפים":

chainValues: [2, 2, 4, 4, 4, 4, 1, 3, 3, 3]

מהי סיבוכיות הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.

נתונה פעולה ראשית במחלקה Test. (1) שרטטו את עץ הירושה עבור שתי אפשרויות היררכיות בין המחלקות כך שהפעולה הראשית תהיה תקינה והתוכנית תרוץ ללא שגיאות. (2) רוצים להוסיף בסוף התוכנית את שורת הקוד: Q q1 = (Q) p1; האם התוכנית הראשית תהיה תקינה עבור שתי האפשרויות שציינתם? אם לא – מהו סוג השגיאה שתתרחש?

codeBlock:

public class Test {
    public static void main(String[] args){
        S s1 = new R();
        P p1 = (P)(new R());
        S s2 = new P();
        P p2 = new Q();
//      (*****)
    }
}

appendedLineHebrew: Q q1 = (Q) p1;

לפניכם המחלקות First, Second. במחלקות Program-ו First, Second חסר מימוש בנאים ופעולות ToString. השלימו את הפעולות במחלקות First-ו Second כך שאחרי הרצת הפעולה הראשית של המחלקה Program יתקבל הפלט הנתון.

givenStubs:

public class First {
 private static int c = 0;
 protected int num;
 public First(int num){...}
 public String toString(){...}
} // stub — body to complete

givenStubsSecond:

public class Second extends First{
 private char ch;
 public Second(int num, char ch){...}
 public String toString(){...}
} // stub — body to complete

programAndExpectedOutput:

public class Program{
 public static void main(String[] args) {
  First f1 = new First(10);
  System.out.println("f1 is "+f1);
  First f2 = new Second(3,'A');
  System.out.println("f2 is "+f2);
  First f3 = new Second(4,'Z');
  System.out.println("f3 is "+f3);
  First f4 = new First(7);
  System.out.println("f4 is "+f4);
 }
}

expectedOutput: [f1 is 1-10, f2 is 2-6-A, f3 is 3-12-Z, f4 is 4-28]

לפניכם קוד המחלקה Two. המחלקה יורשת מהמחלקה One. כתבו במחלקה One את התכונות והפעולות הנדרשות. יש לציין הרשאת גישה (public, protected, private) לכל תכונה ולכל פעולה. אין צורך לממש את הפעולות. אין לשנות את הקוד של המחלקה Two.

codeBlock:

public class Two extends One
{
    private int z;
    public Two()
    {
        this.z = 11;
    }

    public Two(String s1, int z)
    {
        super(s1);
        this.z = z;
    }

    public double p1(int a)
    {
        return a * super.p1(a);
    }

    public int p2()
    {
        return One.w + this.m();
    }

    public void print()
    {
        One.d();
        System.out.println(s+"SON");
    }
}