Chapter 6: Searching — Question Bank — Class 12 Computer Science

Class 12 Computer Science Chapter 6 Question Bank CBSE Board Pattern

Section A — MCQs (10 questions, 1 mark each)

Q1. Linear search compares each element of the list with the key
(a) only once
(b) one by one starting from the first element
(c) only when the list is sorted
(d) using the middle element first

Q2. Binary search can be applied only when
(a) the list contains duplicate values
(b) the list is sorted in ascending or descending order
(c) the list has an odd number of elements
(d) hashing is used

Q3. In hashing, the position of an element in the hash table is calculated using
(a) linear search
(b) a hash function
(c) binary search
(d) sequential comparison

Q4. Assertion (A): Linear search always requires n comparisons when the key is absent or present at the last position.
Reason (R): Linear search compares the key with every element of the list one by one from the beginning.
(a) Both A and R are true and R is the correct explanation of A
(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true

Q5. Assertion (A): Binary search reduces the search area by half after every unsuccessful comparison.
Reason (R): Binary search always compares the key with the middle element of the current search area.
(a) Both A and R are true and R is the correct explanation of A
(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true

Q6. The minimum number of comparisons required by linear search to find the first element of a list of n elements is
(a) n
(b) 1
(c) n–1
(d) 0

Q7. In the binary search algorithm given in the chapter, the middle index is calculated as
(a) (first + last) / 2
(b) (first + last) // 2
(c) first + last
(d) (first – last) // 2

Q8. Collision in hashing occurs when
(a) the hash table size is smaller than the list
(b) two or more elements map to the same index in the hash table
(c) the list is not sorted
(d) linear search is used

Q9. Binary search on a list of 15 elements requires only one iteration when the key is
(a) the first element
(b) the last element
(c) the middle element
(d) absent from the list

Q10. The hash function used in the chapter’s example for a hash table of size 10 is
(a) element + 10
(b) element % 10
(c) element // 10
(d) element * 10

Section B — Very Short Answer (6 questions, 2 marks each)

Q1. Define searching. What does the search result determine?
Q2. Differentiate between linear search and binary search on the basis of (i) requirement of sorted list and (ii) number of comparisons in the worst case.
Q3. What is a hash function? Give the formula of the remainder method used in the chapter.
Q4. What is collision in hashing?
Q5. Write the output of the following code fragment when key = 17 and list = [8, –4, 7, 17, 0, 2, 19].
python index = 0 while index < len(list): if list[index] == key: print("Found at", index+1) break index += 1 else: print("Not found") Q6. State two applications of binary search mentioned in the chapter.

Section C — Short Answer (5 questions, 3 marks each)

Q1. Explain with a dry run how linear search finds the key 17 in the list [8, –4, 7, 17, 0, 2, 19]. Show the value of index after each comparison.
Q2. Identify the error in the following binary search code and correct it.
python def binarySearch(lst, key): first = 0 last = len(lst) while first <= last: mid = (first + last) // 2 if lst[mid] == key: return mid elif key > lst[mid]: first = mid + 1 else: last = mid – 1 return –1 Q3. Write the output of the following code when the input list is created with elements 34, 16, 2, 93 and key = 16 (use the hashFind function given in the chapter).
Q4. Why does binary search require the list to be sorted? Explain using the dictionary example given in the chapter.
Q5. What is the maximum number of comparisons required by linear search on a list of n elements? Justify with an example from the chapter.

Section D — Long Answer (3 questions, 5 marks each)

Q1. Write a complete Python program that accepts a list of numbers and a key, performs linear search, and displays the position if found or an appropriate message if not found. Use the function structure given in Program 6-1 of the chapter.
Q2. Explain the working of binary search algorithm (Algorithm 6.2) with a trace table for the sorted list [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43] when searching for key = 2. Show values of first, last, mid and the decision in each iteration.
Q3. Describe the steps of the linear search algorithm (Algorithm 6.1) and explain the best-case and worst-case number of comparisons with suitable examples from the chapter.

Section E — Case/Source-Based (2 questions, 4 marks each)

Q1. A school maintains a sorted list of roll numbers of students who have paid the annual fee: [101, 105, 110, 115, 120, 125, 130]. The administration wants to quickly check whether a particular roll number has paid the fee.
(a) Which searching technique should be used and why? (1)
(b) If the key is 115, how many iterations will binary search take? Show the first, mid and last values in the first iteration. (1)
(c) What will be the result if the key 108 is searched using binary search? (1)
(d) State one advantage of using binary search over linear search in this scenario. (1)

Q2. A library uses a hash table of size 10 to store book IDs: 34, 16, 2, 93, 80, 77, 51 using the hash function element % 10.
(a) Draw the hash table after inserting all elements. (1)
(b) Using the hashFind logic, at which position will book ID 16 be reported? (1)
(c) What happens if another book with ID 26 is to be inserted? Name the situation. (1)
(d) How many comparisons are needed to search any key using this hashing method? (1)

▶ Answer Key Attempt all questions first,
then tap to reveal

Section A

Section B

Searching means locating a particular element (key) in a collection of elements. The result determines whether the key is present and, if present, its position.
(i) Linear search – no need of sorted list; Binary search – requires sorted list. (ii) Linear – up to n comparisons; Binary – reduces search area by half each time.
A hash function calculates the index of an element in the hash table. Formula: h(element) = element % size(hash table).
Collision occurs when two or more elements map to the same index in the hash table.
Output: Found at 4 (because linear search compares sequentially and finds 17 at index 3).
Searching a dictionary/telephone directory; finding min/max in a sorted list; indexing in databases.

Section C

index values: 0 (8≠17), 1 (–4≠17), 2 (7≠17), 3 (17==17) → found at position 4.
Error: last = len(lst) should be last = len(lst)–1. Corrected code:
python def binarySearch(lst, key): first = 0 last = len(lst) – 1 while first <= last: mid = (first + last) // 2 if lst[mid] == key: return mid elif key > lst[mid]: first = mid + 1 else: last = mid – 1 return –1
Number 16 present at 7 position (hash index 6 + 1).
Binary search uses the ordering of elements to decide whether to search in the first or second half, avoiding unnecessary comparisons (as explained with dictionary example).
Maximum n comparisons (key absent or at last position) – each element is compared one by one.

Section D

(Complete program – use exact Program 6-1 from chapter with proper indentation and input handling.)
Trace table (first=0, last=14, mid=7 → 17>2 → first=0,last=6, mid=3 → 7>2 → … finally found at position 1 after 4 iterations).
Steps of Algorithm 6.1 with best case (1 comparison) and worst case (n comparisons) examples given in chapter.

Section E

Q1. (a) Binary search (list is sorted) (b) 1 iteration, mid=3 (c) Search unsuccessful (d) Reduces comparisons by half each time.
Q2. (a) Hash table: index 0:80, 1:51, 2:2, 3:93, 4:34, 6:16, 7:77 (b) Position 7 (c) Collision (d) Only one comparison.

← Revision Summary All Chapters

All questions are answerable from the NCERT chapter text. Reviewed by GFIS faculty.