This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Bit Array”.
1. 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
Explanation: 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, outperforming many other data structures on functional data sets due to their ability to leverage bit-level parallelism, restrict memory access, and maximise the use of the data cache. This is a bonus of using a bit array. The rest are all bit array drawbacks.
2. 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
Explanation: Vectors and matrices are implemented using normal arrays. Bit arrays play a minor role. Bit Arrays are used in the remaining applications.
3. Which class in Java can be used to represent bit array?
Explanation: The BitSet class creates an array that can contain bit values.
4. Which of the following bitwise operator will you use to invert all the bits in a bit array?
Explanation: To invert all the bits in a bit array, use the NOT operation.
Eg: NOT (10110010) = 01001101.
5. Run-Length encoding is used to compress data in bit arrays.
Explanation: Bit 0 and bit 1 combinations are stored in a bit array. Every bit in the bit array is self-contained. Run length encoding is a data compression technique that stores data as a single value and the number of times the value appears in the data. In arrays, this compression decreases the space complexity. Bit arrays that aren’t compressed take up more space. As a consequence, we’ll use Run-Length encoding to compress data in bit arrays in the vast majority of instances.
6. 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
Explanation: Finding the number of 1s in a bit array is known as hamming/population counting. In data compression, the population count is used.
7. Bit fields and Bit arrays are same.
Explanation: The number of adjacent machine locations used to store the sequence of bits to address a bit or groups of bits is stored in the bit field. A bit array is a set of bit 0 and bit 1 combinations. As a consequence, bit fields and bit arrays are not the same.
8. 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
Explanation: The Find First One operation returns the bit array’s first occurrence of bit 1. The Find First Zero operation returns the bit array’s first occurrence of bit 0. The count lead zeroes operation returns the number of zeroes present before the most significant bit in a bit array if the most significant bit is 1. The count lead one function returns the number of ones present before the most significant bit in a bit array if the most significant bit is 0.
9. 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
Explanation: It stores bits in a compact manner and takes advantage of bit-level parallelism.
10. Which of the following bitwise operations will you use to set a particular bit to 1?
Explanation: 1 OR 1 = 1, 0 OR 1 = 1, any bit OR’ed with 1 gives 1.
11. Which of the following bitwise operations will you use to set a particular bit to 0?
Explanation: 1 AND 0 = 0, 0 AND 0 = 0, any bit AND with 0 gives 0.
12. Which of the following bitwise operations will you use to toggle a particular bit?
Explanation: 1 XOR 1 = 0, 0 XOR 1 = 1, note that NOT inverts all the bits, while XOR toggles only a specified bit.
13. 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
Explanation: Individual Elements are difficult to reach, and in some programming languages, they are not accessible at all. They must be compressed to byte/word array if random access is more common than sequential access. Bit arrays allow you to take advantage of bit parallelism, make the most of your data cache, and store and manipulate data for longer periods of time in a register set.
A bit array (also known as a bit map, bit collection, bit string, or bit vector) is a data structure for storing bits in a compact manner. It can be used to build a basic database schema with a collection of values. A bit array is useful for taking advantage of hardware’s bit-level parallelism to speed up operations. A standard bit array stores kw bits, where w denotes the number of bits in the storage unit, such as a byte or word, and k denotes a nonnegative integer. Internal fragmentation wastes any space if w does not divide the number of bits to be stored.