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

שתי פעולות עצמאיות על תור מספרים שלמים: putInPlace ממקמת מספר נתון כך שכל הקטנים ממנו לפניו וכל השווים/גדולים ממנו אחריו; moveToFront מעבירה את k האיברים האחרונים בתור אל ראשו. בשני הסעיפים פותרים אך ורק עם פעולות התור (insert/remove/head/isEmpty), בעזרת תורי עזר.

putInPlace: עבור q=[2,10,12,3,7,4,1] (ראש→סוף) ו-num=9, תוצאה אפשרית: [2,3,7,4,1,9,10,12], והפעולה מחזירה 6 (המיקום הסידורי של 9, החל מ-1).

q (ראש→סוף): 2,10,12,3,7,4,1  num=9
תוצאה אפשרית (ראש→סוף): 2,3,7,4,1,9,10,12   (הפעולה מחזירה 6)

moveToFront: עבור q=[7,2,5,4,6,8,10,12] (ראש→סוף) ו-k=5, מעבירים את 5 האיברים האחרונים (4,6,8,10,12) אל ראש התור: תוצאה [4,6,8,10,12,7,2,5].

q (ראש→סוף): 7,2,5,4,6,8,10,12   k=5
תוצאה (ראש→סוף): 4,6,8,10,12,7,2,5

בעזרת המחלקה BinNode אפשר לממש שרשרת חוליות דו-כיוונית (getLeft = 'קודם', getRight = 'הבא'). מבקשים לסדר מחדש כך שהזוגיים יופיעו לפני האי-זוגיים, בלי מבנה נתונים נוסף ובלי לשנות את זהות החוליה הראשונה שהקורא מחזיק.

לפני הפעולה: chain -> 1 <-> 11 <-> 4 <-> 6 <-> 3 (null בשני הקצוות). אחרי הפעולה יכולה להיות: chain -> 6 <-> 4 <-> 11 <-> 1 <-> 3 (הזוגיים 6,4 בתחילת השרשרת, האי-זוגיים 11,1,3 בסופה; סדר האיברים בתוך כל קבוצה אינו חשוב).

לפני:  null <- 1 <-> 11 <-> 4 <-> 6 <-> 3 -> null   (chain מצביע על 1)
אחרי (יכולה להיות): null <- 6 <-> 4 <-> 11 <-> 1 <-> 3 -> null   (chain מצביע על 6)

Flower מחלקת-על עם תכונה מוגנת height ותכונה פרטית price; Rose יורשת ממנה, מוסיפה color פרטית ופעולת validHeight. שלושה סעיפים: זיהוי היגדי ירושה נכונים/שגויים, בדיקת תקינות שורות קוד (קומפילציה/ריצה), וכתיבת פעולת מיון-סוגים.

public class Flower {
  protected int height;
  private int price;
  public Flower(int val) { this.height = val; this.price = 10; }
  public int getHeight() { return this.height; }
  public int getPrice() { return this.price; }
}
public class Rose extends Flower {
  private String color;
  public Rose(int val, String col) {
    super(val);
    this.color = col;
  }
  public boolean validHeight() {
    return this.height > 10 && this.height < 30;
  }
}