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

נתונה המחלקה Range (טווח), ולה שתי תכונות: low ו-high, המקיימות high ≥ low, עם get/set. מספר x "מוכל" בעצם Range אם low ≤ x ≤ high. שרשרת חוליות lst1 מטיפוס מספר שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם עבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 שמכילה אותו. הנחות: lst1 ו-lst2 אינן null; כל העצמים בשרשרת lst2 אינם null; השרשרת lst1 ממוינת בסדר עולה; השרשרת lst2 ממוינת בסדר עולה, כלומר עבור כל חוליה קטן ה-high שלה מה-low של החוליה הבאה אחריה בשרשרת.

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; }
}

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; }
}

שרשרת lst1 המוכלת בשרשרת lst2 (דוגמת השאלון)

lst1: (-9)->(-8)->(-7)->(12)->(14)->(15)->null
lst2: [-20,-10]->[-9,0]->[2,4]->[12,12]->[14,17]->null

נתונה המחלקה TwoStack, ולה שתי תכונות: numbers (מחסנית מטיפוס שלם) ו-sums (מחסנית מטיפוס שלם). היחס בין numbers ל-sums: המספר בסוף המחסנית sums שווה למספר בראש המחסנית numbers; המספר השני מסוף sums שווה לסכום שני המספרים האחרונים ב-numbers; המספר השלישי מסוף sums שווה לסכום שלושת המספרים האחרונים ב-numbers; וכן הלאה עד המספר בראש sums, שהוא סכום כל המספרים ב-numbers. במילים אחרות: sums מחזיקה, מהתחתית לראש, את הסכום המצטבר של numbers מהתחתית שלה כלפי מעלה.

המחסניות המקבילות בדוגמת השאלון (numbers מלמטה: 2,-1,4,3,-9)

numbers (top->bottom): -9,3,4,-1,2   sums (top->bottom): -1,8,5,1,2

נתונות שתי הפעולות הרקורסיביות הבאות, הפועלות על מחסנית st מטיפוס שלם. סעיף א עוסק ב-stackSod1, וסעיף ב עוסק ב-stackSod2 (המשתמשת ב-stackSod1 מסעיף א).

public static void stackSod1(Stack<Integer> st, int element)
{
    if(st.isEmpty())
        st.push(element);
    else
    {
        int val = st.pop();
        stackSod1(st, element);
        st.push(val);
    }
}

public static void stackSod2 (Stack<Integer> st)
{
    if(!st.isEmpty())
    {
        int val = st.pop();
        stackSod2(st);
        stackSod1(st, val);
        st.push(val);
    }
}

המחסנית הנתונה בשני הסעיפים (מהראש לתחתית: 6,3,7,4)

st (top->bottom): 6,3,7,4