自学考试数据库结构

考核要求：达到“领会” 层次知识点：有关体系结构的各种概念 1.4.1 三级模式结构数据库的体系结构 分为三级：内部级、概念级和外部级 （数据抽象的三个级别） （1） 外部级：单个用户所能看到的数据特性；单个用户使用的数据视图的描述称外模式。 （最接近用户） （2）概念级：涉及到所有用户的数据定义，是全局的数据视图；全局数据视图的描述称“概念模式”。 （3）内部级：最接近于物理存储，涉及到实际数据存储的结构；物理存储视图的描述称为“内模式”。 1.4.2 三级结构和两级映象（进一步理解三级模式的具体含义，并掌握两个映象。） 数据按外模式的描述提供给用户，按内模式的描述存储在磁盘中， 而概念模式提供了连接这两级的相对稳定的中间观点，并使得任何一级的改变都不受另一级的牵制。 （1）概念模式 （模式）：具体含义；（模式DDL） （2）外模式：具体含义；（外模式DDL） 外模式又称为“用户模式”或“子模式”，通常是概念模式的逻辑子集。 （3）内模式：具体含义；（内模式DDL） （4）模式/内模式映象：用于定义概念模式和内模式之间的对应性。一般在内模式中描述。 （5）外模式/模式映象：用于定义外模式和概念模式间的对应性。在外模式中描述。 1.4.3 两级数据独立性 （1） 物理数据独立性：修改内模式时尽量不影响概念模式及外模式。 （2） 逻辑数据独立性：修改概念模式时尽量不影响外模式和应用程序。 1.4.4 用户及用户界面用户界面定在外部级上。 了解以下概念：DML， 宿主型DML、自含型DML、数据库模式、数据库；数据库模式可以理解为数据库结构，而非数据库本身。

这两本我都学过.自考的数据结构导论是用C语言来描述的,需要有对应课程高级程序语言(一)的基础,也就是要懂的C..如果有数学基础更好,没有也可以硬着头皮啃,这本比较难.至于数据库及其应用是作为数据结构导论的后继课程的..不过这门比较简单,不会数据结构问题也不大,也不需要任何的语言基础..用的是access数据库.兄弟加油!.

数据结构自考题库

【免费定制个人学历提升方案和复习资料： 】广东自已可以的学校有哪些深圳大学、暨南大学、广州大学、惠州学院、广东工业大学、广东财经大学、广东药科大学、华南理工大学、华南师范大学、华南农业大学、南方医科大学、广东白云学院、广东外语外贸大学、广东技术师范学院、广东石油化工学院、佛山科学技术学院、江门职业技术学院、深圳职业技术学院、广东第二师范学院、广州美术学院、城市学院、广东省外语艺术职业学院。自考学校下方免费学历提升方案介绍： 2017年10月自考02331数据结构真题试卷 格式：PDF大小：421.98KB 2017年04月自考00292市政学真题试卷 格式：PDF大小：342.08KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：

【免费定制个人学历提升方案和复习资料： 】自考本科金融学专业培养具有全球视野，系统掌握金融知识和金融理论，具备金融实务专业技能，具有较强的社会适应能力，胜任银行、证券、保险等金融机构及政府部门和企事业单位的专业工作，具有深厚理论功底、精湛专业技能、良好综合素质和优秀人格品质的创新型金融人才。自考本科金融管理专业主要学习货币银行学、国际金融、证券、投资、保险等方面的基本理论和基本知识，受到相关业务的基本训练，具有金融领域实际工作的基本能力，培养管理学、法学与经济学兼修，掌握管理学、法学和经济学的基本知识和业务技能，能在银行、证券、投资、保险及其他经济管理部门和企业从事相关工作的专门人才。下方免费学历提升方案介绍： 2015年10月自考02331数据结构真题试卷 格式：PDF大小：394.82KB 2018年10月自考02331数据结构真题试卷 格式：PDF大小：402.97KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：

数据结构自考题库推荐

全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; inext==head B. p->next->next==headC. p->next==NULL D. p==head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A. SXSSXXXX B. SXXSXSSXC. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ ）A. 串的长度相等 B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）A. head (tail (head (L))) B. head (head(head(L)))C. tail (head (tail (L))) D. head (head (tail (L)))7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1C. 48 D. 498.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）A. Dout B. Dout-1C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）A. 3 B. 4C. 5 D. 610.如图所示的带权无向图的最小生成树的权为（ ）A. 51 B. 52C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）A. O（log2n） B. O（1）C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）A. 插入排序 B. 冒泡排序C. 快速排序 D. 归并排序13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ ）A. T[2] B. T[4]C. T[8] D. T[10]14.适宜进行批量处理的文件类型是（ ）A. 顺序文件 B. 索引顺序文件C. 散列文件 D. 多关键字文件15.VSAM文件的索引结构为（ ）A. B+树 B. 二叉排序树C. B-树 D. 最优二叉树二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 倍。17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 。19.字符串“sgabacbadfgbacst” 中存在有 个与字符串“ba”相同的子串。20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 。21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为{,,,,,}，该树的度是 。22.n个顶点且含有环路的无向连通图中，至少含有 条边。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 结构也无特殊要求。25.顺序文件中记录存放的物理顺序和 顺序一致。三、解答题(本大题共4小题，每小题5分，共20分)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列：后序序列：27.图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct node {int adjvex;struct node *next;}EdgeNode;typedef struct {VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct {AdjList adjlist;int n, e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。题27图28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13，A37，F43，B32，B47，E12，F37，B12第一趟：第二趟：第三趟：29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。（1）（2）四、算法阅读题（本大题共4小题，每小题5分，共20分）30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) {int i,j;for (i=j=0;ilength; i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i];j++；}L->length=j;}(1)(2)31.阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) {int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q)) {e=DeQueue (Q);if (e>=0) EnQueue (Q1,e);else EnQueue (Q2,e)}}（1）（2）32.阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；（2）简述算法f32的功能。int f32 (char*s){int i, n, inword;n=inword=0;for (i=0;s[i]!=’\0’;i++)if (s[i]!=’⊔’&& inword==0){inword=1;n++;}else if (s[i]==’⊔’&& inword==1)inword=0;return n;}（1）（2）33.阅读下列对正整数关键字序列L操作的算法，并回答问题：（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；（2）简述函数f33的功能。int Partition (SeqList*L, int low, int high);‖对L[low..high]做划分，返回基准记录的位置，并使左部的关键字‖都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字int f33 (SeqList L, int k){int low, high, pivotpos;low=1;high=L.length;if (khigh)return-1;do {pivotpos=Partition (&L, low, high);‖调用快速排序的划分算法if (pivotposk)high=pivotpos-1;}while (pivotpos!=k);return L.data [pivotpos];}（1）（2） 五、算法设计题（本题10分）34.二叉排序树的类型定义如下：typedef struct BSTNode {‖ 二叉排序树的结点结构int data; ‖数据域struct BSTNode *lchild, *rchild; ‖左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。

链式存储结构的特点是借助_指示数据元素地址的指针______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___存放形式________。

自考题库及答案可以登录查找。作为专门的在线教育平台，的备考指导栏目就专门收录有自考的历年真题和模拟练习题，还有备考的知识点指导。点击底部咨询官网。 自考怎么复习？ 1、根据自考大纲泛读教材，找好考试重点 了解了自考的考试大纲以后，需要分清知识点的主次，可以让自己较大程度的提高自己学习的效率。 2、依次熟悉题型 对自考教材的知识有了一定把握以后，就可以开始完成刷题做题。在第一次开始完成自考题型的时候，可以先翻开自考资料，将自考科目的每个题型都依次熟悉一遍。了解每个学科对应的是哪些题型，再对每个题型进行多次练习。 3、分析标准答案 在做完一套自考练习之后，可以在校对答案的时候，要学会自己分析自考的参考答案。 有些考生在完成问题后，很少分析答案是如何得到的，这样的学习效果不好。 分析自考的标准答案可以增强对知识点的记忆，避免盲目陷入问题的海洋。 4、做历年真题，了解分值 每个考生都尽量完成一套历年的试题，了解分数的分布，这有利于我们合理分配好自考学习的时间。自考/成考有疑问、不知道如何总结自考/成考考点内容、不清楚自考/成考报名当地政策，点击底部咨询官网，免费领取复习资料：

自学考试数据结构

02142自考数据结构导论今天我们的教务老师给同学来讲讲以下这些问题，如果你觉得还不错，可以收藏我们网站哦，我们专注于自学考试教材购买服务网哦，接下来一起来阅读下面的正文吧！一、什么是02142自考数据结构导论02142自考数据结构导论是一门数据结构课程，是针对自学考试（自考）考生设计的一门课程，是由中国自学考试网络中心制定的一门数据结构课程，课程编号为02142。该课程旨在帮助学生掌握数据结构的基础理论，并能够应用数据结构解决实际问题。二、02142自考数据结构导论的主要内容02142自考数据结构导论的主要内容包括：数据结构的概念与分类、线性表、栈与队列、树与二叉树、图、查找与排序、哈希表、字符串匹配算法等。三、02142自考数据结构导论的学习要求02142自考数据结构导论的学习要求主要是要求学生掌握数据结构的基本概念、基本原理和基本算法，能够熟练掌握数据结构中的常见算法，并能够运用数据结构解决实际问题。四、02142自考数据结构导论的考试形式02142自考数据结构导论的考试形式主要是采用闭卷考试的形式，考试内容主要包括理论知识和实际应用，考试时间为90分钟，满分100分。五、02142自考数据结构导论的学习方法02142自考数据结构导论的学习方法主要有以下几点：1、充分理解数据结构的基本概念、基本原理和基本算法；2、熟练掌握数据结构中的常见算法；3、多练习，熟练掌握数据结构的应用；4、注意把握考试的重点，掌握考试的规律。六、02142自考数据结构导论的重要性02142自考数据结构导论是一门重要的课程，它不仅可以帮助学生掌握数据结构的基本概念、基本原理和基本算法，而且还可以帮助学生掌握数据结构中的常见算法，并能够运用数据结构解决实际问题，这对于学生的今后学习和工作具有重要的意义。自考/成考有疑问、不知道自考/成考考点内容、不清楚当地自考/成考政策，点击底部咨询官网老师，免费领取复习资料：

第六章 树 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结点）；除根外的分支结点称内部结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。 二叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，与度数为2的有序树不同。 二叉树的4个重要性质： ·。二叉树上第i层上的结点数目最多为2^（i-1）（i≥1）。； ·深度为k的二叉树至多有（2^k）-1个结点（k≥1）； ·。在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1； ·。具有n个结点的完全二叉树的深度为int（log2n）+1. 满二叉树是一棵深度为k，结点数为（2^k）-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点； 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树） 树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root确定的。共有2n个指针域，n+1个空指针。 根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。时间复杂度为O（n）。 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。 树和森林及二叉树的转换是对应的。 转换方法： ·树变二叉树：兄弟相连，保留长子的连线。 ·二叉树变树：结点的右孩子与其双亲连。 ·森林变二叉树：树变二叉树，各个树的根相连。 树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。 ·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。 ·双亲孩子链表表示法：将双亲链表和孩子链表结合。 ·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。 树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。 树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为二叉树（即哈夫曼树）。 在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。 哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。 哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的前缀码。 第七章 图 图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。 图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。 有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径； 网络：是带权的图。 图的存储结构： ·邻接矩阵表示法：用一个n阶方阵来表示图的结构是的，适合稠密图。 ·无向图：邻接矩阵是对称的。 ·有向图：行是出度，列是入度。 建立邻接矩阵算法的时间是O（n+n^2+e），其时间复杂度为O（n^2） ·邻接表表示法：用顶点表和邻接表构成不是的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。 ·无向图称边表； ·有向图又分出边表和逆邻接表； ·邻接表结点结构为 adjvex | next， 时间复杂度为O（n+e）。，空间复杂度为O（n+e）。。 图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。 最小生成树：图的生成树不，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树（MST）。 构造最小生成树的算法： ·Prim算法的时间复杂度为O（n^2）与边数无关适于稠密图。 ·Kruskal算法的时间复杂度为O（lge），主要取决于边数，较适合于稀疏图。 最短路径的算法：·Dijkstra算法，时间复杂度为O（n^2）。·类似于prim算法。 拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若 ∈E（G），则在线性序列u在v之前，这种线性序列称为拓扑序列。 拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。 ·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。 第八章 排序 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。 排序是使文件中的记录按关键字递增（或递减）次序排列起来。 ·基本操作：比较关键字大小；改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。 内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 插入排序：·直接插入排序： ·逐个向前插入到合适位置。 ·哨兵（监视哨）有两个作用： ·作为临变量存放R[i] ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为（n+2）（n-1）/2；移动次数为（n+4）（n-1）/2； ·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1. ·希尔排序是就地的不稳定排序。时间复杂度为O（n^1.25），比较次数为（n^1.25）；移动次数为（1.6n^1.25）； 交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为n（n-1）/2；移动次数为3n（n-1）/2； ·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O（nlog2n），比较次数为n（n-1）/2； 选择排序：·直接选择排序： ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O（n^2）。比较次数为n（n-1）/2； ·堆排序 ·建堆：按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。 ·堆排序是就地不稳定的排序，时间复杂度为O（nlog2n），不适宜于记录数较少的文件。 归并排序： ·先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止。 ·归并排序是非就地稳定排序，时间复杂度是O（nlog2n）， 分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O（n）。 ·基数排序：·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序，时间复杂度是O（d*n+d*rd）。 各种排序方法的比较和选择： ·。待排序的记录数目n；n较大的要用时间复杂度为O（nlog2n）的排序方法； ·记录的大小（规模）；记录大用链表作为存储结构，而快速排序和堆排序在链表上难于实现； ·关键字的结构及其初始状态； ·对稳定性的要求； ·语言工具的条件； ·存储结构； ·时间和辅助空间复杂度。 第九章 查找 查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。 衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。 线性表查找的方法： ·顺序查找：逐个查找，ASL=（n+1）/2； ·二分查找：取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N. ·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的关键字及其位置建立有序索引表。 二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ·若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ·左、右子树本身又是一棵二叉排序树。 二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n）。 二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。 ·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p. ·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。 关于B-树（多路平衡查找树）。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。 常见的散列函数构的造方法： ·。平方取中法：hash=int（（x^2）%100） ·。除余法：表长为m，hash=x%m ·。相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618 ·。随机数法：hash=random（x）。 处理冲突的方法：·开放定址法： ·一般形式为hi=（h（key）+di）%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1. ·开放定址法类型： ·线性探查法：address=（hash（x）+i）%m； ·二次探查法：address=（hash（x）+i^2）%m； ·双重散列法：address=（hash（x）+i*hash（y））%m； ·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。 ·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象； ·链表上的结点空间是动态申请的适于无法确定表长的情况； ·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间； ·拉链法构造的散列表删除结点易实现。 ·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。 第十章 文件 文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。 文件·逻辑结构是一种线性结构。 ·操作有：检索和维护。并有实时和批量处理两种处理方式。 文件·存储结构是指文件在外存上的组织方式。 ·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。 ·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。 检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。 顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。 一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。 顺序文件的插入、删除和修改只能通过复制整个文件实现。 索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。 索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。 若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。 索引顺序文件常用的有两种： ·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。 ·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。 散列文件 ·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。 ·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。 多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。 倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。

数据结构自学考试

五 实验及实习要求

课程设置的目的和意义数据结构是计算机专业本科学生必修的一门专业基础课 通过这门课程的学习 可以使学生掌握三类数据结构的表示与实现 并能将其应用实际问题的求解过程中 培养对问题分析 表示和实现的能力 为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础 本课程在本科生阶段的计算机专业基础课处于一个打基础的地位 本课程的前导课程为计算机科学导论 离散数学 C语言程序设计 学习完本课程后 学生应当能够独立分析 表示并求解基本的问题 设计具有一些小规模程序 学生通过自己动手设计数据结构 编制程序并实现 然后形成分析结果 可以使学生充分认识到课堂上所讲授的各种方法的涵义 体会到各种方法的优缺点 并进一步掌握用高级语言编程和训练对实际问题求解的方法

应达到的基本要求学生在进行完本实验课的教学后 应该能够掌握计算机问题求解中常见的数据结构的表示与实现 对于线性结构 树状结构和网状结构三类结构有明确的认识 能够设计比较简单问题的算法 并可以根据算法编制 调试运行相应的程序 可以对算法的复杂度进行估计与证明 能够编写 组织测试数据 根据实验结果作出算法的性能分布图 并对实验结果进行评价

教学文件及教学形式教学文件:数据结构教科书 讲义 实验报告学生自拟 实验环境:本实验可选用的高级语言为C/C++ 实验用机的硬件配置 软件环境自定

实验成绩评定每次实验的成绩按照 分制评分 实验课的总成绩将按一定比例结合到课程总成绩中

实验报告基本格式实验目的:同教材实验要求:同教材上机环境:硬件配置与软件环境(包括操作系统 编译器等) 完成时间:使用多少个小时来完成本题目 程序说明:使用文字和/或框图说明程序的基本结构程序清单:测试数据与测试结果:思考题:感想与建议:

课程设置：英语（二）、高等教学（工本）、计算机网络原理、离散数学、数据库系统原理、数据库系统原理（实践）、计算机系统结构、操作系统、操作系统（实践）。

中国近现代史纲要、马克思主义基本原理概论、概率论与数理统计（二）、软件工程、软件工程（实践）、数据结构、数据结构（实践）、C++程序设计，

C++程序设计（实践）、Java语言程序设计（一）、Java语言程序设计（一）（实践）、网页设计与制作、计算机通信接口技术、互联网及其应用、毕业考核（或论文\综合实践\实验\实习等）。

扩展资料：

中华人民共和国公民，不受性别、年龄、民族、种族和已受教育程度的限制，均可依照本条例的规定参加高等教育自学考试。

自学考试学习方式灵活、工学矛盾小、费用低，实行“宽进严出”，“教考分离”。

自学考试采用学分累计的方式逐步完成学业，学习者完成专业考试计划规定的全部课程并取得合格成绩，完成毕业论文或其他教学时间任务，思想品德鉴定合格者准予毕业取得相应毕业证书，国家承认其学历。

自学考试各专业课程一般分为公共课、专业基础课、专业课和选修课。一般专科专业的考试课程不少于15门，总学分不低于70学分；本科专业的理论考试课程门数不少于20门，总学分不低于125学分（不包括毕业论文、毕业设计的学分数）；

独立本科段专业的理论考试课程门数不少于10门，总学分不低于70学分（不包括毕业论文、毕业设计的学分数）。

自学考试的考试时间安排主要是上半年和下半年两次，上半年安排在四月下旬的第一个周六和周日，下半年安排在十月下旬的第一个周六和周日。

参考资料来源：电子科技大学继续教育学院-招生专业简介

参考资料来源：中国教育考试网-高等教育自学考试暂行条例