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

נתונה המחלקה Game – משחק מחשב, ולה שתי תכונות: • name – שם המשחק, מטיפוס מחרוזת. • price – מחיר המשחק – מספר הגדול מ־0 , מטיפוס שלם. הניחו שיש פעולות get/Get ו־set/Set לתכונות המחלקה. נתונה המחלקה Store – חנות משחקי מחשב, ולה תכונה אחת: • lst – הפניה לשרשרת חוליות שאינה ריקה, מטיפוס Game . כל חוליה בשרשרת מכילה משחק הנמכר בחנות. הערה: המשחקים אינם מסודרים בשרשרת בסדר מסוים, וכל משחק מופיע פעם אחת בלבד.

תרשים 1 (עמוד 2): השרשרת lst הנתונה בדוגמה של סעיף א – שבע חוליות

Store.lst --> [.|*]->[.|*]->[.|*]->[.|*]->[.|*]->[.|*]->[.|null]
each cell's data pointer goes down to a Game box:
1: name: "a", price: 30
2: name: "g", price: 30
3: name: "b", price: 27
4: name: "v", price: 99
5: name: "k", price: 30
6: name: "c", price: 25
7: name: "p", price: 30
(the four price values 30 are printed in bold on the paper)

תרשים 2 (עמוד 2): השרשרת בתום הפעולה remove(3, 30)

Store.lst --> [.|*]->[.|*]->[.|*]->[.|null]
1: name: "b", price: 27
2: name: "v", price: 99
3: name: "c", price: 25
4: name: "p", price: 30  (30 in bold)

תרשים 3 (עמוד 3): השרשרת בתום הפעולה remove(5, 30)

Store.lst --> [.|*]->[.|*]->[.|null]
1: name: "b", price: 27
2: name: "v", price: 99
3: name: "c", price: 25

תרשים 4 (עמוד 3): השרשרת בתום הפעולה removeCheap(5)

Store.lst --> [.|*]->[.|null]
1: name: "v", price: 99
2: name: "p", price: 30

public static boolean mmm (Queue<Integer> q, int z)
{
    q.insert (0);
    int num = q.head();
    int y = 0;
    while (q.head() > 0)
    {
        if (y < z)
        {
            if (q.head() == num)
            {
                y++;
            }
            else
            {
                num = q.head();
                y = 1;
            }
        }
        q.insert (q.remove());
    }
    q.remove();
    return y == z;
}

public static int what (Queue<Integer> q, int n)
{
    if (mmm (q, n))
        return n;
    return what (q, n - 1);
}

עמוד 4 (Java) ועמוד 6 (C#): התור q הנתון לסעיף א

queue q (head on the LEFT, tail on the RIGHT, as the labels ראש התור / סוף התור are printed):
| 1 | 3 | 1 | 1 | 1 | 2 |
head -> 1, 3, 1, 1, 1, 2 <- tail

עמוד 4 (Java) ועמוד 6 (C#): טבלת המעקב הריקה של סעיף א(1)

טבלת המעקב הריקה של סעיף א (עמודות כפי שהן מודפסות, משמאל לימין על הדף):

| התור q | num | y | y < z | q.head() == num |
|---|---|---|---|---|
|  |  |  |  |  |

עמוד 5 (Java) ועמוד 7 (C#): התור q הנתון לסעיף ב (זהה לתור של סעיף א)

queue q (head on the LEFT, tail on the RIGHT, as the labels ראש התור / סוף התור are printed):
| 1 | 3 | 1 | 1 | 1 | 2 |
head -> 1, 3, 1, 1, 1, 2 <- tail

עמוד 5 (Java) ועמוד 7 (C#): טבלת המעקב המוצעת של סעיף ב(1)

טבלת המעקב המוצעת של סעיף ב (עמודות כפי שהן מודפסות, משמאל לימין על הדף):

| התור q שמתקבל בפעולה | הערך n שמתקבל בפעולה | mmm (q, n) == true | ערך מוחזר |
|---|---|---|---|
|  |  |  |  |

"עץ K־שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותר K קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים). שימו לב: ב"עץ K־שמאלי" ייתכן שאין שום מסלול המכיל K קשתות הפונות שמאלה (כלומר ייתכן שבכל אחד מן המסלולים יש פחות קשתות שמאליות מ־K). דוגמה: [העץ מתואר בתרשים: שורש; בן שמאלי L ובן ימני P; ל-L בן ימני יחיד L2; ל-P בן שמאלי Q ובן ימני עלה Q2; ל-Q בן שמאלי עלה Q3 ובן ימני עלה Q4 — סך הכול 8 צמתים] עץ זה אינו "עץ 1־שמאלי" כי בעץ יש מסלול שבו יש יותר מקשת אחת שמאלית (במסלול המקווקו יש שתי קשתות שמאליות). לעומת זאת, עץ זה הוא "עץ 2־שמאלי" כי אין בו מסלול שבו יותר משתי קשתות שמאליות (ובאותה מידה הוא גם "עץ 3־שמאלי", וגם "עץ 4־שמאלי" וכן הלאה).

עמוד 8: עץ הדוגמה של «עץ K־שמאלי», עם מסלול מקווקו

binary tree, 8 unlabelled nodes (drawn as empty circles), arrows point from parent to child:
  R            (root, top centre)
  R.left  = L  (drawn up-left of the root)
  R.right = P  (drawn right of the root)
  L.right = L2 (a single child of L, drawn down-RIGHT of L)
  P.left  = Q  ; P.right = Q2 (leaf)
  Q.left  = Q3 (leaf) ; Q.right = Q4 (leaf)
total: root, L, P, L2, Q, Q2, Q3, Q4 = 8 nodes.
A DASHED contour marks the path root -> P -> Q -> Q3 (one right edge then two LEFT edges);
this is the «מסלול המקווקו» the caption refers to.