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

לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו (שמות הפעולות אינם כתובים ב-Java): insert(x) — מכניסה איבר x שערכו נתון (שלם) למבנה. showMin() — מחזירה את הערך הנמוך ביותר במבנה, בלי לשנות את המבנה. getMax() — מחזירה את האיבר שערכו הגדול ביותר במבנה, ומוציאה אותו מן המבנה (אם יש יותר מאיבר אחד בעל אותו הערך המקסימלי, מוציאה ומחזירה את זה שמופיע ראשון מבין השווים). exists(x) — פעולה בוליאנית: true אם קיים במבנה איבר שערכו x, אחרת false. div7() — פעולה בוליאנית: true אם קיים במבנה איבר שערכו מתחלק ב-7 בלי שארית, אחרת false.

השאלון עצמו נותן דוגמה פתורה (לא לביצוע): מבנה נתונים לביצוע insert ו-showMin בסיבוכיות O(1) ו-exists ו-getMax בסיבוכיות O(n) — הפתרון המוצע שם הוא רשימה מקושרת דו-כיוונית lst מטיפוס שלם, עם מצביע נוסף min לאיבר המינימלי: insert מכניס לראש הרשימה ומעדכן את min אם צריך (O(1)); showMin מחזיר את הערך שמצביע עליו min (O(1)); exists ו-getMax עוברים על כל הרשימה (O(n)).

בשני הסעיפים הבאים (א-ב) יש להציע — לכל אחד בנפרד — מבנה נתונים מתאים לדרישת הסיבוכיות השונה הנתונה, להסביר כיצד ממומשת כל פעולה, ולנמק מדוע המימוש עומד בדרישת הסיבוכיות.

הדוגמה הפתורה שבשאלון: רשימה מקושרת דו-כיוונית + מצביע min

lst (doubly linked, unsorted): head <-> ... <-> tail
min -> pointer to the current minimum node

לפניך הפעולה check(t1, t2) ב-Java. הפעולה מקבלת שני עצים בינריים לא ריקים מטיפוס שלם, t1 ו-t2, ומחזירה רשימה המכילה את כל המספרים הנמצאים בעץ t1 ואינם נמצאים בעץ t2. הפעולה מזמנת פעולה נוספת המקבלת שלושה פרמטרים.

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

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

// הפעולה check(t1,t2) הבאה נתונה (אינה חלק מהמימוש):
public static Node<Integer> check(BinNode<Integer> t1, BinNode<Integer> t2) {
    Node<Integer> first = new Node<Integer>(-1);
    first = check(t1, t2, first);
    return first.getNext();
}

הגרף G = (V , E) הוא גרף לא מכוון המיוצג על ידי רשימת הסמיכויות שלפניך: a → b → c → d b → a → c c → a → b d → a → f → e e → d → f f → e → d

רשימת הסמיכויות של G כפי שנדפסה בשאלון

a: b, c, d
b: a, c
c: a, b
d: a, f, e
e: d, f
f: e, d