Data Structure

Question 1

What is an attribute?

Answer 1

-Column in a table (like fields in databases)

Question 2

How does a record store data?

Answer 2

• Stored by attribute
• Accessed by attribute
• Unordered
• Attributes and structure for record need to be set up in advance
• More friendly in use but more complex to set up
• Data can be modified added or deleted

Question 3

What is a list?

Answer 3

• Ordered set of data organised by an index
• Data accessed through index value (starting at 0)
• Requires little or no set up
• Easier to set up but less user friendly in use
• Data can be modified added or deleted

Question 4

What is a Tuple?

Answer 4

• Immutable list (cannot be changed once it is set up)

- structure exactly like a list

Question 5

What is a 1D array?

Answer 5

• very similar to list but also has defined scope (number of elements)
• Defines a set of variables under a single descriptor with an index, names(0), names(1) etc etc
• can access and manipulate the data by its indexed address

Question 6

What is a 2D array?

Answer 6

• Effectively a table
• data is referred to by its point in a table, (5,5)
• data is accessed by its point in a table
• Data can be altered

Question 7

What is a 3D array?

Answer 7

-same as 1D and 2D but also has a third coordinate (X,Y,Z)

Question 8

What is a stack?

Answer 8

• LIFO
• data added to (pushed) and removed from (popped) the top
• implemented using pointers. Pointer increases values when data added and decreases when data removed
• error message generated when stack full or empty

Question 9

What is a Queues?

Answer 9

• FIFO
• Data does not move forward in the queue but two pointers ,start and end, track the data in the structure
• If item is popped from the queue the start pointer increases in value
• If item is pushed into the queue the end pointer increase in value
• A circular queue can be formed eg; when two locations are free (5 and 1) with 5 being the max location the next items will be added into 5 then 1
• If start pointer = end pointer error message should generate.
• If start pointer = 1 and end pointer = max error message should generate

Question 10

What is a linked list?

Answer 10

• Allows us to store data on various criteria
• Does not modify data stored in memory (you can sort for certain things but it will not reposition these items in memory)

Question 11

How does a linked list function?

Answer 11

• Uses pointers to point to the next item in a certain order
• end of list when pointer = 0
• possible to have more than one pointer at the same time

Question 12

What is the free storage pointer?

Answer 12

-points to the first of these available spaces

Question 14

How do you add data to a linked list?

Answer 14

1-Store data at the location indicated by free storage pointer
2-Alter the pointer to the next free storage space
3-ID where in the list the data should be inserted
4-set the pointer for the item that preceded it to the new data item
5-Update the pointer for the new data item to that previously stored in the item that preceded it

Question 15

How do you remove items from linked lists?

Answer 15

• pointer in the preceding node is set to the value of the pointer in the item to be removed
• that value of the pointer in the item that has been removed will be added to the free pool

Question 16

How do you traverse a linked list?

Answer 16

Algorithms in photos

Question 17

What does each node on a tree have to have?

Answer 17

• sub-tree pointers that point to any subtrees for that node
• data accosted with that node
• pointers to other nodes at the same level

Question 18

What is a binary tree?

Answer 18

• specific kind of tree, each node can only have two children
• each node contains; left and right pointers and data

Question 19

What is preorder traversal of trees?

Answer 19

• start at root node
• traverse left sub-tree
• traverse right sub-tree

Question 20

What is in-order tree traversal?

Answer 20

• Traverse the left sub tree
• visit the root node of the left
• traverse right sub tree
• visit root node of the right

Question 21

What is post order tree traversal?

Answer 21

• traverse left sub tree
• traverse right sub tree
• return to root node

Question 22

Why would we use pre and post order traversal?

Answer 22

• provide a means of writing expressions without needing brackets
• postorder traversal of a tree is one method of converting between infix (human syntax) and reverse polish

Question 23

What is reverse polish? What is it good for?

Answer 23

• postorder (postfix) notation

- able to utilise the stack effectively when processing an expression

Question 24

What is the processes of reverse polish?

Answer 24

1. If the next symbol is an operand load it to the stack
2. If the next symbol is an operator, pop the last two items off the stack, perform the operation and place the result in the stack

Question 25

What is a graph?

Answer 25

• collection of data nodes and the connections between them
• nodes are referred to as vertices
• connections are edges
• edges can be directional (making a directed graph)
• if edges are bi-directional then its an undirected graph
• numbers represent measurements between then

Question 26

What are graphs used for?

Answer 26

- in real life they can map road networks - in computer they can map internet networks - you can work out the shortest distance between them or the best routes between them

Question 27

What is depth first traversal of graphs? Algorithm?

Answer 27

- algorithm in book - visit all the nodes attached to a node connected to the starting node before progressing to the second node attached to the starting node. (Working dow branches of a tree) - uses a stack

Question 28

What is breadth first traversal of graphs? Algorithm?

Answer 28

- algorithm in book - visit all the nodes attached directly to the starting node first - uses a queue

Question 29

What are hash tables used for?

Answer 29

- accessing data of a more random nature | - constructed from 2 parts; array (where data is stored) and a mapping function (the hashing function)

Question 30

What are hash functions? How would we generate one?

Answer 30

-applied to s key item or filed within the data and generates an address where the location of the data can be found -many ways to do this. One way to is to take a string as an input and return a hash value composed of the sum of the ASCII characters that compose the input string MOD the size of the table -

Question 31

What is a problem with hash functions? What is one way this can be avoided?

Answer 31

- may not always generate unique values - collisions can occur - sperate chaining = data elements are stored in linked lists rather than being stored directly within the array. When data hashes to a value, it is stored in the linked list at that index in the array. No limit on length hence collisions no longer an issue

Question 32

How do we find data in a hash table?

Answer 32

- hash the data we are searching for - go to that location in the table - look down the list originating from that location - check if data is there

Question 33

What are the main features of a hash function?

Answer 33

1. Hash value is fully determined by the data being hashed 2. Hash function uses all the input data 3. Data is uniformly distributed across the entire set of possible hash values 4. Function generates very different values for similar data