מה"ט מבני נתונים ותכנות מונחה עצמים — הנדסאי תוכנה — קיץ 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] (משמאל לימין)

התור 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 → 34 → 21 → 13 → 8 → 5 → 3 → 2 → 1

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