CAIE AS and A Level CS revision - Unit 13 (2nd)
跳到导航
跳到搜索
【点此返回复习要点目录】
如遇到公式加载异常，请刷新页面！
Unit 13 Data Representation 数据表示
13.1 User-defined data types 用户定义的数据类型
- 大纲要求
13.1.1 Show understanding of why user-defined types are necessary 理解为什么用户定义类型是必要的
- user-defined data type：用户定义数据类型，指由程序员定义的数据类型，并非程序中自带的built-in data type内置数据类型。
- 必要性：有时程序需要解决一些特定问题，需要用到表示特殊数值的数据类型。这些类型在程序语言设计时无法事先预知，只有当遇到具体问题时程序员才能知道具体的数值，因此不可能提前预设好。这就需要程序员使用user-defined data type用户定义数据类型来设定特殊的数据类型以解决问题。
13.1.2 Define and use non-composite types 定义和使用非复合类型
Including enumerated, pointer 包括枚举、指针
- non-composite data types：非复合数据类型，指在类型的定义中没有使用到其他数据类型。
- 注意：非符合类型中包括一些built-in data type内置数据类型，比如integer、real等，也包括一些user-defined data type用户定义数据类型，比如enumerated枚举、pointer指针等。
- Enumerated data type：枚举型，指将需要的数据列举出来组成的数据类型。
- 定义枚举型数据类型：
TYPE
枚举型名 = (枚举值1, 枚举值2, 枚举值3…) //将所有需要用到的值全部写入括号内，字符形式的值无需加引号
- 定义变量为枚举型：
DECLARE 枚举型变量名 : 枚举型名
- 为枚举型变量赋值：
枚举型变量名 ← 枚举值 //值必须是枚举型定义中提到的值
- 对枚举型变量进行比较：
Weekend = TRUE IF 枚举型变量 > 枚举值 //枚举型数据是暗含顺序的，按照枚举型定义时各值的排列顺序升序排列
- Pointer data type：指针型，指保存着数据内存地址的数据类型，可用于构建动态数据结构。
- 定义指针型数据类型：
TYPE
指针型名 ← ^数据类型 //“^数据类型”指的是指针型对应的数值的类型，本身还是个地址
- 定义变量为指针型：
DECLARE 指针型变量名 : 指针型名
- 为指针型变量赋值：
指针型变量名 ← @变量名 //将变量的地址传递给指针型变量，前面使用“@”表示传递地址
- 对指针型变量的值进行应用：
变量名 ← 指针型变量名^ * 2 //“指针型变量名^”指的是使用指针型变量对应地址中存放的数值
13.1.3 Define and use composite data types 定义和使用复合数据类型
Including set, record and class / object 包括集合、记录和类/对象
- composite data type：复合型数据类型，指在类型的定义中使用到了其他数据类型。
- 注意：常见的复合型数据类型包括set集合型、record记录型、class/object类或对象型等。
- Record data type：记录型。【参考10.1】。
- Set data type：集合型，指将数据集合在一起的数据类型。这些数据之间不强调顺序，但不允许有相同的数值。
- 集合型数据常常用于判断和删除数据结构中的重复值。数据结构可以转换为集合型来剔除重复值，然后再转换回数据结构。
- 集合型数据还可以用来判断两类数据的交叉情况。对两个集合进行交叉可以判断同时属于这两个集合的数据。
13.1.4 Choose and design an appropriate user-defined data type for a given problem 为给定问题选择和设计合适的用户定义数据类型
- 【参考13.1.2和13.1.3】。
13.2 File organisation and access 文件组织和访问
- 大纲要求
13.2.1 Show understanding of the methods of file organisation and select an appropriate method of file organisation and file access for a given problem 展示对文件组织方法的理解，并为给定问题选择适当的文件组织方法和文件访问权限
Including serial, sequential (using a key field), random (using a record key) 包括serial、sequential（使用key field）、random（使用record key）
- 文件的组织形式：有些文件是text file文本文件，有些文件是binary file二进制文件。
- 注意：二进制文件的架构以记录为基础，一个二进制文件中包含若干记录，每个记录中包含若干字段，每个字段中有一个数值。
- 注意：对于文本文件，需要知道每行的数据项数量、每个数据项中的字符数量，如果不知道，则需要使用项目分隔符。文件每行的结尾要有结束符标识。
- 注意：对于二进制文件，需要知道字段数量（如果字段中有字符串，还需要知道字符串中的字符数）。但不需要项目分隔符或结束符。
- 常见的文件类型：
- Serial file：串行文件，指记录没有任何既定顺序的文件。下一条记录仅仅是按照记入文件的时间顺序附在了上一条记录的后面。
- Sequential file：顺序文件，指已经按照某个规则排好顺序的文件。
- 顺序文件中存在key field，即文件已经按照该字段进行排序。
- Direct-access file：直接访问文件，又称random-access file随机访问文件，指无需按照顺序就可以读取文件内任何一处记录的文件。
- 实现的方法包括两种。一种可以考虑另外设立index file索引文件，索引文件中一个字段表示key field关键字段的值，一个字段表示主文件中关键字段值的位置。另一种可以考虑使用hashing algorithm哈希算法。
- Hashing algorithm：哈希算法，又称散列算法。文件中选取数字列作为关键字段，找一个合适的数字作为除数，用关键字段除以除数，得到的余数则作为数值的储存地址。如果余数相同（储存地址已经存入了其他数值），则称为collision冲突，此时可以向后顺延地址，直到找到一个空地址，将数据存入（也可以考虑准备一些溢出地址以供使用）。如果没有数字列，可考虑使用字母列的ASCII码加总。
- 实现的方法包括两种。一种可以考虑另外设立index file索引文件，索引文件中一个字段表示key field关键字段的值，一个字段表示主文件中关键字段值的位置。另一种可以考虑使用hashing algorithm哈希算法。
13.2.2 Show understanding of methods of file access 展示对文件访问方法的理解
Including: 包括：
· Sequential access for serial and sequential files 串行和顺序文件的顺序访问
· Direct access for sequential and random files 直接访问顺序和随机文件
- 向文件添加新数据：
- 向Serial files串行文件添加数据：直接在最后一行添加新数据。
- 向sequential file顺序文件文件添加数据：从头开始逐行读取，将数据从旧文件中按顺序复制到新文件，当到达新数据应该插入的位置时，将新数据复制进新文件，然后将剩余数据复制进新文件。
- 向direct-access file直接访问文件添加数据：采用hashing algorithm哈希算法计算出存储位置，将新数据存放进新文件。
- 对文件数据的访问：
- 对serial files串行文件的访问：从头开始逐行读取，直到找到需要的数据。
- 对sequential file顺序文件的访问：从头开始逐行读取，直到找到需要的数据（如果查找值对应的key field value关键字段值已知，则只需要查找关键字段值）。
- 对direct-access file直接访问文件的访问：将关键字段值输入直接访问文件采用的哈希算法（算法中使用的合适数字与之前相同），由此计算出应该在的储存地址。由于可能存在冲突问题，如果计算的储存地址中不是要访问的数据，可以向后方延伸一些数据位置。
- 对文件数据的编辑或删除：
- 在Serial files串行文件中编辑或删除数据：从头开始逐行读取，将数据从旧文件复制到新文件，当找到需要修改或删除的数据后，对数据进行修改或删除（如果是修改，则修改后复制到新文件中），然后将剩余数据从旧文件复制到新文件中。
- 在sequential file顺序文件文件中编辑或删除数据：从头开始逐行读取，将数据从旧文件中按顺序复制到新文件，当找到需要修改或删除的数据后，对数据进行修改或删除（如果是修改，则修改后复制到新文件中），然后将剩余数据复制进新文件。
- 在direct-access file直接访问文件中编辑或删除数据：采用hashing algorithm哈希算法计算出需要修改或删除的数据位置，如果需要修改则直接进行修改，如果需要删除则做好标记，下次文件读取时会自动跳过含有该标记的存储位置。
13.2.3 Show understanding of hashing algorithms 展示对散列算法的理解
Describe and use different hashing algorithms to read from and write data to a random / sequential file 描述和使用不同的散列算法从随机/顺序文件中读取和写入数据
- 【参考13.2.1和13.2.2】。
13.3 Floating-point numbers, representation and manipulation 浮点数、表示和操作
- 大纲要求
13.3.1 Describe the format of binary floating-point real numbers 描述二进制浮点实数的格式
Use two’s complement form 使用补码形式
Understand of the effects of changing the allocation of bits to mantissa and exponent in a floating-point representation 了解在浮点表示中将位分配更改为尾数和指数的影响
- 计算机采用二进制代码来表示实数，常用的表示方法包括以下两种：
- Fixed-point representation：定点表示法。使用二进制代码中的首位表示符号，其他数位中，一部分位数来表示实数的整数部分，另一部分位数来表示实数的小数部分。
- 转换例子：将十进制的31.75用二进制代码表示。
- 假设采用“1位符号位+5位整数位+2位小数位”的二进制代码来表示实数。
- 十进制的31.75拆分成整数部分的31和小数部分的0.75。
- 符号位为0。
- 整数部分的31转化为二进制的11111。
- 小数部分的0.75转化为二进制的11（因为用来表示小数的位数有2位，能表示4个状态，因此每0.25为一个状态，四个状态为0，0.25，0.5和0.75。0.75是第四个状态，用11表示。）
- 将所有二进制码拼起来，得到01111111，用这个二进制码来表示十进制的31.75。
- 转换例子：将十进制的31.75用二进制代码表示。
- Float-point representation：浮点表示法。使用exponential notation指数计数法（又称scientific notation科学计数法）的形式来表示实数，并使用二进制代码中的一部分数位来表示有效数（含符号位），另一部分数位来表示指数（含符号位）。
- 注意：本方法需要将实数写成 ±M×RE 形式。其中M称为significand有效数或mantissa尾数，E称为exponent指数或exrad。R是底数，默认等于2。
- 注意：M和E需要以two’s complement补码的形式计入二进制代码。【参考1.1.2】
- 转换例子【参考13.3.2】。
- Fixed-point representation：定点表示法。使用二进制代码中的首位表示符号，其他数位中，一部分位数来表示实数的整数部分，另一部分位数来表示实数的小数部分。
13.3.2 Convert binary floating-point real numbers into denary and vice versa 将二进制浮点实数转换为十进制数，反之亦然
- floating-point real number浮点型实数从十进制转为二进制的方法：将整数和小数部分分开，分别转换为二进制代码，中间以小数点隔开，形成M。M的二进制码数位如果不够，则在后面用0填充直到填满分配给的数位。然后对M取补码，进行标准化处理，得到M和E的标准值。将E换成二进制码后，得到实数的表达。（标准化处理参考【13.3.3】）
- 例子：将8.75转换成二进制代码表示的实数。
- 数字拆分成8和0.75。（如果原数是负数，则先按正数进行运算）
- 8的二进制代码为01000（首位是符号位）。
- 0.75的二进制代码为.11。（第四个状态，用11表示）
- 将8和0.75的二进制代码连起来，得到01000.11。
- 假设用10位数位来表示M，则M应为0100011000（M原有7位，需要在尾部补充3个零以填满分配给M的10个数位）。
- 因为原数是整数，补码为自身。（如果原数是负数，则此时需要算出补码）
- 将M标准化，01000.11的小数点需要左移四位，才能构成标准形式0.100011。因此E等于4。
- E的二进制代码为0100。
- 将二者连接起来，01000110000100即为所求的二进制代码。
- 例子：将8.75转换成二进制代码表示的实数。
- floating-point real number浮点型实数从二进制转为十进制的方法：按照指定的位数确定M和E的二进制代码。将E转换为十进制数字。在M的二进制代码的第一位和第二位之间加上小数点，向后移E个数位（逆标准化处理）。小数点前的是M的整数位，后面是M的小数位。将M的整数位和小数位转化为十进制数字后相加。如果是负数，注意补码计算。
- 例子：将10110100000011表示的实数转换成十进制。
- 假设该二进制代码是用10位表示M，4位表示E，则M的代码为1011010000，E的代码为0011。将E转换为十进制，得到3。说明标准化时，小数点向前移了3位。
- 将M加上小数点，得到1.011010000。小数点向后移3位，得到1011.01（因为后续的零已经处于小数点后，可以舍去）。
- M的整数位是1011，小数位是.01。
- 整数位由于符号位是1，代表负数，则要进行补码运算以得到十进制数字，计算可得-5。
- 小数位的.01代表十进制中的0.25（两个数位代表4种状态，分别是0、0.25、0.5和0.75。01代表第2个状态，即0.25）。
- 将整数位与小数位加起来，-5+0.25=-4.75。则原二进制代码表示的十进制数字为-4.75。
- 例子：将10110100000011表示的实数转换成十进制。
13.3.3 Normalise floating-point numbers 规范化浮点数
Understand the reasons for normalisation 了解归一化的原因
- 浮点型实数的尾数M位数越多，其precision精度（准确性）就越高。但相应的，用来表示E的位数越少，其表示的数据范围受限。通过normalisation标准化能够尽可能地保证数据精度。
- 标准化的表示形式：
- 正数的标准化：将由整数、小数点和小数组成的二进制代码的小数点不断左移，直到移到“0.1XXXX”的形式，指数位为挪动的次数。
- 负数的标准化：将由整数、小数点和小数组成的二进制代码的小数点不断左移，直到移到“1.0XXXX”的形式，指数位为挪动的次数。
13.3.4 Show understanding of the consequences of a binary representation only being an approximation to the real number it represents (in certain cases) 理解二进制表示的结果只是它所表示的实数的近似值（在某些情况下）
Understand how underflow and overflow can occur 了解下溢和上溢是如何发生的
- 二进制代码来表示实数的时候，绝大多数的小数部分是无法被准确转化的（只有和2的负n次方有关的小数可以被准确转化，比如1/2、1/4、1/8、1/16等）。在使用二进制代码表示这些小数时，会在一定精度内取其近似值。
- 对小数位非2的负n次方的实数的二进制转换方法：将整数和小数部分分开，分别转换为二进制代码。其中整数部分正常转换。小数部分不断乘2，取整，作为二进制代码，然后用剩余的小数部分继续乘2，反复进行，直到得到的数字极小，以至于很难出现下一个进位1，则过程停止。记录下的二进制代码则为小数位近似的二进制代码。然后【参考13.3.2】的步骤，继续进行下一步转换操作。
- 例子：将8.63转换成二进制代码表示的实数。
- 数字拆分成8和0.63。（如果原数是负数，则先按正数进行运算）
- 8的二进制代码为01000（首位是符号位）。
- 小数0.63不是2的负n次方，需要进行近似运算。
- 0.63*2=1.26，取整，二进制代码记为.1。
- 取上一次计算的小数部分，重复上述操作，0.26*2=0.52，取整，二进制代码拓展为.10。
- 0.52*2=1.04，取整，二进制代码拓展为.101。
- 0.04*2=0.08，取整，二进制代码拓展为.1010。
- 注意到从这里开始，需要运算很多次才能出现下一个1，所以可考虑停止近似运算。
- 所以M可以写成01000.1010。标准化后得到E的二进制代码为0100。
- 参考13.3.2的步骤，如果采取“10位M+4位E”的二进制代码形式，则01000101000100可用来表示十进制的8.63。
- 例子：将8.63转换成二进制代码表示的实数。
- Overflow error上溢错误与underflow error下溢错误：这是由于实数转换成二进制时存储空间范围可能不足导致。
- Overflow error：上溢错误，指需要转换的数字高于二进制代码能表示的数值上限导致的错误。
- Underflow error：下溢错误，指需要转换的数字低于二进制代码能表示的数值下限导致的错误。如果数字过小，程序可能会将其近似为0来处理后续运算，但这存在一定风险，可能会导致程序错误。
13.3.5 Show understanding that binary representations can give rise to rounding errors 理解二进制表示会导致舍入错误
- 【参考13.3.4】。
- 由于二进制对大多数小数进行转换时只能采取近似操作，因此在反复操作的情况下，可能会影响到后续计算的准确性。如果偏差过大则会出现rounding errors舍入错误。
- 为减少rounding error舍入错误，可以考虑使用更高精度的实数类型，为尾数M提供更多有效位，比如double precision双精度或quadruple precision四精度等。