4.2 Types of Data Structures

Question 1

What is a composite data type?

Answer 1

A data type that can group together multiple values of different types under a single name.

Question 2

What are the two composite data types?

Answer 2

String, Array

Question 3

What are abstract data types?

Answer 3

A logical description of how we view the data and possible operations.

Question 4

3 Abstract data types

Answer 4

List, stack, queue

Question 5

What are elementary data types

Answer 5

basic building blocks for representing data and used to define variables and specify the kind of values they can store

Question 6

3 Elementary data types

Answer 6

Integer, real, boolean, char

Question 7

Do arrays exist in python?

Answer 7

No, have to be imported by a library

Question 8

Key differences between arrays and lists

Answer 8

Arrays: defined size, data is stored contiguously in memory
Lists: list is free to grow, values are stored in various locations in memory

Question 9

What are Contiguos elements?

Answer 9

contiguous elements are positioned in a continuous, uninterrupted sequence

Question 10

What type of data structure is a queue

Answer 10

FIFO (first in first out)

Question 11

Functions needed for a linear queue

Answer 11

Add item to the rear of the queue

Remove item from the front of the queue

Check if the queue is empty

Check if the queue is full

Question 12

What is enqueue and how is it acheived

Answer 12

Adding items to a queue
Check that queue is not full
Add to the value of the rear pointer
Then add the new item to the position indicated by the rear pointer.

Question 13

What is dequeing and how is it achieved

Answer 13

Removing an item
Return value at the front of the queue and deleter or pop
Move remaining items up the queue one by one
Decrement the rear pointer.

Question 14

Difference between circular and linear queues

Answer 14

Circular queues do not move items up when an item is dequeued.

Question 15

What is different with the items in a priority queue

Answer 15

All items have a level of priority

Question 16

What are static data structures and what is a example

Answer 16

Static data structures are fixed in size
Cannot grow, shrink, or be freed during execution
Array

Question 17

What are abstract data structures

Answer 17

can grow or shrink.
Allocates and deallocates memory from the heap

Question 18

What problem may come with abstract data structures

Answer 18

may cause overflow(exceeding maximum memory limit).

Question 19

What is a stack

Answer 19

A stack is a last in, first out abstract data type

Question 20

What is a matrix

Answer 20

An array of tables or values

Question 21

What are the six methods required in a stack

Answer 21

push(item) - adds item to the top of the stack.

pop() - removes and returns the item on top of the stack.

isFull() - checks if the stack is full

isEmpty() - checks if the stack is empty

peek() - returns the top item without removing it from the stack.

size() - return the number of items on the stack.

Question 22

What is stack overflow

Answer 22

attempting to push an item onto a stack that is full

Question 23

what is stack underflow

Answer 23

attempting to pop from a stack that is empty

Question 24

What is the call stack

Answer 24

data structure that provides the mechanism for passing parameters and return addresses to subroutines.

Question 25

What is a stack frame

Answer 25

A stack frame contains all the parameters, the return address and the local variables for a single call to a subroutine which has not yet completed.

Question 26

What is a dictionary

Answer 26

A dictionary is an abstract data type made up of associated pairs each pair has a key and a value.

Question 27

Why are hash tables used

Answer 27

a hash table will find any record in a dataset almost instantly, no matter how large the data set.

Question 28

What is a hash table

Answer 28

a data structure that creates a mapping between the keys and values.

Question 29

What causes a collision in a hash table

Answer 29

when an algorithm generates the same address for different primary keys.

Question 30

What is the fix for a collision in hash tables

Answer 30

linear probing happens, this is where the item is put in the next free slot in the table.

Question 31

What is rehashing

Answer 31

is when a new hash table is created

Question 32

What features must a circular queue have

Answer 32

They must have a front and rear pointer. They must have a size attribute.

the front pointer is simply adjusted when an item is removed from the queue - the data is not deleted.

Question 33

6 functions/features of a dictionary

Answer 33

Add
Delete
Amend
Return the value associated with a key
Return True or False depending on whether the key is in the dictionary,
Return the length of the dictionary.

Question 34

Python function to get a list of the key:value pairs of a dictionary named thisdict

Answer 34

x = thisdict.items()

Question 35

Python function to return the keys of a dictionary

Answer 35

x = thisdict.keys()

Question 36

How is a new record added to a hash table (3)

Answer 36

Hash table has an algorithm applied to the key value,

the result is the location in the table where the record should be stored.

If location is not empty the use next free location.

Question 37

What are graphs

Answer 37

Graphs are abstract data structures representing complex relationships between the items of data.

a set of vertices or nodes (the circles with the items of data) connected by edges or arcs.

Question 38

What is a weighted graph

Answer 38

a type of graph where each edge (connection between nodes) has a numerical value associated with it

Question 39

What is a vertex/node

Answer 39

vertices can represent any discrete object or entity on a graph

Question 40

what is a edge/arc

Answer 40

a relationship or connection between two vertices in a graph.

Question 41

What is the difference between directed and undirected graph

Answer 41

In an undirected graph, edges do not have a direction associated with them.

In a directed graph, each edge has a direction associated with it.

Question 42

How do adjacency matricies represent a graph

Answer 42

For an undirected graph with
n vertices, the adjacency matrix is a
n×n matrix.

Question 43

compare the use of adjacency matrices and adjacency lists to represent graphs

Answer 43

Adjacency list appropriate when there are few edges between vertices
when edges rarely change

Question 44

What is a tree

Answer 44

a connected, undirected graph with no cycles.

Question 45

What is a rooted tree

Answer 45

a tree in which onevertex has been designated as the root.

A rooted tree has parent-child relationships between nodes.

Question 46

How do we create a dictionary in python

Answer 46

my_dict = {key: value, key: value etc}

Question 47

How do we check for a value in a dictionary

Answer 47

Use the in keyword

if 2 in mydict.values():
print(True)