אתם מתרגלים שאלה מתוך מה"ט מבני נתונים ותכנות מונחה עצמים — הנדסאי תוכנהמבחן 2026 · אביב מועד א · שאלה 6כל שאלות המבחן ←
מבנים לינאריים›רשימות מקושרות

נתונה המחלקה SpecNode:

public class SpecNode {
    private int value;
    private int numOfSmallers;
    private SpecNode next;

    public SpecNode (int val) {
        this.value = val;
        this.numOfSmallers = 0;
        this.next = null;
    }
}

לכל תכונה במחלקה הוגדרו פעולות get/set. בשרשרת חוליות מסוג SpecNode:

  • value – מספר שלם.
  • numOfSmallers – מספר החוליות המופיעות אחרי החוליה הנוכחית בשרשרת שערך ה-value שלהן קטן מערך ה-value של החוליה הנוכחית.
  • next – מצביע לחוליה הבאה.

לדוגמה (בכל חוליה: value, numOfSmallers):

(7, 4) → (1, 0) → (4, 2) → (8, 2) → (2, 1) → (1, 0)

המצביע P מצביע על החוליה השלישית (value=4).

  • ערך ה-value של החוליה הראשונה הוא 7, ואחריה יש ארבע חוליות שערכי ה-value שלהן קטן מ-7, ובגלל זה ערך התכונה numOfSmallers של החוליה הראשונה הוא 4.
  • P מצביע על חוליה עם value=4, והתכונה numOfSmallers=2 מציינת כי יש שתי חוליות אחריה שערכי ה-value שלהן קטנים מ-4 (כלומר 1 ו-2).
סעיף א

כתבו פעולה חיצונית המכניסה חוליה חדשה לשרשרת במיקום pos ועם ערך val. הפעולה מקבלת הפניה לחוליה הראשונה של שרשרת חוליות מסוג SpecNode, מספר שלם val ומספר שלם חיובי pos (המיקום הראשון בשרשרת הוא 1). אפשר להניח כי מיקום pos חוקי (אינו עולה על אורך רשימה+1). לאחר ההוספה, יש לעדכן את כל ערכי numOfSmallers בהתאם. כותרת הפעולה:

public static SpecNode addNum(SpecNode list, int val, int pos)

לדוגמה: אחרי זימון הפעולה addNum(list, 3, 5) השרשרת שתתקבל תהיה:

(7, 5) → (1, 0) → (4, 3) → (8, 3) → (3, 2) → (2, 1) → (1, 0)

(החוליה (3, 2) היא החוליה החדשה, במקום החמישי.)

סעיף ב

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

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי