מבוא למדעי המחשב מ׳/ח׳ — 234114 Round 5 · Moed Bet · Spring 5787 · practice
3:00:00
gcc 13.2 · -std=c99 0/80
1
לחץ ▶ Run כדי להדר ולהריץ את הקובץ. אם התוכנית תבקש קלט, תוכל להקליד אותו כאן למטה.
גודל טקסט

תרגול מבחן 005

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

זמן מומלץ: 3 שעות · שפת C

ענו על כל השאלות. שמרו על חתימות הפונקציות הנתונות.

שאלה 1 — ניתוח סיבוכיות

לכל קטע קוד בחרו את סיבוכיות הזמן והמקום ההדוקות ביותר.

א

void allocated(int n) {
    if (n <= 1) return;
    int *p = malloc(n * sizeof(int));
    allocated(n / 2);
    allocated(n / 2);
    free(p);
}

ב

void layered(int n) {
    for (int i = 1; i < n; i *= 2)
        for (int j = 0; j < n / i; j++)
            for (int k = 0; k < i; k++)
                putchar('.');
}

ג

void square_growth(int n) {
    for (int i = 2; i < n; i *= i)
        putchar('.');
}

שאלה 2 — שיא במערך הררי

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

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

דוגמה: עבור {1,3,7,9,6,2} מוחזר 3.

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

שאלה 3 — התו הייחודי הראשון

באמצעות מערך ספירה בגודל 26, החזירו את האינדקס הראשון של תו שמופיע פעם אחת בדיוק, או ‎-1 אם אין כזה. אין לשנות את המחרוזת.

int examT_q3(char *s);

דוגמה: עבור "swiss" מוחזר 1; עבור "aabb" מוחזר -1.

דרישות: זמן Θ(n), מקום נוסף Θ(1).

שאלה 4 — תתי־מערכים שהמקסימום שלהם x

ספרו תתי־מערכים רציפים שהאיבר המקסימלי בהם שווה בדיוק ל־x.

int examT_q4(int *arr, int n, int x);

דוגמה: עבור {2,5,3} ו־x=5 מוחזר 4.

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

הנחיות הגשה

בשאלה 4 מותר להוסיף בדיוק את שתי פונקציות העזר הרקורסיביות הנדרשות.