שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2022 - גרפים
מה פלט התכנית הבאה?
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב2022סמסטר א
★★★★★
גרפים
create יוצרת adjacency list (רשימת שכנויות). add מוסיפה קשת. func היא BFS (שימוש ב-queue עם pop(0)).
Adjacency list:
t[0] = [2, 3], t[1] = [4], t[2] = [1], t[3] = [6, 5], t[8] = [6], t[9] = [7, 1]
func(t, 0) — BFS from 0:
q = [0] → pop 0, print 0, add 2,3 → q=[2,3]
pop 2, print 2, add 1 → q=[3,1]
pop 3, print 3, add 6,5 → q=[1,6,5]
pop 1, print 1, add 4 → q=[6,5,4]
pop 6, print 6 → q=[5,4]
pop 5, print 5 → q=[4]
pop 4, print 4 → q=[]
func(t, 9) — BFS from 9:
q=[9] → pop 9, print 9, add 7,1 → q=[7,1]
pop 7, print 7 → q=[1]
pop 1, print 1, add 4 → q=[4]
pop 4, print 4 → q=[]
פלט:
t[0] = [2, 3], t[1] = [4], t[2] = [1], t[3] = [6, 5], t[8] = [6], t[9] = [7, 1]
func(t, 0) — BFS from 0:
q = [0] → pop 0, print 0, add 2,3 → q=[2,3]
pop 2, print 2, add 1 → q=[3,1]
pop 3, print 3, add 6,5 → q=[1,6,5]
pop 1, print 1, add 4 → q=[6,5,4]
pop 6, print 6 → q=[5,4]
pop 5, print 5 → q=[4]
pop 4, print 4 → q=[]
func(t, 9) — BFS from 9:
q=[9] → pop 9, print 9, add 7,1 → q=[7,1]
pop 7, print 7 → q=[1]
pop 1, print 1, add 4 → q=[4]
pop 4, print 4 → q=[]
פלט:
0 2 3 1 6 5 4 9 7 1 4