Data Structures

Question 1

Tuple properties

Answer 1

Has elements of mixed types
It is immutable
Use round brackets () to indicate a tuple

Question 2

Define dynamic

Answer 2

The number of elements can change

Question 3

Define static

Answer 3

Number of elements cannot change

Question 4

Define record

Answer 4

Composed of a fixed number of fields of different data types
Can be implemented as an object

Question 5

Arrays (size, contents, data types)

Answer 5

Size: static
Contents: mutable
Data types: single

Question 6

Tuple (size, contents, data types)

Answer 6

Size: static
Contents: immutable
Data types: mixed

Question 7

Record (size, contents, data types)

Answer 7

Size: static
Contents: mutable
Data types: mixed

Question 8

List (size, contents, data types)

Answer 8

Size: dynamic
Contents: mutable
Data types: mixed

Question 9

Stacks properties

Answer 9

LIFO- last in first out
Single pointer (points to top of stack)

Question 10

Pushing stack steps

Answer 10

1. Check if stack is full
2. If full -> report error, stop
3. Increment the stack pointer
4. Insert new data item into cell pointed to by the stack pointer
5. Stop

Question 11

Popping stack steps

Answer 11

1. Check if stack is empty
2. If empty -> report error, stop
3. Copy data item from cell pointed to by the stack pointer
4. Decrement the stack pointer
5. Return the data
6. Stop

Question 12

Peeking stack steps

Answer 12

1. Check if stack is empty
2. If empty -> report error, stop
3. Copy data item from cell pointed to by the stack pointer
4. Return the data
5. Stop

Question 13

Enqueue steps

Answer 13

1. Check if queue is full
2. If full -> report error, stop
3. Else increment rear pointer
4. Insert new item at rear pointer
5. Stop

Question 14

Dequeue steps

Answer 14

1. Check if queue is empty
2. If empty -> report error, stop
3. Else item = queue[head]
4. Increment head pointer
5. Return item
6. Stop

Question 15

Queue properties

Answer 15

FIFO- first in first out
Two pointers- head and tail pointer
Abstract data type

Question 16

Peeking queue steps

Answer 16

1. Check if queue is empty
2. If empty -> report empty, stop
3. Else
4. Copy data item from cell pointed to by the head pointer
5. Return the data item
6. Stop

Question 17

What does isEmpty() do?

Answer 17

Test for empty list

Question 18

What does append(item) do?

Answer 18

Adds a new item to the end of a list

Question 19

What does remove(item) do?

Answer 19

Remove first occurrence of an item from the list

Question 20

What does count(item) do?

Answer 20

Return the number of occurrences in the list

Question 21

What does len() do

Answer 21

Returns the number of items in the list

Question 22

What does index(item) do

Answer 22

Return the position of the item

Question 23

What does insert(pos,item) do

Answer 23

Add a new item at position pos

Question 24

What does pop() do

Answer 24

Remove and return the last item in the list

Question 25

What does pos(pos) do

Answer 25

Remove and return the item at position pos

Question 26

Define linked list

Answer 26

Dynamic abstract data structure which can be implemented as an array and pointers Composed of nodes

Question 27

A node is composed of two parts: (linked list)

Answer 27

The data (may be complex data structure) A pointer to the next node

Question 28

Linked list pointers

Answer 28

A start pointer identifies the first node in the list A next free pointer shows the index of the next free space in the array

Question 29

What is a graph

Answer 29

An abstract data structure used to represent complex relationships Made up of nodes and edges

Question 30

Define undirected graph

Answer 30

No arrows on the edges that indicate direction

Question 31

Define graph

Answer 31

A set of vertices or nodes connected by edges or arcs

Question 32

Define edges

Answer 32

May be weighted, indicating a cost of traversal

Question 33

Define undirected graph

Answer 33

All edges are bidirectional

Question 34

Define directed graph (bigraph)

Answer 34

All edges are one way

Question 35

Define adjacency matrix

Answer 35

Each row and column represents a connection

Question 36

Adjacency matrix connection

Answer 36

The item at [row, column] indicates a connection In unweighted

Question 37

Adjacency matrix pros

Answer 37

Convenient to work with, and adding edges is simple

Question 38

Adjacency matrix cons

Answer 38

A sparse graph with not many edges will leave most of the cells empty, wasting a lot of memory space

Question 39

Adjacency list pros

Answer 39

Only uses storage for the connections that exist, so it is more space- efficient A good way of representing a large, sparsely graph

Question 40

Graph applications include

Answer 40

Computer networks, with nodes representing computers and weighted edges representing bandwidth between them Page rank algorithm States in a finite state machine Social networks Web pages and links Chemistry, with nodes as atoms, edges as connections Project management, with nodes as tasks, edges representing sequence and weights, time or cost Maps, with nodes representing cities or landmarks, edges representing routes

Question 41

How can a weighted graph be represented

Answer 41

As a dictionary of dictionaries Each key in the dictionary being the node, and the value, a dictionary of adjacent edges and edge weights

Question 42

Define binary tree

Answer 42

A tree in which each node has a maximum of two children