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

ענה על שתיים מן השאלות 4-6 (25 נקודות לכל שאלה). בכל שאלה שנדרש בה שימוש תוכל להיעזר בפעולות המחלקות תור, מחסנית, עץ בינרי וחוליה — בלי להשתמש באוגן, אם אתה משתמש בעולות נוספות, עליך למש אותן.

public class TwoItems
{
    private int num1;
    private int num2;

    public TwoItems(int number1, int number2)
    {
        this.num1 = number1;
        this.num2 = number2;
    }
    // get/set generated for num1, num2
}

המחסנית stk1 לפני הפעולה (מהראש לתחתית): 1,6,32,5,5,7,4,9. לאחר הפעולה תיראה כך: 9,4,7,5,5,32,6,1 (א). בסעיף ב אותה stk1 מתפרקת לזוגות TwoItems: (1,9),(6,4),(32,7),(5,5) מהראש לתחתית.

stk1 (top->bottom): 1 6 32 5 5 7 4 9

שים לב: לשאלה זו נוסח אחד ב-Java (עמוד זה) ונוסח אחר ב-C# (בעמוד הבא). לפניך הפעולה sod1, המקבלת הפניה lst לשרשרת חוליות ותו ch, ומחזירה הפניה לחוליה הראשונה בשרשרת שערכה שווה ל-ch (או null אם אינו מופיע).

public static Node<Character> sod1(Node<Character> lst, char ch)
{
    if (lst == null)
        return null;
    if (lst.getValue() == ch)
        return lst;
    return sod1(lst.getNext(), ch);
}

public static boolean sod2(Node<Character> lst)
{
    if (sod1(lst,'a') != null && sod1(lst,'b') != null)
        return true;
    return false;
}

דוגמת מעקב לסעיף א: שרשרת c->d->v->h, קריאה sod1(lst,'v').

lst: c -> d -> v -> h -> null

דוגמאות לסעיף ג: y-b-a (b,a סמוכים, true); m-a-b-l (a,b סמוכים, true); w-a-c-b (a,b קיימים אך לא סמוכים, false).

y->b->a  |  m->a->b->l  |  w->a->c->b

נתונה הפעולה הבאה (הפעולה מחזירה true אם x קטן מכל הערכים בעץ t, אחרת מחזירה false; סיבוכיות זמן הריצה של הפעולה היא O(n), כאשר n מייצג את מספר הצמתים בעץ t):

public static boolean lessThanTree(BinNode<Integer> t, int x)
{
    if (t == null)
        return true;
    if (!(x < t.getValue()))
        return false;
    return lessThanTree(t.getLeft(), x) && lessThanTree(t.getRight(), x);
}
// lessThanTree מוחזרת true אם x קטן מכל הערכים בעץ t, אחרת false. סיבוכיות זמן הריצה היא O(n), כאשר n מייצג את מספר הצמתים בעץ t.