ics46 midterm

What is a collision in the context of hash functions for string keys?

when multiple keys map to the same integer value

What is the worst-case time complexity for searching a key in a chained hash table where ( n ) is the number of keys and ( m ) is the number of slots in the table?

O(n)

Which of the following data structures is often used to implement the chains in a chained hash table?

Linked list

What is a hash function for strings?

A function that maps strings to integers

Which of the following is an advantage of using a chained hash table over an array-only implementation?

No clustering of keys

SELECT ALL: Which of the following is/are disadvantage(s) of using open addressing with linear probing for a hash table compared to using a chained hash table?

degrades with primary clustering

What is special about a chained hash table?

it allows multiple keys stored in a list at each table slot

What is the average time complexity for inserting a key in a chained hash table (given n is the number of keys and m is the table size)?

( O(1) )

Which distribution of keys from a hash function will give the best performance in a hash table?

uniform

Which of the following is a requirement for a good hash function for strings?

It should always map a given string to same integer

Which of the following is an advantage of using a hash table for strings over a sequential search?

none of the other choices

What is the load factor of a chained hash table with n keys and m slots?

( n/m )

Which of the following is an advantage of using a chained hash table over an open-addressed hash table?

none of the other choices

What is the space complexity of a chained hash table with ( n ) keys and ( m ) slots?

( O(n + m) )

Which of the following can cause a chained hash table to degenerate in performance?

hash table too small for the number of keys

SELECT ALL: What is an advantage of using open addressing with linear probing for a hash table compared to using a chained hash table?

uses less memory

Why is a string hash function that multiplies all the ASCII codes together a poor choice?

common factors result in excessive collisions at non-prime table slots

Why are prime number table sizes used for hash table using open addressing?

to avoid bias when wrapping the table size with modulo

What happens when the load factor of a chained hash table increases?

The number of collisions increases

SELECT ALL: Which of the following factors can affect the quality of a hash function for keys that are character strings?

Common prefixes in the strings

Which operations best suit the deque data structure: [\text{enq()

deq()

Which describes the order items are entered and removed from a stack data structure?

Last in First Out (LIFO)

Which describes the order items are entered and removed from a queue data structure?

First In First out (FIFO)

What is the output of the following program? (stack example)

GFEDCBA

If we are using a singly linked list to implement a queue

which end should be the front?

Which operations best suit the stack data structure?

push()

Which data structure is appropriate for storing requests to be processed by a web server?

queue

Which data structure is appropriate for scheduling execution of threads in a real-time kernel?

priority queue

What is the output of the following program? (queue example)

ABCDEFG

Which operations best suit the queue data structure?

enq()

Which data structure is appropriate for implementing a browser back button?

stack

What is the output of the following program? (deque example)

GFEDCBAABCDEFG

What property of the binary search algorithm hints that its performance is ( O(lgN) )?

At each iteration of the loop

What is the time complexity of binary search using an ( O(N) ) operator[]?

( O(NlgN) )

What is the worst-case execution time of bubble sort?

( O(N^2) )

What is the worst-case execution time of binary search?

( O(lgN) )

SELECT ALL: For binary search

which computes the midpoint?

SELECT ALL: True statements about Ordered Linked Lists vs. Unordered Linked Lists

The search method in OLL can stop early

SELECT ALL: True statements about bubble sort

Short bubble is efficient for nearly sorted arrays

What situation might cause binary search to degenerate in performance?

if the keys are all the same value

SELECT ALL: Conditions for using binary search

Data sorted in ascending/descending order

Which improvement does another_bubble() function make?

decreases the window of swapping to the highest value swapped on the previous pass

SELECT ALL: Why avoid binary search on singly linked lists?

Midpoint cannot be found in constant time

Suppose ( f(N) = O(h(N)) ) and ( g(N) = O(h(N)) ). Is ( f(N) \cdot g(N) = O(h(N))? )

no

Time complexity of find() in unordered linked list?

( O(N) )

Time complexity of nested loops (i=0 to N

j=0 to N)?

Time complexity of insert() in unordered array list?

( O(1) )

Time complexity of insert() in unordered linked list?

( O(1) )

Time complexity of remove() in unordered linked list?

( O(N) )

Is ( f(N) + g(N) = O(h(N)) )?

yes

Time complexity of find() in unordered array list?

( O(N) )

Algorithm for find() in unordered linked lists?

sequential search

Where to insert for O(1) time in singly-linked list?

at the head

SELECT ALL: True statements about Unordered Linked List ADT

Requires helper class for list nodes

Best time complexity of remove() in unordered array list?

( O(1) )