בגרות מדעי המחשב 899271, קיץ 2019 מועד א'

לפניך הפעולה secret1:

public static boolean secret1 (int num, int digit) {
    if (num < 10)
        return ( num % 2 == digit % 2 );
    if ( num % 2 != digit % 2 )
        return false;
    return secret1 ( num / 10, digit );
}

לפניך הפעולה secret2:

public static boolean secret2 ( Stack<Integer> s ) {
    boolean ok;
    int x;
    if ( s.isEmpty() )
        ok = true;
    else {
        x = s.pop();
        if ( !(secret1 (x, x % 10)) )
            ok = false;
        else
            ok = secret2(s);
    }
    return ok;
}

"תור מספר" הוא תור (המיוצג כשרשרת חוליות מטיפוס Node<Integer>) של ספרות בין 1 ל-9 (כולל), המייצג מספר שלם -- החולייה הראשונה (ראש התור) היא ספרת האחדות, השנייה ספרת העשרות וכן הלאה (למשל התור [6,9,1] מייצג את 196). הנח שמספר הספרות האפשרי בתור לא חורג ממה שטיפוס int יכול להכיל. המחלקה הגנרית Node<T> (עם getValue/setValue/getNext/setNext, ובC# Get/Set-PascalCase) אינה מודפסת מחדש בעמוד זה של השאלון -- היא המחלקה הסטנדרטית של הקורס לשרשראות חוליות, הזהה לזו שמופיעה מפורשות בשאלות שרשרת-חוליות אחרות באותה סדרת בחינות (למשל 899381/2022 שאלה 4).

public class Node<T> {
    private T value;
    private Node<T> next;
    public Node(T value) { this.value = value; this.next = null; }
    public T getValue() { return value; }
    public void setValue(T value) { this.value = value; }
    public Node<T> getNext() { return next; }
    public void setNext(Node<T> next) { this.next = next; }
}

תור-מספר בודד המייצג את 196: ראש התור (יחידות)=6, לאחריו 9 (עשרות), 1 (מאות)

q -> [6] -> [9] -> [1] -> null   (ראש=יחידות)

שרשרת של ארבעה תורי-מספר, המייצגים (בהתאמה) את 62, 427, 82, 691

lst -> [q:2,6] -> [q:7,2,4] -> [q:2,8] -> [q:1,9,6] -> null

נתונה המחלקה Range שיש לה שתי תכונות: low -- מספר מטיפוס שלם. high -- מספר מטיפוס שלם, גדול מ-low. הנח שלכל תכונה הוגדרו ב-Java הפעולות get/set (ובC# Get/Set). עץ טווחים הוא עץ שאיבריו הם אובייקטי Range. עץ טווחים מסודר הוא עץ ריק, או עץ שבו לכל צומת מתקיימים: (1) אם יש בן שמאלי -- ה-low של הצומת שווה ל-low של הבן השמאלי, וה-high של הצומת גדול או שווה ל-high של הבן השמאלי; (2) אם יש בן ימני -- ה-high של הצומת שווה ל-high של הבן הימני, וה-low של הצומת קטן או שווה ל-low של הבן הימני; (3) אם יש שני בנים -- ה-high של הבן השמאלי קטן מה-low של הבן הימני. השאלה כוללת סעיף יחיד (ללא תת-סעיפים נוספים) ולכן מסומנת כסעיף א.

public class Range {
    private int low;
    private int high;
    public Range(int low, int high) { this.low = low; this.high = high; }
    public int getLow() { return low; }
    public void setLow(int low) { this.low = low; }
    public int getHigh() { return high; }
    public void setHigh(int high) { this.high = high; }
}

public class BinNode<T> {
    private T value;
    private BinNode<T> left;
    private BinNode<T> right;
    public BinNode(T value) { this.value = value; this.left = null; this.right = null; }
    public T getValue() { return value; }
    public void setValue(T value) { this.value = value; }
    public BinNode<T> getLeft() { return left; }
    public void setLeft(BinNode<T> left) { this.left = left; }
    public BinNode<T> getRight() { return right; }
    public void setRight(BinNode<T> right) { this.right = right; }
}

דוגמה לעץ טווחים מסודר: שורש [1,10]; בן שמאלי [1,4] עם בן שמאלי [1,3]; בן ימני [5,10] עם בנים [5,6] ו-[8,10]

            [1,10]
           /      \
       [1,4]      [5,10]
        /          /    \
     [1,3]      [5,6]  [8,10]