מבחן מסכם

1. באיזה מהמבנים הבאים מציאת איבר מינימלי תעשה ב (O(1?

א. heap
ב. מערך ממוין
ג. רשימה ממוינת
ד. כל התשובות נכונות

2. באיזה מהמבנים הבאים מחיקת איבר מינימלי תעשה ב (O(1?

א. heap
ב. מערך ממוין
ג. רשימה ממוינת
ד. אף תשובה אינה נכונה

3. מה מהבאים נכון:

א. כל מה שניתן לעשות ברקורסיה ניתן לעשות על-ידי לולאות, אך לא להפך.
ב. כל מה שניתן לעשות על-ידי לולאות ניתן לעשות ברקורסיה, אך לא להפך.
ג. כל מה שניתן לעשות ברקורסיה ניתן לעשות על-ידי לולאות ולהפך.
ד. יש דברים שניתן לעשות רק בשילוב של לולאות ורקורסיה.

4. מה מהבאים אינו נכון:

א. לא ניתן להחזיק מערך ממוין, מבלי שהכנסת איבר תהיה ב- (O(N , ב- worst case.
ב. מערך ממוין יעיל יותר לפעמים מאשר מערך לא ממוין.
ג. מערך לא ממוין יעיל יותר לפעמים מאשר מערך ממוין.
ד. ניתן לבנות hash table שתעבוד ב- (O(1 גם ב- Worst case: בכל פעם שיהיו יותר מ- 5 איברים מאותה יציאה של הטבלה, אצור hash table חדש, שאליו תצביע היציאה של ה hash table המקורי, כך שמאף יציאה של הhash table החדש לא יהיו יותר מ- 5 איברים.

5. באיזה מהמבנים הבאים יותר כדאי להשתמש אם 99.9% מהפעולות יהיו פעולות הכנסה: בעץ אדום שחור או ברשימה לא ממוינת?

א. במספר מאוד גדול של איברים, יש לעץ אדום-שחור יתרון.
ב. תמיד ברשימה לא ממוינת, מכיוון שהכנסה בה נעשית ב- (O(1.
ג. תמיד בעץ אדום שחור, מכיוון שמספיק שפעם אחת אצטרך לחפש ב (O(N, וזה יהיה יקר יותר מכל מה שחסכתי בהכנסות במחיר (O(LogN.
ד. ככל שמספר האיברים גדול יותר, כך גדל היתרון של רשימה לא ממוינת, מכיוון שההבדל במחיר ההכנסה גדל.