Unit 7 - Data structures Flashcards
What are the three categories of data types?
The three data types are elementary, composite and abstract.
What are the three steps required for a subroutine call? (call stack)
1) The parameters being passed are saved onto the. stack
2) Local variables are saved onto the stack.
3) The return address is saved onto the stack.
What are the five steps of a subroutine execution?
1) Stack space allocated for local variables.
2) Execution of subroutine code.
3) Return address retrieved.
4) Parameters are popped.
5) Transfer execution back to return address.
What are the three components of a stack frame?
Parameters for the subroutine at the bottom, the return address in the middle and the local variables on top.
What is the recommended load factor of a hashing table?
The load factor should be between 50% and 70% for the most efficient usage of a hashing table.
What is the general procedure for the mid-square method hashing algorithm.
1) The numeric item is squared.
2) Some of the digits from the squared result are extracted (such as the middle two).
3) Typical hash table modulus is applied to find the address.
What is the general procedure for the folding method hashing algorithm?
1) Divide the data into numerous equal-sized pieces (apart from maybe the last bit) e.g 12345 -> 12 34 5.
2) Find the sum of the pieces e.g 12+34+5 = 51
3) Perform modulus division on the output to find the address.
What is the definition of a binary tree?
A binary tree is a tree in which each node has a maximum of two children.
What is the order of left, right & node for a pre-order traversal?
Pre-order traversal is node, left then right.
What is the order of left, right & node for an in-order traversal?
In-order traversal is left, node then right.
What is the order of left, right & node for a post-order traversal?
Post-order traversal is left, right, node.
What aspect of a binary tree should be minimised to ensure efficient searching?
The height of the tree should be minimised.
What is the convex combination of two vectors?
The convex combination of vectors is the space bound by the two vectors (v and u) and a line connecting their tails. All vectors that end inside this region can be written as w = au + bv, where a, b >= 0 and a + b = 1.
