初识数据结构 　练习　2022-2023学年浙教版（2019）高二信息技术选修一

台州市书生中学高二信息选修一 信心 细心 恒心 编制：台州市书生中学信息技术高二备课组 1.初识数据结构 【要点提示】 1.瑞士计算机科学家沃斯指出“___________________”,形象地阐明了计算机程序设计的本质是______________________的设计。 2.数据结构的概念： (1)数据元素：数据的______单位，可由若干数据项组成。数据项是具有独立含义的______数据表示单位。这个表中一共有______个数据元素。 第三个数据元素的第三个数据项的名称为_________，值为__________ (2)数据类型：具有__________的计算机数据的集合及在这个数据集合上的一组操作。数据类型可分为__________和__________。 (3)数据结构：数据之间的相互关系，即数据的__________。主要包含数据的__________、数据的__________和数据的________。 3.常见的数据结构 (1)数组：表示一批数据，不仅可以描述数据本身，还可以描述数据所处的位置或数据之间的前后顺序关系。可以迅速地通过______精确访问序列中的某个数据元素，又可以通过下标按顺序______序列中的每个元素。 (2)链表：表示一批数据，这类数据之间具有明确的相互链接的___________，但对数据对象本身的___________不作要求。常用的链表有单向链表、双向链表、循环链表。 (3)队列：数据具有“____________”且中间__________的组织和操作的性质。在数据序列的头部（称为队首）进行数据的读取（即出队），在数据序列的尾部（称为队尾）进行数据的插入（即入队）。 (4)栈：数据具有“___________”且所有操作只能在一端（称为栈顶）进行的性质。仅可在一端进行数据的读取(称为出栈)和插入（称为入栈）操作。 (5)树：数据元素前面只有一个元素，后面可以有______________元素相邻，所有元素之间的关系特征像一棵倒放的树。 4.对于同一问题，若依据不同的数据结构来设计算法，则算法的处理效率、程序的实现效率也会_______。 限时训练 1.以下关于数据结构的描述，不正确的是( ) A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系 B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储 C.数据的运算是指对数据施加的操作，包括删除、查找、插入数据等 D.数据结构设计时不需要考虑编程实现和数据处理的效率 2.数据元素及其关系在计算机存储器内的表示，也称为数据的( ) A.线性结构 B.物理结构 C.逻辑结构 D.空间结构 3.下列数据结构中属于线性数据结构的是( ) ①数组 ②栈 ③队列 ④链表 ⑤树 A.①②③④⑤ B.①②③④ C.①②④⑤ D.①②③⑤ 4.用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态)，且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是( ) A.1、2、3、4 B.2、3、4、1 C.4、2、3、1 D.3、2、1、4 5.关于数据项与数据元素的描述，下面说法不正确的是( ) A.数据元素可由若干数据项组成 B.同一数据元素中各数据项的数据类型必须相同 C.数据项是数据的最小单位，通常用来描述实体的某种属性 D.数据元素是数据的基本单位，在计算机中通常作为一个整体来处理 6.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是( ) A.链表 B.队列 C.树 D.栈 7.在日常幻灯片（如PowerPoint演示文稿）的放映中，可以通过超链接的方式进行幻灯片之间的任意跳转。与这种页面之间相互链接的表现形式相似的数据结构是( ) A.树 B.链表 C.队列 D.栈 8.数据结构中栈和队列的共同特点是( ) A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除数据 D.没有共同点 9.小陈同学高一结束后需要换寝室，他将全部物品打包成6个箱子并编号叠放在一起（如图1-10所示）。为了搬运物品方便，他借了一辆手推车，该手推车一次最多能叠放3个箱子（如图1-11所示）箱子从上往下依次叠放在小推车上（假定每次只放一个箱子），小推车每次可以叠放1、2或3个箱子，小