أسئلة المقال وتتبع الشيفرة وتصحيح الأخطاء وكتابة الشيفرة في بنك أسئلة الأسبوع:
هياكل البيانات والخوارزميات (DSA27) · الأسبوع 7
Queues (Lecture 07)
هذه اختبارات للتدريب الذاتي، تُحفظ إجاباتك على هذا الجهاز فقط ولا تُرسل إلى أحد. الأسئلة والشرح بالإنجليزية لغة المقرر.
-
"FIFO" means:
Last in, first out (a) is a stack — Week 6.
-
enqueue(1),enqueue(2),enqueue(3),dequeue(),enqueue(4),dequeue(). What does the nextdequeue()return?The queue goes [1, 2, 3] → dequeue 1 → [2, 3] → enqueue 4 → [2, 3, 4] → dequeue 2 → [3, 4]; the next dequeue returns 3. (A stack would have returned 4 — the difference in one question.)
-
In
SlowQueue,dequeueispop(0)on aDynamicArray. Its cost on a queue of n items is:pop(0)moves the n − 1 elements behind the front. Amortised O(1) (c) is the cost ofappend, the enqueue. -
An array-based queue that enqueues with
insert_at(0, x)and dequeues withpop()at the end has costs:pop()at the end moves nothing, butinsert_at(0, x)shifts everything. With a plain array, whichever end is the front, one operation is O(n). -
A
CircularQueuewith capacity 8 has head = 6 and size = 3. The nextenqueuewrites to slot:(6 + 3) % 8 = 9 % 8 = 1. Slot 9 (a) does not exist; the items are in slots 6, 7 and 0.
-
A
CircularQueuewith capacity 5 has head = 4 and size = 2. After onedequeue, head is:(4 + 1) % 5 = 0: the head wraps. Slot 5 (a) is past the end of the
Array. -
A ring buffer that stores only
headandtail(no size) findshead == tail. The queue is:Empty: nothing between head and tail. Full: the tail has come all the way round to the head. Both look the same.
-
CircularQueuekeeps a_sizefield because:With the size, empty is
size == 0and full issize == capacity. TheArraydoes know its length (c):len(block). -
A full ring of capacity 4 holds
[E, F, C, D]with head = 2. It grows to capacity 8 by copyingnew[i] = old[i]and keeping head = 2. Read front to back, the queue is now:Slots 2 and 3 of the new block hold C and D, slots 4 and 5 are empty, and E and F sit in slots 0 and 1 — behind the front. The correct copy gives (a) with head = 0.
-
A queue on a singly linked list with
headandtailreferences should put the front of the queue at:Dequeue at the head (
pop_front, O(1)), enqueue after the tail (O(1)). -
Why not dequeue at the tail of a singly linked list?
The new tail is the node before the old one, and a singly linked list can only find it by walking from the head.
-
A queue built from two stacks (
inboxandoutbox, pouring only whenoutboxis empty):enqueue(1),enqueue(2),enqueue(3),dequeue(). How many items are now inoutbox?The first dequeue finds
outboxempty and pours all three:outboxholds 3, 2, 1 (1 on top). It pops 1, leaving 2 and 3. -
The cost of
dequeueon that two-stack queue is:One dequeue can pour n items, so the worst case (c) is O(n), but each item is pushed, poured and popped once in its life.
-
Which of these needs a queue?
BFS visits nodes in the order they were discovered: FIFO. The other three are stack applications from Week 6.
-
n enqueues followed by n dequeues on a
SlowQueuecost in total:Dequeue number i shifts n − i elements: (n-1) + (n-2) + … + 0 = n(n-1)/2.
-
In Python,
(0 - 1) % 8is:Python's
%takes the sign of the divisor, so the result is in 0..7: stepping back from slot 0 wraps to slot 7. In C or Java the answer would be −1 (a). -
A deque is a structure that:
A double-ended queue. (a) is a priority queue.
-
Measured, a ring-buffer dequeue and a linked-queue dequeue are both flat lines as n grows, but the ring is about five times slower. The reason:
Both are O(1); the ring pays more per operation. Big-O hides constant factors, and measurement shows them.
-
Five people A, B, C, D, E stand in a circle; counting from A, every second person leaves. Who is left last?
B, D, A and E leave in that order (W7-C2); C is last.
-
An array queue with a head index but no wrap-around, 8 slots: 8 enqueues, then 5 dequeues. How many more enqueues fit without growing the block?
Tail = 8: there is no slot 8, even though slots 0 to 4 are dead and free. That is why the queue must wrap.
-
A
CircularQueuethat doubles its capacity when full has an enqueue cost of:The occasional copy is O(n), but doubling makes the copies total less than 2n over n enqueues — Lecture 04's argument.
-
A priority queue (Week 12) differs from a queue because it dequeues:
Same two operations, a different rule — and a different structure underneath, the heap.
-
A
CircularQueue(4), starting empty:enqueue(1),enqueue(2),enqueue(3),enqueue(4),dequeue(),dequeue(),enqueue(5). Which describes the ring now?After four enqueues the ring is full (
1 2 3 4, head 0). Two dequeues move head to 2, size 2. The tail is(2 + 2) % 4 = 0, so 5 goes into slot 0, freed by 1. Slot 4 (b) does not exist: that is the missing%. Head 0 (a) forgets that dequeue moves the head; size 4 (d) counts the dequeued items. -
A
CircularQueue(5), starting empty: enqueue A, B, C, D, E; dequeue three times; enqueue F, then G. What is in the block, from slot 0 to slot 4?The three dequeues leave D, E in slots 3 and 4, with head 3. F goes to
(3 + 2) % 5 = 0, G to slot 1, and slot 2 is still empty. (b) islist(q), the queue order, not the block. (d) forgets thatdequeueclears the slot it read, so C is gone. (c) has seven slots in a five-slot block. -
A full
CircularQueueof capacity 4 holds C D E F (front to back), with head = 2.enqueue(G)makes the correct_growdouble the block first. Afterwards, head is ___ and G is in slot ___:_growcopies in queue order: C D E F go to slots 0–3 and head becomes 0. Then G is written at(0 + 4) % 8 = 4. (a) is what happens if head is kept, which is the naive grow of W7-M09. (b) would overwrite the front. -
A student's
_growcopies in queue order into anArray(8)and setshead = 0, but forgets to setself._capacity = 8. On the full ring of W7-M25,enqueue(G)then:The tail is still computed modulo 4:
(0 + 4) % 4 = 0, so G overwrites C, the front, andlist(q)readsG D E F G. No error is raised, which is what makes the bug dangerous: (c) is wrong. (a) is wrong because the arithmetic, not the block, decides where G goes. -
A
dequeueupdates the head withself._head += 1instead ofself._head = (self._head + 1) % self._capacity. On aCircularQueue(4): enqueue A, B, C, D; dequeue four times; enqueue E; dequeue. What happens?The four dequeues read slots 0–3, so they work, and head ends at 4. The enqueue writes E at
(4 + 0) % 4 = 0, which also works. Then the dequeue readsself._block[4], and theArrayraisesIndexError. The bug hides until the head has gone once round the ring: (b) is what the correct code does. -
A linked queue's
enqueuetestsif self._tail is None:to decide that the queue is empty, and itsdequeuemovesheadon but never resetstail. Afterenqueue(1),dequeue(),enqueue(2), the nextdequeue():After the first dequeue, head is
Nonebut tail still refers to the removed node 1. Soenqueue(2)takes theelsebranch and links 2 after that dead node, and head staysNone. The next dequeue finds headNoneand raises, althoughlensays 1. The fix: when the queue becomes empty, resettailtoNonetoo (W7-B4). -
A queue from two stacks (pour only when
outboxis empty). Count everypushandpopon the two stacks, including the pours: enqueue 1, 2, 3; dequeue; enqueue 4, 5; dequeue three times. How many stack operations is that in total?Each item costs at most four operations: push to
inbox, pop frominbox, push tooutbox, pop fromoutbox. Items 1–4 are dequeued, so 4 × 4 = 16. Item 5 was poured but not dequeued, so 3 more: 19. Step by step: 3 pushes; a pour of 3 items (6) and 1 pop; 2 pushes; 2 pops; a pour of 2 (4) and 1 pop. (b) and (a) forget to count the pours as two operations per item; (c) is not a real count. -
A ring buffer that leaves one slot unused to tell full from empty has a block of 8 slots. It holds at most:
One slot always stays empty, so that
head == tailcan only mean empty. Eight slots hold seven items. (a) would need a size field, which is whatdsa/queue.pykeeps. -
A ring with 8 slots stores only
headandtailand leaves one slot unused. Now head = 3 and tail = 2. How many items does it hold, and is it full?The size is
(tail - head) % 8 = (2 - 3) % 8 = 7, and full is defined as(tail + 1) % 8 == head:3 == 3. With one slot left unused, 7 is the most an 8-slot ring can hold, so (d) is impossible. (a) reads the distance the wrong way round; (b) confusestail + 1 == head(full) withhead == tail(empty). -
CircularQueue.dequeuesets the slot it read back toNone. Why?The slot is outside the live part of the ring, so the queue is correct without clearing it (a, c and d are wrong:
is_emptyuses_size,enqueueuses(head + size) % capacity, and__iter__walks onlysizeslots from head). But the block would keep a reference to the object, and Python's garbage collector could not free it. -
Which of these is a typical use of a ring buffer?
A fixed block that overwrites its oldest entry is exactly a ring buffer. Brackets (a) and undo (b) need stacks; sorting (c) needs neither.
-
What does this print?
q = CircularQueue() q.enqueue("1") for _ in range(6): s = q.dequeue() print(s, end=" ") q.enqueue(s + "0") q.enqueue(s + "1")The queue gives breadth-first order: the children of
1(10, 11) are dequeued before the children of10(100, 101), and those before the children of11(110, 111). That is the binary numbers 1 to 6, in order. (b) follows one branch only (depth-first); (d) swaps 100 and 101; (c) enqueuess + "1"first. -
Six people, 1 to 6, are put in a queue. Until one is left: move two people from the front to the back, then dequeue the third, who leaves. In what order do they leave, and who is left?
Queue 1 2 3 4 5 6: move 1, 2, remove 3. Queue 4 5 6 1 2: move 4, 5, remove 6. Queue 1 2 4 5: move 1, 2, remove 4. Queue 5 1 2: move 5, 1, remove 2. Queue 5 1: move 5, 1, remove 5. 1 is left. (a) removes 2 before 4: it loses track after the queue wraps.
-
A graph search dequeues a node, then enqueues its unvisited neighbours, and repeats. If the queue is replaced by a stack (pop instead of dequeue, push instead of enqueue), the same loop:
The stack hands back the most recently found node first, so the search goes as deep as it can before backing up. That is why Week 14 puts
bfsanddfs_iterativeside by side: the loops are the same, and only the structure differs. (c) cannot happen as long as visited nodes are not added again. -
With Python's
collections.deque, the O(1) way to remove the front item of a queuedis:popleft()removes the front in O(1).deque.pop()(b) removes the back, anddeque.pop(0)(a) is an error:poptakes no argument. On alist,pop(0)would work but costs O(n).dequehas nodequeuemethod (c). -
A moving average of the last k readings keeps a
CircularQueue(k)and a running total beside it. The running total is there because:When a reading arrives, subtract the value that leaves the window and add the new one: O(1) per update. Adding up k values each time would cost O(k). The ring can be iterated (a), and
_sizetells full from empty (b). -
A
CircularQueuewith capacity 6 has head = 4 and size = 5. Front to back, the queue's items are in slots:Slot of offset i is
(4 + i) % 6, for i = 0 to 4: 4, 5, then round to 0, 1, 2. (b) forgets the%; (c) ignores head; (d) walks backwards. -
A naive
_growcopiesnew[i] = old[i]and keeps head. It passes a test that fills a freshCircularQueue(4)with A, B, C, D and then enqueues E. Why does the test not catch the bug?With head = 0, the i-th item of the queue really is in slot i, so copying slot by slot happens to give the right order. The naive copy goes wrong only once the data has wrapped: on the ring of W7-M25 it gives
C D None None G. So (a) is wrong. A test must wrap the ring before it grows it.
32 درجات
أسئلة المقال
9 أسئلة مقالية (32 درجة). اكتب إجابتك أولًا، ثم اعرض الإجابة النموذجية ونقاط التصحيح، وقدّر درجتك بأمانة: كل نقطة تساوي درجة تقريبًا.
مجموع درجات المقال: 0 / 32
-
State the Queue ADT with the cost of each operation. Explain why an array-based queue that shifts is O(n) per dequeue, and why swapping which end is the front does not help. How does a ring buffer fix it?
الإجابة النموذجية ونقاط التصحيح
- ADT:
enqueue(x)at the back,dequeue()from the front (FIFO),is_empty,len— all O(1);dequeueraisesIndexErrorwhen empty. - Shifting: on a plain array the front is a fixed position, index 0; removing it moves the n − 1 others: O(n).
- Swapping ends does not help: the back at index 0 makes enqueue shift everything instead. A queue uses both ends, and an array is cheap at only one.
- Ring buffer: do not move data, move the indices.
headmarks the front; the back is(head + size) % capacity; both wrap round with%, so slots freed at the front are reused. Every operation O(1).
- ADT:
-
In a ring buffer,
head == tailcan mean two different things. Explain which two, with an example of each, and describe two ways of telling them apart. Which one doesdsa/queue.pyuse?الإجابة النموذجية ونقاط التصحيح
- Empty: nothing in the ring, e.g. a new queue: head = tail = 0.
- Full: the tail has caught up with the head, e.g. capacity 4, head 2, four items: tail = (2 + 4) % 4 = 2.
- Fixes: (1) keep a count
size— empty issize == 0, full issize == capacity; (2) leave one slot always unused — full is(tail + 1) % capacity == head, sohead == tailmeans only empty; (3) a flag set when an enqueue makes head equal tail. dsa/queue.pykeeps_size(and computes the tail from it).
-
A full
CircularQueuemust grow. Explain, with an example, why copying the block slot by slot gives a wrong queue once the data has wrapped, give the correct copy, and explain why doubling keeps enqueue amortised O(1).الإجابة النموذجية ونقاط التصحيح
- Example: capacity 4, head 2, block
[E, F, C, D], queue C D E F. A slot-by-slot copy into 8 slots keeps C, D in slots 2, 3 and E, F in slots 0, 1; with head 2 the queue now reads C, D, then empty slots — E and F are lost behind the front. - Correct copy: in queue order:
new[i] = old[(head + i) % old_capacity]for i in 0..size − 1, then head = 0 (and the capacity updated). - Amortised O(1): a copy happens only when the ring is full, and doubling means the copies after n enqueues total 1 + 2 + 4 + … < 2n: O(n) over n operations, O(1) each on average.
- It only goes wrong once the data has wrapped, which is why it survives tests that never dequeue before growing.
- Example: capacity 4, head 2, block
-
Describe a queue built from two stacks. Show that it is amortised O(1) per operation, and explain why pouring must happen only when the
outboxis empty.الإجابة النموذجية ونقاط التصحيح
inboxtakes every enqueue;dequeuepopsoutbox, and whenoutboxis empty it first pours all ofinboxinto it — which reverses them, so the oldest is on top.- Amortised: each item is pushed on
inboxonce, moved tooutboxonce and popped once — three O(1) steps in its life, so n operations cost O(n). - Pour only when empty: pouring into a non-empty
outboxwould put newer items on top of older ones and break FIFO; pouring back and forth on every dequeue keeps FIFO but costs O(n) per dequeue (W7-K3).
-
Compare the ring buffer and the linked queue (with head and tail): cost per operation, memory, and when you would choose each. Where does Python's
collections.dequefit?الإجابة النموذجية ونقاط التصحيح
- Ring buffer: O(1) (amortised if it grows); one contiguous block, no allocation per item, good locality. Choose it when the maximum size is known or bounded — hardware and OS buffers — or for speed in general.
- Linked queue: O(1) worst case, never copies; but a node per item (more memory, scattered). Choose it when a worst-case guarantee matters more than memory.
collections.dequecombines them: a doubly linked list of fixed blocks — O(1) at both ends, few allocations. It is what to use in real Python code.
-
Three ring-buffer bugs: the tail computed as
head + sizewith no%; the head moved withhead += 1with no%; and a_growthat never updates_capacity. For each, say what goes wrong and the shortest operation sequence that shows it. Why do all three pass a test that never wraps the ring?الإجابة النموذجية ونقاط التصحيح
- No
%on the tail: once the back reaches the end of the block, the write goes to slotcapacityand theArrayraisesIndexError, although there are free slots at the front. Shortest:CircularQueue(2): enqueue, enqueue, dequeue, enqueue (tail = 1 + 1 = 2). - No
%on the head: dequeues work until head reachescapacity; the next dequeue reads slotcapacityand raises. Shortest:CircularQueue(1): enqueue, dequeue (head = 1), enqueue (written to(1 + 0) % 1 = 0), dequeue. _capacitynot updated in_grow: the new block is bigger, but every%still wraps at the old size, so the next enqueue after the grow overwrites the front, silently. Shortest: fill a ring of capacity 1, enqueue twice more.- Why the tests miss them: while the ring has not wrapped, head is 0 and
head + sizeis below the capacity, so%changes nothing. Every test must take the ring round at least once, and grow it after it has wrapped.
- No
-
When a ring buffer is full, it can refuse (a bounded queue) or grow. Explain both choices, give a real use for each, and say which
level_orderandbfsneed, and why.الإجابة النموذجية ونقاط التصحيح
- Refuse (bounded): raise an error, or make the producer wait, or drop data when full. Memory is fixed. Used for audio and network buffers, and keyboard buffers, where memory must not grow.
- Grow: allocate a block twice as big and copy in queue order; enqueue stays amortised O(1). Used for general-purpose queues such as
collections.deque. level_orderandbfsneed a growing queue: they cannot know in advance how many nodes will be waiting at once (a whole level of a tree, a whole frontier of a graph), and refusing would make the search fail.
-
Describe
enqueueanddequeuefor a queue on a singly linked list withheadandtail, including the empty cases. Explain why the front must be the head, and what goes wrong ifdequeuedoes not resettailwhen the queue becomes empty.الإجابة النموذجية ونقاط التصحيح
- enqueue: make a node. If the queue is empty, it becomes both
headandtail; otherwise settail.nextto it and movetailto it. O(1). - dequeue:
IndexErrorif empty; otherwise takehead.value, moveheadtohead.next; ifheadis nowNone, settail = Nonetoo. O(1). - Front at the head: removing at the head is O(1); removing the last node of a singly linked list needs the node before it, an O(n) walk. So we add at the tail and remove at the head.
- Stale tail:
tailstill refers to the removed node. Ifenqueueteststailto detect emptiness, the new node is linked after that dead node andheadstaysNone:lensays 1, but the next dequeue raises. (If it testshead, the bug hides, buttailstill keeps a dead node alive.)
- enqueue: make a node. If the queue is empty, it becomes both
-
Explain why breadth-first order needs a queue, using the binary numbers 1, 10, 11, 100, … generated from "1" (dequeue s, enqueue s + "0" and s + "1"). What order do you get if the queue is replaced by a stack, and why?
الإجابة النموذجية ونقاط التصحيح
- A queue hands items back in the order they were discovered: everything at one level is dequeued before anything at the next. From "1": dequeue 1, enqueue 10, 11; dequeue 10, enqueue 100, 101; dequeue 11, enqueue 110, 111…
- So the order is 1, 10, 11, 100, 101, 110, 111, …: the binary numbers in increasing order, level by level (by length).
- With a stack, the last item found comes out first: 1, 11, 111, 1111, … (with
s + "0"pushed befores + "1"). The search goes deep along one branch and never comes back to 10. That is depth-first order, as in Week 14.