חידון: מבני נתונים ואלגוריתמים
האם אתה יכול לעבוד על עץ בינארי?
ברוכים הבאים לחידון מבני הנתונים והאלגוריתמים שלי!
חידון זה יבחן את הידע שלך במבני נתונים (מחסניות, רשימות, עצים וכו’), ואלגוריתמים (), ובמורכבות זמן.
20 שאלות… התחל!
איזה מבנה נתונים מתאים ביותר לדפוס גישה LIFO (אחרון נכנס, ראשון יוצא)?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מחסניות מתאימות ביותר לדפוסי גישה LIFO. תורים מתאימים ביותר לדפוסי גישה FIFO (ראשון נכנס, ראשון יוצא).
מהי סיבוכיות הזמן של אלגוריתם שתמיד לוקח אותו זמן לביצוע, ללא קשר לגודל הקלט?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
O(1) מייצג סיבוכיות זמן קבועה. זה אומר שהאלגוריתם תמיד לוקח אותו זמן לרוץ, ללא תלות בגודל הקלט.
מהי סיבוכיות הזמן לחישוב אורך של רשימה מקושרת חד-כיוונית?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
כדי לחשב את אורך של רשימה מקושרת חד-כיוונית, יש לעבור על כל הצמתים מהראש לזנב, מה שמוביל לסיבוכיות זמן O(n).
מהי סיבוכיות הזמן הממוצעת לחיפוש איבר בעץ חיפוש בינארי מאוזן?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
בעץ חיפוש בינארי מאוזן, סיבוכיות הזמן הממוצעת לחיפוש היא O(log n) מכיוון שכל רמה מאפשרת לצמצם את מרחב החיפוש בחצי.
מהי סיבוכיות הזמן של אלגוריתם מיון מיזוג במקרה הגרוע?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מיון מיזוג תמיד פועל עם סיבוכיות במקרה הגרוע של O(n log n) מכיוון שהוא מפצל את המערך לחצאים שוב ושוב וממזג את תת-המערכים הממוינים.
מהי סיבוכיות הזמן של מיון ערימה במקרה הגרוע?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מיון ערימה שומר על סיבוכיות זמן במקרה הגרוע של O(n log n), מכיוון שהוא בונה ערימה ושולף שוב ושוב את האלמנט המקסימלי.
מהי סיבוכיות הזמן הממוצעת לגישה לאלמנט בטבלת גיבוב?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
לטבלאות גיבוב יש סיבוכיות זמן ממוצעת של O(1) לגישה לאלמנטים, בהנחה שפונקציית הגיבוב טובה וממזערת התנגשויות.
איזו קבוצה מכילה פעולות אופייניות המתבצעות על מחסנית?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
הפעולות העיקריות של מחסנית הן Push (הוספת איבר), Pop (הסרת איבר) ו-Peek (צפייה באיבר העליון מבלי להסירו).
איזה אלגוריתם נפוץ למציאת המסלול הקצר ביותר בגרף משוקלל עם קשתות לא שליליות?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
אלגוריתם דייקסטרה (Dijkstra’s Algorithm) משמש לעיתים קרובות למציאת המסלול הקצר ביותר בגרפים עם משקלי קשתות לא שליליים. הוא משתמש בתור עדיפות כדי לקבוע את המרחק הקצר ביותר ביעילות.
איזו קבוצה מכילה דוגמאות למבני נתונים של עצי חיפוש בינאריים מאוזנים עצמית?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
עצי AVL ועצים אדום-שחור הם סוגים של עצים מאוזנים עצמית, המבטיחים שהעץ נשאר מאוזן לאחר כל הכנסה או מחיקה.
מהן שתי הפעולות העיקריות של תור?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
שתי הפעולות העיקריות בתור הן הכנסה (הוספת איבר לסוף) והוצאה (הסרת איבר מההתחלה).
מהם התנאים לביצוע מיון טופולוגי על גרף?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
ניתן לבצע מיון טופולוגי על גרף אם הוא מכוון וחסר מעגלים (DAG). סוג זה של סדר שימושי בבעיות תזמון משימות.
מהי סיבוכיות הזמן של מימוש רקורסיבי נאיבי של סדרת פיבונאצ’י?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
למימוש הרקורסיבי הנאיבי של סדרת פיבונאצ’י יש סיבוכיות זמן של O(2^n) בשל החישובים החוזרים הרבים עבור כל מספר פיבונאצ’י.
איזה מבנה נתונים משמש בדרך כלל למימוש תור עדיפויות?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
תור עדיפויות מיושם לרוב באמצעות ערימה כי היא מאפשרת שליפה יעילה של האלמנט בעל העדיפות הגבוהה או הנמוכה ביותר.
איזו קבוצה מציגה את סדרי הסריקה הנפוצים של עומק-ראשון בעץ בינארי?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
סדר-תוך, סדר-קדם וסדר-אחר הם שלושת סדרי הסריקה הנפוצים של עומק-ראשון בעץ בינארי, כל אחד עם סדר ביקור שונה בצמתים. סריקת רוחב-ראשון גם היא נפוצה, אך היא קטגוריית סריקה שונה.
איזו מהתכונות הבאות נכונה לגבי ערימת מינימום?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
בערימת מינימום, השורש הוא תמיד האלמנט הקטן ביותר, וגובה העץ הוא O(log n), מה שהופך הכנסה והוצאה ליעילות.
האם אלגוריתם מיון בועות הוא יציב?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מיון בועות הוא אלגוריתם מיון יציב מכיוון שהוא שומר על הסדר היחסי של איברים שווים במהלך המיון.