Karteikarten
Unit 7
Karten in diesem Stapel (31)
- 1Composite data typeString
Array - 2Abstract data typeList
Stack
Queue
A logical description of how we view the data and possible operations - 3EncapsulationA type of information hiding
- 4Queue functionsenQueueI(item) - adds item to rear
deQueue - remove and return item from front
isEmpty - indicates if queue is empty
isFull - indicates if queue is full - 5Circular queueReuses the empty spaces at the front of the queue
- 6Priority queueItems have a 'priority' associated, they will 'jump' the queue depending on their priority
- 7Static data structureIs fixed in size, can't grow or shrink
An array is static - 8Dynamic data structuresAllocates and de-allocates memory from the heap
Excessive allocation without de--allocation will cause overflow - 9Operations of listsisEmpty() - Tests for empty list
append(item) - Adds 'item' to the list
remove(item) -Remove 1st 'item' from list
count(item) - Returns no. of 'item' in list
len(list) - Returns length of the list
index(item) - Returns position of 'item'
insert(item,pos) - Adds 'item' at 'pos'
pop() - Removes, returns last item in list
pop(pos) - Removes, returns item at 'pos' - 10Operations of stackspush(item) - adds item to the top
pop() - removes and returns item on top
isFull() - checks if stack is full
isEmpty() - checks if stack is empty
peek() - return top item without removing it
size() - returns no. of items in stack - 11OverflowAttempting to push onto a stack that's full
- 12UnderflowAttempting to pop from a stack that's empty
- 13The call stack- Is a system level data structure
- Provides mechanism for passing parameters and return addresses
- The use of the call stack is hidden from the programmer - 14Stack frameContains all parameters, return addresses and local variables for a subroutine call
- 15Linear searchIsn't effective, is the only option if data is in random order
- 16Binary searchIs efficient if data is in order
- 17Hashing algorithmCalculates a unique address for a piece of data, from the data itself
- 18Hash tablesAre used to store the hashed data
- 19How is a piece of data hashed?The 'key' is provided, the each piece of data is 'modded' by the key to produce the address
- 20What is a collision?When the desired address is already full.
The data is then moved to the next available address - 21What is the ideal load factor of the data needed to be hashed?50 - 70% of the hash table size?
- 22Mid-square hashing method- Square the data
- Extract some portion of the result
-Mod to get the address - 23Folding hashing method- Divide the data into 2 digit numbers
- Add them up
- Mod to get the address - 24Extra hashing information- Alphanumeric data is converted via ASCII before hashing
- Deleted items must be replaced with a dummy, e.g. 'deleted'
- Hashing is used to calculate where dictionary items should be stored/where they are stored - 25DictionaryUsed to store items, allowing the to be looked up
- 26GraphAn abstract data structure representing complex relationships
- 27Graphs can be implemented using:- Adjacency matrix
- Adjacency list - 28TreeA connected, undirected graph with no cycles
- 29Binary treeA rooted tree in which each node has a maximum of 2 children
- 30Vectors can be represented as:- A list of numbers
- A function
- A geometric point in space - 31Vector notationR^2 is a 2-vector over R, where R is the set of Real numbers
Informationen
- Beschreibung
- Karteikarten am Unit 7, erstellt von . . am 28/05/2019.
- Erstellt von
- . .
- Aufrufe
- 0
- Bewertung