לחץ ▶ Run כדי להדר ולהריץ את הקובץ. אם התוכנית תבקש קלט, תוכל להקליד אותו כאן למטה.

גודל טקסט

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

234114 / 234117 · מועד ב׳ · סמסטר אביב תשפ"ו

משך הבחינה: שלוש שעות חומר עזר: אין 4 שאלות · 25 נקודות לשאלה

תרגול מדומה — תחזית 1 מתוך 12 למועד ב׳ אביב 2026. אינו מבחן אמיתי של הטכניון.

שאלה 1 25 נק' — סיבוכיות

לכל סעיף ציינו סיבוכיות זמן וסיבוכיות מקום נוסף, בסימון Θ, כפונקציה של n. חובה לפשט את הביטוי ככל שניתן. הניחו כי סיבוכיות הזמן והמקום של printf ו-free היא Θ(1), וכי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות המקום שלה היא Θ(n). הניחו כי sqrt פועלת בזמן Θ(1).

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

א.

void f1(int n) {
    for (int i = 1; i < n; i++)
        for (int j = 0; i * j < n; j++)
            printf("*");
}

ב.

int f2(int n) {
    if (n <= 1) return 1;
    int* a = (int*) malloc(n * sizeof(int));
    if (a == NULL) return 0;
    int r = f2(n - 1);
    free(a);
    return r;
}

ג.

void f3(int n) {
    for (int i = 1; i < n; i *= 2)
        for (int j = 1; j < i; j *= 2)
            printf("*");
}

שאלה 2 25 נק'

הגדרה: מערך arr באורך n ייקרא מערך מסובב אם הוא התקבל ממערך ממוין בסדר עולה ממש על ידי סיבוב מחזורי שמאלה ב-r מקומות, עבור 0 ≤ r < n כלשהו. הערך r אינו נתון.

לדוגמה, {0,1,2,4,5,6,7} מסובב ב-3 מקומות הוא {4,5,6,7,0,1,2}.

int examT_q2(int arr[], int n, int k);

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

קלט	פלט	הסבר
arr = {4,5,6,7,0,1,2}, n = 7, k = 1	0	הקטן ביותר
arr = {4,5,6,7,0,1,2}, n = 7, k = 4	4	הרביעי בגודלו
arr = {4,5,6,7,0,1,2}, n = 7, k = 7	7	הגדול ביותר
arr = {30,40,50,10,20}, n = 5, k = 3	30	—

ניתן להניח כי הקלט תקין, כי n ≥ 1 וכי כל האיברים שונים זה מזה.
אין לשנות את המערך, אין למיין אותו ואין להקצות זיכרון דינמי.
שימו לב: מציאת r היא רק חצי מהפתרון — לאחר מכן יש להמיר את k לאינדקס במערך המסובב.

דרישות סיבוכיותזמן Θ(log n)מקום נוסף Θ(1)

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אותיות אנגליות קטנות בלבד.

רצף במחרוזת הוא קטע רציף ומקסימלי של תווים זהים. לדוגמה, במחרוזת "aabbbca" יש ארבעה רצפים: aa, bbb, c, a.

int examT_q3(char* s);

על הפונקציה לכווץ כל רצף במחרוזת לתו בודד — במקום, בתוך s עצמה — ולהחזיר את אורכה החדש של המחרוזת. יש להקפיד שהמחרוזת החדשה תסתיים ב-'\0'.

קלט	פלט	s לאחר הקריאה
s = "aabbcc"	3	"abc"
s = "aaaa"	1	"a"
s = "abababab"	8	"abababab"
s = "mississippi"	8	"misisipi"

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

דרישות סיבוכיותזמן Θ(n)מקום נוסף Θ(1)

שאלה 4 25 נק' — רקורסיה

נתונים שני מערכים של מספרים שלמים: a באורך na ו-b באורך nb.

נאמר ש-a הוא תת-סדרה של b אם ניתן למחוק אפס איברים או יותר מ-b, מבלי לשנות את סדר הנותרים, ולקבל בדיוק את a.

int examT_q4(int* a, int na, int* b, int nb);

על הפונקציה להחזיר 1 אם a הוא תת-סדרה של b, ו-0 אחרת.

קלט	פלט	הסבר
a = {1,2}, b = {1,3,2}	1	מוחקים את 3
a = {2,1}, b = {1,3,2}	0	הסדר אינו נשמר
a = {1,1,1}, b = {1,2,1}	0	ב-b יש רק שני 1
a = {2,4,6}, b = {1,2,3,4,5,6}	1	מוחקים את 1, 3, 5

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

איך עובדים כאן

כתבו בעורך שמשמאל. שלושה קבצים, לשונית לכל שאלה. אל תשנו את main.
הרץ בדיקות מריץ את הפונקציה שלכם מול מקרי הבדיקה של השאלה — כולל בדיקות של האילוצים (לולאות ברקורסיה, שינוי הקלט, פונקציית מעטפת).
סיבוכיות אינה נבדקת אוטומטית. פתרון שעובר את כל הבדיקות בסיבוכיות שגויה — נכשל בשאלה.
בסיום לחצו סיום והגשה, שמרו את קובץ ההגשה, ובקשו מ-Claude ציון עם /grade.