Topic Two- Data Structures

Question 1

What is an abstract data structure?

Answer 1

Abstract data structures don’t exist as data structures in their own right, instead they make use of other data structures such as arrays to form a new way of storing data.

Question 2

What is a Queue?

Answer 2

A queue is an abstract data structure based on an array. Just like a queue at a bus stop,the first item added to a queue is the first to be removed. Because of this, queues are referred to as “first in, first out” (or FIFO) abstract data structures.

Question 3

When is a Queue used?

Answer 3

In keyboard buffers in computers, when each keypress is pressed, it is added to the queue and then removed once the computer has processed this. This means that the keys will appear in the order they were pressed.
The breadth-first search algorithm also uses a queue.

Question 4

What is a priority Queue?

Answer 4

In a priority queue, items are assigned a priority. Items with the highest priority are dequeued before low-priority items. In the case that two or more items have the same priority, the items are removed in the usual first-in, first-out order.

Question 5

When is a priority Queue used?

Answer 5

Processors assign priority to applications - Applications currently in use by the user are prioritised over background applications, allowing for a faster user experience.

Question 6

Operation of a stack

Answer 6

A stack is a first in, last out (FILO) abstract data structure. Like queues, stacks are often based on an array but have just one pointer: a top pointer. Operations that can be performed on a stack include Push (add an item), Pop (remove the item at the top) and Peek. Peek is a function which returns the value of the item at the top of the stack without actually removing the item. The functions IsFull and IsEmpty can also be executed on stacks, just like with a queue.

Question 7

Advantages and Disadvantages of an adjacency matrix in comparison to an adjacency list.

Answer 7

matrix:
-Allows a specific edge to be queried quickly as you just have to look up the row and column
- Well suited to dense graphs where there are lots of connections so it is not memory inefficient as usually you would be wasting space if you use this as there would be many empty spaces.

list:
-Memory efficient, only stores the edges that exist in the graphs
-Slow to query as each item in the list must be searched sequentially until the desired edge is found so it is time inefficient

Question 8

What is a graph and when is it used?

Answer 8

It is used to portray complex relationships between data sets. it could be used when representing networks like transport networks, IT networks, and the Internet. It consists of nodes/vertices (the circles) and edges. the edges may have a weighting (a number) which will represent something (e.g. in a map the weightings could represent the distance between two cities.

Question 9

What is a tree?

Answer 9

A tree is a connected, undirected graph with no cycles

Question 10

What is a rooted tree?

Answer 10

It is where the tree starts from a root node (one node) and travels down. It progresses as root node, parent node, child node(nodes with a parent), and leaf node (child node with no children).

Question 11

What is a binary tree?

Answer 11

A rooted tree in which the parent node has no more than two child nodes.

Question 12

What can rooted trees be used for?

Answer 12

Can be used to represent family trees or file systems on a computers hard drive

Question 13

What are the three ways to traverse a binary tree?

Answer 13

• Pre order- Visit the root then traverse the left subtree , then the right subtree
• In-order: Traverse the left subtree, visit the root then traverse the right subtree.
  Post-order: Traverse the left subtree then the right subtree then visit the root .
  In order, pre-order and post order refer to when the root is visited

Question 14

What is a binary search tree? How is it done?

Answer 14

A BST holds items in a way that the tree can be searched quickly and easily for a particular item. Nodes are added in the order given with the first item at the root. Starting ay the root each time, the node is added to the left or the right depending on its value (if it is larger than the root- the right) Apply the same rule to the root of each subtree.

Question 15

How to do Vector Addition?

Answer 15

The vector sum (a+b) is found by relocating b so that the head touches the tail. Add vectors by adding x and y parts separately. Addition is like translation as it is the shifting of the vector.

Question 16

Scalar multiplication

Answer 16

Multiplying a vector by a scalar value changes the magnitude of the vector. Multiply x and y by the scalar value.

Question 17

Describe three ways to represent a vector

Answer 17

• A list
• a function
  -A point in space

Question 18

What is the convex combination of two vectors?

Answer 18

The space bounded by the two vectors and the red line. It is an expression of the form ( w= alpha u + beta v)
where alpha and beta must always be smaller than 0 and alpha and beta must add up to give 1.

Question 19

What is dot product?

Answer 19

A method for multiplying two vectors , written using a dot. Multiply the corresponding components of each vector.

Question 20

Uses of dot product

Answer 20

• One vector contains unit prices and another contains numbers sold then dot product gives the amount of money taken. Or it can be used to find the angle between two vectors.

Question 22

Describe the principles of operation of a hash table.

Answer 22

A hashing algorithm takes an input and returns a hash that corresponds to the location in memory where the value should be stored. The value is then stored alongside the key.