בחינת מתכונת במדעי המחשב תשפ"ג

1. משך הבחינה: שלוש שעות.

2. מבנה השאלון ומפתח הערכה:  בשאלון זה שלושה פרקים.

פרק ראשון        –         בפרק זה יש שלוש שאלות , מהן עליך לענות על שתיים  25 - נקודות.

                        שאלה 1 חובה                                   (1 X 10)        

                        יש לענות על שאלה אחת מהשאלות 2-3            (1 X 15)        

פרק שני        –         בפרק זה יש שלוש שאלות,

                        מהן יש לענות על שתיים.                             (2 X 25)  50 נקודות.

פרק שלישי        –         בפרק זה יש שתי שאלות,

                        מהן יש לענות על אחת.                             (1 X 25) 25 נקודות.

3. חומר עזר מותר בשימוש:  כל  חומר מודפס או בכתב יד בלבד.

בהצלחה!

---

פרק ראשון - ענו על שאלה 1 ועל אחת מהשאלות 2-3 (25 נקודות)

שאלה 1-חובה (10 נקודות)

מערך יקרא מוכל שלא ברצף אם כל איבריו מופיעים לפי הסדר במערך השני אך לא בהכרח ברצף.  

למשל :  מערך A :  'ג','ד','ו','ל'

 מערך B :  'א','ב','ג','ד','ה','ו','י','כ','ל','ל','נ','נ'

אזי מערך A מוכל שלא ברצף במערך B   (הערה : מיקום התווים של מערך A במערך B מודגש).

1. כתבו פעולה המקבלת כפרמטרים שני מערכים של תווים ומחזירה אמת אם המערך הראשון מוכל שלא ברצף במערך השני, אחרת מחזירה שקר.  אין לשכפל את המערכים.

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

שאלה 2  (15 נקודות)

נתונה המחלקה Time  המייצגת זמן בשעון:

Time
שעה ביממה דקה	int hour     (0-23) int minute (0-59)
פעולה בונה	public Time (int hour, int minute)
פעולה המקבלת עצם מטיפוס Time  ובודקת האם ערכיו שווים לTime הנוכחי	public boolean Equals(Time t)

הערה : השעה 7 והשעה 19 הינן שעות שונות.

כרטיס קולנוע Ticket מאופיין על-ידי חמש תכונות:

• שם הסרט – name  מטיפוס מחרוזת.
• שעת תחילת ההקרנה - time  מטיפוס Time.
• מחיר – price מטיפוס ממשי.
• מספר שורה – row  מטיפוס שלם.
• מספר כיסא - seat  מטיפוס שלם.

1. ממשו את הפעולה Equals במחלקה Time.

2. הוסיפו למחלקה Ticket פעולה המקבלת כרטיס (Ticket) : במידה שבשני הכרטיסים - זה שעליו מופעלת הפעולה וזה שהתקבל כפרמטר, שם הסרט ושעת ההקרנה זהים  הפעולה תחזיר את המרחק בשורות בין שני הכרטיסים בערך מוחלט, אחרת תחזיר 999.

3. כתבו פעולה חיצונית המקבלת מערך מטיפוס Ticket  וכרטיס ( (Ticket ומחזירה כמה כרטיסים במערך הינם לאותו סרט ובאותה שעה של הכרטיס שקבלה הפעולה כפרמטר.    ניתן להניח כי המערך מלא.

שאלה 3 (15 נקודות)

בגלריה לאומנות מוצגות עד 100 תמונות . כל תמונה Image מאופיינת ע"י התכונות הבאות:

• קוד תמונה
• שם האמן
• גודל התמונה  (במ"ר)
• מחיר התמונה (מספר ממשי)

המחלקה גלריה Gallery   מכילה מערך של תמונות.

1. כתבו את כותרת המחלקה Gallery   כולל התכונות שלה ופעולת הבנאי עם כל הפרמטרים.

2. כתבו פעולה במחלקה גלריה המקבלת גלריה וקוד תמונה ומסירה אותה ממערך התמונות בגלריה באופן שהמערך יישאר מצופף (= כל התאים הריקים בסוף המערך בלבד).

3. כתבו פעולה חיצונית המקבלת עצם מסוג גלריה וסוכמת את מחירי התמונות בגלריה ששווין מעל 1000 ₪ או שגודלן אינו עולה על  4.9  מ"ר.  

---

פרק שני - ענו על שתיים מהשאלות 4-6 (50 נקודות)

שאלה 4 (25 נקודות)

עץ "אומברה" הוא עץ שכל צמתיו מכילים אובייקט "גוונים" אשר לו שני צבעים, ראשון ושני.
העץ הוא עץ "אומברה" אם לכל אחד מהבנים ישנו לפחות צבע אחד זהה לאחד משני הצבעים בצומת האב שלו. דוגמה לעץ "אומברה":

Shade

private string one       private string two

public Shade(string one, string two)

 לפניך תיאור חלקי של המחלקה Shade המתאר את האובייקט גוונים.  כמו כן, הוגדרו פעולות get  סטנדרטיות לכל תכונה.

1. כתבו פעולה המקבלת עץ מטיפוס Shade ומחזירה true  אם הוא עץ "אומברה" ו- false אם לא.
2. כתבו פעולה המקבלת עץ מטיפוס Shade ומחזירה את כמות הצבעים השונים בעץ. בעץ הנתון בדוגמה הצבעים הם  כחול, ירוק, תכלת, סגול, ורוד ואדום ולכן הפעולה תחזיר 6.

3. מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיף 2 ? נמק/י ! 

שאלה 5 (25 נקודות)

נתונה הפעולה check המקבלת תור של מספרים q  ומספר x  :

.1

   

                        

               

       

       כתבו טבלת מעקב על הזימון   check(q,4)עבור התור  q :4,4,4,5(4-ראש התור).

 

       מה מבצעת הפעולה  ? מה תהיה תוצאת הזימון ?

2.    נתונה הפעולה Check1 המקבלת תור של מספרים q  :

       

      עקבו אחר הפעולה check1 עבור התור 2,3,1,1,4,4,4,5 : q   (2-ראש התור).

      במעקב הראו את הערכים של x ,y ,z והתור q לאחר כל שינוי. אין צורך לפרט

      את המעקב על הפעולה check.   מה מטרת הפעולה ?

1. .

3.   כתבו פעולה בשם maxQueue המקבלת תור של תורים.

      הפעולה תפעיל על כל אחד מהתורים בתור את הפעולה check1 ותעדכן כל תור לפי הפעולה.

      הפעולה  תחזיר את התור עבורו התקבל הערך המקסימאלי.  ניתן להניח כי התור אינו ריק.

שאלה 6 (25 נקודות)

1. כתבו פעולה המקבלת רשימה מעגלית של חוליות עם ערכים שלמים בכל אורך שהוא. עבור כל זוג חוליות שכנות/סמוכות הפעולה תחשב ותשמור את ההפרש בערך מוחלט בין הערכים שלהן ותדרוס את ערכי החוליות המקוריות. יתכן בהחלט שלחוליות שונות יש את אותו ערך.  סדר החוליות ברשימה הוא בכיוון השעון. יש לממש את הפעולה ללא יצירת חוליות חדשות !

לדוגמה - עבור השרשרת הבאה :

לאחר הפעולה תראה השרשרת כך:

2. כתבו פעולה המקבלת כפרמטר 2 רשימות מעגליות lst1,lst2 הממוינות בסדר יורד, כאשר בכל רשימה ערכים שלמים השונים זה מזה. הפעולה תיצור רשימה מעגלית ממוזגת חדשה בסדר יורד מ-2 הרשימות, כך שערך המופיע ב-2 הרשימות יופיע פעם אחת בלבד ברשימה המעגלית הממוזגת (= ללא חזרות).  הערה : אין קשר בין סעיפים 1 ו- 2 .

3. מהי סיבוכיות זמן הריצה של הפעולה שכתבת בסעיף 2 ? נמק/י !