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.