שאלו 3 שאלות:
1. א – מהם שני סוגי החיפוש בעצים? – לאורך ולרוחב.
ב – נתון שבשביל לממש חיפושים אלה, משתמשים בתור ובמחסנית. באיזה סוג חיפוש משתמשים בתור, ובאיזה למחסנית?
2. השאלה על הכפל, תוך שימוש ב inc, dec, jnz, אשר מופיעה כאן בפוסטים קודמים.
3. נתון הקוד הבא:
קוד: בחר הכל
extern short const_array[2000]
long fun(short x) {
static array[2000];
long res = 0;
for (int i=1999; i>0; i–) array[i] = array[i-1];
array[0] = x;
for (i=0; i<2000, i++) res += array[i]*const_array[i];
return res;
}
כאשר כתיבה למערך לוקחת 5 מחזורי שעון, קריאה והשמה למשתנה 5 מ"ש, וכל פעולה אחרת מ"ש אחד. ללולאת ה for עצמה איך בזבוז מ"ש.
לצורך העניין, סיבוכיות הפונקציה הנ"ל היא 23n+6 (כאשר n מייצג 2000).
המשימה: לצמצם את זמן הריצה.
אני הגעתי ל 18n, אבל המראיין אמר לי שאפשר בסדר גודל של חצי. לא הצלחתי .
המשך –
ל-traversing שהוא depth first (כלומר כל ה pre / post / in orders), צריך להשתמש במחסנית. הרעיון הוא שדוחפים ושולפים נתונים מהמחסנית בהתאם לסוג הסריקהץ
ל-traversing שהוא breadth first, משתמשים בתור (שהוא בעצם FIFO). למה זה היגיוני? תחשבו שהכנסתם לתור את האב, שני בניו, ואז 4 "נכדים". הסריקה צריך להתבצא מהאב -> בנים -> נכדים.