מחרוזת t תקרא פרמוטציה של s אם s ו-t מכילות בדיוק את אותם תווים, אבל לא בהכרח באותו סדר.למשל עבור המחרוזת "all" אוסף הפרמוטציות האפשריות (בסידור לקסיקוגרפי) הוא: "all","lal","lla"עליכם לממש את הפונקציה הבאה:int exam_q3(char ∗s);הפונקציה מקבלת מחרוזת שמכילה אותיות קטנות באנגלית בלבד.הפונקציה תבחן שתיים מהפרמוטציות של המחרוזת הנתונה: הקטנה והגדולה ביותר בסדר לקסיקוגרפי, ותחליף את המחרוזת באחת מבין שתיהן שיותר קרובה אליה (הכי מעט תווים שיש לשנות). אם שתי הפרמוטציות קרובות באותה מידה למחרוזת s, הפונקציה תחליף את s בפרמוטציה הקטנה. על הפונקציה להחזיר את מספר התווים ששונו ב-s.דוגמאות:| s לפני הקריאה לפונקציה | s אחרי הקריאה לפונקציה | ערך החזרה | הסבר |
|---|
| dbcae | abcde | 2 | הפרמוטציה הקטנה ביותר היא "abcde" והיא שונה מהמחרוזת המקורית ב-2 מקומות (יש להחליף את התו d בתו a ואת התו a בתו d). הפרמוטציה הגדולה ביותר היא "edcba" והיא שונה מהמחרוזת המקורית ב-4 מקומות (התו היחיד שנשאר במקום ולא מוחלף זה התו c) |
| xzyw | xyzzw | 3 | הפרמוטציה הקטנה ביותר היא "wxyzz" והיא שונה מהמחרוזת המקורית ב-4 מקומות (התו היחיד שנשאר במקום ולא מוחלף זה התו z). הפרמוטציה הגדולה ביותר היא "zzyxw" והיא שונה מהמחרוזת המקורית ב-3 מקומות. |
| abcd | abcd | 0 | אין צורך לשנות את המחרוזת כיוון שהיא הפרמוטציה הקטנה ביותר והיא דורשת 0 שינויים. |
- נתונה לכם תוכנית אשר קוראת מהמשתמש את המחרוזת s (אורך ותוכן), קוראת לפונקציה ומדפיסה את הערך החוזר ואת המחרוזת החדשה.
- ניתן להניח שהקלט תקין (s מחרוזת חוקית המכילה רק אותיות קטנות).
דרישות סיבוכיות:- סיבוכיות זמן: Θ(n) כאשר n הוא אורך המחרוזת s.
- סיבוכיות מקום: Θ(1).
הטכניוןמועד א · 2025 · סמסטר קיץ
מחרוזותפרמוטציותמערכיםסיבוכיות זמןסיבוכיות מקום
עליכם לממש את הפונקציה הבאה:int exam_q2(int arr[], int n);הפונקציה מקבלת מערך arr באורך n של מספרים טבעיים (שלמים גדולים מאפס).המערך מייצג אזור עם n קירות. הקיר ה-i נמצא בנקודה ה-i בציר ה-x וגובהו arr[i].עליכם למצוא קיר שביחד עם הקיר השמאלי ביותר (הקיר במקום 0) וציר ה-x יוצרים את המיכל שיכול להכיל הכי הרבה מים. החזירו את כמות המים שמיכל זה מכיל.דוגמאות:קלט: arr={5,8,6,2,5,4,8,3,2}, n=9פלט: 30הסבר: מערך הגבהים המתואר בקלט נראה כך:[גרף היסטוגרמה]הקיר השמאלי של המיכל בגובה 5 (הקיר במקום 0). המיכל הגדול ביותר יתקבל אם נבחר את הקיר הימני להיות הקיר במקום 6. זהו מיכל ברוחב 6 ובגובה 5, כלומר כמות המים היא 30=6×5הערות:- נתונה לכם תוכנית אשר קוראת מהמשתמש את אורך המערך, ולאחר מכן את תוכנו.
- ניתן להניח שהקלט תקין, בפרט arr מכיל רק מספרים חיוביים ו-1<n.
דרישות סיבוכיות:- סיבוכיות זמן: Θ(n).
- סיבוכיות מקום: Θ(1).
הטכניוןמועד א · 2025 · סמסטר קיץ
מערכיםלולאותסיבוכיות זמןסיבוכיות מקוםיעילות
שאלה :2 ] 25 נקודות[עליכם לממש את הפונקציה הבאה:הפונקציה מקבלת מערך arr באורך n של מספרים שלמים ללא חזרות, תו סידור c ומספר x. עליכם למצוא האם התו c נמצא במערך. אם כן, יש להחזיר את האינדקס שלו, אחרת יש להחזיר −1.נתון שהמערך הנתון מסודר לפי אחד מהכללים הבאים, כתלות בתו c:| התו c | סידור המערך |
|---|
| ′u′ | המערך ממוין בסדר עולה |
| ′d′ | המערך ממוין בסדר יורד |
compare. אסור להגדיר פונקציות עזר נוספות.דוגמאות:| תוכן המערך | c | x | ערך החזרה |
|---|
| 1, 2, 3, 4, 5 | ′u′ | 3 | 2 |
| 10, 5, 2, -1, -3 | ′d′ | 7 | -1 |
| 12, 0, -2 | ′d′ | 0 | 1 |
- נתונה לכם תוכנית אשר קוראת מהמשתמש את אורך המערך, ולאחר מכן את תוכנו ואת התווים c ו-x.
- ניתן להניח שהקלט תקין, בפרט arr לא מכיל את אותו איבר פעמיים, c הוא אחת מהאפשרויות לעיל ו-arr מסודר בהתאם אליו.
דרישות סיבוכיות:- סיבוכיות זמן עבור הפונקציה
compare: Θ(1). - סיבוכיות זמן כוללת: O(log(n)).
- סיבוכיות מקום נוסף: O(1).
הטכניוןמועד ב · 2025 · סמסטר קיץ
חיפוש בינארימערכיםסיבוכיות זמןסיבוכיות מקוםשיטות סטטיות
שאלה :1 ]25 נקודות[ענו על השאלה במטלה המתאימה ב-Gradescope. לכל סעיף עם קטע קוד יופיעו שני תתי-סעיפים, אחד לסיבוכיות זמן ואחד לסיבוכיות מקום. בכל תת-סעיף עליכם לבחור אפשרות אחת ולסמן אותה.בכל הסעיפים יש להניח כי סיבוכיות הזמן והמקום של פונקציות הספרייה המוכרות printf, fgets היא Θ(1). בנוסף יש להניח כי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות מקום נוסף היא Θ(n).א. חשבו את סיבוכיות הזמן והמקום של הפונקציה f1 המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך לפרט את שיקוליכם. חובה לפשט את הביטוי ככל שניתן.ב. חשבו את סיבוכיות הזמן והמקום של הפונקציה f2 המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך לפרט את שיקוליכם. חובה לפשט את הביטוי ככל שניתן.ג. בקובץ c1_finalB.q יש תוכנית שבה קולטים שמות סטודנטים מהמשתמש ושומרים אותם במטריצה names.ד. הפונקציה:ה. קוראת את מספר הסטודנטים, ושמות הסטודנטים מהמשתמש ושומרת אותם במערך names. מובטח כי השם הארוך ביותר לא יהיה יותר מ LEN_MAX תוים.הפונקציה:משחררת את הזכרון שהוקצה באופן דינמי.בקובץ יש גם פונקצית main אשר קוראת לפונקציה read_names, מדפיסה את השמות, וקוראת לפונקציה free_names.בקובץ יש טעויות. בפתרון עליכם להגיש את התוכנית המתוקנת.לרשותכם הכנו בגריידסקופ טסט שנכשל עם התוכנית הנתונה.שימו לב:- ב
main אין טעויות ואסור לשנות אותו. - אין לשנות את חתימות הפונקציות.
- זה שהטסט עובר לא אומר שתיקנתם את כל הטעויות.
- כל הקצאה דינמית יש לוודא שהצליחה.
- יש לשחרר כל זכרון שהוקצה דינמית.
- פונקציה המקבלת מצביע, תמיד צריכה לבדוק שהוא שונה מ
NULL לפני שתשתמש בו.
הטכניוןמועד ב · 2025 · סמסטר קיץ
סיבוכיות זמןסיבוכיות מקוםרקורסיהמערך דו-ממדימחרוזותמערכים
שאלה 3 ]25 נקודות[עליכם לממש את הפונקציה הבאה:הפונקציה מקבלת 2 מחרוזת שמייצגות מספרים שלמים אי שליליים. על הפונקציה להחזיר את הסכום של מספרים אלו. על הפונקציה להחזיר את התוצאה במחרוזת שתוקצה דינאמית.דוגמאות:| המחרוזת s1 | המחרוזת s2 | מחרוזת התוצאה |
|---|
| "1" | "1" | "2" |
| "998" | "2" | "1000" |
| "5" | "0" | "5" |
| "123456789012" | "1" | "123456789013" |
- נתונה לכם תוכנית אשר קוראת מהמשתמש את המחרוזות s1 ו-s2 (אורך ותוכן), קוראת לפונקציה ומדפיסה את המחרוזת החדשה (ומשחררת אותה).
- ניתן להניח ש- s1 ו- s2 מחרוזות חוקיות שמכילות רק ספרות.
- המחרוזות לא יכילו אפסים מובילים (אבל הן יכולות להיות "0").
- לא ניתן להניח שהמספרים המתקבלים יכולים להיות מיוצגים כ- int ואפילו לא כ- long long.
דרישות סיבוכיות:- סיבוכיות זמן: O(n) כאשר n הוא אורך המחרוזת הארוכה יותר.
- סיבוכיות מקום: O(n).
הטכניוןמועד ב · 2025 · סמסטר קיץ
מחרוזותמערכיםסיבוכיות זמןסיבוכיות מקוםייצוג מספריםלולאות
ענו על השאלה במטלה המתאימה ב-Gradescope. לכל סעיף עם קטע קוד יופיעו שני תתי-סעיפים, אחד לסיבוכיות זמן ואחד לסיבוכיות מקום. בכל תת-סעיף עליכם לבחור אפשרות אחת ולסמן אותה. בכל הסעיפים יש להניח כי סיבוכיות הזמן והמקום של פונקציות הספרייה המוכרות printf, perror היא Θ(1). בנוסף יש להניח כי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות מקום נוסף היא Θ(n).א. חשבו את סיבוכיות הזמן והמקום של הפונקציה f1 המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך לפרט את שיקוליכם. חובה לפשט את הביטוי ככל שניתן.ב. חשבו את סיבוכיות הזמן והמקום של הפונקציה f2 המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך לפרט את שיקוליכם. חובה לפשט את הביטוי ככל שניתן.ג. בקובץ q1_finalA.c תוכנית שבה משתמשים ב-2 מערכים: מערך ids של ת.ז. ומערך grades של ציונים. 2 המערכים באותו אורך, כאשר grades[i] הוא הציון הממוצע של הסטודנט שת.ז. שלו היא ids[i].הת.ז. מיוצגת ע"י מחרוזת של 9 תווים בדיוק (סה"כ 10 בתים, יחד עם התו '\0'), והציון הוא מספר ממשי.הפונקציה:קוראת את המערכים מהמשתמש (אורך, ת.ז. וציון לכל סטודנט)הפונקציה:משחררת את הזכרון שהוקצה באופן דינמי.בקובץ יש גם פונקציית main אשר קוראת לפונקציה read_arrays, מדפיסה את הערכים (הציונים מודפסים בדיוק של 2 ספרות לאחר הנקודה), וקוראת לפונקציה free_arrays.בקובץ יש טעויות. בפתרון עליכם להגיש את התוכנית המתוקנת.לרשותכם הכנו בגריידסקופ טסט שנכשל עם התוכנית הנתונה.שימו לב:- אין לשנות את חתימות הפונקציות.
- זה שהטסט עובר לא אומר שתיקנתם את כל הטעויות.
- כל הקצאה דינמית יש לוודא שהצליחה.
- יש לשחרר כל זכרון שהוקצה דינמית.
- פונקציה המקבלת מצביע, תמיד צריכה לבדוק שהוא שונה מ-
NULL לפני שתשתמש בו.
הטכניוןמועד א · 2025 · סמסטר קיץ
סיבוכיות זמןסיבוכיות מקוםרקורסיהלולאותמערכיםמחרוזות
ידוע כי בטקס מגדלי הירקות השנתי ישנה ארוחת ערב חגיגית בה מתיישבים הסועדים ב-N שולחנות של 5 אנשים כל אחד. סה"כ מספר הסועדים הוא בדיוק 5Nהשפית הידועה מדאם כרובית אחראית על ארוחת הערב החגיגית ועליה לתכנן מראש אילו מנות להגיש לכל אחד מ-N השולחנות. לשם כך יש להתחשב באילוצים הבאים:- כל סועד סימן מראש שלוש מנות מתוך תפריט של K מנות, כאשר לכל מנה יש מספר שונה החל מ-0 ועד K−1. יש להכין לו בדיוק מנה אחת מתוך השלוש שסימן.
- משיקולים קולינריים, ישנן מנות שלא יכולות להיות יחד באותו שולחן. אילוצים אלו מתוארים במטריצת אילוצים בגודל K×K, בה האיבר במקום [i][j] הוא 0 אם מנה i לא יכולה להיות עם מנה j באותו שולחן, ו-1 אם הן יכולות להיות יחד.
עליכם לממש את הפונקציה הבאה:int exam_q4(int mat1[][3],int mat2[K][K]);הפונקציה מקבלת את בחירות הסועדים במטריצה mat1 (שורות 0 עד 4 הסועדים בשולחן הראשון, שורות 5 עד 9 הסועדים בשולחן השני, וכך הלאה), ואת מטריצת האילוצים mat2.על הפונקציה להחזיר את מספר המנות השונות המינימלי שיכול לקיים את כל האילוצים. אם לא קיימת אפשרות העונה על כל האילוצים יש להחזיר -1.למשל, עבור 2 שולחנות ו-6 מנות, אם בחירת הסועדים היא:ומטריצת האילוצים היא:כלומר כל המנות יכולות להיות על אותו שולחן, מלבד מנות 0 ו-5 שלא יכולות להיות על אותו שולחן.ניתן להגיש לכל הסועדים בשולחן הראשון את מנה 0, ובשולחן השני ניתן להגיש לכולם את מנה 3. לכן הפונקציה תחזיר 2 (2 מנות שונות יוגשו לשולחנות).הערות:- נתונה לכם תוכנית אשר קוראת מהמשתמש את בחירות הסועדים ומטריצת האילוצים.
- יש להשתמש בשיטת backtracking כפי שנלמדה בכיתה.
- בשאלה זו אין דרישות סיבוכיות, אולם כמקובל ב-backtracking יש לוודא שלא מתבצעות קריאות רקורסיביות מיותרות עם פתרונות שאינם חוקיים.
- ניתן ומומלץ להשתמש בפונקציות עזר (ויש לממש את כולן).
- ניתן להניח כי מטריצת האילוצים סימטרית ואיברי האלכסון כולם 1.
הטכניוןמועד א · 2025 · סמסטר קיץ
רקורסיהרקורסיה עם מעקבמערכיםמערך דו-ממדימעקב אחר קוד
שאלה :4 ] 25 נקודות [יוסי מנסה לתכנן טיול מסביב לעולם דרך מדינות שנמספרות 0,1,2,3,…,N−1. יוסי רוצה לעבור בכל מדינה בדיוק פעם אחת, לא פחות ולא יותר. לשם כך הוא נעזר במטריצת מעברים בין המדינות בשם routes בגודל N×N המייצגת את כל המסלולים הקיימים. אם קיים מעבר ממדינה i למדינה j אזי routes[i][j] יהיה מחיר המעבר. אם לא קיים מעבר, routes[i][j] יהיה 0.שימו לב שהמטריצה לא חייבת להיות סימטרית, כלומר ייתכן שקיים מעבר מ i ל j אך לא קיים מעבר מ j ל i, או שהמחיר שונה.עליכם לממש את הפונקציה הבאה:אשר מחזירה את מחיר המסלול הזול ביותר שמקיים את כל הדרישות, ו-0 אם לא קיים מסלול כזה.למשל, עבור N=3 (3 מדינות) ומטריצת המעברים הבאה: | j=0 | j=1 | j=2 |
|---|
| i=0 | 0 | 200 | 300 |
| i=1 | 50 | 0 | 25 |
| i=2 | 150 | 0 | 0 |
| j=0 | j=1 | j=2 |
|---|
| i=0 | 0 | 200 | 0 |
| i=1 | 0 | 0 | 0 |
| i=2 | 0 | 100 | 0 |
- נתונה לכם תוכנית אשר קוראת מהמשתמש את המטריצה
routes, קוראת לפונקציה ומדפיסה למסך את המחיר. - יש להשתמש בשיטת backtracking כפי שנלמדה בכיתה.
- בשאלה זו אין דרישות סיבוכיות, אולם כמקובל ב-backtracking יש לוודא שלא מתבצעות קריאות רקורסיביות מיותרות עם פתרונות שאינם חוקיים.
- ניתן ומומלץ להשתמש בפונקציות עזר (ויש לממש את כולן).
- ניתן להניח כי המטריצה מכילה ערכים אי שליליים בלבד, וכי איברי האלכסון כולם 0.
הטכניוןמועד ב · 2025 · סמסטר קיץ
רקורסיהרקורסיה עם מעקבמערך דו-ממדיגרפיםמעקב אחר קוד
שאלה 4 [25 נקודות]ממשו פונקציה:הפונקציה מקבלת מערך של ספרים שלמים בעלות אורך n, ספר שלם x. חטבומ שלכל ספרים בעלות המערך. השחטבומ רבע ספרים תוגוז בעלות המערך שסכומם שווה ל-x.אם אין תוגוז כזו להחזיר על הפונקציה 0.תורעה:• הנתונה רבע ספרי המערך, אוכן, הסור ואת ספר x.• ניתן להניח כי טלקהש ניתן.• כל תוגוז חייב להיות מורכב משני אתומים זרים בעלות המערך.• רוסא שמתשמן תואלולב.• לא ניתן להחזיר להחזיר להחזיר להחזיר להחזיר לפונקציה exam_q4 היצקנופה תרחא דבלמ - main.• ניתן לעזור תוצקנופב שמתשמן – הן תובייח תויהל תוביסרוקר בדוגל.דרישות סיבוכיות:• סיבוכיות זמן: Θ(n).
• סיבוכיות מקום: Θ(n).דוגמה עם קלט/פלט:| קלט | פלט | הסבר |
|---|
arr = [-70, -20, 50 100], x=30 | 2 | קיימות שתי תוגוז בעלות המערך שמבינים את הסכום 30: 100+(−70)=30, 50+(−20)=30 |
arr = [10, 10, -10, -10, 30], x=0 | 4 | קיימות ארבע תוגוז בעלות המערך שמבינים את הסכום 0: arr[0] + arr[2] = 10 + (-10) = 0, arr[0] + arr[3] = 10 + (-10) = 0, arr[1] + arr[2] = 10 + (-10) = 0, arr[1] + arr[3] = 10 + (-10) = 0 |
הטכניוןמועד א · 2025 · סמסטר א
טבלאות גיבוברקורסיהמערכיםסיבוכיות זמןסיבוכיות מקום
שאלה 1 [25 נקודות]
א. חשבו את סיבוכיות הזמן והמקום של הפונקציה f1, המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך להסביר את השיקוליכם. חובה להרחיב את הביטוי ככל שניתן. ניתן להניח כי printf היא Θ(1).
ב. חשבו את סיבוכיות הזמן והמקום של הפונקציה f2, המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך להסביר את השיקוליכם. חובה להרחיב את הביטוי ככל שניתן. ניתן להניח כי malloc ו-free היא Θ(1).
ג. חשבו את סיבוכיות הזמן והמקום של הפונקציה f3, המוגדרת בקטע הקוד הבא, כפונקציה של n. אין צורך להסביר את השיקוליכם. חובה להרחיב את הביטוי ככל שניתן. ניתן להניח כי n>1.
הטכניוןמועד א · 2025 · סמסטר א
סיבוכיות זמןסיבוכיות מקוםלולאותרקורסיה
שאלות מבוא למדעי המחשב בטכניון עם פתרונות
מאגר מבחנים במבוא למדעי המחשב מהטכניון (הטכניון) - 969 שאלות ממוינות לפי נושא ורמת קושי, עם פתרונות מלאים לבדיקה עצמית. השאלות מכסות מועדים לאורך השנים, כולל מבחנים מ-2023, 2024, 2025 ו-2026. נושאים מרכזיים: רקורסיה, מערכים, מחרוזות, יעילות, עצים בינאריים. ניתן לסנן שאלות חוזרות, להתאמן על נושא ספציפי או להריץ סימולציית מבחן לפני הבחינה. הכנה למבוא למדעי המחשב מתמקדת בתרגול רקורסיה, מערכים ועצים בינאריים - הנושאים הנפוצים ביותר במבחנים. לימוד עצמי עם שאלות ממבחנים, בדגש על מעקב אחר קוד, מכין ביעילות לבחינה.