自考数据结构导论笔学习记
自考数据结构导论20051年10月试卷
全国2005年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能 ．．．的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) 浙02142# 数据结构导论试题第 1 页（共 4 页）
02142数据结构导论201604
2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是 A．线性表 B．队列 C．树 D．图 2．计算n!(整数n≥0)的递归算法是：int Factorial(int n){if(n= =o)return l；else return n*Factorial(n--1)；}其时闯复杂度为 A．0(n) B．0(log2n) C．O(n0) D．O(n2) 3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A．p=q； B．p--：>next=q； C．q一>next=p--：>next；p-->next=q； D．p一>next—q；q-->next—p--：>next； 4. 设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是 A．sxxssxxs B．ssxsxxxs C．ssxxxssx D．sssxxxsx 5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是 A．顺序表 B．单链表C．栈 D．队列 6．设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为 A．O(n)、O(1) B．O(1)、O(1) C．O(1)、O(n) D．0(n)、0(n) 7．若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为 A．4 B．5 C．6 D．7 8．按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是
全国自学考试数据结构导论试题及答案(4套)
全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
数据结构导论串讲笔记
数据结构导论串讲笔记
1）已知出栈序列，写出可能的入栈序列并分析操作过程。 2）已知入栈序列，写出可能的出栈序列并分析操作过程。 [2004/1]如下图所示，输入元素为（A，B，C），在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。 AB 输输 栈 【分析】A，B，C三个字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为BCA时，输出无法得到ABC。因为输入序列为BCA时，要想先输出A，必须BCA均入栈，但这样只能得到序列ACB。其余五种输入序列都可在输出端得到序列ABC。 【解答】ABC、ACB、BAC、CAB、CBA
2．队列的操作 分析顺序队中元素入队出队操作及队列的状态。（考过） [2003/10]设有一顺序队列sq ，容量为5，初始状态时sq ．front=sq ．rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。 （1） d ，e ，b 入队 （2） d ，e 出队 （3） i ，j 入队 （4） b 出队 （5） n ，o ，p 入队 【解答】队列及其头尾指针的状态变化情况如下图所示 Sq.f Sq.r b e d Sq.f b Sq.f Sq.r j b i Sq.f Sq.r j i Sq.f Sq.r
（a ）初态 （b ）d ，e ，b 入队 （c ） d ，e 出队 （d ） i ，j 入队 （e ）b 出队 第5步操作无法进行，因队列已满。 3．二叉树的存储结构 1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。（[2000/10] [2003/10] [2004/10]考过） [2003/10]画出下列二叉树的二叉链表表示图。 【解答】二叉树的二叉链表表示 B E D F H G A C B B ∧ ∧ A D ∧ C G ∧ ∧ F H ∧ ∧ E ∧ ∧
自考数据结构导论复习资料
数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象
8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被
自考02142《大数据结构导论》串讲笔记
第一概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。
自考数据结构导论
全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A )
数据库和应用串讲笔记(珍藏版)
数据库及其应用串讲笔记(珍藏版) 第一章数据库基础知识 第一节数据库的基本概念 ［填空］数据管理技术与计算机硬件、软件和计算机的应用围有着密切的联系，其发展主要经历了人工管理方式、文件系统方式和数据库系统方式等三个阶段。 ［简答］数据库技术的特点： （1）数据结构化。 （2）数据共享。 （3）数据冗余小。 （4）有较高的数据独立性。 （5）数据库系统为用户提供了使用方便的用户接口。 （6）增加了系统的灵活性。 ［简答］简述数据独立性的含义及其作用。 数据独立性是指应用程序与数据库的数据结构之间的相互独立，是数据库系统努力追求的目标。数据独立性有两层含义，如果数据库物理结构改变时，不影响数据库的整体逻辑结构、用户的逻辑结构和应用程序，这样我们就认为数据库达到了“物理数据独立性”；如果在整体逻辑结构改变时，不影响用户的逻辑结构及应用程序，那么我们就认为数据库达到了“逻辑数据独立性”。 ［选择］数据库的基本术语： 数据库：是指长期存储在计算机的、有组织的、统一管理的相关数据的集合。 数据库系统：是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机硬件、软件和数据资源组成的系统，实际上是指采用了数据库技术后的整个计算机系统。 ［简答］DBMS是数据库系统中专门用来管理数据的软件，它位于用户与操作系统（Operating System,简记为OS）之间，是用户使用数据库的接口，为用户提供了访问DB的方法，包括DB的建立、查询、更新和各种数据控制。 ［填空］DBMS总是基于某种数据模型，主要有关系型、层次型、网状型和面向对象型等。 第二节数据描述 ［填空］联系是指实体之间的关系。与一个联系有关的实体集的个数，称为联系的元数。 ［选择、填空］二元联系的三种类型： （1）一对一联系（简记为1∶1） 对于不同型实体集A和B，如果A中的一个实体最多只与B中的一个实体有联系，反之亦然，则称A和B两实体为1∶1联系。例如，一夫一妻制社会中，“丈夫”与“妻子”两实体集之间为1∶1联系。 （2）一对多联系（简记为1∶n） 如果实体集A中至少有一个实体与实体集B中多于一个的实体有联系（可以是零个、一个或多个），则称A对B为1∶n联系。例如，“母亲”和“子女”
全国数据结构导论10月高等教育自学考试试题与答案
全国20XX 年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)l A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为???? ??????010100110，则该图中顶点V 1的出度为（ C ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，A C.E ，A ，B ，C ，D D.E ，D ，C ，B ，A 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ A ） A.O （1） B.O （log 2n ） C.O （n ） D.O (n 2) 7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ B ） A.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ B ） A.O (1) B.O (n) C.O (n ) D.O (log 2n)
自考02142《数据结构导论》串讲笔记
第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。
2020年10月全国数据结构导论自考试题及答案解析.doc
??????????????????????精品自学考料推荐?????????????????? 全国 2019 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（） A. 逻辑结构、存储结构、机外表示 B. 存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D. 机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 3.下列关于线性表的基本操作中，属于加工型的操作是（） A. 初始化、求表长度、插入操作 B. 初始化、插入、删除操作 C.求表长度、读元素、定位操作 D. 定位、插入、删除操作 4.在一个单链表中，若p 所指结点不是最后结点， s 指向已生成的新结点，则在p 之后插入
s 所指结点的正确操作是（）A.s–>next=p –>next; p –>next=s; C.s–>next=p; p –>next=s; B.p –>next=s –>next; s –>next=p; D.s–>next=p –>next; p=s; 5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（） A.3 种 B.4 种 C.5 种 D.6 种 6.C 语言对数组元素的存放方式通常采用（） A. 按行为主的存储结构 B. 按列为主的存储结构 C.按行或列为主的存储结构 D. 具体存储结构无法确定 7.根据定义，树的叶子结点其度数（） A. 必大于 0 B. 必等于 0 C.必等于 1 D. 必等于 2 8.二叉树若采用二叉链表结构表示，则对于n 个结点的二叉树一定有（） A.2n 个指针域其中n 个指针为 NULL B.2n 个指针域其中n+1 个指针为 NULL C.2n-1 个指针域其中n 个指针为 NULL D.2n-1 个指针域其中n+1 个指针为 NULL 9.在一个无向图中，所有顶点的度数之和等于边数的（） A.1 倍 B.2 倍 C.3 倍 D.4 倍 10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（） 1
自考02142《数据结构导论》串讲笔记
： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。
自考数据结构导论20120年01月试卷
全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( ) A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( ) A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( ) A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1) 12.三个顶点v1,v2,v3的图的邻接矩阵为 010 001 010 ?? ?? ?? ?? ?? ，该图中顶点v3的入度为( ) A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找 的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 浙02142# 数据结构导论试题第 2 页共 5 页 数据结构导论复习大纲 第1章概论 一、程序设计的实质（计算机专业人员必须完成的两项基本任务）： 数据表示：机外表示->逻辑结构->存储结构 数据处理：处理要求->基本运算和运算->算法 数据表示和数据处理是密切相关的，数据处理方式总是与数据的某种表示形式相联系。 二、“数据”分成三个不同的层次，即数据、数据元素和数据项。 凡能被计算机存储、加工的对象通称为数据。 数据元素是数据的基本单位，又被称为元素、结点、顶点或记录。 数据项是数据不可分割的最小单位。 三、数据的逻辑结构 数据的逻辑结构就是数据的组织形式。所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 通常有集合、线性结构、树形结构、图状结构。 ＊逻辑结构与数据元素本身的形式、内容、相对位置、结点个数无关 四、运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。分为两种基本类型： 1. 加工型运算：插入、删除、更新 2. 引用型运算：读取、查找 五、存储实现的基本目标是建立数据的机内表示。数据的机内表示称为数据的存储结构。包括三个主要部分： 1. 存储结点。每个结点存放一个数据元素 2. 数据元素之间关联方式的表示，也就是逻辑结构的机内表示 3. 附加设施。 存储结构的主要部分是数据元素之间关联方式的表示。由于每个存储结点存放一个数据元素，数据元素之间的关联方式便由存储结点之间的关联方式间接地表达。通常有四种基本存储方式： 1. 顺序存储方式 2. 链式存储方式 3. 索引存储方式 4. 散列存储方式 六、运算实现 运算的实现是指一个完成该运算功能的程序。运算实现的核心是算法设计。 算法分为三类： （1）运行终止的程序 （2）伪语言算法 （3）非形式算法 七、算法质量的评价： （1）正确性：算法应能正确地实现预定的功能 （2）易读性：算法应易于阅读和理解。 （3）健壮性：当环境发生变化时，算法能适当地做出反应或进行处理 （4）高效性：达到所需要的时空性能。 算法在所有输入下的计算量的最大值称为算法的最坏情况时间复杂性或最坏情况时间复杂度 自考网络注册学习加分科目介绍 一、什么是网络注册学习？ 为建立和完善高等教育自学考试，经湖北省教育考试院批准（鄂自考[ ] 11号文件），在湖北省内开展自学考试网络助学班综合评价项目。考生参加"课程网络助学"的学习，可取得过程性评价成绩，过程性评价成绩以30%的比例计入总分。即经过网上课程学习，能够把网上学习的成绩按30%比例计入考试总分，大大提高考试经过率！ 二、成绩评定 a) 参加课程网络助学的考生在学习过程结束后，可取得过程性评价成绩。过程性评价成绩经湖北省教育考试院审核确认以后以30%的比例计入总分，即自考课程成绩 = 过程性评价成绩 ×30% + 国家统考笔试成绩×70%。 b) 例一考生小明《资产评估》课程的国家统考笔记成绩为52分，因参加了课程网络助学，获得了过程行评价成绩96.02分，折算后，她的最终成绩为65分。具体换算：过程性评价成绩96.02分× 30% + 国家统考笔试成绩52分× 70% =最终成绩65.206分，约等于65分。（对于想考学位的同学而言，是不是很轻松就能获得？） c) 过程性评价成绩在一年内均有效。即一年内，每次报考该课程均可获得30%的网络平台的平时成绩! “过程性评价成绩”即“平时成绩”；简单理解网络注册学习折算下最多来能够加：17分（按照要求可100%获得）。 三、学习形式与流程 网络助学采用"网络+面授"混合式的助学模式，为考生提供线上线下学习支持服务。即经过学习在网上看视频教程，做相关知识点测评，及相关辅导老师的线下辅导，学习结束后评估出考生过程性评价成绩，即平时成绩，过程性评价成绩湖北省教育考试院审核确认后可与国家统考笔试成绩进行合并。 四、报考学习 1、报考资格：所有湖北地区自考人员均可报考 2、报考类型：提供网络注册学习账户，直接在网络进行学习，加考前串讲面授，大大提高经过率。 1） 已知出栈序列，写出可能的入栈序列并分析操作过程。 2） 已知入栈序列，写出可能的出栈序列并分析操作过程。 [2004/1]如下图所示，输入元素为（A , B , C ）,在栈的输出端得到一个输出序列 ABC , 求出在栈的输入端所有可能的输入序列。 ABC 输入端 【分析】A ，B ，C 三个字符排成的序列可以有： ABC 、ACB 、BAC 、BCA 、CAB 、 CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为 BCA 时， 输出无法得到 ABC 。因为输入序列为 BCA 时，要想先输出 A ，必须BCA 均入栈，但这 样只能得到序列 ACB 。其余五种输入序列都可在输出端得到序列 ABC 。 【解答】ABC 、ACB 、BAC 、CAB 、CBA 2 ?队列的操作 分析顺序队中元素入队出队操作及队列的状态。 （考过） [2003/10] 设有一顺序队列 sq ,容量为5，初始状态时sq ? front=sq ? rear=0，画出做完 下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。 (1) d , e , b 入队 (2) d , e 出队 (3) i , j 入队 (4) b 出队 (5) n , o , p 入队 【解答】队列及其头尾指针的状态变化情况如下图所示 3 .二叉树的存储结构 1）给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。 [2004/10]考过） [2003/10] 画出下列二叉树的二叉链表表示图。 输出端 j - Sq.rear j i i b ~Sq.rear b -—Sq.rear b e ■*- Sq.front "-Sq.front d Sq.fr ont -Sq.rear H — Sq.fro nt （a ）初态 （b ） d , e , b 入队 第5 步操作无法进行，因队列已满。 (d ) i , j 入队 (e ) b 出队 ([2000/10] [2003/10] *- Sq.rear Sq.fro nt 1）已知出栈序列，写出可能的入栈序列并分析操作过程。 2）已知入栈序列，写出可能的出栈序列并分析操作过程。 [2004/1]如下图所示，输入元素为（A ，B ，C ），在栈的输出端得到一个输出序列ABC ，求出在栈的输入端所有可能的输入序列。 【分析】A ，B ，C 三个字符排成的序列可以有：ABC 、ACB 、BAC 、BCA 、CAB 、CBA 六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为BCA 时，输出无法得到 ABC 。因为输入序列为BCA 时，要想先输出A ，必须BCA 均入栈，但这样只能得到序列ACB 。其余五种输入序列都可在输出端得到序列ABC 。 【解答】ABC 、ACB 、BAC 、CAB 、CBA 2．队列的操作 分析顺序队中元素入队出队操作及队列的状态。 （考过） [2003/10]设有一顺序队列sq ，容量为5，初始状态时sq ．front=sq ．rear=0，画出做完 下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。 （1） d ，e ，b 入队 （2） d ，e 出队 （3） i ，j 入队 （4） b 出队 （5） n ，o ，p 入队 【解答】队列及其头尾指针的状态变化情况如下图所示 （a ）初态 （b ）d ，e ，b 入队 （c ） d ，e 出队 （d ） i ，j 入队 （e ）b 出队 第5步操作无法进行，因队列已满。 3．二叉树的存储结构 1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。（[2000/10] [2003/10] [2004/10]考过） [2003/10]画出下列二叉树的二叉链表表示图。 Sq.front Sq.rear Sq.front Sq.rear Sq.rear Sq.front Sq.rear 全国2018年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的四种基本逻辑结构是指( ) A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性 C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性 3.下列关于线性表的叙述中，不正确的是( ) A.线性表是n个结点的有穷序列 B.线性表可以为空表 C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系 4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( ) A.p=p->next B.p->next=p->next C.p->next=p->next->next D.p->next=p 5.栈和队列( ) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处 6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( ) A.127 B.142 C.150 D.157 7.深度为k的二叉树至多有( ) A.2k个结点 B.2k-1个结点 C.2k-1个结点 D.2k-1-1个结点 8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( ) A.ABCDEF B.ABECDF C.CDFBEA D.CBDAEF 1 全国2003年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。错选、多选或未选均无分。每小题2分，共30分) 1.下列数据结构中，( )不都是线性结构。 A.栈和队列 B.队列和数组 C.数组和串 D.文件和队列 2.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。 A.顺序存储 B.链式存储 C.索引存储 D.散列存储 3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( ) A.s->t1->r1=s->t1;s->r1->t1=s->r1; B.s->t1->r1=s->r1;s->r1->t1=s->t1; C.s->r1=s->t1->r1;s->t1=s->r->t1; D.s->t1=s->t1->r1;s->r1=s->r->t1; 4.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( ) A.q->right=s; s->left=q; q->right->left=s; s->right=q->right; B.s->left=q; q->right=s; q->right->left=s; s->right=q->right; C.s->left=q; s->right=q->right; q->right->left=s; q->right=s; D.以上都不对 5.由下列三棵树组成转的森林换成一棵二叉树为( ) 6.具有100个结点的完全二叉树的深度为( ) A.6 B.7 C.8 D.9 浙江省2018年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号 内。每小题1分，共14分) 1.计算机算法指的是( )。 A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法 2.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s↑.next:=p；p↑.next=s; B. s↑.next:=p↑.next;p↑.next:=s； C. s↑.next:=p↑.next;p:=s; D. p↑.next:=s;s↑.next=p; 3.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。 A.110 B.108 C.100 D.120 4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素 个数是( )。 A.(rear-front+m) MOD m B.rear-front+1 C.rear-front-1 D.rear-front 5.栈和队列的共同特点是( )。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6.深度为n的二叉树中所含叶子结点的个数最多为( )个。 A.2n B.n C.2n-1 D.2n-1 7.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 8.下面的二叉树中，( )不是完全二叉树。 9.下列说法错误的是( )。 选择题 1. 在二维数组中，每个数组元素同时处于（2）个向量中。 2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A 的末尾，其时间复杂度应为（O(m)）。 3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(front == NULL)。 4. 若让元素1,2,3依次进栈，则出栈次序不可能出现(3,1,2 )种情况。 5. 图的广度优先搜索类似于树的（层次）遍历。深度优先搜索遍历类似于树的先根遍历 6. 下面程序段的时间复杂度为(O(m*n) )。 for(int i=0; i数据结构导论
自考网络注册学习加分科目介绍
数据结构导论串讲笔记
数据结构导论串讲笔记
1月全国自考数据结构导论试题及答案解析
自考数据结构导论20030年01月试卷
浙江省1月自学考试数据结构导论试题及答案解析
数据结构导论选择
- 全国数据结构导论10月高等教育自学考试试题与答案
- 自考02142《数据结构导论》串讲笔记
- 2020年1月全国自学考试试题及答案解析数据结构导论试卷及答案解析
- 2006年10月全国自考数据结构导论试题及答案
- 自考数据结构导论20051年10月试卷
- 全国1月高等教育自学考试数据结构导论试题及答案解析
- 全国自学考试数据结构导论试卷与答案(4套)
- 自考02142数据结构导论串讲笔记
- 全国2014年10月自考全国数据结构导论试题及答案
- 2015年4月全国自考《数据结构导论》试题
- 自考数据结构导论
- 自考02142《数据结构导论》串讲笔记
- 全国2010年1月自考数据结构导论考试试题,答案,笔记
- 数据结构导论自考全书重点综合复习
- 全国自学考试数据结构导论试题及答案(4套)
- 自考数据结构导论20120年01月试卷
- 1月全国自考数据结构导论试题及答案解析
- 2020年10月自考02142数据结构导论试题及答案含评分标准
- 2004年10月全国自考数据结构导论试题及答案
- 自考数据结构导论复习资料