בחינה ב-"מבנה נתונים – C++"

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

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

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

בחר שתי שאלות מקבוצת שאלות הראשונה
ושאלה אחת מקבוצת השאלות השניה
(ערכה של כל שאלה  בקבוצה א'  30%, ובקבוצה ב'(40%   

השתמש באתר  :http://www.geocities.com/comp_ophir/ 

קבוצה 1:
1. מצא את bug  בפונקציה שעושה מיון: Quicksort  והממומשת ב-c_lecture5. 
          בדוק אותה על סדרת הנתונים המתקבלת כאשר ind_case=2, והקלט הוא הסדרה:
  44, 55, 12, 42, 94,18, 6, 67לאחר המיון של Quicksort בתוכנית המיושמת ב-c_lecture5 מתקבלת  הסדרה:
6, 18, 12, 42, 44, 45, 67, 94   
    המספרים 18,12  הם מוחלפים.

2. נתונה סדרת מספרים:
   7,3,5,12,6,9,8,4      	
          שאותה ממינים.
          הסדרה עוברת שנויים בשלבים השונים של המיון.  נתונות סדרות הביניים בכל שלבי המיון:

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

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

3. תוריד מהאתר את התוכנית    Stack1 מתוך   ((c_lecture4 
  c_Question3_Stack_reverse   ב- c_final_examination ובדוק בעזרת ה-debugger מה
   היה מצב המחסנית לפני ואחרי בצוע השיטה (method) בשם reverse.  קבע מה עושה שיטת
   ה-reverse, מה היא הופכת?  הצג את תוכנה של המחסנית st3 לפני ואחרי פעולת ה-reverse.

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

float CPoint::distance(CPoint p1, CPoint p2)                  	

קבוצה 2:
5 .כתוב תוכנית: "חד- מחלקתית" המייצגת מספרים מורכבים (complex)  ומבצעת פעולות
    חשבון בסיסיות: 
    חיבור (+), חיסור (-), כפל (*), חילוק (/).

6. משרד הפנים קיבל משימה לארגן לקראת הבחירות  את מערך הקלפי במדינת ישראל.
    כתוב תוכנית "רב- מחלקתית"  המתארת המערך הנ"ל:
    חלוקת המדינה לנפות: צפון, דרום ומרכז.  כל נפה מחולקת לאזורים, בכל אזור קיימים ישובים: 
    ערים, מושבים, קיבוצים, ישובים קהילתיים.  ישובים מעל 3000 אלפי בעלי זכות הבחירה   
    מחולקים לשכונות.  בכל שכונה מוצבת קלפי אחת.  יש לארגן את ספירת הקולות בקלפיות
    בהתאם למקום הימצאותן: המות המצביעים בכל אחת מהיחידות הבאות: נפה, אזור, ישוב
    ושכונה.