חידון: מבני נתונים ואלגוריתמים האם אתה יכול לעבוד על עץ בינארי?
ברוכים הבאים לחידון מבני הנתונים והאלגוריתמים שלי!
חידון זה יבחן את הידע שלך במבני נתונים (מחסניות, רשימות, עצים וכו’), ואלגוריתמים (), ובמורכבות זמן.
20 שאלות… התחל!
איזה מבנה נתונים מתאים ביותר לדפוס גישה LIFO (אחרון נכנס, ראשון יוצא)?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מחסניות מתאימות ביותר לדפוסי גישה LIFO. תורים מתאימים ביותר לדפוסי גישה FIFO (ראשון נכנס, ראשון יוצא).
מהי סיבוכיות הזמן של אלגוריתם שתמיד לוקח אותו זמן לביצוע, ללא קשר לגודל הקלט?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
O(1) מייצג סיבוכיות זמן קבועה. זה אומר שהאלגוריתם תמיד לוקח אותו זמן לרוץ, ללא תלות בגודל הקלט.
מהי סיבוכיות הזמן לחישוב אורך של רשימה מקושרת חד־כיוונית שאינה שומרת מונה איברים?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
כדי לחשב את אורך של רשימה מקושרת חד-כיוונית, יש לעבור על כל הצמתים מהראש לזנב, מה שמוביל לסיבוכיות זמן O(n).
O(1)
O(log n)
O(n^2)
O(n)
O(n log n)
מהי סיבוכיות הזמן הממוצעת לחיפוש איבר בעץ חיפוש בינארי מאוזן?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
בעץ חיפוש בינארי מאוזן, סיבוכיות הזמן הממוצעת לחיפוש היא O(log n) מכיוון שכל רמה מאפשרת לצמצם את מרחב החיפוש בחצי.
O(1)
O(log n)
O(n)
O(n^2)
O(n log n)
מהי סיבוכיות הזמן של אלגוריתם מיון מיזוג במקרה הגרוע?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מיון מיזוג תמיד פועל עם סיבוכיות במקרה הגרוע של O(n log n) מכיוון שהוא מפצל את המערך לחצאים שוב ושוב וממזג את תת-המערכים הממוינים.
O(n^2)
O(log n)
O(n log n)
O(n)
O(1)
באיזה מבנה נתונים משתמשים בדרך כלל למימוש חיפוש לרוחב (BFS)?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
BFS משתמש בתור כדי לחקור צמתים רמה אחר רמה, תוך עיבוד צמתים בצורה לרוחב (לפי רמה).
תור
מחסנית
תור עדיפויות
מפת גיבוב
קבוצה
איזו סריקה מזהה מעגל מכוון באמצעות מציאת קשת לקודקוד שעדיין נמצא במחסנית הרקורסיה שלה?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
חיפוש לעומק (DFS) משמש בדרך כלל לזיהוי מעגלים בגרף על ידי שמירת מחסנית רקורסיה למעקב אחר צמתים שביקרו בהם.
מיון מהיר
חיפוש לרוחב
מיון מיזוג
חיפוש לעומק
מיון בועות
מהי סיבוכיות הזמן של מיון ערימה במקרה הגרוע?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מיון ערימה שומר על סיבוכיות זמן במקרה הגרוע של O(n log n), מכיוון שהוא בונה ערימה ושולף שוב ושוב את האלמנט המקסימלי.
O(n^2)
O(n log n)
O(n)
O(log n)
O(1)
מהי סיבוכיות הזמן הממוצעת לגישה לאלמנט בטבלת גיבוב?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
לטבלאות גיבוב יש סיבוכיות זמן ממוצעת של O(1) לגישה לאלמנטים, בהנחה שפונקציית הגיבוב טובה וממזערת התנגשויות.
O(n)
O(log n)
O(1)
O(n^2)
O(n log n)
איזו קבוצה מכילה פעולות אופייניות המתבצעות על מחסנית?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
הפעולות העיקריות של מחסנית הן Push (הוספת איבר), Pop (הסרת איבר) ו-Peek (צפייה באיבר העליון מבלי להסירו).
Push, Pop, Peek
Enqueue, Dequeue, Peek
Insert, Search, Delete
Traverse, Visit, Sort
איזה אלגוריתם חמדני משתמש בתור עדיפויות למציאת מסלולים קצרים ממקור יחיד בגרף עם משקלי קשתות לא שליליים?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
אלגוריתם דייקסטרה (Dijkstra’s Algorithm) משמש לעיתים קרובות למציאת המסלול הקצר ביותר בגרפים עם משקלי קשתות לא שליליים. הוא משתמש בתור עדיפות כדי לקבוע את המרחק הקצר ביותר ביעילות.
Kruskal's Algorithm
Prim's Algorithm
Bellman-Ford Algorithm
Dijkstra's Algorithm
Floyd-Warshall Algorithm
איזו קבוצה מכילה דוגמאות למבני נתונים של עצי חיפוש בינאריים מאוזנים עצמית?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
עצי AVL ועצים אדום-שחור הם סוגים של עצים מאוזנים עצמית, המבטיחים שהעץ נשאר מאוזן לאחר כל הכנסה או מחיקה.
עץ חיפוש בינארי וערימת מינימום
עץ AVL ועץ אדום-שחור
ערימת מינימום וערימת מקסימום
מחסנית ותור
מה חייב להיות מוגדר בפונקציה רקורסיבית כדי למנוע רקורסיה אינסופית?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
מקרה בסיס הכרחי בפונקציה רקורסיבית כדי לעצור את הקריאות הרקורסיביות כאשר מתקיים תנאי מסוים, ובכך למנוע רקורסיה אינסופית.
לולאה אינסופית
גלישת מחסנית
מקרה בסיס
משתנה גלובלי
מגבלת תחום
מהן שתי הפעולות העיקריות של תור?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
שתי הפעולות העיקריות בתור הן הכנסה (הוספת איבר לסוף) והוצאה (הסרת איבר מההתחלה).
הכנסה לתור (Enqueue) והוצאה מהתור (Dequeue)
דחיפה (Push) ושליפה (Pop)
הצצה (Peek) וראש (Top)
סריקה (Traverse) ומיון (Sort)
מהם התנאים לביצוע מיון טופולוגי על גרף?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
ניתן לבצע מיון טופולוגי על גרף אם הוא מכוון וחסר מעגלים (DAG). סוג זה של סדר שימושי בבעיות תזמון משימות.
הגרף חייב להכיל מעגלים
הגרף חייב להיות משוקלל וקשיר
הגרף חייב להיות לא מכוון וחסר מעגלים
הגרף חייב להיות מכוון וחסר מעגלים
מהי סיבוכיות הזמן של מימוש רקורסיבי נאיבי של סדרת פיבונאצ’י?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
למימוש הרקורסיבי הנאיבי של סדרת פיבונאצ’י יש סיבוכיות זמן של O(2^n) בשל החישובים החוזרים הרבים עבור כל מספר פיבונאצ’י.
O(1)
O(2^n)
O(n)
O(log n)
O(n^2)
איזה מבנה נתונים משמש בדרך כלל למימוש תור עדיפויות?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
תור עדיפויות מיושם לרוב באמצעות ערימה כי היא מאפשרת שליפה יעילה של האלמנט בעל העדיפות הגבוהה או הנמוכה ביותר.
מערך
מחסנית
ערימה
תור
רשימה מקושרת
איזו קבוצה מציגה את סדרי הסריקה הנפוצים של עומק-ראשון בעץ בינארי?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
סריקה תוך־סדרית (in-order), סריקה קדם־סדרית (pre-order) וסריקה אחר־סדרית (post-order) הם שלושת סדרי הסריקה הנפוצים של עומק-ראשון בעץ בינארי, כל אחד עם סדר ביקור שונה בצמתים. סריקת רוחב-ראשון גם היא נפוצה, אך היא קטגוריית סריקה שונה.
סריקה תוך־סדרית (in-order), סריקה קדם־סדרית (pre-order), סריקה אחר־סדרית (post-order)
רוחב-ראשון, עומק-ראשון, ערימה
מיון, חיפוש, סיבוב
דחיפה, שליפה, הצצה
איזו מהתכונות הבאות נכונה לגבי ערימת מינימום?
הסתכל על תבנית הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
בערימת מינימום, השורש הוא תמיד האלמנט הקטן ביותר, וגובה העץ הוא O(log n), מה שהופך הכנסה והוצאה ליעילות.
כל הצמתים ממוינים משמאל לימין
השורש הוא תמיד האלמנט הגדול ביותר
כל העלים נמצאים באותה רמה
השורש הוא האלמנט הקטן ביותר והגובה הוא O(log n)
האם מיון בועות שמחליף איברים סמוכים רק כאשר השמאלי גדול ממש מהימני הוא יציב?
הסתכל על דפוס הגישה, לא על שם המבנה. התשובה הנכונה בדרך כלל נובעת ממה שחייב לקרות ראשון או אחרון.
בתנאי ההשוואה המחמירה שצוין, איברים בעלי מפתחות שווים אינם מוחלפים זה על פני זה, ולכן מיון בועות יציב. מימוש שמחליף גם מפתחות שווים עלול לאבד תכונה זו.
לא יציב
יציב
תלוי במימוש
אף אחד
הסיבוכיות קובעת את היציבות
