Bit Stuffing Algorithm MCQs: 10 Solved Questions with Explanations

Solve 10 bit-stuffing MCQs with clear rules, payload traces, overhead calculations, recurring PYQs and delimiter logic.

KnowledgeGate Team

Exam prep & CS education

Updated 31 Oct 20266 min read
Bit Stuffing Algorithm MCQs: 10 Solved Questions with Explanations

Bit-stuffing MCQs look easy until a small counting mistake changes the whole output. The usual traps are miscounting a run of 1s, stuffing a boundary flag, and confusing bit-oriented framing with byte-oriented escaping.

Choose an option first, mark every trigger run, and trace the final bit count before reading the answer. The CS Fundamentals route connects this calculation with the broader core-CS syllabus.

Bit stuffing rule to apply before solving the MCQs

In standard bit-oriented framing, the sender inserts 0 after five consecutive payload 1s, and the receiver removes it. The boundary flag 01111110 (0x7E) is not payload-stuffed. Byte-oriented escaping uses reserved bytes instead; Intro to Byte Stuffing MCQs owns that case, while every calculation here uses bit patterns and delimiter protection.

Number payload 110111111100 from 1 to 12. Positions 4 to 8 form the first five-1 run. Insert 0 after position 8:

110 + 11111 + [0 stuffed] + 11 + 00 = 1101111101100

The result has 13 bits. The complete frame is:

01111110 | 1101111101100 | 01111110

The two flags were added after payload stuffing.

Three rows show the input bits, the stuffed payload with one inserted 0, and the framed payload between two flags.

Bit Stuffing MCQs 1-3: encode, decode and protect delimiters

Question 1

Bit stuffing refers to

  • A. inserting a '0' in user stream to differentiate it with a flag

  • B. inserting a '0' in flag stream to avoid ambiguity

  • C. appending a nibble to the flag sequence

  • D. appending a nibble to the use data stream

Correct answer: A. inserting a '0' in user stream to differentiate it with a flag.

The sender inserts one payload 0 after five 1s so data cannot imitate the flag. The flag stays fixed, and a nibble is four bits.

This question is from BEL 2007, Computer Science.

Question 2

A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

  • A. 0111110100

  • B. 0111110101

  • C. 0111111101

  • D. 0111111111

Correct answer: B. 0111110101.

Scan 01111100101 from left to right. The first five consecutive 1s are followed by a stuffed 0; deleting only that bit gives 0111110101. A changes the final bit, while C and D create extra 1s.

This question is from GATE 2014, Computer Science, Set 3. It also appears in DSSSB 2018 and TPSC 2025.

Question 3

In a data link protocol, the frame delimiter flag is 0111. With bit stuffing, the transmitter sends the data sequence 01110110 as

  • A. 01101011

  • B. 011010110

  • C. 011101100

  • D. 0110101100

Correct answer: D. 0110101100.

For delimiter 0111, insert 0 after each trigger prefix 011. Split the original as 011 | 1 | 011 | 0; stuffing both prefixes gives 0110 | 1 | 0110 | 0 = 0110101100.

This question is from GATE 2004, Information Technology.

Bit Stuffing MCQs 4-5: purpose, framing family and overhead

Mechanism

What it does

Bit stuffing

Provides data transparency in flag-based bit-oriented framing

Character stuffing

Escapes reserved bytes in byte-oriented framing

Error detection or correction

Uses separate redundancy, such as a CRC or code bits

Overhead depends on payload patterns, not maximum frame size. Here it is 1/12 x 100 = 8.33%, not a fixed rate.

Question 4

In data link layer framing, which of the following techniques may suffer from the problem of bit stuffing overhead?

  • A. Character Count

  • B. Character Stuffing

  • C. Flag-based framing (Bit-oriented framing)

  • D. Physical Layer Encoding

Correct answer: C. Flag-based framing (Bit-oriented framing).

The reserved flag makes some payloads longer, as in our 12-to-13-bit example. Character stuffing uses bytes, character count uses length, and encoding is a physical-layer concern.

Question 5

Which of the following statements about bit stuffing in the data link layer is correct?

  • A. Bit stuffing is used to ensure that the frame does not contain sequences identical to the flag used for frame delimiting.

  • B. Bit stuffing is required only when the payload size exceeds the maximum frame size.

  • C. Bit stuffing guarantees error correction by appending redundant bits to the payload.

  • D. Bit stuffing is applicable only in stop-and-wait protocols.

Correct answer: A. Bit stuffing is used to ensure that the frame does not contain sequences identical to the flag used for frame delimiting.

A states the data-transparency purpose. B uses the wrong trigger, C confuses stuffing with error correction, and D incorrectly ties it to stop-and-wait.

Bit Stuffing MCQs 6-7: HDLC and the 0x7E boundary flag

HDLC is bit-oriented and supports point-to-point and multipoint links. Group its 01111110 flag as 0111 1110: hexadecimal 7 and E give 0x7E.

Stop-and-wait, sliding window and Go-back-N are control or retransmission strategies, not complete protocol names.

Question 6

__________ is a bit-oriented protocol for communication over point-to-point and multipoint links.

  • A. Stop-and-wait

  • B. HDLC

  • C. Sliding window

  • D. Go-back-N

Correct answer: B. HDLC.

HDLC is the named protocol and uses flags plus bit stuffing. The other choices are flow or error-control techniques.

This question is from UGC NET 2014, Computer Science, December.

Question 7

In "bit stuffing", each frame begins and ends with a bit pattern in hexadecimal ?

  • A. Ox8C

  • B. Ox6F

  • C. OxFF

  • D. Ox7E

Correct answer: D. Ox7E.

The intended notation is 0x7E, binary 01111110. This flag has six consecutive 1s; stuffing after five payload 1s prevents an accidental copy.

This question is from UGC NET 2023, Computer Science, December.

Bit Stuffing MCQ 8: calculate the stuffed payload bit by bit

Question 8

A bit stuffing framing protocol uses a 8-bit delimiter pattern of 01111110. If the input bit-string is 110111111100 then the output bit-string is

  • A. 1101111110100

  • B. 1101111101100

  • C. 1101111111000

  • D. 1101111011100

Correct answer: B. 1101111101100.

Positions 4 to 8 form the first five-1 run. Insert 0 after position 8 and retain positions 9 to 12:

110 + 11111 + [0 stuffed] + 11 + 00 = 1101111101100

The 12 bits become 13. A inserts late; C and D misplace the group. Insert after the fifth 1, even if another follows. The delimiter is not added to these payload-only options.

Bit Stuffing MCQ 9: recognise a repeated exam stem

BEL 2007 and ISRO 2016 used the same definition stem and options. Treat the recurrence as a speed check: identify the user stream and reject any change to the fixed flag. Both exams test the same rule.

Question 9

Bit stuffing refers to

  • A. inserting a '0' in user stream to differentiate it with a flag

  • B. inserting a '0' in flag stream to avoid ambiguity

  • C. appending a nibble to the flag sequence

  • D. appending a nibble to the user data stream

Correct answer: A. inserting a '0' in user stream to differentiate it with a flag.

The inserted 0 belongs to the user-data stream and prevents payload bits from imitating the delimiter. The flag remains unchanged, and a nibble is four bits rather than one stuffed bit.

This question is from ISRO 2016, Computer Science.

Bit Stuffing MCQ 10: infer a delimiter from original and transmitted data

This is a generalised puzzle, not the HDLC five-1 rule. Test a candidate by inserting the complement of its final bit after every occurrence of its prefix.

Question 10

In data link layer, bit stuffing is employed. The transmitter sends the data sequence 1011010110110 as 10101010010101010. Find the frame delimiter flag

  • A. 011

  • B. 0110

  • C. 110

  • D. 0111

Correct answer: A. 011.

For 011, the prefix is 01; complementing its final 1 means stuffing 0. The prefix occurs at positions 2-3, 5-6, 7-8 and 10-11:

1 | 01 | 1 | 01 | 01 | 1 | 01 | 10

After four insertions:

1 | 010 | 1 | 010 | 010 | 1 | 010 | 10 = 10101010010101010

The input grows from 13 to 17 bits and matches. For 0110, 110 and 0111, the prefix occurs three times or the stuffed bit is wrong, producing 16 bits or a mismatch. Positions and values must also match.

Two-row delimiter-inference trace compares 1011010110110 with 10101010010101010, showing four boxed 01 prefixes, four inserted zeros, and transmission growing from 13 to 17 bits.

Final bit-stuffing checklist and what to practise next

Use this five-step check on every question:

  1. Identify the framing or stuffing rule.

  2. Exclude boundary flags from payload stuffing.

  3. Scan the original data from left to right.

  4. Insert immediately after the trigger run or prefix.

  5. Verify both the final string and the increase in bit count.

Stuffing provides transparency, not error correction. Continue with Computer Networks MCQs for broader practice. Use GATE Guidance by Sanchit Sir as a structured Computer Networks route, or Computer Science Fundamentals for Placements by Sanchit Sir for placement-focused core-CS revision.