دفتر هاتف بمليون اسم. إذا فحصتها واحداً تلو الآخر، قد تقوم بمليون مقارنة. لكنك تعرف بالفعل الحيل: افتحها في المنتصف…
English narration · English + 中文 subtitles burned in · سرد باللغة الإنجليزية · ترجمة مدمجة بالإنجليزية + الصينية
19.1
Searching algorithms · خوارزميات البحث
Syllabus · المنهج
English
Candidates should be able to:
Notes and guidance
Show understanding of linear search and binary search methods
Write an algorithm to implement a linear search Write an algorithm to implement a binary search The conditions necessary for the use of a binary search How the performance of a binary search varies according to the number of data items
Show understanding of insertion sort and bubble sort methods
Write an algorithm to implement an insertion sort Write an algorithm to implement a bubble sort Performance of a sorting routine may depend on the initial order of the data and the number of data items
Show understanding of and use Abstract Data Types (ADT)
Write algorithms to find an item in each of the following: linked list, binary tree Write algorithms to insert an item into each of the following: stack, queue, linked list, binary tree Write algorithms to delete an item from each of the following: stack, queue, linked list Show understanding that a graph is an example of an ADT. Describe the key features of a graph and justify its use for a given situation. Candidates will not be required to write code for a graph structure
Show how it is possible for ADTs to be implemented from another ADT
Describe the following ADTs and demonstrate how they can be implemented from appropriate built-in types or other ADTs: stack, queue, linked list, dictionary, binary tree
Show understanding that different algorithms which perform the same task can be compared by using criteria (e.g. time taken to complete the task and memory used)
Including use of Big O notation to specify time and space complexity
العربية
يجب أن يكون المرشحون قادرين على:
ملاحظات وإرشادات
إظهار فهم طريقتي البحث الخطي والبحث الثنائي
كتابة خوارزمية لتنفيذ البحث الخطي كتابة خوارزمية لتنفيذ البحث الثنائي الشروط اللازمة لاستخدام البحث الثنائي كيف يتغير أداء البحث الثنائي وفقاً لعدد عناصر البيانات
إظهار فهم طريقتي الفرز بالإدراج والفرز الفقاعي
كتابة خوارزمية لتنفيذ الفرز بالإدراج كتابة خوارزمية لتنفيذ الفرز الفقاعي قد يعتمد أداء روتين الفرز على الترتيب الأولي للبيانات وعدد عناصر البيانات
كتابة خوارزميات لإيجاد عنصر في كل مما يلي: قائمة مترابطة، شجرة ثنائية كتابة خوارزميات لإدراج عنصر في كل مما يلي: مكدس، طابور، قائمة مترابطة، شجرة ثنائية كتابة خوارزميات لحذف عنصر من كل مما يلي: مكدس، طابور، قائمة مترابطة إظهار الفهم بأن الرسم البياني هو مثال على نوع抽象 للبيانات. وصف الميزات الرئيسية لـالرسم البياني وتبرير استخدامه لموقف معين. لن يُطلب من المرشحين كتابة كود لهيكلة الرسم البياني
إظهار كيفية إمكانية تنفيذ الأنواع المجردة للبيانات باستخدام نوع abstract آخر
وصف الـADTs التالية وإظهار كيفية تنفيذها من أنواع مدمجة مناسبة أو ADTs أخرى: مكدس، طابور، قائمة مترابطة، قاموس، شجرة ثنائية
إظهار الفهم أن الخوارزميات المختلفة التي تؤدي نفس المهمة يمكن مقارنتها باستخدام معايير (مثل الوقت المستغرق لإنجاز المهمة والذاكرة المستخدمة)
بما في ذلك استخدام رمزية Big O لتحديد تعقيد الوقت والمساحة
Source: Cambridge International syllabus · المصدر: منهج كامبريدج الدولي
English
Big O: how algorithms scaleInsertion sort: slide each card into placeBubble sort, pass by passBinary search: halve and conquer
A search finds a target value in a collection (often an array 数组) and returns its position, or "not found".
Linear search
A linear search 线性查找 walks from start to end, comparing each element with the target:
No preparation is needed, so it works on any list. Worst case O($n$) (target at the end or absent); best case 1 comparison. Use it on unsorted data or small lists. (The returned -1 is a sentinel value — an impossible position that means "not found"; the caller tests IF result = -1.)
The exam's version. Paper 3 asks you to complete a linear search written with a flag and a WHILE loop, and Paper 4 to write a function that returns the index or a count. Both look like this:
To stop at the first match instead, use a WHILE Index <= 100 AND NOT Found loop that sets Found ← TRUE and remembers the index. The marks are for the loop over every element, the comparison, and what is returned when the value is absent.
Binary search
A binary search 二分查找 needs the data sorted. Look at the middle element; if it is the target, done; if the target is smaller, search the left half, else the right half — halving the range each time:
Worst case O($\log_{2} n$) — for a million items, about 20 comparisons. Much faster than linear search on large sorted arrays, but you must sort first (a one-off O($n \log n$) cost), worth it if you search many times.
"State the condition necessary for a binary search."The data must be in order (sorted, ascending or descending, on the key being searched). "Describe how to perform a binary search" (three marks): (1) find the middle item of the list (or of the current range) and compare it with the target; (2) if it matches, the search ends; if the target is smaller, repeat on the lower half, if larger, on the upper half; (3) keep halving the range until the item is found or the range is empty, which means it is not present.
The exam's version, with the bounds and a flag, is the one to reproduce when asked to complete the algorithm:
"Explain how the performance varies with the number of items." Each comparison halves the number of items left, so the maximum number of comparisons is about $\log_{2} n$: doubling the size of the list adds only one more comparison. This is O($\log n$). "Compare linear and binary search": a linear search needs up to $n$ comparisons (O($n$)) and, on average, half that, but works on unsorted data; a binary search needs at most $\log_{2} n$ (O($\log n$)) and is far faster for large lists, but the data must first be sorted and it must allow direct access to the middle item (an array, not a linked list). For $1000$ items: $1000$ against $10$ comparisons.
العربية
Big O: how algorithms scaleInsertion sort: slide each card into placeفرز الفقاعات، مررة بمررةBinary search: halve and conquer
البحث يكتشف قيمة مستهدفة في مجموعة (غالباً مصفوفة) ويعود بموقعها، أو "غير موجود".
البحث في قائمة مرتبة، مثل دفتر الهاتف، أسرع بكثير من التحقق من كل سجل واحد تلو الآخر
البحث الخطي
البحث الخطي يمر من البداية إلى النهاية، مقارناً كل عنصر بالمستهدف:
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
لا حاجة لتحضير، لذا يعمل على أي قائمة. أسوأ حالة O($n$) (المستهدف في النهاية أو غائب); أفضل حالة 1 مقارنة. استخدمه على بيانات غير مرتبة أو قوائم صغيرة. (الـ -1 المُرجع هو قيمة إشارة — موقع مستحيل يعني "غير موجود"؛ يختبر الـ IF result = -1.)
النسخة الامتحانية. يطلب الورق 3 إكمال بحث خطي مكتوب باستخدام علم وحلقة WHILE، والورق 4 كتابة دالة تُرجع الفهرس أو عدداً. كلاهما يبدو هكذا:
FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
DECLARE Index, Count : INTEGER
Count ← 0
FOR Index ← 1 TO 100
IF Data[Index] = Target THEN
Count ← Count + 1
ENDIF
NEXT Index
RETURN Count // how many times Target occurs; 0 means not found
ENDFUNCTION
للوقوف عند أول تطابق بدلاً من ذلك، استخدم حلقة WHILE Index <= 100 AND NOT Found تضع Found ← TRUE وتحتفظ بالفهرس. النقاط مخصصة للحلقة على كل عنصر، والمقارنة، وما يُرجع عندما يكون القيمة غائبة.
البحث الخطي يتحقق من كل حرف على التوالي — 23 مقارنة لإيجاد W
البحث الثنائي
البحث الثنائي يحتاج البيانات مرتباً. انظر إلى العنصر الأوسط؛ إذا كان هو المستهدف، انتهى؛ إذا كان المستهدف أصغر، ابحث في النصف الأيسر، وإلا النصف الأيمن —减半 النطاق كل مرة:
low ← 1
high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDWHILE
RETURN -1
أسوأ حالة O($\log_{2} n$) — لمليون عنصر، حوالي 20 مقارنة. أسرع بكثير من البحث الخطي على مصفوفات كبيرة مرتبة، لكن يجب ترتيبها أولاً (تكلفة O($n \log n$) لمرة واحدة)، يستحق الأمر إذا كنت تبحث مرات عديدة.
"اذكر الشرط الضروري للبحث الثنائي."يجب أن تكون البيانات في ترتيب (مرتبة، تصاعدياً أو تنازلياً، على المفتاح الذي يتم البحث عنه). "وصف كيفية إجراء بحث ثنائي" (ثلاث نقاط): (1) إيجاد العنصر الأوسط للقائمة (أو النطاق الحالي) ومقارنته بالمستهدف؛ (2) إذا تطابق، ينتهي البحث؛ إذا كان المستهدف أصغر، كرر على النصف السفلي، إذا كان أكبر، على النصف العلوي؛ (3) استمر في تقسيم النطاق إلى نصفين حتى يتم العثور على العنصر أو يصبح النطاق فارغاً، مما يعني أنه غير موجود.
النسخة الامتحانية، مع الحدود والعلم، هي ما يجب إعادة إنتاجه عند طلب إكمال الخوارزمية:
DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
Mid ← (Lower + Upper) DIV 2
IF Names[Mid] = Target THEN
Found ← TRUE
ELSE
IF Names[Mid] < Target THEN
Lower ← Mid + 1
ELSE
Upper ← Mid - 1
ENDIF
ENDIF
ENDWHILE
IF Found THEN
OUTPUT Mid
ELSE
OUTPUT "Not found"
ENDIF
"اشرح كيف تتغير الأداء مع عدد العناصر." كل مقارنة تُضعف عدد العناصر المتبقية، لذا الحد الأقصى للمقاربات هو حوالي $\log_{2} n$: مضاعفة حجم القائمة تضيف فقط واحدة مقارنة إضافية. هذا O($\log n$). "قارن بين البحث الخطي والثنائي": البحث الخطي يحتاج حتى $n$ مقاربات (O($n$)) وعلى average نصف ذلك، لكنه يعمل على بيانات غير مرتبة؛ البحث الثنائي يحتاج حتى $\log_{2} n$ (O($\log n$)) وأسرع بكثير للقوائم الكبيرة، لكن البيانات يجب أن تكون مرتباً أولاً ويجب أن يسمح بـ الوصول المباشر إلى العنصر الأوسط (مصفوفة، وليس قائمة مرتبطة). لـ $1000$ عناصر: $1000$ مقابل $10$ مقاربات.
البحث الثنائي يُضعف النطاق في كل خطوة (منخفض / وسط / عالي) — مجرد 3 مقاربات لإيجاد W
*فهرس بطاقات: السجلات المرتبة هي ما يجعل البحث الثنائي ممكناً — ضعّف، انظر، ضعّف مرة أخرى
Explore · استكشف
Linear vs binary search · البحث الخطي مقابل الثنائي
Search for a value. Binary search halves the list each step (only on sorted data); linear search checks one by one. · البحث عن قيمة. البحث الثنائي ينصف القائمة في كل خطوة (فقط على البيانات المرتبة)؛ بينما البحث الخطي يفحص العناصر واحداً تلو الآخر.
A bubble sort 冒泡排序 repeatedly walks the array, swapping adjacent pairs that are out of order, so the largest "bubbles" to the end each pass:
Best case O($n$) (already sorted, with the early exit); average/worst O($n^{2}$). Simple but slow for large $n$.
Insertion sort
An insertion sort 插入排序 builds a sorted prefix from the left, inserting each new element into place by shifting larger ones right:
Best case O($n$) (already sorted); worst O($n^{2}$). Good for small or nearly-sorted arrays. It sorts in place 原地 and is stable 稳定 (keeps the order of equal elements).
Tracing a sort
A common task is to show the array after each outer pass. For [D, T, H, R] with insertion sort: pass 1 (key T) no change; pass 2 (key H) → [D, H, T, R]; pass 3 (key R) → [D, H, R, T].
Writing a sort from scratch. "Write pseudocode to sort DataArray[1:1000] into ascending order" is answered by a complete bubble sort with the early-exit flag, or an insertion sort, declared and indented; either scores full marks if it works for every input:
For descending order change > to <; to sort records or a 2D array by one field, compare that field but swap the whole record (or every column). Asked to write an insertion sort "that performs the same task" as a given bubble sort, keep the same array name and direction and reproduce the insertion sort above with the comparison reversed if the order is descending.
"Describe two ways the performance of a sort is affected by the data" (two marks). (1) The number of items: an $O(n^{2})$ sort takes four times as long for twice as many items. (2) How far the data is already in order: a bubble sort with a flag, or an insertion sort, finishes in one pass over already-sorted data ($O(n)$) and does the most work on data in reverse order; the number of swaps depends on how many pairs are out of order. (Also accepted: the range or number of duplicate values, and whether the items are large records that are expensive to move.) Bubble and insertion sort are both O($n^{2}$) in the worst and average cases and O($n$) at best; quicksort and merge sort are O($n \log n$), which is why they are used for large data.
العربية
ترتيب الفقاعات
ترتيب الفقاعات يمر مراراً عبر المصفوفة، مبدلاً أزواجاً مجاورة غير مرتبة، بحيث "تطفو" أكبر القيم إلى النهاية في كل مرور:
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
temp ← A[i]
A[i] ← A[i + 1]
A[i + 1] ← temp
swapped ← TRUE
ENDIF
NEXT i
IF swapped = FALSE THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
أفضل حالة O($n$) (مرتب مسبقاً، مع الخروج المبكر); متوسط/أسوأ O($n^{2}$). بسيط لكن بطيء لـ $n$ كبير.
الترتيب بالإدراج
ترتيب الإدراج يبني بادئاً مرتباً من اليسار، بإدراج كل عنصر جديد في مكانه عن طريق تحريك الأكبر يميناً:
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j]
j ← j - 1
ENDWHILE
A[j + 1] ← key
NEXT i
أفضل حالة O($n$) (مرتب مسبقاً); أسوأ O($n^{2}$). جيد لـ صغيرة أو قريبة من الترتيب المصفوفات. يرتب محلياً و ثابت (يحافظ على ترتيب العناصر المتساوية).
تتبع الترتيب
مهارة شائعة هي عرض المصفوفة بعد كل مرور خارجي. لـ [D, T, H, R] مع ترتيب الإدراج: المرور 1 (المفتاح T) لا تغيير؛ المرور 2 (المفتاح H) → [D, H, T, R]؛ المرور 3 (المفتاح R) → [D, H, R, T].
كتابة ترتيب من الصفر. "اكتب كوداً وهمياً لترتيب DataArray[1:1000] إلى ترتيب تصاعدي" يُجاب به بترتيب فقاعات كامل مع علم الخروج المبكر، أو ترتيب إدراج، مُعلَن ومهبط؛ كلاهما يحصل على الدرجة الكاملة إذا عمل لكل المدخلات:
DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO 1000 - Pass
IF DataArray[Index] > DataArray[Index + 1] THEN
Temp ← DataArray[Index]
DataArray[Index] ← DataArray[Index + 1]
DataArray[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000
لتغيير الترتيب تنازلياً، غيّر > إلى <؛ لتصنيف السجلات أو مصفوفة 2D حقلًا واحداً، قارن ذلك الحقل لكن قم بتبديل السجل الكامل (أو كل عمود). عند الطلب كتابة خوارزمية ترتيب الإدراج "تقوم بنفس المهمة" كخوارزمية الفقاعات المعطاة، احتفظ بنفس اسم المصفوفة والاتجاه وأعد إنتاج ترتيب الإدراج أعلاه مع عكس عملية المقارنة إذا كان الترتيب تنازلياً.
"وصف طريقتين تتأثر بهما أداءية عملية الفرز بواسطة البيانات" (درجتان). (1) عدد العناصر: تأخذ عملية الفرز $O(n^{2})$ أربعة أضعاف الوقت لضعف عدد العناصر. (2) مدى تكون البيانات مرتبة مسبقاً: خوارزمية الفقاعات ذات علم، أو فرز الإدراج، تنتهي بمرور واحد على بيانات مرتبة مسبقاً ($O(n)$) وتبذل أقصى قدر من العمل على بيانات بترتيب عكسي؛ يعتمد عدد التبديلات على عدد الأزواج غير المرتبة. (مقبول أيضاً: النطاق أو عدد القيم المكررة، وما إذا كانت العناصر سجلات كبيرة مكلفة التحريك.) كل من فقاعات وفرز الإدراج هما O($n^{2}$) في أسوأ الحالات والمتوسط، وO($n$) في أفضل حالة؛ فرز سريع وفرز دمج هما O($n \log n$)، ولهذا السبب يستخدمان للبيانات الكبيرة.
فرز إدراج لـ [D, T, H, R]، حيث يتم إزاحة كل مفتاح إلى مكانه مرحلة تلو الأخرى
Explore · استكشف
Watch a sort run · مشاهدة عملية ترتيب
Step through a sort and watch the bars settle into order — how a sorting algorithm works pass by pass. · مرر خوارزمية الترتيب وراقب الأعمدة ترتب نفسها — كيف تعمل خوارزمية الترتيب خطوة بخطوة.
19.1
ADTs in algorithms · الأنواع المجردة للبيانات (ADTs) في الخوارزميات
English
The Abstract Data Types (ADTs) from Topic 10 appear inside many algorithms: a stack 栈 drives depth-first traversal and undo; a queue 队列 drives breadth-first traversal and print ordering; a linked list 链表 lets data grow and shrink.
ADTs can be built from other ADTs, not just from arrays: a queue from two stacks; a stack from a linked list (push = prepend a head node 节点); a queue from a linked list with head and tail pointers 指针; a binary tree 二叉树 from nodes with two child pointers; a dictionary 字典 stores key→value pairs (often on a hash table). Layering this way separates concerns — the algorithm using the ADT need not know how it is built.
The ADTs the exam asks you to describe and implement
Stack (last in, first out): items are added (pushed) and removed (popped) at the same end, the top; a pointer TopOfStack holds the index of the top item. Implemented with an array and that one pointer: push checks the stack is not full, increments the pointer and stores the item; pop checks it is not empty, returns the top item and decrements the pointer.
Queue (first in, first out): items join at the rear (enqueue) and leave from the front (dequeue); two pointers and a count. In a linear queue the front pointer creeps along the array until the space at the start is wasted; a circular queue 循环队列 wraps both pointers round with MOD, so every cell is reused.
Linked list: a sequence of nodes, each holding a data item and a pointer to the next node; a start pointer gives the first node and a null pointer (0 or $-1$) ends the list. In an array implementation two parallel arrays hold the data and the pointers, and unused cells are chained into a free list 空闲列表 so that an insertion knows where to put the new node.
To insert into an ordered list: take the first free cell (NewNode ← FreeList, FreeList ← Pointer[FreeList]), store the item, then walk the list with a Previous and Current pointer until Data[Current] > Item or the end; set Pointer[NewNode] ← Current and Pointer[Previous] ← NewNode (or Start ← NewNode if it goes first). To delete, re-link the previous node past the deleted one and return the cell to the free list.
Binary tree: a root node, each node holding data, a left pointer to a subtree of smaller values and a right pointer to a subtree of larger values. Implemented as a 2D array (or three 1D arrays) Tree[Index, 0..2] for left pointer, data, right pointer, with a root pointer and a next-free pointer.
To insert: store the item in the next free node with both pointers $-1$; if the tree is empty make it the root; otherwise walk down from the root, going left or right by comparison, until the pointer you would follow is $-1$, and set that pointer to the new node. An ADT from another ADT: a stack is a linked list where push and pop both work at the start; a queue is a linked list with a start and an end pointer; a queue can be made from two stacks (push onto one, pop from the other, moving everything across when the second is empty); a binary tree's nodes are records or objects linked by pointers, so it is built from a linked structure of nodes. Say which operations of the new ADT map onto which operations of the old one.
العربية
تظهر الأنواع المجردة للبيانات (ADTs) من الموضوع 10 داخل العديد من الخوارزميات: المكدس يقود التمرير العميق وإلغاء الإجراءات؛ القائمة الانتظار تقود التمرير العرضي وترتيب الطباعة؛ القائمة المترابطة تسمح للنمو والتقلص.
يمكن بناء ADTs من أنواع مجردة أخرى وليس فقط من المصفوفات: قائمة انتظار من مكدسين؛ مكدس من قائمة مترابطة (دفع = إضافة رأس عقدة)؛ قائمة انتظار من قائمة مترابطة مع مؤشرات الرأس والذيل؛ شجرة ثنائية من عقد بمؤشرين للطفل؛ قاموس يخزن أزواج المفتاح→القيمة (غالباً على جدول هاش). فصل المهام بهذه الطريقة — لا يحتاج الخوارزم المستخدم للـ ADT إلى معرفة كيفية بنائه.
الـ ADTs التي يطلب منك الامتحان وصفها وتنفيذها
المكدس (آخر يدخل، أول يخرج): تُضاف العناصر (تُضغط) وتُزيل (تُفصح) في نفس النهاية، وهي الأعلى؛ مؤشر TopOfStack يحتفظ بمؤشر العنصر العلوي. يُنفذ باستخدام مصفوفة ذلك المؤشر واحد: يتحقق الدفع من أن المكدس ليس ممتلاً، يزيد المؤشر ويخزن العنصر؛ يتحقق الفصح من أنه ليس فارغاً، يعيد العنصر العلوي وينقص المؤشر.
FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
IF TopOfStack = 9 THEN // full (array 0 to 9)
RETURN FALSE
ENDIF
TopOfStack ← TopOfStack + 1
StackData[TopOfStack] ← Item
RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
IF TopOfStack = -1 THEN // empty
RETURN -1
ENDIF
TopOfStack ← TopOfStack - 1
RETURN StackData[TopOfStack + 1]
ENDFUNCTION
قائمة الانتظار (أدخل أولاً، يخرج أولاً): تنضم العناصر إلى الخلف (دخول) وتخرج من الأمام (خروج)؛ مؤشران وعدد. في قائمة الانتظار الخطية ينزلق مؤشر الأمام عبر المصفوفة حتى تُهدر المساحة في البداية؛ قائمة الانتظار الدائرية تعيد تدوير كلا المؤشرين مع MOD، بحيث يتم إعادة استخدام كل خلية.
قائمة انتظار دائرية: يتقدم مؤشرا الخلف والأمام مع MOD، لذا تُعاد استخدام أول خلايا المصفوفة بعد مغادرة عناصرها
FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
IF Count = 6 THEN // full
RETURN FALSE
ENDIF
Rear ← (Rear + 1) MOD 6
QueueArray[Rear] ← Item
Count ← Count + 1
RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
IF Count = 0 THEN // empty
RETURN ""
ENDIF
DECLARE Item : STRING
Item ← QueueArray[Front]
Front ← (Front + 1) MOD 6
Count ← Count - 1
RETURN Item
ENDFUNCTION
القائمة المترابطة: تسلسل من العقد، كل منها يحمل عنصراً ومؤشراً للعقدة التالية؛ مؤشر البدء يعطي العقدة الأولى ومؤشر فارغ (0 أو $-1$) ينتهي القائمة. في تنفيذ المصفوفة تحتفظ مصفوفتان موازيان بالبيانات والمؤشرات، وتُربط الخلايا غير المستخدمة في قائمة حرة بحيث تعرف عملية الإدراج أين تضع العقدة الجديدة.
قائمة مترابطة في مصفوفتين: ترتيب القائمة موجود في المؤشرات، وليس في المواقع؛ إدخال اسم يعني أخذ خلية من القائمة الحرة وإعادة ربط مؤشرين
FUNCTION FindInList(Target : STRING) RETURNS INTEGER // index, or 0 if absent
DECLARE Current : INTEGER
Current ← Start
WHILE Current <> 0
IF Data[Current] = Target THEN
RETURN Current
ENDIF
Current ← Pointer[Current]
ENDWHILE
RETURN 0
ENDFUNCTION
لـ الإدراج في قائمة مرتبة: خذ أول خلية حرة (NewNode ← FreeList، FreeList ← Pointer[FreeList])، تخزن العنصر، ثم امشِ القائمة مع Previous وCurrent مؤشر حتى Data[Current] > Item أو النهاية؛ ضع Pointer[NewNode] ← Current وPointer[Previous] ← NewNode (أو Start ← NewNode إذا كان الأول). لـ الحذف، أعد ربط العقدة السابقة لتتجاوز المحذوفة وأعد الخلية للقائمة الحرة.
شجرة ثنائية: عقدة جذر، تحمل كل عقدة بيانات، إشارة يسرى لشجرة جزئية بقيم أصغر وإشارة يمنى لشجرة جزئية بقيم أكبر. تُنفذ كمصفوفة 2D (أو ثلاث مصفوعات 1D) Tree[Index, 0..2] للإشارة اليسرى، البيانات، الإشارة اليمنى، مع إشارة للجذر وإشارة للموقع الحر التالي.
FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER // index, or -1
DECLARE Current : INTEGER
Current ← Root
WHILE Current <> -1
IF Tree[Current, 1] = Target THEN
RETURN Current
ENDIF
IF Target < Tree[Current, 1] THEN
Current ← Tree[Current, 0] // go left
ELSE
Current ← Tree[Current, 2] // go right
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION
لـ الإدراج: ذخّر العنصر في العقدة الحرة التالية بكلا المؤشرين $-1$؛ إذا كانت الشجرة فارغة اجعلها الجذر؛ وإلا مشِ للأسفل من الجذر، اذهب يميناً أو يساراً بالمقارنة، حتى يصبح المؤشر الذي ستتبعه $-1$، وضع ذلك المؤشر على العقدة الجديدة. ADT من نوع ADT آخر: المكدس هو قائمة مترابطة يعمل فيها الدفع والفصح كلاهما في البداية؛ قائمة الانتظار هي قائمة مترابطة مع مؤشر بداية ومؤشر نهاية؛ يمكن إنشاء قائمة انتظار من مكدسين (دفع على أحدهما، فصح من الآخر، نقل كل شيء عندما يكون الثاني فارغاً)؛ عقد الشجرة الثنائية هي سجلات أو كائنات مربوطة بمؤشرات، لذلك تُبنى من بنية قائمة مترابطة من العقد. قائل أي عمليات النوع المجرد الجديد تتوافق مع أي عمليات النوع المجرد القديم.
شجرة ثنائية: لكل عقدة ما يصل إلى عقدتي طفلثلاثة تمريرات عميقة للشجرة الثنائية: المسبقة، الترتيبية (الترتيب المرتب) واللاحقة
Time complexity 时间复杂度 is how the running time grows with input size $n$, written in Big-O notation 大O表示法 (the dominant term): O(1) constant, O($\log n$) binary search, O($n$) linear search, O($n \log n$) good sorts, O($n^{2}$) bubble/insertion sort. A smaller order is better at scale, even if another algorithm is faster for small $n$.
To make that concrete: to sort a million items, an $O(n \log n)$ sort finishes in a fraction of a second, while an $O(n^{2})$ sort can take minutes.
Worked example. A sorted list holds $1000$ items. How many comparisons does each search need in the worst case?
A linear search checks items one at a time, so it may need up to $1000$ comparisons — this is $O(n)$. A binary search halves the list each step, so it needs at most $\lceil \log_2 1000 \rceil = 10$ comparisons — this is $O(\log n)$. Doubling the list to $2000$ items adds only one comparison to the binary search, but up to another $1000$ to the linear search — which is why the order of growth, not raw speed, decides the winner at scale.
Describing an order.O(1): the time is constant, independent of the number of items (pushing onto a stack, reading an array element). O($\log n$): the time grows with the logarithm of the number of items, so doubling the data adds only a fixed extra step (binary search). O($n$): the time grows in proportion to the number of items (linear search, one pass through a list). O($n \log n$): a little worse than linear (efficient sorts). O($n^{2}$): the time grows with the square of the number of items, so doubling the data quadruples the time (bubble and insertion sort). "State the Big O of a binary search of Names[0:99]" is answered $O(\log n)$, and "describe its meaning" as above; Big O measures how the time or memory scales, not the actual time.
Space complexity
Space complexity 空间复杂度 is the extra memory needed. Bubble and insertion sort use O(1) extra (in place); merge sort uses O($n$); recursion uses stack memory proportional to its depth. There is often a time–memory trade-off.
Other criteria
Simplicity (easier to code and maintain), stability, and adaptiveness (faster on nearly-sorted data). The right algorithm depends on the data and the constraints.
العربية
تعقيد الوقت
تعقيد الوقت هو كيفية نمو وقت التشغيل مع حجم الإدخال $n$، يُكتب بـ رمزية بي-أو O (الحد المهيمن): O(1) ثابت، O($\log n$) بحث ثنائي، O($n$) بحث خطي، O($n \log n$) عمليات فرز جيدة، O($n^{2}$) فقاعات/فرز إدراج. الرتبة الأصغر أفضل على النطاق الواسع، حتى لو كان خوارزمية أخرى أسرع لأحجام صغيرة $n$.
لتوضيح ذلك بشكل ملموس: لترتيب مليون عنصر، يكمل ترتيب $O(n \log n)$ في جزء من الثانية، بينما قد يستغرق ترتيب $O(n^{2})$ دقائق.
مثال محلول. قائمة مرتبة تحتوي على $1000$ عنصر. كم عدد المقارنات التي تحتاجها كل عملية بحث في أسوأ حالة؟
يبحث الخطي عن العناصر واحداً تلو الآخر، لذا قد يحتاج إلى ما يصل إلى $1000$ مقارنات — وهذا هو $O(n)$. أما البحث الثنائي فيقسم القائمة إلى نصفين في كل خطوة، لذا يحتاج إلى ما لا يزيد عن $\lceil \log_2 1000 \rceil = 10$ مقارنات — وهذا هو $O(\log n)$. مضاعفة القائمة لتصل إلى $2000$ عنصر تضيف فقط مقارنة واحدة للبحث الثنائي، ولكن ما يصل إلى $1000$ إضافية للبحث الخطي — ولهذا السبب، فإن ترتيب النمو وليس السرعة الخام هو ما يحدد الفائز على النطاق الواسع.
وصف الترتيب.O(1): الوقت ثابت، ولا يتأثر بعدد العناصر (إضافة عنصر إلى المكدس، قراءة عنصر في مصفوفة). O($\log n$): ينمو الوقت مع اللوغاريتم لعدد العناصر، لذا فإن مضاعفة البيانات تضيف فقط خطوة إضافية ثابتة (البحث الثنائي). O($n$): ينمو الوقت بنسبة طردية مع عدد العناصر (البحث الخطي، مرور واحد عبر القائمة). O($n \log n$): أسوأ قليلاً من الخطي (الترتيبات الفعالة). O($n^{2}$): ينمو الوقت مع مربع عدد العناصر، لذا فإن مضاعفة البيانات تضاعف الوقت أربع مرات (ترتيب الفقاعة والإدراج). يُجيب عن "اذكر Big O لعملية بحث ثنائي على Names[0:99]" بـ $O(\log n)$، و"صف معناها" كما ذُكر أعلاه؛ قياس Big O كيف يتوسع الوقت أو الذاكرة، وليس الوقت الفعلي.
كيف تقارن الترتيبات الشائعة للنمو: الترتيب الأصغر يفوز على النطاق الواسعكيف ينمو وقت الترتيب مع عدد العناصر $n$: ترتبط الترتيبات $O(n^2)$ بعيداً عن ترتيب $O(n\log n)$
تعقيد المساحة
تعقيد المساحة هو الذاكرة الإضافية المطلوبة. يستخدم ترتيب الفقاعة والإدراج O(1) إضافياً (في المكان)؛ يستخدم ترتيب merge sort O($n$)؛ تستخدم الاستدعاءات المتكررة ذاكرة مكدس تتناسب مع عمقها. غالباً ما يكون هناك توازن بين الوقت والذاكرة.
معايير أخرى
البساطة (أسهل في البرمجة والصيانة)، الاستقرار، والتكيّف (أسرع على البيانات شبه المرتبة). تعتمد الخوارزمية الصحيحة على البيانات والقيود.
Explore · استكشف
How running time grows with n · كيف ينمو وقت التنفيذ مع n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs. · ارفع n للأعلى وقارن المنحنيات: O(1) و O(log n) تظل مسطحة تقريبًا، O(n) ترتفع باستمرار، O(n²) تنفجر. ولهذا السبب تُستخدم Big-O — وليس ساعة إيقاف — للمقارنة بين الخوارزميات على المدخلات الكبيرة.
Explore · استكشف
Big-O growth · نمو Big-O
Change the input size n and compare how fast each algorithm's work grows — the idea behind time complexity. · غيّر حجم الإدخال n وقارن مدى سرعة نمو عمل كل خوارزمية — وهو المبدأ وراء التعقيد الزمني.
19.2
Recursion · الاستدعاء المتكرر
Syllabus · المنهج
English
Candidates should be able to:
Notes and guidance
Show understanding of recursion
Essential features of recursion How recursion is expressed in a programming language Write and trace recursive algorithms When the use of recursion is beneficial
Show awareness of what a compiler has to do to translate recursive programming code
Use of stacks and unwinding
العربية
يجب أن يكون المرشحون قادرين على:
ملاحظات وإرشادات
إظهار فهم الاستدعاء الذاتي
الميزات الأساسية لـالاستدعاء الذاتي كيف يتم التعبير عن الاستدعاء الذاتي في لغة برمجة كتابة وتتبع الخوارزميات الاستدعاء الذاتي متى يكون استخدام الاستدعاء الذاتي مفيداً
إظهار الوعي بما يجب على المترجم فعله لترجمة كود البرمجة الاستدعاء الذاتي
استخدام المكدسات وإزالة الاستدعاءات
Source: Cambridge International syllabus · المصدر: منهج كامبريدج الدولي
English
Recursion: the call stack winds up and unwinds
Recursive algorithms use recursion 递归: the routine calls itself with a smaller version of the same problem, until a base case 基本情形 ends the chain. It has two parts: the base case (small enough to solve directly — without it the recursion never stops) and the recursive case 递归情形 (reduce the input and call itself).
Factorial 阶乘:
Recursion is natural for self-similar problems: trees, divide-and-conquer 分治 (binary search, merge sort), and nested data. When it is a poor fit, a loop is usually cleaner.
"Describe what is meant by recursion" (two marks).A function or procedure that is defined in terms of itself: it calls itself from within its own body, with a smaller version of the problem each time, until a base case is reached."State three essential features of recursion": (1) a base case (stopping condition) that returns a value without a further call; (2) a general case 一般情形 in which the routine calls itself; (3) each call moves the problem closer to the base case (the parameter is reduced), so that the recursion terminates. Some schemes add: values are returned as the calls unwind.
"Describe when the use of recursion is beneficial, and give an example." When the problem is naturally defined in terms of smaller versions of itself, so that the recursive solution is shorter, clearer and closer to the mathematical definition than a loop would be: a factorial or Fibonacci number, a binary search, traversing a binary tree, merge sort or quicksort, and processing nested structures such as folders within folders. It is a poor choice when the depth is large (the stack may overflow) or when the same sub-problem is computed many times (naive Fibonacci).
Tracing a recursive call
For Factorial(4): the calls go down to Factorial(1)=1, then unwinding multiplies back up: 2*1=2, 3*2=6, 4*6=24. Final result 24. Track each pending call on a stack.
Worked example. The function below is given without an explanation. Trace Unknown(3, 5) and state its output and return value.
Call 1: $X = 3, Y = 5$: $3 < 5$, output 8, call Unknown(4, 4). Call 2: $4 < 4$ is false, return 0. Unwinding: call 1 returns $0 + 1 = 1$. Output 8, return value 1. Write the trace as a table with a row per call (parameters, condition, output, what it returns), and do the returns from the deepest call upwards: that is the unwinding the mark scheme looks for.
Worked example (Fibonacci).Fib(n) returns n when n < 2, otherwise Fib(n - 1) + Fib(n - 2). Find Fib(5).
Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. So Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. The base case is reached many times (Fib(2) is computed three times), which is why this version is slow: it makes 15 calls for $n = 5$ and roughly doubles the calls for every increase in $n$.
Converting recursion to iteration. Every recursive routine can be rewritten with a loop, which uses less memory and is faster: keep a running result and loop from the base case upwards. Factorial as a loop:
Asked to change a recursive insertion sort or search into an iterative one, replace the self-call with a loop over the index that the recursion was stepping through, and turn the base case into the loop's exit condition.
Risks
infinite recursion if the base case is missed — crashes with a stack overflow 栈溢出.
high memory use for deep recursion.
slow if it repeats work (naive Fibonacci is exponential — use a loop or memoisation 记忆化).
العربية
الاستدعاء المتكرر: المكدس يلتف ثم ينفك
الخوارزميات المتكررة تستخدم الاستدعاء المتكرر: تستدعي الدالة نفسها بإصدار أصغر من نفس المشكلة، حتى تنتهي سلسلة من خلال حالة أساسية. تتكون من جزأين: الحالة الأساسية (صغيرة بما يكفي لحلها مباشرة — بدونها لن يتوقف الاستدعاء المتكرر أبداً) والحالة المتكررة (تقليل المدخلات والاستدعاء لنفسها).
المضروب (Factorial):
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1
ELSE
RETURN n * Factorial(n - 1)
ENDIF
ENDFUNCTION
الاستدعاء المتكرر طبيعي للمشاكل ذاتية التشابه: الأشجار، القسمة والفتح (البحث الثنائي، ترتيب merge)، والبيانات المتداخلة. عندما يكون غير مناسب، تكون الحلقة عادة أنظف.
"صف ما يعنيه الاستدعاء المتكرر (درجتان).* دالة أو إجراء مُعرَّف بالنسبة إلى نفسه: فهو يستدعي نفسه من داخل جسمه الخاص، بإصدار أصغر من المشكلة في كل مرة، حتى يتم الوصول إلى حالة أساسية.* "اذكر ثلاث خصائص أساسية للاستدعاء المتكرر": (1) حالة أساسية (شرط توقف) تُرجع قيمة دون استدعاء إضافي؛ (2) حالة عامة تستدعي فيها الدالة نفسها؛ (3) ينتقل كل استدعاء المشكلة أقرب إلى الحالة الأساسية (يتم تقليل المعامل)، بحيث ينتهي الاستدعاء المتكرر. تضيف بعض المخططات: يتم إرجاع القيم أثناء انفكاك الاستدعاءات.
"صف متى يكون استخدام الاستدعاء المتكرر مفيداً، وأعط مثالاً. عندما تكون المشكلة معرفّة بطبيعتها بدلالة إصدارات أصغر منها، بحيث يكون الحل المتكرر أقصر وأوضح وأكثر قرباً من التعريف الرياضي مقارنة بالحلقة: المضروب أو عدد فيبوناتشي، البحث الثنائي، تجول شجرة ثنائية، ترتيب merge أو quicksort، ومعالجة الهياكل المتداخلة مثل المجلدات داخل المجلدات. إنه خيار سيء عندما يكون العمق كبيراً (قد يمتلئ المكدس) أو عندما يتم حساب نفس المشكلة الفرعية مراراً وتكراراً (فيبوناتشي البديهي).
تتبع استدعاء متكرر
بالنسبة لـ Factorial(4): تذهب الاستدعاءات نزولاً حتى Factorial(1)=1، ثم الانفكاك يضرب صعوداً: 2*1=2، 3*2=6، 4*6=24. النتيجة النهائية 24. تتبع كل استدعاء معلق على المكدس.
مثال محلول. الدالة أدناه معطاة بدون شرح. تتبع Unknown(3, 5) واذكر مخرجاتها وقيمتها المُرجعة.
FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
IF X < Y THEN
OUTPUT X + Y
RETURN Unknown(X + 1, Y - 1) + 1
ELSE
RETURN 0
ENDIF
ENDFUNCTION
الاستدعاء 1: $X = 3, Y = 5$: $3 < 5$، الإخراج 8، استدعاء Unknown(4, 4). الاستدعاء 2: $4 < 4$ غير صحيح، إرجاع 0. الانفكاك: يعود الاستدعاء 1 بـ $0 + 1 = 1$. إخراج 8، القيمة المُرجعة 1. اكتب التتبع كجدول بصف لكل استدعاء (المعاملات، الشرط، الإخراج، ما يُرجعه)، وقم بإرجاعات الاستدعاء الأعمق صعوداً: هذا هو الانفكاك الذي يبحث عنه مفتاح التصحيح.
مثال محلول (فيبوناتشي).Fib(n) يُرجع n عندما n < 2، وإلا Fib(n - 1) + Fib(n - 2). أوجد Fib(5).
Fib(5) = Fib(4) + Fib(3)؛ Fib(4) = Fib(3) + Fib(2)؛ Fib(3) = Fib(2) + Fib(1)؛ Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. لذا Fib(3) = 1 + 1 = 2، Fib(4) = 2 + 1 = 3، Fib(5) = 3 + 2 = 5. يتم الوصول إلى الحالة الأساسية مرات كثيرة (يتم حساب Fib(2) ثلاث مرات)، وهو سبب بطء هذه النسخة: فهي تقوم بـ 15 استدعاءً لـ $n = 5$ وتضاعف تقريباً عدد الاستدعاءات لكل زيادة في $n$.
تحويل الاستدعاء الذاتي إلى تكرار. يمكن إعادة كتابة كل إجراء استثنائي باستخدام حلقة، والتي تستهلك ذاكرة أقل وتكون أسرع: احتفظ بنتيجة متراكمة وكرر من الحالة الأساسية للأعلى. المضروب كحلقة:
FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
DECLARE Result, Count : INTEGER
Result ← 1
FOR Count ← 2 TO N
Result ← Result * Count
NEXT Count
RETURN Result
ENDFUNCTION
عند الطلب لتحويل ترتيب إدراج استثنائي أو بحث إلى شكل تكراري، استبدل الاستدعاء الذاتي بحلقة على الفهرس الذي كان يتدرج خلاله الاستدعاء الذاتي، وحول الحالة الأساسية إلى شرط خروج الحلقة.
يستخدم الاستدعاء الذاتي مكدس الاستدعاءات: تدفع الاستدعاءات أطرًا للأسفل نحو الحالة الأساسية، ثم تنفك العودات للأعلى
المخاطر
الاستدعاء الذاتي اللانهائي إذا تم تفادي الحالة الأساسية — يتوقف البرنامج بسبب انفجار المكدس.
استخدام ذاكرة مرتفع للاستدعاءات العميقة.
بطيء إذا كان يعيد العمل (فيبوناتسي بدائي أسّي — استخدم حلقة أو التخزين المؤقت).
Explore · استكشف
Recursion unwinds from the leaves up · تتراجع العودية من الأوراق صعوداً
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow. · مرر عبر fib(4) بالترتيب الذي تنتهي فيه المكالمات فعليًا: تتحلل الأوراق (الحالات الأساسية) أولاً، ثم يجمع كل أب أبنائه. لاحظ أن fib(2) يتم حسابه مرتين — هذا العمل المكرر هو السبب في بطء العودية البدائية.
What the compiler does for recursive code · ما يفعله المترجم للكود الاستثنائي
English
Recursion needs each call to have its own copy of its parameters 参数 and local variables 局部变量. The compiler keeps these on the call stack 调用栈. For each call it pushes a stack frame 栈帧 holding the parameters, the local variables, and the return address 返回地址 (where to resume in the caller). When the function returns, the return value is handed back, the frame is popped, and control resumes at the return address.
Because each call has its own frame, recursive calls don't trample each other's variables. The stack can grow large for deep recursion, which is why very deep recursion may overflow it. This is the same call-and-return mechanism used for ordinary (non-recursive) calls — there is no special "recursion mechanism".
"Explain why a stack is suitable for implementing recursion" (three marks). Each recursive call must save its return address, its parameters and its local variables, and the calls are completed in the reverse order to that in which they were made (the last call made is the first to finish), which is exactly the last in, first out behaviour of a stack: each new call pushes a frame, and each return pops the most recent frame, restoring the caller's state and telling it where to continue. This is the compiler's job when it translates recursive code: it generates the push of a stack frame on every call and the pop on every return, and the frames are unwound as the results come back.
العربية
يحتاج الاستدعاء الذاتي إلى أن يكون لكل استدعاء نسخة خاصة به من المعاملات والمتغيرات المحلية. يحافظ المترجم على هذه البيانات في مكدس الاستدعاءات. لكل استدعاء، يدفع إطار مكدس يحتوي على المعاملات، والمتغيرات المحلية، وعنوان الإرجاع (أين يستأنف في الدالة المستدعية). عندما تعود الدالة، يتم إعادة القيمة المُرجعة، يُزال الإطار، ويستأنف التحكم عند عنوان الإرجاع.
بما أن لكل استدعاء إطارًا خاصًا به، فإن الاستدعاءات الاستثنائية لا تتداخل في متغيراتها. يمكن أن ينمو المكدس بشكل كبير للاستدعاءات العميقة، ولهذا قد يؤدي الاستدعاء العميق جدًا إلى انفجاره. هذا هو نفس آلية الاستدعاء والإرجاع المستخدمة للاستدعاءات العادية (غير الاستثنائية) — لا يوجد "آلية استثنائية" خاصة.
"اشرح لماذا يعتبر المكدس مناسبًا لتنفيذ الاستدعاء الذاتي" (ثلاث درجات). يجب على كل استدعاء استثنائي حفظعنوان إرجاعه، ومعاملاته ومتغيراته المحلية، وتتم الاستدعاءات بالترتيب العكسي لترتيب حدوثها (آخر استدعاء تم إجراؤه هو الأول في الانتهاء)، وهو بالضبط سلوك الأخير دخولاً، الأول خروجاً للمكدس: كل استدعاء جديد يدفع إطارًا، وكل إرجاع يرفع أحدث إطار، مستعيدًا حالة الدالة المستدعية وإخبارها بمكان الاستئناف. هذه مهمة المترجم عند ترجمة الكود الاستثنائي: يولد دفع إطار مكدس في كل استدعاء والرفع في كل إرجاع، وتنفك الأطر بينما تعود النتائج.
19.2
Definitions the examiner accepts · التعريفات التي يقبلها المصحح
English
A definition question is marked against fixed wording. Learn these exactly, and give one answer only.
Term
Definition
linear search
checking each item in turn from the start until the target is found or the end is reached
binary search
repeatedly comparing the target with the middle item of a sorted list and discarding the half that cannot contain it
bubble sort
repeatedly passing through the list, swapping adjacent items that are in the wrong order, until a pass makes no swaps
insertion sort
taking each item in turn and inserting it into its correct place among the items already sorted
abstract data type
a collection of data and the operations that can be performed on it, defined independently of how it is stored
stack
a last-in-first-out structure with push and pop at the top
queue
a first-in-first-out structure with items added at the rear and removed from the front
linked list
a sequence of nodes, each holding data and a pointer to the next node, with a start pointer
binary tree
nodes each holding data and pointers to a left subtree of smaller values and a right subtree of larger values
Big O notation
a way of classifying the time (or memory) an algorithm needs by how it grows with the size of the input
recursion
a routine that calls itself with a smaller version of the problem until a base case stops the calls
base case
the condition under which a recursive routine returns without calling itself
unwinding
the returns of a chain of recursive calls, from the deepest call back to the first, as the stack frames are popped
العربية
تُصنّف أسئلة التعريف بناءً على صياغة ثابتة. احفظ هذه التعريفات بدقة، وقدم إجابة واحدة فقط.
مصطلح
تعريف
البحث الخطي
فحص كل عنصر بالتتابع من البداية حتى العثور على الهدف أو الوصول إلى النهاية
البحث الثنائي
مقارنة الهدف بشكل متكرر مع العنصر الأوسط لقائمة مرتبة والتخلص من النصف الذي لا يمكن أن يحتوي عليه
ترتيب الفقاعات
المرور المتكرر عبر القائمة، وتبادل العناصر المتجاورة التي تقع في الترتيب الخاطئ، حتى لا تقوم أي مرور بتبادلات
ترتيب الإدراج
أخذ كل عنصر بالتتابع وإدخاله في مكانه الصحيح بين العناصر المرتبة مسبقًا
نوع البيانات المجرد
مجموعة من البيانات والعمليات التي يمكن تنفيذها عليها، يتم تعريفها بشكل مستقل عن طريقة تخزينها
مكدس
هيكل الأخير دخولاً، الأول خروجاً مع الدفع والرفع في الأعلى
طابور
هيكل الأول دخولاً، الأول خروجاً مع إضافة العناصر من الخلف وإزالتها من الأمام
قائمة مربوطة
تسلسل من العقد، كل منها يحمل بيانات ومؤشرًا للعقدة التالية، مع مؤشر بداية
شجرة ثنائية
عقد تحمل كل منها بيانات ومؤشرات إلى شجرة فرعية يسرى لقيم أصغر وشجرة فرعية يمنى لقيم أكبر
ترميز بي-أو
طريقة لتصنيف الوقت (أو الذاكرة) الذي يحتاجه خوارزمية بناءً على نموها مع حجم المدخلات
الاستدعاء الذاتي
إجراء يستدعي نفسه بنسخة أصغر من المشكلة حتى توقف حالتان أساسية الاستدعاءات
الحالة الأساسية
الشرط الذي يعود فيه الإجراء الاستثنائي دون استدعاء نفسه
الانفك
عودات سلسلة من الاستدعاءات الاستثنائية، من أعمق استدعاء إلى الأول، أثناء رفع إطارات المكدس
19.2
Exam tips · نصائح للامتحان
English
Searches: linear needs no order and O($n$); binary needs a sorted array, halves each time and is O($\log n$). Know both algorithms by heart, including the bounds and the flag.
Sorts: bubble with a swapped flag, insertion with a key that shifts larger items right; both O($n^{2}$) worst, O($n$) on sorted data. Performance depends on the number of items and how ordered they are.
ADT implementations are pointer bookkeeping: a top pointer; front, rear and count with MOD; start, pointers and a free list; root with left and right pointers. Always check for full and empty.
Big O is about scaling: constant, logarithmic, linear, square. Say "doubling the data adds one comparison" for a binary search.
Recursion: base case, general case, progress towards the base case; beneficial when the problem is defined in terms of itself; a stack holds the return addresses and variables because calls return in reverse order. Trace with a table and unwind from the deepest call.
Common mistakes
Using a binary search on unsorted data, or on a linked list; and setting Lower ← Mid instead of Mid + 1, which loops for ever.
A bubble sort inner loop that runs to the end of the array every pass, or a swap without a temporary variable.
A push or enqueue that does not test for full, or a pop or dequeue that does not test for empty.
Moving the queue's front pointer without MOD in a circular queue, or treating front = rear as always meaning empty.
Inserting into a linked list by shifting the array contents; only the pointers change.
A recursive function with no base case, or one whose recursive call does not make the problem smaller.
Tracing a recursive call but forgetting to add the pending work on the way back up.
Answering "why a stack" with "because it is fast"; the reason is the last-in-first-out order of the returns.
العربية
البحث: يتطلب البحث الخطي عدم وجود ترتيب وO($n$)؛ يتطلب البحث الثنائي مصفوفة مرتبة، وي减半 كل مرة ويكون O($\log n$). احفظ كلا الخوارزميتين حفظًا تامًا، بما في ذلك الحدود والعلم.
أنواع الترتيب: الفقاعة مع علم تبديل، والإدراج بمفتاح يُزيح العناصر الأكبر يمينًا؛ كلاهما O($n^{2}$) في أسوأ الحالات، وO($n$) على البيانات المرتبة. يعتمد الأداء على عدد العناصر ومدى ترتيبها.
تطبيقات ADT هي إدارة مؤشرات: مؤشر علوي؛ أمامي وخلفي وعدد مع MOD؛ بداية ومؤشرات وقائمة حرة؛ جذر مع مؤشرات يسرى ويمنى. تحقق دائمًا من الامتلاء والفراغ.
Big O تتعلق بالتوسع: ثابت، لوغاريتمي، خطي، مربعي. قل "تضاعف البيانات يضيف مقارنة واحدة" للبحث الثنائي.
الاستدعاء الذاتي: الحالة الأساسية، الحالة العامة، التقدم نحو الحالة الأساسية؛ مفيد عندما يتم تعريف المشكلة بدورها؛ تحتفظ المكدس بعناوين الإرجاع والمتغيرات لأن الاستدعاءات ترجع بالترتيب المعكوس. تتبع باستخدام جدول وفك الأعمدة من أعمق استدعاء.
أخطاء شائعة
استخدام البحث الثنائي على بيانات غير مرتبة، أو على قائمة مترابطة؛ وضبط Lower ← Mid بدلاً من Mid + 1، مما يسبب حلقة لا نهائية.
حلقة داخلية لترتيب الفقاعة تعمل حتى نهاية المصفوفة في كل مرور، أو تبديل بدون متغير مؤقت.
دفع أو إضافة لا يختبران الامتلاء، أو سحب أو إزالة لا يختبران الفراغ.
تحريك مؤشر الأمامي للطابور بدون MOD في طابور دائري، أو اعتبار front = rear تعني دائمًا الفراغ.
الإدراج في قائمة مترابطة عن طريق إزاحة محتويات المصفوفة؛ تتغير فقط المؤشرات.
دالة ذاتية ببدون حالة أساسية، أو واحدة يكون فيها الاستدعاء الذاتي لا يصغر المشكلة.
تتبع استدعاء متكرر ولكن نسيان إضافة العمل المعلق أثناء العودة للأعلى.
الإجابة عن "لماذا استخدام المكدس؟" بـ "لأنه سريع"؛ السبب هو ترتيب العودة من آخر إلى أول (LIFO).
Interactive lessons on this topic · دروس تفاعلية حول هذا الموضوع
Work through it step by step, with instant-check exercises. · ا-working عليه خطوة بخطوة، مع تمارين تحقق فوري.
Pick one and the site follows you — notes, papers, videos and practice all open on it. · اختر واحدًا وسيتبعك الموقع — الملاحظات، الأوراق، الفيديوهات والتدريب جميعها تفتح عليه.
Type to search notes, lessons, code, vocabulary and past-paper questions across every subject. · اكتب للبحث عن ملاحظات، دروس، أكواد، مفردات وأسئلة امتحانات سابقة عبر جميع المواد.
*فهرس بطاقات: السجلات المرتبة هي ما يجعل البحث الثنائي ممكناً — ضعّف، انظر، ضعّف مرة أخرى
