אתם מתרגלים שאלה מתוך בגרות מדעי המחשב — מבני נתונים (שאלון 899271)מבחן 2022 · קיץ מועד א · שאלה 4כל שאלות המבחן ←
מבנים לינארייםרשימות מקושרות

נתונה המחלקה Range (טווח), ולה שתי תכונות: low ו-high, המקיימות high ≥ low, עם get/set. מספר x "מוכל" בעצם Range אם low ≤ x ≤ high. שרשרת חוליות lst1 מטיפוס מספר שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם עבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 שמכילה אותו. הנחות: lst1 ו-lst2 אינן null; כל העצמים בשרשרת lst2 אינם null; השרשרת lst1 ממוינת בסדר עולה; השרשרת lst2 ממוינת בסדר עולה, כלומר עבור כל חוליה קטן ה-high שלה מה-low של החוליה הבאה אחריה בשרשרת.

public class Node<T> {
    private T value;
    private Node<T> next;
    public Node(T value) { this.value = value; this.next = null; }
    public T getValue() { return value; }
    public void setValue(T value) { this.value = value; }
    public Node<T> getNext() { return next; }
    public void setNext(Node<T> next) { this.next = next; }
}

public class Range {
    private int low;
    private int high;
    public Range(int low, int high) { this.low = low; this.high = high; }
    public int getLow() { return low; }
    public void setLow(int low) { this.low = low; }
    public int getHigh() { return high; }
    public void setHigh(int high) { this.high = high; }
}

שרשרת lst1 המוכלת בשרשרת lst2 (דוגמת השאלון)

lst1: (-9)->(-8)->(-7)->(12)->(14)->(15)->null
lst2: [-20,-10]->[-9,0]->[2,4]->[12,12]->[14,17]->null
סעיף א

ממשו את הפעולה החיצונית שלהלן: הפעולה מחזירה true אם lst1 "מוכלת" ב-lst2, אחרת מחזירה false. הפעולה חייבת לעבוד בסיבוכיות זמן ריצה של O(N), כאשר N הוא אורך השרשרת הארוכה מבין שתי השרשראות.

public static boolean isIncluded (Node<Integer> lst1, Node<Range> lst2)

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

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

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

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