מה"ט מבני נתונים ותכנות מונחה עצמים — הנדסאי תוכנה — קיץ 2024 מועד א' (97105)

כתבו פעולה המקבלת מחסנית של מספרים שלמים ובודקת אם היא "מאוזנת". יש לשמור על תוכן של המחסנית אחרי ביצוע הפעולה.

כותרת הפעולה:

public static boolean isBalanced(Stack<Integer> st)

מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.

כתבו פעולה המקבלת תור של מספרים שלמים ו-2 מספרים נוספים x ו-y. אם אורך התור זוגי, הפעולה תחליף את 2 האיברים האמצעיים לערכים x ו-y. אם אורך התור אי-זוגי, הפעולה תיצור מספר אקראי בין x ל-y (כולל) ותחליף את האיבר האמצעי של התור לערך אקראי שנוצר. שאר איברי התור יישארו ללא שינוי.

לדוגמה: עבור התור q הבא ופרמטרים x=20, y=30

[8, 10, 11, 2, 3, 16, 12, 4] (משמאל לימין; מאומת מול -layout וכלל ההחלפה)

התור q אחרי זימון הפעולה יהיה:

[8, 10, 11, 20, 30, 16, 12, 4]

מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.

כתבו פעולה המקבלת הפנייה לשרשרת חוליות של מספרים שלמים. הפעולה תבדוק אם ערכים של השרשרת הם סדרה יורדת. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.

כותרת הפעולה:

public static boolean isDownList (Node<Integer> chain)

כתבו פעולה המקבלת מספר שלם וחיובי num וזוג מספרים שלמים a ו-b. הפעולה תחזיר הפניה לחוליה הראשונה של שרשרת חוליות שאבריה הם num המספרים הראשונים של סדרה יורדת המתחילה במספרים a ו-b.

כותרת הפעולה:

public static Node<Integer> buildDown (int num, int a, int b)

לדוגמה: עבור הזימון buildDown(9, 55, 34) הפעולה תחזיר הפנייה לחוליה הראשונה של שרשרת החוליות הבאה:

chain → 55 → 3 → 2 → 1 → 8 → 5 → 3 → 2 → 1

⚠️ כך מופיעה השרשרת בתרשים בעמוד זה (מאומת חזותית ב-200dpi, לא תקלת OCR). שימו לב שזו אינה הסדרה 55,34,21,13,8,5,3,2,1 שמתקבלת מהנוסחה שבגוף השאלה (איבר1=55, איבר2=34, איברN=|איברN-1 − איברN-2| עבור N≥3) — וגם אינה תואמת את התרשים המקביל במבחן ה-C# באותו שאלון (עמ' 13), שם השרשרת מוצגת נכון כ-55,34,21,13,8,5,3,2,1. זהו כנראה פגם דפוס בגרסת ה-Java בלבד של שאלון זה. הועתק verbatim מהמקור; ראו fidelity_notes.

מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.