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

גודל טקסט

תרגול מבחן 002

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

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

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

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

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

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

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

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

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

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

דוגמה: עבור [4,5,6,7,0,1,2] ו־x=0 יוחזר 4; עבור x=3 יוחזר -1.

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

כתבו מחדש את המחרוזת כך שכל רצף מקסימלי יוחלף בתו ובמספר הופעותיו. אורך כל רצף הוא לכל היותר 9. החזירו את האורך החדש.

int examT_q3(char *s);

דוגמה: "aaabbc" הופכת ל־"a3b2c1", והפונקציה מחזירה 6.

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

החזירו את הספרות של n בסדר הפוך. הקריאה הראשית תמיד תתבצע עם acc=0.

int examT_q4(int n, int acc);

דוגמאות: examT_q4(1234,0) מחזירה 4321; עבור 1000 מוחזר 1.

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

שמרו על חתימות הפונקציות הנתונות. ניתן להוסיף משתנים מקומיים בלבד, אלא אם השאלה מציינת אחרת.