פתרון מבחן במבוא למדעי המחשב

החוג למדעי המחשב

אוניברסיטת חיפה

מבוא למדעי המחשב

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

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

נתונה הפונקציה הבאה:

int what (char a[], int n, char b[], int m)
{
int i, j, k, count1, count2;
if(n!=m) return 0;
for(i=0; i<n; i++) {
count1 = count2 = 0;
for(k=0; k<n; k++) {
if(a[k]==a[i]) count1++;
if(b[k]==b[i]) count2++;
}
for(j=0; j<m; j++) {
if(a[i]==b[j])
count1--;
if(b[i]==a[j])
count2--;
}
if(count1 || count2) return 0;
}
return 1;
}

א. (5 נק') תארו בקצרה מה עושה הפונקציה.

ב. (5 נק') מהי סיבוכיות הזמן והמקום של הפונקציה?

ג. (5 נק') האם ניתן לכתוב פונקציה אשר עושה את אותו הדבר בסיבוכיות זמן טובה יותר? אם כן - תארו
במילים את האלגוריתם וכתבו מהי סיבוכיות הזמן והמקום החדשים. אם לא - הסבירו מדוע.

שאלה 2 (30 נק')

סעיף א (10 נק')

ממשו את הפונקציה שחתימתה
void reverse(int a[ ], int n, int ind)
הפונקציה מקבלת כקלט מערך aשל מספרים שלמים, את גודלו ,nואינדקס indבמערך.

על הפונקציה להפוך את סדר האיברים בתת המערך שמתחיל באינדקס 0ונגמר באינדקס .ind
לדוגמא, עבור = aו- ,ind=4לאחר הפונקציה aיהיה:
ועבור = aו- ,ind=2לאחר הפונקציה aיהיה:
הערה: ניתן להניח ש- indהינו אינדקס חוקי )כלומר ,(0 ≤ ind < nואין צורך לבדוק זאת.

סעיף ב (20 נק')

ממשו את הפונקציה שחתימתה
void sort(int a[ ], int n)
הפונקציה מקבלת מערך שמכיל את המספרים 0ו- 1בלבד )אין צורך לוודא זאת.(
על הפונקציה למיין את המערך, כך שבהתחלה יופיעו כל ה- 0ואחריהם כל ה-.1
דרישה: על מנת לשנות את סדר איברי המערך מותר לפונקציה להשתמש אך ורק בפונקציה reverse
מסעיף א׳ )גם אם לא מימשתם אותה.

שאלה 3 (30 נק')

ממשו את הפונקציה שחתימתה
int sum_exists(int a[ ][COL], int n, int m, int sum)
הפונקציה מקבלת מערך דו מימדי aשמכיל מספרים שלמים, את מימדיו - nשורות ו- mעמודות, ומספר
נוסף שלם .sumהפונקציה בודקת האם קיים מסלול מתא ] a[0][0עד תא ] a[n-1][m-1אשר סכום
המספרים בו שווה בדיוק ל- .sumאם קיים מסלול כזה הפונקציה תחזיר ,1אחרת תחזיר .0
הצעדים המותרים במסלול הם לתא שנמצא מימין, למטה או באלכסון. כלומר:
מתא ] a[i][jמותר לעבור לתאים ]a[i][j+1], a[i+1][j], a[i+1][j+1
לדוגמא, במערך הבא: אם ,sum=20הפונקציה תחזיר ) 1מאחר ויש מסלול
שסכומו ,20מסומן באפור( ואם sum=10הפונקציה תחזיר 0.

שאלה 4 (25 נק')

נתונה רשומה מטיפוס Nodeהמוגדרת כך:
typedef struct node {
int data;
struct node* left;
struct node* right;
}Node;
ממשו את הפונקציה שחתימתה
int is_sequential(Node* p)
הפונקציה מקבלת מצביע pלשורש עץ חיפוש בינארי מלא, שמכיל מספרים שלמים, שונים וחיוביים
בלבד.
כלומר - לכל צומת בעץ יש שני בנים או אין בנים כלל. בנוסף, הערך בכל צומת גדול מכל הערכים
בצמתים שבתת העץ השמאלי שלו, וקטנים מכל הערכים בצמתים בתת העץ הימני שלו.

הפונקציה תחזיר 1אם המספרים בעץ, כשהם ממוינים, מהווים סידרה חשבונית עולה עם הפרש , 3ו-0
אחרת.
כלומר - לכל ערך xבעץ, הערכים x-3ו x+3נמצאים בעץ. מלבד המינימום שעבורו קיים רק ,x+3
והמקסימום שעבורו קיים רק .x-3
ניתן להניח שהעץ הינו עץ חיפוש בינארי מלא ואין צורך לבדוק זאת.
דרישות:
• סיבוכיות מקום ).O(1
• ניקוד מלא יינתן רק עבור פונקציה שתעבוד בסיבוכיות זמן לינארית במספר הצמתים בעץ.

**יש פתרון לכל השאלות.

**הפתרון כולל את השאלות ואת התשובות. בפתרון השאלות מופיעות באופן מסודר כולל הפונקציות ולא מבולגן כמו כאן בגלל ההעתקה לhtml.