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

גודל טקסט

תרגול מבחן 008

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

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

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

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

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

א

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 shrinking(int n) {
    for (int left = n; left > 0; left--)
        for (int j = 0; j < left; j++)
            putchar('.');
}

ג

void half(int n) {
    if (n <= 1) return;
    half(n / 2);
}
void down(int n) {
    if (n <= 1) return;
    down(n - 1);
}
void both(int n) {
    half(n);
    down(n);
}

שאלה 2 — חיפוש מדרגות במטריצה

כל שורה וכל עמודה ממוינות בסדר עולה. החזירו 1 אם x נמצא, אחרת 0.

#define N 3
int examT_q2(int mat[][N], int m, int x);

דוגמה: במטריצה ששורותיה {1,4,7},{2,5,8},{3,6,9}, עבור x=6 מוחזר 1.

דרישות: התחילו בפינה הימנית העליונה; זמן O(m+N), מקום O(1).

שאלה 3 — הסרת כפילויות במקום

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

int examT_q3(char *s);

דוגמה: "programming" הופכת ל־"progamin", ומוחזר 8.

דרישות: שני סמנים ומערך seen בגודל 26; זמן Θ(n), מקום Θ(1).

שאלה 4 — סכום מסודר של 1 ו־2

החזירו את מספר הרצפים המסודרים של 1 ו־2 שסכומם n. הסדר חשוב.

int examT_q4(int n);

דוגמה: עבור n=4 מוחזר 5.

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

הנחיות הגשה

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