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

נתונה פעולה חיצונית נתונה delete (זמינה לשימוש, אין לממש) המוחקת חוליה עם ערך נתון משרשרת. נתונה גם המחלקה BiList - דו-שרשרת, ולה שתי תכונות: lst1 ו-lst2, שתיהן הפניות לתחילת שרשרת חוליות מטיפוס שלם. לפניך ממשק חלקי של המחלקה (בונה + addNum) - זמין לשימוש; אסור להוסיף לו get/set או פעולות נוספות.

// פעולה נתונה (זמינה לשימוש, אין לממש):
// public static Node<Integer> delete (int num, Node<Integer> lst)
// מוחקת את החוליה שבה הערך num משרשרת lst, ומחזירה מצביע לתחילת השרשרת.

// נתונה המחלקה BiList - דו-שרשרת, ולה שתי תכונות:
// lst1 - הפניה לתחילת שרשרת חוליות מטיפוס שלם
// lst2 - הפניה לתחילת שרשרת חוליות מטיפוס שלם
// לפניך ממשק חלקי (זמין לשימוש, אין להוסיף לו get/set או פעולות נוספות):
public BiList ()                              // בונה עצם עם שתי שרשראות ריקות
public void addNum (int num, int codeList)    // מוסיפה חוליה עם הערך num לסוף lst1 (אם codeList=1) או לסוף lst2 (אם codeList=2)

שרשרת lst ופיצולה ל-lst1 (המחצית הגדולה) ו-lst2 (המחצית הקטנה), כפי שמודגם בשאלון

lst:  88 -> -9 -> 0 -> 10 -> 6 -> 13 -> null
BiList result:
  lst1: 88 -> 10 -> 13 -> null
  lst2: -9 -> 0 -> 6 -> null

בשרשרת חוליות, "העברה מעגלית של n חוליות" היא העברת n החוליות האחרונות לתחילת השרשרת (בלי לשנות את סדר ההופעה של אותן n חוליות ביניהן). הנח: n≥0 ומספר החוליות בשרשרת גדול מ-n.

שרשרת lst לפני ואחרי העברה מעגלית של n=2 חוליות (דוגמת השאלון)

before: 5 -> 1 -> 2 -> 8 -> 4 -> null
after (n=2): 8 -> 4 -> 5 -> 1 -> 2 -> null

לפניך שתי פעולות רקורסיביות הפועלות על מערך arr מטיפוס שלם. סעיף א עוסק ב-sod1, וסעיף ב עוסק ב-sod2 (המשתמשת ב-sod1 מסעיף א).

public static boolean sod1 (int[] arr, int x, int i)
{
    if ( i == -1) return false;
    if (arr[i] == x) return true;
    return sod1(arr, x, i - 1);
}

public static boolean sod2 (int[] arr, int x, int i)
{
    if ( i == 0) return false;
    if (sod1(arr, x - arr[i], i - 1)) return true;
    return sod2(arr, x, i - 1);
}

המערך הנתון בשני הסעיפים

a: index 0..4 = [5, 4, 15, 12, 2]