Data structures: lists, arrays and tables

Apréndelo jugando

Responde estas preguntas para ganar energía, luego pesca y explora. Sin cuenta.

Para educadores: diapositivas de la lección, apuntes de repaso listos para usar sobre Data structures: lists, arrays and tables (KS3 Computing, Computer Science) — úsalos en tu lección, o presenta el tema como una actividad interactiva de clase que tus aprendices juegan como un juego en vivo.

Apuntes de la lección

What are Data Structures?

A data structure is a way of organising and storing data so it can be used efficiently.
Common data structures include lists, arrays, and tables.
Choosing the right structure makes programs simpler and faster.
In programming, a list is a collection of items in a particular order.
An array is a type of list where all elements are of the same data type and stored in contiguous memory.
A table (or two-dimensional array) stores data in rows and columns, like a spreadsheet.

An array is an ordered collection of same-type values stored under one name and reached by index.

Lists and Arrays

A list is a mutable, linear collection of elements.
An array is a collection of elements of the same type, each identified by an index.
Arrays are stored in memory so that the address of each element can be calculated from its index.
For example, an array of 10 integers starting at address 2000 uses addresses 2000, 2004, 2008, ... (each integer takes 4 bytes).
The address of element with index i is: base address + (i × size of each element).
The first element's address is called the base address.

Indexing

Indexing is how you access individual elements in a list or array.
Most programming languages use zero-based indexing: the first element is at index 0.
Some languages (like Lua) use one-based indexing: the first element is at index 1.
The index is usually a non-negative integer.
Using the index, you can read or change the value at that position.

Adding and Removing Items

Lists are mutable, meaning you can add, remove, or change items.
To add an item, you can use methods like `append()` (add to end) or `insert()` (add at a specific index).
To remove an item, you can use `remove()` (by value) or `pop()` (by index).
In arrays, the size is often fixed, but in dynamic lists (like Python lists) the size can change.
When you add or remove items, the indices of later items may change.

Iterating Over a List

Iterating means going through each element of a list one by one.
You can use a for loop to iterate over a list.
Example in Python: `for item in my_list:` processes each item.
You can also use a loop with an index: `for i in range(len(my_list)):`.
Iteration is useful for calculating totals, finding items, or transforming data.

Traversal visits each indexed cell in turn, from the first index to the last.

Two-Dimensional Arrays (Tables)

A two-dimensional array (or table) is like a grid with rows and columns.
It is sometimes called a matrix.
You access an element using two indices: `table[row][column]`.
Tables are useful for representing data like a spreadsheet, a chessboard, or a timetable.
You can iterate over a table using nested loops (one for rows, one for columns).

Choosing the Right Structure

Use a list/array when you have a sequence of items that you need to access by position.
Use a table when your data naturally has two dimensions, like rows and columns.
Consider whether you need to add/remove items frequently; lists are flexible, arrays may be fixed-size.
Think about the data type: arrays usually require all elements to be the same type.
Choosing the right structure makes your code clearer and more efficient.

Real-World Applications

Arrays are used to implement vectors and matrices in mathematics.
Databases often store records in arrays.
Arrays are used to implement other data structures like stacks, queues, and strings.
Lookup tables are arrays used to quickly find values.
Almost every program uses arrays in some way.

Diapositivas

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

REGÍSTRATE — GRATIS INICIAR SESIÓN

Preguntas de práctica

Vista previa gratis — 8 de 60 preguntas. Regístrate para verlas todas.

1.What is an array in computer science?
Easy
- AA data structure consisting of a collection of elements, each identified by at least one index
- BA type of computer memory that stores programs
- CA programming language used for web development
- DA single variable that can hold only one value
2.In zero-based indexing, the first element of an array has index 1.
Easy
True or false?
3.Which of the following is a correct way to describe a two-dimensional array?
Easy
- AA collection of elements arranged in rows and columns, like a grid
- BA collection of elements all stored in a single row
- CA list that can only store numbers
- DA data structure that cannot be indexed
4.Which of the following are common uses of arrays? (Select all that apply)
Easy
- AImplementing mathematical vectors and matrices
- BStoring a single value in a program
- CImplementing other data structures such as lists and strings
- DReplacing all conditional statements in a program
- ECreating lookup tables
5.Which of the following is a reason why arrays are efficient for computers?
Easy
- AThey can store elements of different sizes
- BThe position of each element can be computed from its index using a mathematical formula
- CThey do not require memory allocation
- DThey can only be accessed sequentially
6.Match each indexing convention to its description.
Easy
- Zero-based indexing
- One-based indexing
- Base address
- First element has index 0
- First element has index 1
- Address of the first element
7.Arrange the following steps to compute the address of an array element using the formula: address = base + (index × size).
Medium
- Multiply the index by the size of each element
- Add the result to the base address
- Identify the base address and the size of each element
8.Arrays are used to implement many other data structures such as lists, stacks, and queues.
Easy
True or false?

Más preguntas

9.Match each type of data structure to its most common use.
Easy
- Array
- List
- Table
- Storing a fixed collection of same-type items
- Storing an ordered collection that can grow or shrink
- Storing data in rows and columns
10.Arrange the steps to add an item to the end of a list in a typical high-level language (e.g., Python).
Medium
- Check if the list has capacity
- Create a new larger array
- Copy existing elements
- Insert the new item at the end
11.Which of the following are valid ways to iterate over a list in Python? (Select all that apply)
Medium
- Afor i in range(len(my_list)):
- Bfor item in my_list:
- Cfor i in my_list:
- Dwhile i < len(my_list):
- Efor i in range(my_list):
12.In a two-dimensional array, the first index typically represents the row and the second index represents the column.
Easy
True or false?
13.Which of the following is a common reason to use a table (two-dimensional array) rather than a list?
Medium
- ATo store data that naturally has rows and columns, such as a spreadsheet.
- BTo store a collection of items of different data types.
- CTo allow the collection to grow and shrink easily.
- DTo store items in a random order without any structure.
14.In Python, which of the following correctly removes the last item from a list named 'scores'?
Medium
- Ascores.pop()
- Bscores.remove()
- Cscores.delete()
- Dscores.clear()
15.Which of the following are true about arrays? (Select all that apply)
Medium
- AArrays are often used to implement other data structures like stacks and queues.
- BArrays can store elements of different data types.
- CArrays are stored in contiguous memory locations.
- DThe index of an array element can be computed at runtime.
- EArrays are always one-dimensional.
16.In a 2D array, the elements are stored in memory in a single continuous block, either row by row or column by column.
Easy
True or false?
17.A program stores the daily temperature readings for a week in an array called `temps`. The reading for Monday is stored at index 0. Which index would you use to access the temperature for Friday?
Easy
- A4
- B5
- C6
- D3
18.Which of the following are true about a two-dimensional array (table)? (Select all that apply)
Medium
- AIt can be thought of as a matrix.
- BIt is always stored in memory as a single continuous block.
- CIt can only store numbers.
- DThe first index typically represents the row.
19.In a one-based indexing system, the first element of an array has index 1.
Easy
True or false?
20.A table (2D array) has 3 rows and 4 columns. Each element is a 2-byte integer. The table is stored starting at memory address 1000. What is the memory address of the element at row 1, column 2 (using zero-based indexing)?
Medium
- A1012
- B1008
- C1016
- D1010
21.A program uses an array to store the names of students in a class. Which of the following is the most appropriate reason to use an array rather than separate variables?
Hard
- ATo make the program run faster
- BTo allow a single loop to process all names
- CTo reduce the amount of memory used
- DTo make the names easier to type
22.A school records the marks of 30 students in 5 subjects in a 2D array called `marks`. The array is indexed as `marks[student][subject]` with zero-based indexing. Which expression gives the total mark for the student at index 2?
Challenge
- Asum(marks[2])
- Bsum(marks[:][2])
- Csum(marks[2][:])
- Dsum(marks[2][0:5])
23.A student writes a program to store the daily maximum temperature for each day of a week (Monday to Sunday). They decide to use an array. Which of the following is the most appropriate reason to use an array rather than seven separate variables?
Medium
- ATo allow the program to process all seven values using a loop.
- BTo reduce the memory used by the program.
- CTo make the program run faster.
- DTo store values of different data types together.
24.In a one-dimensional array with zero-based indexing, the last element has an index equal to the length of the array.
Easy
True or false?
25.A program stores the heights of 30 students in an array called `heights`. The first student's height is at index 0. Which loop correctly calculates the total height of all students?
Medium
- Atotal = 0 for i in range(1, 31): total = total + heights[i]
- Btotal = 0 for i in range(0, 30): total = total + heights[i]
- Ctotal = 0 for i in range(0, 31): total = total + heights[i]
- Dtotal = 0 for i in range(1, 30): total = total + heights[i]
26.An array of 6 integers is stored starting at memory address 3000. Each integer occupies 4 bytes. Using the formula address = base + (index × size), what is the memory address of the element with index 4?
Medium
- A3016
- B3020
- C3024
- D3012
27.Which of the following are true about two-dimensional arrays (tables)? (Select all that apply)
Medium
- AThey can be used to represent a matrix.
- BThey are always stored in column-major order.
- CThey have rows and columns.
- DThey can only store numbers.
- EThe elements are accessed using two indices.
28.In Python, the `append` method adds an item to the beginning of a list.
Medium
True or false?
29.Match each data structure to its most common use.
Medium
- 1D array
- 2D array (table)
- List
- Storing a sequence of temperatures
- Storing a game board (e.g., chess)
- Storing a dynamic collection of items
30.A program uses a 2D array to store the scores of 10 players across 5 rounds. The array is indexed as `scores[player][round]` with zero-based indexing. Which of the following correctly calculates the average score for player 3?
Hard
- Asum(scores[3]) / 5
- Bsum(scores[3]) / 10
- Csum(scores[5]) / 3
- Dsum(scores[3][:]) / 5
31.Arrange the steps to compute the address of an element in a one-dimensional array using the formula.
Medium
- Multiply the index by the size of each element
- Add the result to the base address
- Identify the base address of the array
- Determine the index of the element
32.An array is a data structure that can hold elements of different data types at the same time.
Easy
True or false?
33.The memory address of an element in an array can be calculated from its index using a mathematical formula.
Easy
True or false?
34.Which of the following is the correct definition of a one-dimensional array?
Easy
- AA collection of elements all of the same data type, each identified by one index
- BA collection of elements that can be of different data types, each identified by one index
- CA collection of elements all of the same data type, each identified by two indices
- DA collection of elements stored in a non-linear structure such as a tree
35.Which of the following is the most appropriate term for an array that has two indices, typically representing rows and columns?
Easy
- ATwo-dimensional array
- BOne-dimensional array
- CVector
- DLinked list
36.Which of the following statements about arrays is TRUE?
Easy
- AThe set of valid index tuples is always fixed while the array is in use.
- BArrays are often used to implement other data structures such as lists and strings.
- CIn most programming languages, arrays can store elements of different data types.
- DThe memory address of an array element cannot be calculated from its index.
37.Match each indexing convention to its correct description.
Easy
- Zero-based indexing
- One-based indexing
- Index
- First element has index 0
- First element has index 1
- A non-negative scalar integer used to select an element
38.Match each term related to arrays to its correct definition.
Easy
- Base address
- Index
- Array
- Table
- The memory address of the first element of an array
- A number used to identify an element in an array
- A collection of elements of the same type, each identified by an index
- A two-dimensional array often used for storing data in rows and columns
39.Arrange the following steps in the correct order to compute the memory address of an element in a one-dimensional array using the formula address = base + (index × size).
Medium
- Identify the base address of the array
- Multiply the index by the size of each element
- Add the result to the base address
- Determine the index of the element
40.Which of the following are valid ways to access elements in a two-dimensional array (table)? (Select all that apply)
Medium
- AUsing two indices, such as array[row][column]
- BUsing a single index that combines row and column
- CUsing the element's memory address directly
- DUsing a loop to iterate over each row and column
41.Fill in the blank.
Easy
The memory address of the first element of an array is called the ____ address.
42.What is the term used in computing to refer to an array that is mathematically equivalent to a tuple?
Easy
43.An array of 10 integers is stored starting at memory address 2000. Each integer takes 4 bytes. What is the memory address of the element with index 5?
Medium
44.Complete the sentence with the correct term.
Easy
In computing, a ____ is a data structure that stores a collection of elements of the same type in a contiguous block of memory, and each element can be accessed by its ____.
45.A table (2D array) has 3 rows and 4 columns. Each element is a 2-byte integer. The table is stored starting at memory address 1000. What is the memory address of the element in row 2, column 3? (Assume row-major order and zero-based indexing.)
Medium
46.What is the main difference between a list and an array in terms of size?
Medium
47.An array of 8 integers is stored starting at memory address 3000. Each integer takes 4 bytes. What is the memory address of the element with index 3?
Medium
48.An array of 10 integers is stored starting at memory address 1000. Each integer takes 4 bytes. What is the memory address of the element with index 3?
Easy
49.What is the name given to a two-dimensional array that represents a mathematical concept of rows and columns?
Medium
50.A 2D array has 4 rows and 5 columns, stored in row-major order. Each element is a 2-byte integer. The array starts at memory address 2000. What is the memory address of the element at row 2, column 3 (using zero-based indexing)?
Medium
51.What is the name for the process of iterating over each element in a list or array?
Medium
52.Give one reason why arrays are considered efficient for computers.
Medium
53.Explain why the elements of an array are required to have the same size and data representation.
Medium
54.Explain why the elements of an array are required to have the same size and data representation. Refer to how arrays are stored in memory.
Hard
55.Describe how a two-dimensional array (table) is stored in memory in row-major order, and explain how the address of an element is calculated.
Hard
56.An array of 10 integers is stored starting at memory address 2000. Each integer takes 4 bytes. What is the memory address of the element with index 5?
Medium
- A2222
- B2020
- C2424
- D1818
57.A table (2D array) has 3 rows and 4 columns. Each element is a 2-byte integer. The table is stored starting at memory address 1000. What is the memory address of the element in row 2, column 3? (Assume row-major order and zero-based indexing.)
Medium
- A1124
- B1022
- C920
- D1226
58.An array of 8 integers is stored starting at memory address 3000. Each integer takes 4 bytes. What is the memory address of the element with index 3?
Medium
- A3313
- B3614
- C2711
- D3012
59.An array of 10 integers is stored starting at memory address 1000. Each integer takes 4 bytes. What is the memory address of the element with index 3?
Easy
- A1113 bytes
- B1214 bytes
- C1012 bytes
- D911 bytes
60.A 2D array has 4 rows and 5 columns, stored in row-major order. Each element is a 2-byte integer. The array starts at memory address 2000. What is the memory address of the element at row 2, column 3 (using zero-based indexing)?
Medium
- A2432 bytes
- B1823 bytes
- C2026 bytes
- D2229 bytes

Apuntes de repaso

## Data Structures: Lists, Arrays and Tables ### What is an Array? An **array** is a data structure that stores a collection of elements (values or variables) of the **same data type** in a **linear** order. Each element is identified by an **index** (also called a subscript). Arrays are **mutable** (can be changed) and are one of the oldest and most important data structures. ### Indexing - **Zero-based indexing**: The first element is at index 0. (Common in many languages like Python, C, Java) - **One-based indexing**: The first element is at index 1. (Used in some languages like Fortran, MATLAB) ### Key Operations on Lists/Arrays - **Access**: Get an element using its index, e.g., `myList[2]`. - **Add**: Insert an element at a specific position or append to the end. - **Remove**: Delete an element by index or value. - **Iterate**: Loop through all elements, e.g., `for item in myList:`. ### Two-Dimensional Arrays (Tables) A **two-dimensional array** (or **matrix**) is like a grid with rows and columns. It is often used to represent tables. For example, a table of student scores: ``` Scores = [ [85, 90, 78], [92, 88, 95] ] ``` Here, `Scores[0][1]` gives the element in the first row, second column (90). ### Choosing the Right Structure - Use a **list/array** when you have a collection of similar items that need to be accessed by index. - Use a **table** (2D array) when data naturally fits in rows and columns, like a spreadsheet. - Consider the size and whether it changes: arrays have fixed size in some languages, but lists in Python are dynamic. ### Why Arrays are Useful - **Fast access**: Elements can be accessed directly using their index. - **Efficient iteration**: A single loop can process all elements. - **Implement other structures**: Arrays are used to build lists, stacks, queues, and more. ### Memory and Addressing (Optional) In memory, an array is stored contiguously. The address of an element is computed using a formula: `base_address + (index × element_size)`. For example, an array of 4-byte integers starting at address 2000 has element `i` at `2000 + (i × 4)`. ### Key Takeaways - Arrays store elements of the same type. - Indexing starts at 0 or 1 depending on the language. - Lists are dynamic arrays in Python. - Tables are 2D arrays. - Choose the structure that fits the data.

Array: A data structure consisting of a collection of elements (values or variables), of the same memory size, each identified by at least one array index or key.
Index: A non-negative scalar integer used to select an individual element in an array; also called a subscript.
Zero-based indexing: Indexing where the first element of the array is indexed by subscript 0.
One-based indexing: Indexing where the first element of the array is indexed by subscript 1.
Two-dimensional array: An array that represents a grid of elements arranged in rows and columns, also called a matrix.
Table: A data structure often implemented as an array, especially a two-dimensional array, used to store rectangular data.
List: A data structure that can be implemented using arrays; in programming, often a dynamic array that can grow or shrink.
Base address: The memory address of the first element of an array; also called first address or foundation address.

Tarjetas

What is an array in computer science?

An array is a data structure consisting of a collection of elements (values or variables) of the same data type, each identified by at least one index or key. It is a mutable, linear collection.

What is the simplest type of array?

The simplest type is a linear array, also called a one-dimensional array.

What is an index in an array?

An index (also called a subscript) is a non-negative scalar integer that identifies the position of an element in an array. It maps the array value to a stored object.

What is zero-based indexing?

Zero-based indexing means the first element of an array is indexed by subscript 0.

What is one-based indexing?

One-based indexing means the first element of an array is indexed by subscript 1.

In an array, what is the base address?

The base address (also called first address or foundation address) is the memory address of the first element of the array.

How is the memory address of an element computed in a one-dimensional array?

The address is computed using a formula: base address + (index × size of each element). For example, for an array of 4-byte integers starting at address 2000, element i is at 2000 + (i × 4).

What is a two-dimensional array also called?

A two-dimensional array is sometimes called a matrix, because it can represent a mathematical matrix as a two-dimensional grid.

What is a table in the context of arrays?

A table is often implemented as an array, especially a lookup table. The word 'table' is sometimes used as a synonym for array.

Why are arrays useful for processing many elements?

Arrays allow element indices to be computed at run time, so a single iterative statement (like a loop) can process arbitrarily many elements.

What requirement do elements of an array have?

Elements of an array must have the same size and use the same data representation.

What is an array data type?

An array data type is a kind of data type provided by most high-level programming languages that consists of a collection of values or variables that can be selected by one or more indices computed at run-time.

Name some other data structures that arrays can be used to implement.

Arrays can implement lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.

What is a control table?

A control table is an array used to determine partial or complete control flow in a program, as a compact alternative to multiple IF statements. It is used with an interpreter that changes control flow based on array values.

What is a list in programming?

A list is a data structure that can hold an ordered collection of items. In many languages, lists are dynamic and can grow or shrink, and are often implemented using arrays.

How do you add an item to a list?

You add an item to a list using an operation like 'append' or 'insert', which adds the item at the end or at a specified position.

How do you remove an item from a list?

You remove an item using an operation like 'remove' or 'delete', specifying the item or its index.

What does it mean to iterate over a list?

Iterating over a list means to access each element in sequence, often using a loop, to perform some operation on each item.

What is a two-dimensional table?

A two-dimensional table is a data structure with rows and columns, often represented as a two-dimensional array or a list of lists.

How do you access an element in a two-dimensional array?

You access an element using two indices: one for the row and one for the column, like array[row][column].

When choosing a data structure, what should you consider?

You should consider the type of data and the operations you need: whether the data is ordered, whether you need fast access by index, and whether the size changes.

What is the difference between a list and an array?

In many contexts, a list is dynamic and can change size, while an array has a fixed size. However, in some languages, lists are implemented using arrays.

What is a lookup table?

A lookup table is an array (or table) used to store precomputed values for quick retrieval, often to replace complex calculations.

What is the purpose of using a data structure like a list or array?

Data structures allow you to store and organize multiple values efficiently, making it easier to access, modify, and process data in programs.

Unlock all 60 questions, flashcards & more

Crea una cuenta gratis para ver todas las preguntas, las diapositivas, las tarjetas y los apuntes de repaso de este tema.

REGÍSTRATE — GRATIS INICIAR SESIÓN

Exámenes anteriores

La práctica con exámenes anteriores de este tema llegará pronto.

Próximamente