CBSE/Karnataka PU Board PUC II Chapter 6 Searching Question Bank

What is the simplest search method?
a) Binary search
b) Hashing
c) Linear search
d) Tree search
Answer: c) Linear search
Which search method is only efficient for sorted lists?
a) Linear search
b) Binary search
c) Hashing
d) Graph search
Answer: b) Binary search
What does a hash function do?
a) Sorts the list
b) Finds maximum
c) Maps a value to an index
d) Deletes an element
Answer: c) Maps a value to an index
Linear search is also called:
a) Parallel search
b) Sequential search
c) Spiral search
d) Ordered search
Answer: b) Sequential search
In binary search, if the key is less than the middle element, where do you continue searching?
a) Second half
b) First half
c) Middle half
d) Last element
Answer: b) First half
What is a collision in hashing?
a) When an element isn't found
b) When two elements map to the same index
c) When searching fails
d) When list is unsorted
Answer: b) When two elements map to the same index
Which technique is fastest for presence check in a well-designed hash table?
a) Linear search
b) Binary search
c) Hashing
d) Tree search
Answer: c) Hashing
What is a perfect hash function?
a) No collisions
b) No sorting required
c) Always returns 0
d) Works only on sorted lists
Answer: a) No collisions
Which search keeps dividing list size by half?
a) Hashing
b) Binary search
c) Linear search
d) Tree traversal
Answer: b) Binary search
What is the worst-case time complexity of linear search?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: c) O(n)
Which of the following is NOT a search technique discussed in the chapter?
a) Linear search
b) Binary search
c) Hashing
d) Selection sort
Answer: d) Selection sort
Binary search can be applied to:
a) Unsorted lists
b) Sorted lists
c) Both
d) None
Answer: b) Sorted lists
Hash tables are used to:
a) Store data sequentially
b) Search data quickly
c) Delete data
d) Sort data
Answer: b) Search data quickly
The time complexity of binary search is:
a) O(n)
b) O(log n)
c) O(n log n)
d) O(1)
Answer: b) O(log n)
Linear search checks:
a) Only first element
b) Every element
c) Only last element
d) Only middle element
Answer: b) Every element
A good hash function distributes keys:
a) Unevenly
b) Sequentially
c) Evenly
d) Randomly
Answer: c) Evenly
The process of handling collisions is called:
a) Mapping
b) Resolving
c) Chaining
d) Addressing
Answer: c) Chaining
Which statement is true about linear search?
a) Only works for sorted lists
b) Must start at last element
c) Can work for any list
d) Requires a hash function
Answer: c) Can work for any list
The method used for searching in phonebooks is usually:
a) Linear search
b) Binary search
c) Hashing
d) Tree traversal
Answer: b) Binary search
Which one is NOT a collision resolution technique?
a) Chaining
b) Linear probing
c) Binary search
d) Double hashing
Answer: c) Binary search
Hashing provides _____ search time if no collisions.
a) Linear
b) Logarithmic
c) Constant
d) Quadratic
Answer: c) Constant
If the data is constantly changing, which search is not ideal?
a) Linear search
b) Binary search
c) Hashing
d) Sequential search
Answer: b) Binary search
The extraction method in hashing involves:
a) Squaring the key
b) Taking parts of key
c) Dividing by table size
d) Adding keys
Answer: b) Taking parts of key
Binary search splits list into:
a) Thirds
b) Halves
c) Quarters
d) Single elements
Answer: b) Halves
Hash tables need extra:
a) Space
b) Time
c) Data
d) Sorting
Answer: a) Space
Linear search works best on _____ lists.
a) Large sorted
b) Small unsorted
c) Large unsorted
d) Small sorted
Answer: b) Small unsorted
The mid-square method is used in:
a) Linear search
b) Binary search
c) Hashing
d) Sorting
Answer: c) Hashing
What does binary search do if the key is greater than middle value?
a) Search first half
b) Search second half
c) Stop search
d) Search both halves
Answer: b) Search second half
Linear search is slow for:
a) Small lists
b) Large lists
c) Sorted lists
d) Hash lists
Answer: b) Large lists
In hashing, open addressing means:
a) Keeping table open
b) Searching next available spot
c) Adding comments
d) Removing collisions
Answer: b) Searching next available spot
Binary search requires comparison of:
a) Every element
b) Middle element
c) First and last only
d) Only the hash value
Answer: b) Middle element
Linear search stops when:
a) End is reached
b) Key is found
c) List is sorted
d) Hash value is assigned
Answer: b) Key is found
Hashing is best for:
a) Searching small data sets
b) Searching large, static data sets
c) Searching sorted data sets
d) Searching dynamically changing data sets
Answer: b) Searching large, static data sets
Modulo method in hashing:
a) Divides key by table size
b) Multiplies key and table size
c) Adds key to table size
d) Subtracts table size from key
Answer: a) Divides key by table size
The number of possible comparisons in an n-element linear search is:
a) n
b) n/2
c) 2n
d) log n
Answer: a) n
Double hashing uses:
a) Two tables
b) Two hash functions
c) Two keys
d) Double memory
Answer: b) Two hash functions
Chaining in hashing involves:
a) Linked lists
b) Double tables
c) Searching all elements
d) Sorting the table
Answer: a) Linked lists
Linear search vs binary search: which is more efficient for large, sorted lists?
a) Linear search
b) Binary search
c) Both same
d) None
Answer: b) Binary search
In hashing, the position of data is determined by:
a) Data content
b) Search method
c) Hash function
d) Table size
Answer: c) Hash function
What search method is used in symbol tables in compilers?
a) Linear search
b) Binary search
c) Hashing
d) Tree search
Answer: c) Hashing
Binary search eliminates:
a) One element each time
b) Half of elements each time
c) Two elements each time
d) All elements but one
Answer: b) Half of elements each time
Linear search begins at:
a) The middle
b) The end
c) The first element
d) Random position
Answer: c) The first element
The main disadvantage of hash tables is:
a) Requires sorting
b) Collisions
c) Sequential access
d) No index
Answer: b) Collisions
Perfect hash function means:
a) Each key has unique index
b) Some keys share index
c) No mapping is done
d) All keys ignored
Answer: a) Each key has unique index
Which method is slower in practical use for very large lists?
a) Binary search
b) Hashing
c) Linear search
d) Chaining
Answer: c) Linear search
Binary search time complexity:
a) O(n)
b) O(1)
c) O(log n)
d) O(n^2)
Answer: c) O(log n)
Collisions in hashing must be:
a) Ignored
b) Resolved
c) Sorted
d) Multiplied
Answer: b) Resolved
Linear probing finds:
a) Next available slot
b) Previous slot
c) Hash value
d) The key
Answer: a) Next available slot
Extraction method uses:
a) Specific digits or letters of the key
b) Multiplication of key
c) Addition of table size
d) Random values
Answer: a) Specific digits or letters of the key
Searching is important because:
a) It wastes time
b) It retrieves data quickly for use
c) Only programmers need it
d) It removes duplicates
Answer: b) It retrieves data quickly for use

1 Mark Questions (10 Questions, With Answers):

What is the primary use of linear search?
- Answer: To find an element in an unsorted list.
What is a key in the context of searching?
- Answer: The element to be located in a collection.
How does binary search split the list?
- Answer: It divides the sorted list into halves.
What is hashing used for in searching?
- Answer: To check the presence of an element in constant time.
Name another term for linear search.
- Answer: Sequential search.
What is required for binary search to work?
- Answer: The list must be sorted.
What is a collision in hashing?
- Answer: Two distinct elements mapping to the same index.
What type of list is best suited for linear search?
- Answer: Small and unordered lists.
What is a perfect hash function?
- Answer: A hash function with no collisions.
What is the main disadvantage of linear search?
- Answer: Slow performance for large lists.

2 Marks Questions (10 Questions, With Answers):

Explain the basic working principle of a linear search.
- Answer: Linear search compares each item in the list with the key sequentially until a match is found or the list ends.
What are the three possibilities when comparing the key with the middle element in binary search?
- Answer: The key matches the middle element, is less than the middle element (search first half), or greater than the middle element (search second half).
Why is a sorted list necessary for binary search?
- Answer: Because binary search operates by comparing the key to the middle element and eliminating half the list at each step, which only works if the list is ordered.
Define a hash table.
- Answer: A data structure that continuously maps keys to unique indices (generated by a hash function) for fast searching.
What is collision resolution in hashing?
- Answer: Methods used to place multiple items mapping to the same index in a hash table.
Give a simple hash function example for numeric values.
- Answer: Modulo method: hash value = element % size_of_hash_table.
List two real-world applications of binary search.
- Answer: Searching words in a dictionary and looking up a name in an ordered database.
What happens in linear search if the key is not present in the list?
- Answer: Every element is compared and the search is declared unsuccessful after n comparisons.
How does hashing differ from linear and binary search in time complexity?
- Answer: Hashing provides constant-time search (O(1)) if there are no collisions, whereas linear search is O(n) and binary search is O(log n).
Name two methods other than modulo used in hash functions.

Answer: Mid-square method and extraction method.

3 Marks Questions (10 Questions, With Answers):

Describe the algorithm steps for linear search and mention its best and worst-case scenarios.
- Answer: Linear search starts from the first element, comparing each element to the key until found or the list ends. The best case is when the key is the first element (1 comparison), worst case is when the key is last or absent (n comparisons).
Explain the binary search algorithm and its performance for large lists.
- Answer: Binary search works by dividing the sorted list in half, comparing the key to the middle element, and narrowing the search area until found or exhausted. For very large lists, its O(log n) complexity allows fast searching, even amongst millions of items.
What are the main advantages and disadvantages of hashing in searching?
- Answer: Advantages: Constant-time search for each lookup, efficient for large datasets. Disadvantages: Needs good hash function, possible collisions requiring resolution, extra memory for hash table.
How does binary search reduce the number of elements to be checked after each comparison?
- Answer: After comparing with the middle element, it eliminates half the list (either the first or second half) based on whether the key is less than or greater than the middle.
Give an example where linear search outperforms binary search.
- Answer: For very small, unsorted lists, linear search may be faster as it does not require sorting or complex logic.
What is meant by collision in hashing? How is it generally resolved?
- Answer: Collision occurs when two keys generate the same hash value/index. It is commonly resolved by methods such as chaining (linked lists), open addressing, or double hashing.
Contrast sequential search and binary search techniques in terms of their efficiency.
- Answer: Sequential search (linear) checks every element, O(n), slow for large lists. Binary search eliminates half the list at each step, O(log n), much quicker for large, sorted lists.

Write a Python snippet for creating a simple hash table using the remainder method.

Answer:


python
table = [None]*10
values = [34, 16, 2, 93, 80, 77, 51]
for v in values:
    index = v % 10
    table[index] = v

How does the presence of multiple elements with the same hash value affect search efficiency?
- Answer: Collisions lead to extra steps for resolution, decreasing efficiency from constant time to worse depending on the method used and the number of collisions.
What factors should be considered when choosing a search technique for a given dataset?
- Answer: List size, ordering, required speed, memory availability, possibility of collisions (for hashing), and whether data is changing or static.

5 Marks Questions (10 Questions, With Answers):

Describe and compare linear search, binary search, and hashing. Include their algorithms, use cases, and time complexities.
- Answer: Linear search compares each element sequentially (O(n)), suitable for small or unsorted lists. Binary search divides a sorted list and eliminates half each time (O(log n)), suitable for large, ordered data. Hashing uses a hash function to directly map keys to indexes (O(1)), ideal for fast lookups in large data, but needs perfect hash function and collision handling.

Write Python code for binary search and explain the process with an example list.

Answer:


python
def binary_search(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]:
            last = mid - 1
        else:
            first = mid + 1
    return -1
# Example:
# lst = [1, 2, 4, 8, 16, 32, 64]
# key = 16 -> returns 4

The code divides and eliminates half of the search range each time.

Explain different ways in which collisions can be resolved in hashing. Give examples.
- Answer: Main methods include chaining (using linked lists at each index to store multiple items), linear probing (searching next available slot), double hashing (using a second hash function). For example, with chaining, if indices collide, both values are appended at the index list.
What are the advantages and disadvantages of using binary search over linear search?
- Answer: Advantages: Much faster for large, sorted lists (O(log n)); less comparisons required. Disadvantages: Requires list to be sorted; more complex implementation; not ideal for small or frequently changed lists.
Give a detailed example of linear search and binary search for the same list. Show how many comparisons or iterations occur.
- Answer: For the list , searching for 18—Linear search checks each one from first (6 comparisons); binary search finds it in log2(7) ≈ 3 iterations.
Discuss the real-world applications of different search techniques: where would you use linear search, binary search, and hashing?
- Answer: Linear search: small or unsorted datasets, such as searching a small set of files; binary search: ordered collections, e.g., dictionary lookup, phonebook; hashing: quick access for large databases, symbol table in compilers.
What happens if a hash function is not perfect? How does this affect search results and efficiency?
- Answer: Imperfect hash functions cause collisions, needing extra time for collision resolution and possible degradation of performance from O(1) to O(n) if collisions are frequent.
Why is it important to have a good hash function, and what are some properties of an ideal hash function?
- Answer: A good hash function distributes values evenly and minimizes collisions, ensuring efficient searching. Properties: uniform distribution, quick computation, and minimal collisions.
Provide and explain an application where modified binary search is used.
- Answer: Modified binary search is used in database indexing, finding the first or last occurrence of a value, searching ranges, or in router routing tables for efficient decision-making.
Compare and contrast real efficiency in practice—if you must search for an element in a database with millions of entries, which method would be most efficient and why?

Answer: Hashing is most efficient for direct lookups (O(1)), provided a good hash function and low collision rate. Binary search (O(log n)) is highly efficient for sorted data but slower than hashing for single lookups. Linear search is impractical for large datasets due to O(n) time.

[NOTE: Kindly cross check answers once from other source also, Quantity and Quality of answers also kindly check before use, specially 5 marks answers are not sufficient kindly add from your side, this gives quick review]

Habbit2Code

Search This Blog

CBSE/Karnataka PU Board PUC II Chapter 6 Searching Question Bank

Comments

Post a Comment