מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 1/שאלות


שימו לב:

*נא להגיש רק את שאלות 1-5.
  • שאלה 6 שייכת למעשה לקורס חדו"א. אנא וודאו שהנכם מבינים את המשפט, אך אין צורך להגיש את התשובה.
  • שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1 עריכה

אנא הוכח או הפרך את הטענות הבאות:

  1.  .
  2.  .
  3.  .
  4.  .
  5.  .


 

שימו לב:

הכוונה בסעיף הראשון לפונקציה הקבועה  ,‏ ולא לקבוע 80.

2 עריכה

נתונות שתי פונקציות:

 
 
כאשר  .

  1. האם  ?
  2. האם  ?

3 עריכה

נתבונן בפסוודו-קוד הבא:

Foo(n)
1	Bar-1(n)
2	Bar-2(n)
3	Bar-3(n)

נתון:

  1. זמן הריצה של Bar-1(n) הוא  .
  2. זמן הריצה של Bar-2(n) הוא  .
  3. זמן הריצה של Bar-3(n) הוא  .

עבור כל אחד מהחסמים הבאים, אנא ציין האם הוא בהכרח מתקיים, בהכרח לא מתקיים, או שאי אפשר לקבוע בוודאות האם הוא בהכרח מתקיים או לא:

  1. זמן הריצה של Foo(n) הוא  .
  2. זמן הריצה של Foo(n) הוא  .
  3. זמן הריצה של Foo(n) הוא  .

4 עריכה

אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b), המקבלת:

  1. מערך ממויין A של מספרים שלמים חיוביים
  2. מספר שלם חיובי a
  3. מספר שלם חיובי b גדול ממש מa

ומחזירה את מספר האיברים בA שכל אחד מהם נמצא בתחום  .



דוגמה:

אם A = [1, 2, 4, 5, 99 , 11999], אז Find-Num-In-Range(A, 3, 99) תחזיר 2 (יש שני איברים בתחום).

  • הערה: אנא מצא מימוש הפועל בזמן לוגריתמי באורך המערך.

5 עריכה

להלן הפונקציה Merge המקבלת שני מערכים ממויינים:

# Merge. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )
	
2	l = r = m = 1
	
3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6		else if l > Length(L)
7			Merged[m++] = R[r++]
8		else if L[l] < R[r]
9			Merged[m++] = L[l++]
10		else
11			Merged[m++] = R[r++]

12	return Merged

אנא הוכח שהפונקציה מחזירה מערך ממויין המכיל את איחוד ערכי מערכי הכניסה, ונתח את סיבוכיות הפונקציה.

6 עריכה

אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):

  1. אם   מונוטונית לא יורדת, אז  
  2. אם   מונוטונית לא עולה, אז  

7 עריכה

  ו  הן פונקציות חיוביות ממש, והגבול   קיים ושווה ל . אנא הוכח או הפרך את הטענה הבאה: אם   או  ,‏ אז  .

8 עריכה

אנא הוכח או הפרך כ"א מהכללים הבאים:

  1.  
  2.  

9 עריכה

  היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה   כך שמתקיים   אבל הגבול   אינו קיים.