Data Structure Multiple Choice Questions on “Bit Array”.
1. What is a bit array?
a) Data structure for representing arrays of records
b) Data structure that compactly stores bits
c) An array in which most of the elements have the same value
d) Array in which elements are not present in continuous locations
Answer: b
Clarification: It compactly stores bits and exploits bit-level parallelism.
2. Which of the following bitwise operations will you use to set a particular bit to 1?
a) OR
b) AND
c) XOR
d) NOR
Answer: a
Clarification: 1 OR 1 = 1, 0 OR 1 = 1, any bit OR’ed with 1 gives 1.
3. Which of the following bitwise operations will you use to set a particular bit to 0?
a) OR
b) AND
c) XOR
d) NAND
Answer: b
Clarification: 1 AND 0 = 0, 0 AND 0 = 0, any bit AND with 0 gives 0.
4. Which of the following bitwise operations will you use to toggle a particular bit?
a) OR
b) AND
c) XOR
d) NOT
Answer: c
Clarification: 1 XOR 1 = 0, 0 XOR 1 = 1, note that NOT inverts all the bits, while XOR toggles only a specified bit.
5. Which of the following is not an advantage of bit array?
a) Exploit bit level parallelism
b) Maximal use of data cache
c) Can be stored and manipulated in the register set for long periods of time
d) Accessing Individual Elements is easy
Answer: d
Clarification: Individual Elements are difficult to access and can’t be accessed in some programming languages. If random access is more common than sequential access, they have to be compressed to byte/word array. Exploit Bit parallelism, Maximal use of data cache and storage and manipulation for longer time in register set are all advantages of bit array.
6. Which of the following is not a disadvantage of bit array?
a) Without compression, they might become sparse
b) Accessing individual bits is expensive
c) Compressing bit array to byte/word array, the machine also has to support byte/word addressing
d) Storing and Manipulating in the register set for long periods of time
Answer: d
Clarification: Bit arrays allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the data cache, they often outperform many other data structures on practical data sets. This is an advantage of bit array. The rest are all disadvantages of bit array.
7. Which of the following is/are not applications of bit arrays?
a) Used by the Linux kernel
b) For the allocation of memory pages
c) Bloom filter
d) Implementation of Vectors and Matrices
Answer: d
Clarification: Normal Arrays are used to implement vectors and matrices. Bit arrays have no prominent role. Remaining all are applications of Bit Arrays.
8. Which class in Java can be used to represent bit array?
a) BitSet
b) BitVector
c) BitArray
d) BitStream
Answer: a
Clarification: The BitSet class creates a special type of array that can hold bit values.
9. Which of the following bitwise operator will you use to invert all the bits in a bit array?
a) OR
b) NOT
c) XOR
d) NAND
Answer: b
Clarification: NOT operation is used to invert all the bits stored in a bit array.
Eg: NOT (10110010) = 01001101.
10. Run-Length encoding is used to compress data in bit arrays.
a) True
b) False
Answer: a
Clarification: A bit array stores the combinations of bit 0 and bit 1. Each bit in the bit array is independent. Run Length encoding is a data compression technique in which data are stored as single value and number of times that value repeated in the data. This compression reduces the space complexity in arrays. Bit arrays without compression require more space. Thus, we will use Run-Length encoding in most of the cases to compress data in bit arrays.
11. What does Hamming weight/population count mean in Bit arrays?
a) Finding the number of 1 bit in a bit array
b) Finding the number of 0 bit in a bit array
c) Finding the sum of bits in a bit array
d) Finding the average number of 1’s and 0’s in bit arrays
Answer: a
Clarification: Hamming/ population count involves finding the number of 1’s in the bit array. Population count is used in data compression.
12. Bit fields and Bit arrays are same.
a) True
b) False
Answer: b
Clarification: Bit field contains the number of adjacent computer locations used to store the sequence of bits to address a bit or groups of bits. Bit array is an array that stores combinations of bit 0 and bit 1. Thus, bit fields and Bit arrays are different.
13. Which one of the following operations returns the first occurrence of bit 1 in bit arrays?
a) Find First Zero
b) Find First One
c) Counting lead Zeroes
d) Counting lead One
Answer: b
Clarification: Find First One operation returns the first occurrence of bit 1 in the bit array. Find First Zero operation returns the first occurrence of bit 0 in the bit array. If the most significant bit in bit array is 1, then count lead zeroes operation returns the number of zeroes present before the most significant bit. If the most significant bit in bit array is 0, then the count lead one returns the number of ones present before the most significant bit.