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

גודל טקסט

תרגול מבחן 007

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

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

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

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

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

int halves(int n) {
    if (n <= 1) return 1;
    return halves(n / 2) + halves(n / 2);
}

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

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

בחרו שני קירות כך שהשטח (j-i) * min(arr[i],arr[j]) יהיה מרבי, והחזירו אותו.

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

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

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

ספרו תתי־מחרוזות של s שאורכן כאורך p והן אנגרמה של p. אין לשנות את המחרוזות.

int examT_q3(char *s, char *p);

דוגמה: עבור "cbaebabacd" ו־"abc" מוחזר 2.

דרישות: חלון מחליק והיסטוגרמה קבועה, זמן Θ(n), מקום Θ(1).

החזירו 1 אם איברי b מופיעים ב־a באותו סדר יחסי, אחרת 0.

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

דוגמה: {2,4} היא תת־סדרה של {1,2,3,4,5}, אך {4,2} אינה.

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

אין לשנות את חתימות הפונקציות.