1.4.2 - data structures

Question 1

one dimensional array

Answer 1

A finite, ordered set of elements of the same type stored in contiguous memory.

Question 2

Does row or column come first in 2D array?

Answer 2

row

Question 3

tuple

Answer 3

An immutable, ordered set of values of any data type.

Question 4

immutable

Answer 4

Its elements cannot be changed and you cannot dynamically add or delete elements from a tuple.

Question 5

record

Answer 5

Contains a number of fields, each holding one item of data.

Question 6

list

Answer 6

A contiguously stored data structure consisting of a number of ​ordered ​items where the items can occur more than once​.

Question 7

list.isEmpty()

Answer 7

Test for an empty list.

Question 8

list.append(item)

Answer 8

Adds item to the end of a list.

Question 9

remove(item)

Answer 9

Removes the first occurrence of an item from a list.

Question 10

search(item)

Answer 10

Return whether an item exits in a list or not.

Question 11

list.length()

Answer 11

Returns number of items in a list.

Question 12

list.index(item)

Answer 12

Returns the position of item.

Question 13

list.insert(position, item)

Answer 13

Insert a new item at position.

Question 14

list.pop()

Answer 14

Remove and return the last item in the list.

Question 15

list.pop(position)

Answer 15

Remove and return the item at position.

Question 16

linked list

Answer 16

A dynamic data structure used to hold an ordered sequence not necessarily in contiguous data locations.

Question 17

What is each item in a linked list called?

Answer 17

a node

Question 18

2 parts of a node and their explanation

Answer 18

• data field: actual item
• pointer field: contains address of next item in sequence.

Question 19

null pointer in a linked list

Answer 19

Used to identify the last item of data.

Question 20

List 4 operations that can be carried out on queues.

Answer 20

1- enQueue()
2- deQueue()
3- isEmpty()
4- isFull()

Question 21

3 uses of queues

Answer 21

• storing print jobs until the printer is ready to print
• CPU scheduling
• breadth first traversal of a graph

Question 22

linear queues

Answer 22

When an item of data is removed from the front, all the other items move up one place. This is only suitable in a small queue, otherwise data processing time can be excessive.

Question 23

circular queues

Answer 23

When an item of data is removed from the front, the two pointers have to be updated to identify the new front and rear of the queue.

Question 24

2 uses of graphs

Answer 24

• locations on a map
• products on an e-commerce website

Question 25

2 uses of hash tables

Answer 25

- customer records - password verification

Question 26

hash table

Answer 26

A data structure that is used for very large collections of data or where quick access to data is required.

Question 27

2 approaches to dealing with collisions in a hash table

Answer 27

1- A rehashing algorithm is used to determine the next empty slot in which to store the data. 2- We can create a separate data structure such as a linked list from each storage location and store the collisions there.

Question 28

2 uses of stacks

Answer 28

1- To reverse the order of a set of data. 2- Used by processors to handle interrupts.

Question 29

Why is a hash table better suited to storing records than a linked list?

Answer 29

- A hash table enables direct access to the location of the record. - A hash table will take the same time to search through regardless of the number of records.

Question 30

describe a depth first traversal

Answer 30

- goes to left child if possible - else goes to right child - if no child, node is marked as visited and backtracks to parent node - uses a stack

Question 31

describe a breadth-first traversal

Answer 31

- Visits all nodes connected directly to the start node. - The visits all the nodes directly connected to each of those and so on. - Uses a queue.

Question 32

Explain backtracking in depth-first traversals.

Answer 32

- when a node has no children - the algorithm goes back to the previous visited node - to check if that has further children nodes to visit

Question 33

Describe the purpose of a free list pointer. (2)

Answer 33

* Points to where the next/first free node is * To add data into the linked listed.

Question 34

4 ways that a graph is different from a tree

Answer 34

* Trees have one root node // graphs do not have a root node (1) * Trees do not allow cycles/loops // graphs do allow cycles / loops (1) * Trees store hierarchy // graphs have no hierarchy (1) * Trees are always undirected // graphs can be directed (1) * Trees are always connected // graphs can be connected or disconnected (1)

Question 35

explain why a record data structure is suitable

Answer 35

* Can store multiple items of data under one identifier // so all the data about a task can be accessed using the same identifier * Can store data of different data types and this task has string, real and integers

Question 36

advantages of storing in a binary tree instead of a 1-dimensional array

Answer 36

* Searching is faster ( O(log n) ) * Inserting new tasks is faster * Do not need to sort the structure (each time a new task is inserted)