Unit 7 - Data structures Flashcards

1
Q

What are the three categories of data types?

A

The three data types are elementary, composite and abstract.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the three steps required for a subroutine call? (call stack)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the five steps of a subroutine execution?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the three components of a stack frame?

A

Parameters for the subroutine at the bottom, the return address in the middle and the local variables on top.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the recommended load factor of a hashing table?

A

The load factor should be between 50% and 70% for the most efficient usage of a hashing table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the general procedure for the mid-square method hashing algorithm.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the general procedure for the folding method hashing algorithm?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the definition of a binary tree?

A

A binary tree is a tree in which each node has a maximum of two children.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the order of left, right & node for a pre-order traversal?

A

Pre-order traversal is node, left then right.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the order of left, right & node for an in-order traversal?

A

In-order traversal is left, node then right.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the order of left, right & node for a post-order traversal?

A

Post-order traversal is left, right, node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What aspect of a binary tree should be minimised to ensure efficient searching?

A

The height of the tree should be minimised.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the convex combination of two vectors?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly