数据的组织一轮复习课件浙江省高三信息技术选修一

数据的组织知识过关

1.数据结构的概念(1)数据元素(DataElement)。①数据元素是数据的基本单位。②数据元素也称为元素、节点、顶点、记录等。③有时一个数据元素可以由若干个数据项组成,如字段、域等,数据项是具有独立含义的最小数据表示单位。(2)数据类型。①数据类型是指具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。②数据类型可以分为基本数据类型(也称为原子数据类型,如整型、实型、布尔型、字符型等)和结构数据类型(如记录类型、集合、类等)。(3)数据结构。数据结构是指数据之间的相互关系,即数据的组织形式。它包括下列三个方面的内容:①数据元素之间的逻辑关系,也称为数据的逻辑结构。②数据元素及其关系在计算机存储器内的表示,也称为数据的存储结构或物理结构。③数据的运算,即对数据施加的操作。(4)数据结构设计的目的。数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑,既确保数据处理的正确性,又提高编程实现和数据处理的效率。2.常见的数据结构常见的数据结构有数组、链表、队列、栈、树和图等。(1)数组。使用数组来组织数据时,既可以快速地通过下标精确地访问序列中的某个数据元素,又可以方便地通过数组下标按顺序遍历序列中的每一个元素。(2)链表。链表存储的是数据之间的相互链接顺序。常用的链表形式有单向链表、双向链表和循环链表。(3)队列。①队列的特点是先进先出(FIFO)或后进后出(LILO)。②插入和取出数据分别在队列的两端进行。在队列的尾部插入数据(入队),从队列的头部取出数据(出队)。(4)栈。①栈的特点是先进后出(FILO)或后进先出(LIFO)。②插入和取出数据在栈的同一端进行。栈的一端封闭,一端开放,插入数据(入栈)和取出数据(出栈)都是在开放的一端进行。(5)树。数组、队列、栈、链表都是一种线性的数据结构,而树是一种非线性的数据结构。3.数据结构的作用(1)设计算法解决问题离不开数据结构。瑞士科学家沃斯提出了“算法+数据结构=程序”的思想。(2)不同的数据结构会导致处理效率的不同。

典例精选【例1】下列关于数据与数据结构的说法,错.

误.

的是(

)A.在链表中,一个节点就是一个数据元素B.在二维表中,一条记录中的一个字段是一个数据项C.数据结构在设计时需要考虑数据处理的效率D.数据结构是指数据的逻辑结构和存储结构,不包括数据的运算【解析】本题考查数据结构的相关知识。每个节点是数据元素,节点中的值和指针是数据项,A不符合题意。一条记录是数据元素,字段是数据项,B不符合题意。数据结构要考虑数据的存储、逻辑结构和数据运算,C不符合题意。D【例2】数据结构在解决问题的过程中有重要作用。下列关于数据结构的描述,正确的是(

)A.对同一事物,只能构造出一种数据结构B.选择的数据结构不同,解决问题的步骤也可能不同C.数据逻辑结构中相邻的数据,其存储位置也一定相邻D.对同一操作如，插入、删除等,不同数据存储结构的实现方法相同【解析】本题考查对数据结构的理解。对同一事物,可以构造出多种不同的数据结构,A错误。数据逻辑结构中相邻的数据,其存储位置也不一定相邻,如数组中相邻数据的存储位置是相邻的,而链表中的就不一定相邻,C错误。对同一操作,如插入、删除等,不同数据存储结构的实现方法不一定相同,如队列的数据插入和删除与栈的操作方法是不一样的,D错误。对于同一个问题,选择的数据结构不同,其解决问题的步骤也可能不同,B正确。B【例3】下列关于队列的说法,正确的是(

)A.队列具有先进后出的特点B.程序设计时,通常使用列表来模拟队列C.插入和删除数据元素都是在队列的同一端进行的D.可随时从队列的中间取出数据元素【解析】本题考查队列的特点及操作。队列具有先进先出或后进后出的特点,A错误。数据元素的插入是在队列的尾部进行,而数据元素的删除是从队列的头部进行,C错误。在队列操作时,只能从队列的头部取出数据元素,即不能取出队列中间位置上的数据元素,D错误。在程序设计时,通常使用列表来模拟队列,B正确。B【例4】下列关于数组的说法,错.

误.

的是(

)A.数组中各元素的存储是没有先后顺序的B.用数组来组织数据时,可通过数组的下标精确地访问序列中的指定数据元素C.数组中存储的是相同类型的数据元素D.数组属于线性的数据结构【解析】本题考查数组的含义。数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起,A符合题意。A【例5】下列关于数据结构的说法,错.

误.

的是(

)A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储C.数据的运算是指对数据施加的操作,包括删除、查找、插入数据等D.数据结构设计时,不需要考虑编程实现和数据处理的效率【解析】数据结构包括数据的逻辑结构、数据的存储结构和数据的运算。数据的运算是在数据存储结构实现后,对数据进行增、删、改、查等操作。数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑,既确保数据处理的正确性,又提高编程实现和数据处理的效率。在设计数据结构时,就需要考虑效率问题,D符合题意。D【例6】下列关于数据项与数据元素的说法,错.

误.

的是(

)A.数据元素可由若干数据项组成B.同一数据元素中各数据项的数据类型必须相同C.数据项是数据的最小单位,通常用来描述实体的某种属性D.数据元素是数据的基本单位,在计算机中通常作为一个整体来处理【解析】数据元素由若干数据项组成,数据项是具有独立含义的最小数据表示单元,各数据项之间的数据类型可以不相同,B符合题意。B

自我检测1.下列有关数据与数据结构的说法,不正确的是(

)A.在链表中,一个节点就是一个数据元素B.在二维表中,一条记录中的一个字段是一个数据项C.数据结构在设计时需要考虑数据处理的效率D.数据结构是指数据的逻辑结构和存储结构,不包括数据的运算【解析】本题考查数据结构的相关知识。A选项中的每个节点是数据元素,节点中的值和指针是数据项。B选项一条记录是数据元素,字段是数据项。C选项中的数据结构要考虑数据的存储、逻辑结构和数据运算,D选项错误。D2.下列关于数据结构的描述,不正确的是(

)A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储C.数据的运算是指对数据施加的操作,包括删除、查找、插入数据等D.数据结构设计时不需要考虑编程实现和数据处理的效率【解析】数据结构包括数据的逻辑结构、数据的存储结构和数据的运算。数据的运算是在数据存储结构实现后,对数据进行增、删、改、查等操作。数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑,既确保数据处理的正确性,又提高编程实现和数据处理的效率。在设计数据结构时,就需要考虑效率问题,D正确。D3.关于数据项与数据元素的描述,下列说法中不正确的是(

)A.数据元素可由若干数据项组成B同一数据元素中各数据项的数据类型必须相同C.数据项是数据的最小单位,通常用来描述实体的某种属性D.数据元素是数据的基本单位,在计算机中通常作为一个整体来处理【解析】数据元素由若干数据项组成,数据项是具有独立含义的最小数据表示单元,各数据项之间的数据类型可以不相同,B正确。B4.数据元素及其关系在计算机存储器内的表示,也称为数据的(

)A.线性结构 B.物理结构C.逻辑结构 D.空间结构【解析】数据元素及其关系在计算机内的表示,也称为数据的存储结构或物理结构,B正确。B5.下列关于数据的说法,正确的是(

)A.在二维表中,一条记录就是一个数据元素B.数据即“数字”“数值”等跟数有关的常识C.数据项是数据的基本单位D.数据结构是指数据的逻辑结构,不包括数据的存储结构【解析】本题考查数据与数据结构的相关知识。在二维表中,一条记录就是一个数据元素,A正确。数据还可以是文本、图像、音频和视频等,B错误。数据元素是数据的基本单位,数据项是数据的最小单位,C错误。数据结构是指数据的物理结构(存储结构)和逻辑结构,D错误。A6.下列关于队列和栈的说法,错.

误.

的是(

)A.队列是一种先进先出的线性表,可在队尾进行插入操作B.栈的特性是“先进后出,后进先出”C.某栈的入栈顺序为“abc”,出栈顺序只有4种D.队列和栈都是线性数据结构,都可以用数组来实现【解析】入栈的顺序为“abc”,出栈顺序可能是abc、acb、bac、bca、cba,共5种,C符合题意。C必备知识练1.下列关于数据结构的说法,错.

误.

的是(

)A.数据在计算机存储器中的存储方式称为数据的存储结构B.数据的存储结构包括顺序存储结构和链表存储结构C.数据的存储结构不同,但对数据进行相同操作的实现方法相同D.数据结构中数据的组织方式包括数据的逻辑结构和数据的物理结构【解析】本题考查数据结构的含义及特性。数据的存储结构不同,对数据进行同一操作的实现方法也不同,C符合题意。C2.若要在队列中进行插入和删除元素的操作,下列说法中,正确的是(

)A.在队列的同一端进行插入和删除操作B.最先进队的元素总是最后才被删除C.在队列的一端插入元素,删除元素在另一端进行D.可以在队列的中间位置插入一个元素【解析】本题考查队列的特点。队列的两端都是开放的,一端用于插入元素,另一端用于删除元素,插入元素时只能在队尾进行,不能在中间插入;队列的特点是先进先出,或后进后出,因此,最先进队的元素总是最先被删除。C正确。C3.下列关于数据结构的说法,正确的是(

)A.常见的线性关系数据结构有数组、链表、队列等B.数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构C.游客们排队有序进入景区体现了栈的思想D.数据结构设计只要考虑数据对象的存储结构【解析】本题考查数据结构知识。数组不适合频繁插入与删除的数据结构,B错误。游客们排队有序进入景区体现了队列的思想,C错误。数据结构设计除了考虑数据对象的存储结构外,还需要考虑逻辑结构等,D错误。A4.下列选项中,属于栈和队列共同特点的是(

)A.都是先进先出 B.都是先进后出C.都是线性表 D.都是在两端进行操作【解析】本题考查栈和队列的特点。栈的特点是先进后出,插入和删除元素在同一端进行,另一端封闭;队列的特点是先进先出,插入元素在一端进行,删除元素则在另一端进行;它们都属于线性的数据结构。C正确。C5.下列关于链表特征的说法,正确的是(

)A.数据在内存中的存储地址一定是连续的

B.插入或删除时,无须移动其他元素C.可以随机访问表内的元素

D.需要事先估计存储空间【解析】本题考查链表的基本特性。数据在内存中的地址(即物理地址)不一定连续,A错误。对于单链表来说,只有指向链表头的头指针,所以不能随机访问表内元素,只能通过指针的移动来访问指定的元素,C错误。链表的存储空间是不需要事先估计的,它不是线性的,所以可以随着节点的增加而随时增加存储空间,D错误。链表是用指针来指向元素的值,所有的操作都是通过移动指针来进行的,本身的元素不需要移动,B正确。B6.制作某电子作品时,各个素材存储的文件夹如图所示。下列选项中,与该文件系统结构相类似的数据结构是(

)A.链表 B.队列C.树 D.栈【解析】文件系统有根节点和子节点,符合树结构特征,C正确。C7.下列关于数据结构的说法,正确的是(

)A.栈结构只允许从栈底入栈,从栈顶出栈B.可以直接访问链表中任意一个节点的值C.树结构的每个元素前面必须只有一个元素D.数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构【解析】栈是一种受限的数据结构,只能在一端进行操作,A错误;链表需通过头指针依次访问各个节点,B错误;树的特征是只有一个根节点,每个节点只有一个前驱,可以有多个后继,C正确;数组元素的插入与删除需移动多个元素,D错误。C8.采用链式存储线性表时,如果要进行插入和删除操作,那么在算法的执行效率方面与采用顺序存储的线性表进行比较。下列说法中,正确的是(

)A.插入操作和删除操作的效率都要低

B.插入操作的效率要低,删除操作的效率要高C.插入操作的效率要高,删除操作的效率要低

D.插入操作和删除操作的效率都要高【解析】链表是采用链式存储结构的线性表,在链表中进行插入、删除操作比在顺序表中效率高,D正确。D关键能力练

9.下列关于栈、队列、数组等数据结构的说法,正确的是(

)A.队列的操作方式是后进先出

B.栈的操作方式是先进先出C.数组是通过下标来访问序列中的数据元素

D.线性表的线性存储结构优于链表存储结构【解析】队列的操作方式是先进先出,A错误;栈的操作方式是先进后出,B错误;线性表的线性存储结构和链表存储结构各有优缺点,没有绝对的好或不好,D错误。C10.在长度为n的顺序表中,在第i个元素之前插入一个新元素时,需向后移动的元素个数为(

)A.n－i B.n－i＋1C.n－i－1 D.i【解析】本题考查顺序表的操作。在第i个元素之前插入一个新元素,需要对后面n－i＋1个元素进行后移,B正确。B11.下列关于数据结构的说法,错.

误.

的是(

)A.队列和栈都是操作受限的线性表B.计算机中一般会采用树形结构来管理文件C.链表中数据元素的逻辑顺序是通过链表中指针的指向实现的D.同一个数组中的元素的数据类型可以不同【解析】本题考查数据结构基本知识。同一数组中元素的数据类型相同,D符合题意。D12.下列关于线性表的说法,正确的是(

)A.链表在访问、插入、删除节点操作时,算法效率比数组高B.栈是一种“先进先出,后进后出”的线性表结构C.循环队列是首尾相连的队列,数据入队时无须考虑是否会“溢出”D.字符串是元素个数有限的线性表结构【解析】本题考查链表、栈和队列的特性。链表每次需要从头节点开始遍历才能访问中间的值,而数组可以直接通过索引访问,效率更高,A错误。栈是一种“先进后出,后进先出”的线性表结构,B错误。当队列的元素个数超过数组空间,也会溢出,循环队列解决了数据入队时的“假溢出”现象,C错误。D13.下列关于数组的说法,正确的是(

)A.在计算机内部存储时,一维数组是线性存储,二维数组是非线性存储B.对数组进行操作的过程中,若某些数据元素已被删除,其占用的存储空间也会被释放C.数组结构中采用下标访问数据,访问效率要高于链表结构D.同一数组元素的数据类型可以不相同【解析】本题考查数组的相关知识。线性存储指数据依次存储,二维数组先按行,再按列,第二行接在第一行的最后一列后面,也是线性存储,A错误。数据元素被删除,只是数据下标范围发生变化,其占用的存储空间不变,B错误。数组在内存中是连续存储的,可以通过下标直接访问任意位置的数据。访问链表中的某个元素,需要从头节点开始,沿着指针逐个访问节点,直到找到目标元素,C正确。同一数组元素的数据类型是相同的,D错误。C14.下列关于数据结构的说法,错.

误.

的是(

)A.在程序设计中,数据结构设计时主要考虑对象之间逻辑关系的实现B.链表结构适用于初始规模确定,但在处理过程中频繁进行插入、删除操作的问题C.数组结构中的数据访问效率要高于链表结构D.大多数软件中都有“撤销”功能,在撤销操作