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

לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו (שמות הפעולות אינם כתובים ב-Java או ב-C#): 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

עץ בינרי כללי (לא בהכרח עץ חיפוש ממוין) מיוצג בעזרת המחלקה BinNode<T> (value, left, right, get/set). רשימה מקושרת חד-כיוונית מיוצגת בעזרת המחלקה Node<T> (value, next, get/set) — שתיהן מוגדרות למטה. סעיף א עוסק בבדיקת קיום ערך בעץ בינרי כלשהו; סעיף ב עוסק בהשוואת שני עצים בינריים לא ריקים t1 ו-t2 ובבניית רשימה חדשה מהערכים שקיימים ב-t1 ואינם קיימים ב-t2, תוך שימוש בפעולה מסעיף א; סעיף ג עוסק בסיבוכיות הפעולה מסעיף ב. הפעולה הנתונה check(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();
}

שאלה זו בשאלון המקורי כללה שני סעיפים א-ב שאין קשר ביניהם ("אין קשר בין הסעיפים"): סעיף א עוסק בגרף ובסריקות DFS/BFS (מובא כאן במלואו), וסעיף ב הוא טבלת שיטת ההובלה/סימפלקס (תחום חקר ביצועים) שאינו קיים בשאלוני 899371/899271 הנוכחיים ולכן לא נכלל.

הגרף 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