בחינה ב-"מבנה נתונים – C++"  מועד א' – קיץ 2003

המרצה: ד"ר דן אופיר
קהל היעד: סטודנטים הנדסת חשמל ואלקטרוניקה

מועד הבחינה: 30.10.03   שעה: 9:00

משך הבחינה 3- שעות.

בחר שתי שאלות מקבוצת שאלות הראשונה
ושאלה אחת מקבוצת השאלות השניה
(ערכה של כל שאלה  בקבוצה א'  30%, ובקבוצה ב'  40%    ) 
השתדל לענות על השאלה בצורה מעמיקה – הציון נקבע על ידי הפרמטרים הבאים:
מודולריות, כלליות, בהירות (לשלב העורות בקוד).

השתמש באתר  :http://www.geocities.com/comp_ophir/
מותר השמוש במחברות ובספרים. 

קבוצה 1:
1. הורד את התוכנית sort הנמצאת באתר ב-c_lecture5    ושנה את המיון של quicksort 
      למיון בסדר יורד.
 
   2. נתונה סדרת מספרים  שאותה ממינים.
       הסדרה עוברת שנויים בשלבים השונים של המיון.  נתונות סדרות הביניים בכל שלבי המיון:

הסדרה	שלב	
	0  - הנתונים	
	1	
	2	
	3	
	4	
	5	
	6	
	7	

ציין מהי שיטת המיון שבעזרתה נעשה המיון.  אם ידוע שהמיון היה באחת השיטות הבאות:
Insertion, Selection ,Exchange  - נמק.
השלם את השורה הריקה  (שלב 0) – שורת הנתונים .
האם יש פתרון אחד או יותר לשחזור השורה הריקה?

3. תוריד מהאתר את התוכנית    Stack_insert מתוך c_final_examination_Oct_03 ובדוק 
    בעזרת  ה-debugger מה היה מצב המחסנית לפני ואחרי בצוע השיטה (method) בשם insert. 
    הצג את תוכנה של המחסנית st1 לפני ואחרי פעולת ה-insert. 
   קבע מה עושה שיטת ה-insert?   מהם הארגומנטים שלה.  

4. קח Project line  מתוך c_lecture3_1,  תוסיף לו method (שיטה)  המחזיר
  את הקו החוצה והנצב באורך הקו הנתון. 
.  ה-Prototype של השיטה נראה כך:

CLine CLine:: middleLine(CLine line_original)                  	

קבוצה 2:
5 .כתוב תוכנית: "חד- מחלקתית" המייצגת אוסף של ספרות לפי הכלל:
    כל ספרה מופיעה לכל היותר פעם אחת.  נקרא לאוסף "קבוצה".
    דוגמא: {2,4 8,9}. 
          אם הספרות עולות בערכן אזי נקרא לקבוצה – קבוצה קנונית כמו בדוגמא לעיל.

הצג את הקבוצה בתור class CKvuca, המכילה שני נציגים (members):
1.arr[9]    -מערך באורך 9   (עבור 9 ספרות ללא 0),
     כל אבר במערך – ערכו כערך הספרה בקבוצה. ספרה 0 מסמלת מקום ריק במערך.  רק אברים 
     הראשונים במערך השונים מ-0 מראים על ספרה השיכת לקבוצה.

2. num  - מספר האלמנטים השונים מ-0, 

הפעולות – השיטות שיתבצעו על ידי המחלקה יהיו כלהלן: 
חיבור (+) – איחוד של קבוצות, למשל: (2,3,5} + {3,8,9} = {2,3,5,8,9},
כפל (*)  - חיתוך של קבוצות  (החלק המשותף בין שתי קבוצות),
         למשל: (2,3,5} * {3,8,9} = {3}
חיסור (-) – חיסור מקבוצה ראשונה את המשותף לשתי הקבוצות,
         למשל: (2,3,5} - {3,8,9} = {2,5}
משלים (~)    פעולה אונרית - משלים של קבוצה – קבוצת האברים שלא מופיעים בקבוצה המקורית,
         למשל: (2,3,5}  = {1,4,6,7,8,9}~
קנוניזציה  (-) – פעולה אונרית: סדור האברים בקבוצה בסדר עולה,
         למשל: (5,2,3}  = {2,3,5}-,
נתן גם לכתוב שיטה – method בשם void CKvuca::canonic()   המחזירה קבוצה קנונית.

רמז: כדי להקל על אלגוריתמי השיטות מומלץ קודם כל לבצע קנוניזציה של הקבוצות ורק אחר כך  את הפעולות היעודיות של האופרטורים – ראה מחלקה Fraction  שנלמדה בהרצאה c_lecture9.

6. חומר ה-DNA הנמצא באורגניזם נמצא רובו (אצל בן אדם) ב-23 כרומוזומים.
    כל כרומוזום מכיל גנים (genes)   ו-introns, הגנים מכילים אזור מקודד (coded)   ולאזור לא
    מקודד (un-coded).  כל ה-DNA מרכב מחומצות גרעין .(nucleotide)  
    כתוב תוכנית "רב- מחלקתית"  המתארת את הארגון הנ"ל:
    השיטה הבסיסית סופרת count את כמות ה Nucleotides בכל אחד מתתי המערכות הנ"ל. 
   ישם אותה בקוד התוכנית C++ (להבדיל מקוד ה-DNA).