全国1月高等教育自学考试数据结构导论试题及答案解析
全国2018年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
7.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，
4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( )
A.(2，1，3)
B.(3，1，5)
C.(3，2，-1)
D.(2，3，-1)
8.无向图的邻接矩阵是一个( )
A.对称矩阵
B.零矩阵
C.上三角矩阵
D.对角矩阵
9.下列说法中正确的是( )
A.一个具有n 个顶点的无向完全图的边数为n(n-1)
B.连通图的生成树是该图的一个极大连通子图
C.图的广度优先搜索是一个递归过程
D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量
10.顺序查找法与二分查找法对存储结构的要求是( )
A.顺序查找与二分查找均只适用于顺序表
B.顺序查找与二分查找既适用于顺序表，也适用于链表
C.顺序查找只适用于顺序表
D.二分查找只适用于顺序表
11.在开散列表上，每个地址单元所链接的同义词表( )
A.其键值相同
B.其元素值相同
C.其散列地址相同
D.其含义相同
12.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为
( )
A.磁道
B.块
C.柱面
D.桶
13.索引非顺序文件中的索引表是( )
A.非稠密索引
B.稠密索引
C.主索引
D.多级索引
14.对n 个记录的文件进行堆排序，最坏情况下的执行时间为( )
A.O(log 2n)
B.O(nlog 2n)
C.O(n)
D.O(n 2)
15.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序方法，以第一个记录为
基准得到的一次划分结果为( )
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
二、填空题（每小题2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16.下列程序段的时间复杂性的量级为_________。
for (i=1;i for(j=i;j t=t+1 17.设某非空单链表，其结点形式为， 若要删除指针q 所指结点的直接后继 p=q->next;________;free(p); 18.队列可以看成是一种运算受限制的线性表，也称为______线性表。 19.链栈的类型定义如下： { DateType date; struct node *next; }LStackTp; 若栈非空，则退栈操作可以用下列算法片段实现： p=ls;/* ls 为栈顶指针*/ *x=p->date; /*栈顶元素通过参数返回*/ ___________; free(p); /*释放原栈顶结点空间*/ 20.在非空树上，_____没有直接前趋。 21.设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有____个结点。 22.无向图中的连通分量定义为无向图的_________。 23.在开散列表上查找键值等于K 的结点，首先必须计算该键值的______，然后再通过指针查 找该结点。 24.对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找 所花费的平均时间大约减少_____。 25.若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二 叉树采用_________遍历法。 26.文件的基本存取单位是_________。 27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素a i 和a i+1的值，若a i 的值 大于a i+1的值，则交换a i 和a i+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。 28.在插入排序、快速排列、堆排序、归并排序中，排序方法不稳定的有_________。 三、应用题(本大题共5小题，共30分) 29.现有一组单词(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相应的散列函数值为(3，2，6， 3，2，5，6，0)，散列表长度为10(散列地址空间为0..9)，要求：(6分) (1)构造该闭散列表，并用线性探测法解决冲突； (2)若对每个元素查找一次，求总的比较次数。 30.已知无向图G 的邻接矩阵如下。假设对其访问时每行元素必须从右到左，请画出其所有的 连通分量，并且写出按深度优先搜索时各连通分量的访问序列。(8分) 4 321043 2 1 v v v v v 0001000001000101010001000v v v v v ???????????????? 31.设要将序列(Q ，H ，C ，Y ，P ，A ，M ，S ，R)按字母升序排序，请画出采用堆排序方法时 建立的初始堆及第一次输出堆顶元素后筛选调整以后的堆。(8分) 32.设二叉树后根遍历的结果为BCA ，画出所有可得到这一结果的二叉树。(5分) 33.设有一循环队列sq.data ［maxsize ］,一般情况下队列中至多可存放多少个元素?为什么?(3 分) 四、设计题(本大题共2小题，共14分) 34.设有两个按升序排列的单链表X 和Y ，其头指针分别为p,q 结点结构说明如下： { int data; struct nodel *next }node; 试设计一个算法void concat(node *p,*q)将它们合并成一个以p为头指针的单链表Z，使其仍然有序。(6分) 35.设有序表r长度为n，欲在表中查找键值为Kn的某元素。若查找成功，则返回该元素在 有序表r中的位置，若不成功，则返回0值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下：(8分) typedef struct { keytype key; Elemtype data; }rec; typedef struct { rec item［maxsize+1］; int n; }sqtable; 全国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 页） 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的满二叉树进行层序遍历时，队列中所出现的元素个数最多是 全国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．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 全国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 ) 全国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) 第一张概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。 ??????????????????????精品自学考料推荐?????????????????? 全国 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 2004----01 16下列程序段的时间复杂性量级是____0(n*i)_________。 for (i=1;i 全国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.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 第一概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。 我想在自考将要来临之际,为各位正在忙碌复习当中的自考学友们,提供一点复习思路,以便能顺利通过10月份的考试.下面就是我的一点复习心得和总结,希望能对你有所帮助! "如果你想通过数据结构导论这门课,至少得看两遍书吧?" 第一遍就是粗略的看一下,这样你心里也就有了底,也就大概的了解了数据结构导论 这门课所讲的内容,并且那里是考点在头脑里也就都有了大致的把握,这样,你就可以带着相应的重点,去重点把握你觉得重要的东西了!不过其实你到现在如果连一遍也没看过呢,也没关系,我下面的总结就是希望能对这些还没看过书的人,有所帮助! 下面就列出一些我觉得是重点的东西: 1,线性表,这一章整个都比较重要,因为这一章中关于线性表的顺序实现和链接实现及在上面的基本运算,在最后考试中很有可能以多种形式的考法出现(如:选择,填空,应用及程序设计等).并且由于这一章是整本书的基础,所以考试时占的比重会比较大,最后的程序设计题很可能就从这一章里出一道甚至两道都从这章里出(一道程序设计题6分).这一点是我在作过大量模拟试题和分析了历年试卷的基础上得出的结论,应当比较有参考价值.在这一章中有一个知识点应引起大家的注意,就是链式存储结构,因为这种存储结构在以后的各章中对于各种结构的实现(如:树,图等)都比较有用且实用.所以对于它的掌握应当达到"综合应用"的等级!(一点建议:如果你在第一次看的时候遇到了自己不懂的问题,可以先尝试着跳过去看后面的,等后面的看完了,再回过头看不会的这一段,问题就可能迎刃而解了!^>,中国水利水电出版社,宁郑元主编一书)只要知道它的各种运算及结果就可以了(考试时也就这么考了:--P) 如:DELETE ("ACABA",3,3)=? 结果为:"AC" 又如:SUBSTR("ABBCA",2,2)=? 结果为:"BB" 2,栈,队列和数组:这一章里你要掌握的东西就比较简单了(如果你掌握了上一章的内容对于这一章来讲,基本上就没有难题了)这一章里你要牢记两个概念:关于栈和队列的修改原则:(1),栈,后进先出,所有操作都是在栈顶进行的.(2),队列,先进先出,插入运算只能在对尾进行,删除运算只能在对头进行!且注意对头指针指示对头元素在数组中实际位置的前一个位置;实现递归调用属于栈的应用! 再附上关于栈和队列的几道例题如下: 1,运算(*作)是数据结构的一个重要方面,试举一例,说明两个数据结构的.逻辑结构和存储方式完全相同,只是对于运算(*作)的定义不同,因而两个结构具有显著不同的特性,是两个不同的结构. 2014年10月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码02142) 本试卷共5页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡"的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。 1．下列算法的时间复杂度为B 2．根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即 A．集合、顺序结构、树形结构、图结构 B．集合、线性结构、链式结构、图结构 C．集合、线性结构、树形结构、图结构 D．线性结构、顺序结构、链式结构、图结构 3．在表长为101的顺序表中做删除运算，平均移动元素的次数为 A．25 B．50 C．5l D．100 4．在表长为n的顺序表中做插入运算的时间复杂度为A 5．单链表与顺序表相比，其特点是 A．运算算法实现简单 B．便于随机存取数据 C．不需要预先分配存储空间 D．结点个数受到限制 6．关于链栈的说法，正确的是 A．链栈不用预先考虑容量的大小 B．链栈出栈时不需要判断栈空 C．链栈进栈时需要判断栈满 D．链栈出栈时需要判断栈满 7．循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为 A．rear=rear+1 B．rear=(rear+1)％(m一1) 第一章概论 1，数据表示：将数据从机外表示转化为机内表示。变化过程：机外表示->逻辑结构->存储结构。 2，数据处理：计算机执行对机内表示的数据的各种操作从而实现处理要求，得到所需结果。 过程：处理要求->基本运算和运算->算法 3，计算机专业人员的两项基本任务：数据表示和数据处理。 4，从数据结构观点看，通常的数据分为三个层次：数据、数据元素、数据项。 5，凡能被计算机存储、加工的对象通称为数据。 6，数据元素是数据的基本单位，具有完整确定的实际意义，又称为元素，结点，顶点或记录。 7，数据项是数据的不可分割的最小单位，不具备完整确定的实际意义，又称字段、域。数据元素由数据项组成。8，逻辑关系是指数据元素之间的关联方式或称邻接关系 9，数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。 10，数据逻辑结构四种基本形式：集合、线性结构、树形结构、图状结构。 11，集合：任何两个结点之间都没有逻辑关系，组织形式松散。 12，线性结构：结点按逻辑关系依次排列成一条锁链。 13，树形结构：具有分支、层次特点，其形态类似自然界中的树。 14，图状结构：各个结点按逻辑关系相互缠绕，任何两个结点都可以邻接。 15逻辑结构与数据元素本身形式、内容无关。逻辑结构与数据元素相对位置无关。逻辑结构与结点个数无关。 16，在数据的逻辑结构上规定的某种操作称为运算。运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象，以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。 17，运算两种基本类型：加工型运算和引用型运算。查找：找出满足某条件的结点在逻辑结构中的位置。 读取：读出某逻辑结构中指定位置的结点的内容。插入：在某逻辑结构中指定位置增加一个新结点。 删除：撤销某逻辑结构中指定位置的结点。更新：修改某逻辑结构中指定位置的结点内容。 18，数据结构中将数据的组织形式（逻辑结构）和对数据的操作方式（基本运算）作为一个整体来看待。 19，存储实现的目的是建立数据的机内表示。建立的数据的机内表示称为数据的存储结构。 20，一个存储结构分为三个部分：存储节点，数据元素之间的关联方式，附加设施。 21，四种基本存储结构：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。（理解四种形式） 22，算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。一个算法规定了求解给定问题所需要的所有处理步骤及其执行顺序，使得给定类型的任何问题都能在有限时间内被机械的求解。 23，任何算法都是用某种语言加以描述的。三类：程序（计算机语言描述算法），伪语言算法，非形式算法。 24，非形式算法：用自然语言同时可能还使用了程序设计语言或伪语言描述的算法。 25，评价算法的4个方面：正确性，易读性，健壮性，高效性。高效性是指算法的时间性能和空间性能。 1、章节作业 第一章概论 1．设计算法在整型数组A[n]中查找值为K的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。 int search (int A[],int n,int k) { int i; i=0; while (i<=n-1) if (A[i]!=k) i++; else break; if (i<=n-1) return I; else return -1； } 当查找成功时，A[i]与k比较次数≤n；当查找不成功时，A[i]与k比较n次，所以，算法时间复杂度T(n)=O(n)。 2．写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。 void matrixmultiply (int A[][n],int B[][n],int C[][n],int n) { int I,j; for (i=0;i } 以方阵阶数n作为输出规模。可知第二层循环中的第一条赋值语句共执行n2次，第三层循环体中的乘法和赋值语句共执行n3次，所以此算法的计算量为n3+n2，算法时间复杂T(n)=O(n3) 第二章线性表 1．设带头结点的单链表的结点结构如下： struct node { DataType data； struct node *next； } Node， *LinkList； 试编写一个函数int count(LinkList head，DataType x)统计单链表中数据域为x的结点个数。 int count(LinkList head,DataType x) { LinkList p=head->next; Int m=0; while (p!=NULL) { if(p->data==x) m++; p=p->next; } return m; } 2．试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表 (a 1，a 2 ，…，a n )逆置为(a n ，a n-1 ，…，a 1 )。 顺序表逆置算法 2016年10月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共4页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间。超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共10小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．已知问题规模为n，则下列程序片段的时间复杂度是C 2．若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是 A．栈 B．队列 C．树 D．图 3．若线性表采用链式存储结构，则适用的查找方法为 A．随机查找 B．散列查找 C．二分查找 D．顺序查找 4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在S所指结点之后插入上述单链表应执行的语句为 A．q→next；s→next；s→next2P； B．s→next=P；q→next=s→next； C．p→next=s→next；s→next=q； D．s→next2q；p→next2s→next； 5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是 A．abed B．dcba C．cabd D．bcda 6．在实现队列的链表结构中，其时间复杂度最优的是 A．仅设置头指针的单循环链表 B．仅设置尾指针的单循环链表 C．仅设置头指针的双向链表 D．仅设置尾指针的双向链表 7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是 A．不一定相同 B. 都相同 C．都不相同 D．互为逆序 8．若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是 全国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自考数据结构导论20051年10月试卷
02142数据结构导论201604
全国自学考试数据结构导论试题及答案(4套)
自考数据结构导论复习资料
自考数据结构导论
全国数据结构导论10月高等教育自学考试试题与答案
自考02142《数据结构导论》串讲笔记
2020年10月全国数据结构导论自考试题及答案解析.doc
数据结构导论填空题目汇总
自考数据结构导论20120年01月试卷
自考02142《数据结构导论》串讲笔记
自考02142《大数据结构导论》串讲笔记
“数据结构导论”的学习方法
02142数据结构导论201410试题及答案
数据结构导论2142复习资料
数据结构导论作业一
02142数据结构导论201710月份真题和答案解析
1月全国自考数据结构导论试题及答案解析
自考数据结构导论20030年01月试卷
- 全国数据结构导论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月全国自考数据结构导论试题及答案
- 自考数据结构导论复习资料