Algorithms MCQs (Set-4)

What is the comparison sorting lower bound?

A O(1)
B Omega of log n
C Omega of n log n
D O(n squared) minimum

Why is comparison sorting lower bounded by n log n?

A Arrays cannot be indexed
B Every key must be hashed
C Input must be copied twice
D Decision tree needs many leaves

What does counting sort use to order values?

A Pairwise comparisons only
B Graph traversals
C Frequency counts
D Recursive pivots

What does radix sort process repeatedly?

A Digits or key positions
B Array halves only
C Hash buckets by collision
D Edges by weight

What assumption often supports counting sort?

A Keys are arbitrary objects
B Small integer key range
C Input is a graph
D Every value is unique

What does bucket sort distribute values into?

A Tree rotations
B Value ranges
C Graph components
D String prefixes

What is a binary search lower bound operation?

A Last array value always
B Middle value only
C First duplicate in any list
D First value at least key

What is quickselect used to find?

A Every sorted element
B Shortest graph path
C Element of a given rank
D Common string prefix

What is randomized quickselect's expected time?

A O(n)
B O(n log n)
C O(log n)
D O(n squared) always

What does KMP use to avoid repeated matching work?

A Heap ordering
B Hash load factor
C Prefix function
D Graph indegrees

What does Rabin Karp compare for pattern search?

A Tree heights
B Rolling hashes
C Graph cuts
D Sorted indices

What is a trie useful for?

A Prefix based string lookup
B Minimum spanning trees
C Numeric heap extraction
D Sorting arbitrary records

What does a perfect hash function provide for a fixed key set?

A No collisions among those keys
B Constant worst case sorting
C Negative lookup always
D A sorted array automatically

What is an approximation algorithm for?

A Only array indexing
B Exact string matching
C Reading source code
D Hard optimization problems

What does an approximation ratio compare?

A Input length to memory only
B Algorithm value to optimum
C Runtime to processor clock
D Hash keys to buckets

What is class P informally?

A Problems with no algorithms
B Only sorting problems
C Problems requiring exponential time
D Problems solvable in polynomial time

What is class NP informally?

A Problems never decidable
B Only graph problems
C Solutions verifiable in polynomial time
D Algorithms using no memory

What makes a problem NP complete?

A Only solvable by recursion
B In NP and NP hard
C Always has linear algorithm
D Cannot be verified efficiently

What does an NP hard problem require?

A Membership in P
B At least NP complete difficulty
C A sorted input
D A constant time solution

What is a polynomial time reduction used for?

A Sort one input array
B Balance a search tree
C Count hash collisions
D Relate problem difficulty

What is an online algorithm?

A Makes decisions as input arrives
B Requires all input first
C Always uses random choices
D Only sorts a static array

What is a streaming algorithm designed for?

A Process data in limited memory
B Store every input item
C Sort all possible records
D Build a full graph matrix

What does parallel speedup compare?

A Memory use to input length
B Two sorting outputs
C Serial time to parallel time
D Hash capacity to load factor

What limits ideal parallel speedup in Amdahl's law?

A Number of array indexes
B Input alphabet size
C Hash function choice
D Serial fraction of work

What does an algorithm invariant help establish?

A Correctness across steps
B A faster processor clock
C A smaller source file
D A sorted input requirement