Data Structures - Test 2 Review Flashcards
cout «_space;value int sum = 0; if (count < 20) { total = total + current; area = (1.0 / 2.0) * base * height;
examples of O(1)
“for (int j = 1; j<= n; j++) { cout «_space;"”this prints n times”” «_space;endl; }”
example of O(n)
“for (int j = 1; j<= n; j++) { for (int k = 1; k<= n; k++) { cout «_space;"”this prints n^2 times”” «_space;endl; } }”
example of O(n^2)
“for (int j = 1; j<= sqrt(n); j++) { cout «_space;"”this prints sqrt(n) times”” «_space;endl; }”
example of O(n^1/2)
“for (int j = n; j> 0; j /= 2) { cout «_space;"”this prints lg n times”” «_space;endl; }”
example of O(lg n)
A hash table is…
a fixed size list of records organized to a unique key
The key is…
usually one of the data fields in the record
Each cell in the hash table is called a…
bucket
Buckets may be empty - wasting memory
true
The hash function maps the record’s key to an integer called the…
hash index(this indicates into which bucket to put the record)
If every key maps to a unique hash index, then the hash table operations are fast
Search, Insert, and Delete are all O(1)
A collision occurs when…
two keys map to the same hash index
One way to solve collisions?
Chaining
Let k = max # of records stored in one bucket. If using vectors then: Search and Delete are… Insert is…
O(k)O(1)
Another category of handling collisions is…
Open addressing
Open addressing includes…
Linear probingQuadratic probingDouble hashing
Double hashing uses…
a secondary hash function d(k) and handles collisions by placing an item in the first available cell of the seriesh(k,i) = (h(k) + i*d(k)) mod Nfor i = 0, 1, …, N - 1
The secondary hash function d(k) cannot have…
zero values
The table size N must be a…
prime to allow probing of all the cells
Common choice of compression map for the secondary hash function:…
d(k) = q - (k mod q)where:q < Nq is a prime
The possible values for d(k) are…
1, 2, …, q
26 mod 11
4
21 mod 11
10
21 mod 5
1
Stack operations… Last In, First Out
push, pop, topthese are all O(1)
stackADT
+ push(Type Item) : void+ pop() : void+ top() : Type+ size() : int+ empty() : bool
Expression: 6 3 + 2 * = Push 6 into stack
|| || || 6 |——-
Expression: 6 3 + 2 * = Push 3 into stack
|| || 3 || 6 |——-
Expression: 6 3 + 2 * = + Pop stack twice op2 = 3; op1 = 6;
|| || || |——-
Expression: 6 3 + 2 * = op1 + op2 = 9 Push 9 into stack
|| || || 9 |——-
Expression: 6 3 + 2 * = Push 2 into stack
|| || 2 || 9 |——-
Expression: 6 3 + 2 * = * Pop stack twice op2 = 2; op1 = 9;
|| || || |——-
Expression: 6 3 + 2 * = op1 + op2 = 18 Push 18 into stack
|| || ||18|——-
Expression: 6 3 + 2 * = = Pop stack and print: 18
|| || || |——-
Queue operations… First In, First Out
enqueue, dequeue, frontthese are all O(1)
queueADT
+ enqueue(Type Item)+ dequeue()+ front() :Type+ rear() :Type
A technique in which one system models the behavior of another system is called…
simulation
A ________ _____ is a restricted form of a list.
priority queue
In a priority queue…
items are arranged according to their priorities (or keys)the keys may or may not be uniqueunlike a queue which is FIFO
A priority queue removes items based on…
priority
Each item in a PQ is a composition of 2 objects:
- the key (priority)- the datathis gives us a pair (key, data)which we can use to implement using a linked list
Two types of PQ’s
min PQmax PQ
Min PQ
minimum key value is the highest priority
Max PQ
maximum key value is the highest priority
In either type of PQ, it must hold a…
Total Order Relation(reflexive, antisymmetric, transitive)
Implementation: Priority Queue Unsorted list implementation: store the items of the priority queue in a list-based sequence, in arbitrary order
4, 5, 2, 3, 1
Implementation: Priority Queue Unsorted list implementation Performance: _______ takes O(1) time since we can insert the item at the beginning or end of the sequence _______, _______ and _______ take O(n) time since we have to traverse the entire sequence to find the smallest key
insertItemremoveItem, min/maxKeymin/maxElement
Implementation: Priority Queue Sorted list implementation: store the items of the priority queue in a sequence, sorted by key
1, 2, 3, 4, 5
Implementation: Priority Queue Sorted list implementation Performance: _______ takes O(n) time since we have to find the place where to insert the item _______, _______, and _______ take O(1) time since the smallest key is at the beginning of the sequence
insertItemremoveItem, min/maxKeymin/maxElement
Queues vs Priority Queues
Queue: structure ensures items processed in the order receivedPriority queues: customers (jobs) with higher priority pushed to the front of the queue
Priority Queues are useful for…
sorting
Sorting using a priority queue: Given a sequence of N items, a PQ can be used to sort the sequence:
Step 1: Insert N items into the PQ via insertItem (key, data)Step 2: Remove the items by calling removeItem() N timesthe first removes the largest item, the second call the second largest, …, the last removes the smallest item
8 mod 6
2
6 mod 6
0
12 mod 6
0
10 mod 6
4
20 mod 6
2
16 mod 6
4
What’s the load factor?
(num items) / (table size)
Main deque operation - insertFirst(object o):
inserts element o at the beginning of the deque
Main deque operation insertLast(object o):
inserts element o at the end of the deque
Main deque operation removeFirst():
removes and returns the element at the front of the deque
Main deque operation removeLast():
removes and returns the element at the end of the deque
Main deque operation first():
returns the element at the front without removing it
Main deque operation last():
returns the element at the end without removing it
Main deque operation size():
returns the number of elements stored
Main deque operation isEmpty():
returns a Boolean value indicating whether no elements are stored
Doubly linked list operation insertFront(e):
inserts an element on the front of the list
Doubly linked list operation removeFront():
returns and removes the element at the front of the list
Doubly linked list operation insertBack(e):
inserts an element on the back of the list
Doubly linked list operation removeBack():
returns and removes the element at the end of the list
7 mod 7
0
14 mod 7
0
