数据结构习题
一、单项选择题
1.下面程序段的时间复杂度为( C ) 。
for(int i=0; i for(int j=0; j a[i][j]=i*j; A． O(m2) B． O(n2) C． O(m*n) D． O(m +n) 2.设有一个递归算法如下 int fact(int n){//n大于等于0 if(n<=0) return 1； else return n*fact(--n)； } 则计算fact(n)需要调用该函数的次数为( D )次，不计 fact(n)。 A．n B．n+1 C．n+2 D．n-l 3.评价排序算法好坏的标准主要是(D)。 4.A．执行时间 B．辅助空间 5.C．算法本身的复杂度 D．执行时间和所需的辅助空间 6.在需要经常查找结点的前驱与后继的场合中，使用( B )比 较合适。 收集于网络，如有侵权请联系管理员删除 7. A．单链表 B．双链表 C．顺序表 D．循 环链表 8.在一个单链表HL中，若要删除由指针q所指向结点的后继 结点，则执行（ C ）。 A．p = q->next ; p->next = q->next; B．p = q->next ; q->next = p; C．p = q->next ; q->next = p->next; D．q->next = q->next->next; q->next = q; 9.已知单链表A长度为m，单链表B长度为n，若将B联接在 A的末尾，其时间复杂度应为( B )。 A．O(1) B．O(m) C．O(n) D．O(m+n) 10.链表不具有的特点是（ A ）。 11. A．可随机访问任一元素 B．插入删除不需要移动元 素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比 12.若要在单链表中的结点*p之后插入一个结点*s，则应执 行的语句是( A )。 收集于网络，如有侵权请联系管理员删除 A．s->next=p->next; p->next=s; B．p->next=s; s- >next=p->next; C．p->next=s->next; s->next=p; D．s->next=p; p- >next=s->next; 13.假定一个链式队列的队头和队尾指针分别为front和 rear，则判断队空的条件为 ( D )。 A．front==NULL B．front!=NULL C．rear!=NULL D．front= =rear 14.栈和队列都是（C）。 A．链式存储的线性结构 B．顺序存储的线性结构 C．限制存取位置的线性结构 D．限制存取位置的非线性结构 15.对于给定的结点序列abcdef，规定进栈只能从序列的左端 开始。通过栈的操作，能得到的序列为（ A ）。 A．abcfed B．cabfed C．abcfde D．cbafde 16.队列通常采用两种存储结构是( A )。 17. A．顺序存储结构和链表存储结构 B．散列方式和索引 方式 收集于网络，如有侵权请联系管理员删除 18. C．链表存储结构和数组 D．线性存储结构和非线 性存储结构 19.若让元素1，2，3依次进栈，则出栈次序不可能出现 （C）种情况。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 20.若一个串非空，子串的定位操作通常称为( C )。 A. 串的长度 B.原串的子串 C.串的模式匹配 D.串的连接 21.设有一个n×n的对称矩阵A，将其上三角部分按行存放在 一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中( C )处。 A．(i+3)*i／2 B．(i+1)*i／2 C．(2n-i+1)*i／2 D．(2n-i-1)*i／2 22.在( C )运算中，使用顺序表比链表好。 23.A．插入 B．删除 C．根据序号查找 D．根据元素 值查找 24.带头结点的单链表head为空的判断条件是( C )。 收集于网络，如有侵权请联系管理员删除 25.A．head= =NULL B．head->next= =NULL C．head->next=head D．head!=NULL 26.设一个链表最常用的操作是在末尾插入结点和删除尾结 点，则选用（ C ）最节省时间。 A）单链表 B）循环链单表 C）带尾指针的循环链单表 D）带头结点的双循环链表 27.栈的插入与删除操作在（ A ）进行。 A．栈顶 B．栈底 C．任意位置 D．指定位置28.设一个栈的输入序列为A、B、C、D，则借助一个栈所 能得到的输出序列不可能是（ D ）。 29.A．ABCD B．DCBA C．ACDB D．DABC 30.在一个链队中，假设F和R分别是队首和队尾指针，则 删除一个结点的运算是( C )。 31.A．R=F->next; B．R=R->next; C．F=F- >next; D．F=R->next; 32.串是一种特殊的线性表，其特殊性体现在( B )。 33.A．可以顺序存储 B．数据元素是一个字符 收集于网络，如有侵权请联系管理员删除 34.C．可以链接存储 D．数据元素可以是多个字符 35.以下说法正确的是（ C ）。 A）空串与空格串是相同的 B）“fox”是“FoxBase”的子串 C）空串是零个字符组成的串 D）空串长度等于1 36.若n为主串长，m为子串长（m 算法最坏情况下，需要比较字符总数是（ C ）。 A．m B．m(n-m+1) C．n*m D．(n-m)*(m-1) 37.将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维 数组B[1..298]中，A中元素A[66，65]在B数组中的位置k 为（ B ）。 A）198 B）195 C）197 38.一个稀疏矩阵的转置矩阵应是（ B ）。 A.下三角矩阵 B．稀疏矩阵C．非稀疏矩阵 D．有时为稀疏矩阵 39.广义表（（e））的表头是（ C ）。 A）e B）( ) C）(e) D）((e)) 40.深度为5的二叉树至多有( C )个结点。 41.A．16 B．32 C．31 D．10 收集于网络，如有侵权请联系管理员删除 42.具有10个叶子结点的二叉树中有（B）个度为2的结 点。 A．8 B．9 C．10 D．11 43.在二叉树的中序遍历递归算法中，顺着搜索路径，在第 ( B )次经过结点时作访问操作。 44.A．1 B．2 C．3 D．4 45.在中序线索二叉树中，若某结点有右孩子，则该结点的直 接后继是( D )。 46. A 左子树的最右下结点 B 右子树的最右下结点 47. C 左子树的最左下结点 D 右子树的最左下结点 48.按照二叉树的定义，具有3个结点的二叉树有( C )种形 态。 A．3 B．4 C．5 D．6 49.某二叉树的先序序列和后序序列正好相反，则该二叉树一 定是（B）的二叉树。 50.A．空或只有一个结点 B．高度等于其结点数 51.C．任一结点无左孩子 D．任一结点无右孩子 52.图的广度优先搜索类似于树的( D )次序遍历。 收集于网络，如有侵权请联系管理员删除 A．先根 B．中根 C．后根 D．层次 53.n个顶点的强连通图中至少含有( B )。 A．n-l条有向边 B．n条有向边 C．n(n-1)/2条有向边 D．n(n-1)条有向边 54.任何一个无向连通图的最小生成树（B）。 55. A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 56.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含 V1，E2包含E1，则称( A )。 57.A．G1是G2的子图 B．G1是G2的连通分量 58.C．G2是G1的连通分量 D．G2是G1的子图 59.下面关于图的存储的叙述中，哪一个是正确的。 ( A ) 60.A．用邻接矩阵法存储图,占用的存储空间数只与图中结点 个数有关,与边数无关 61.B．用邻接矩阵法存储图,占用的存储空间数只与图中边数 有关,与结点个数无关 62.C．用邻接表存储图，占用的存储空间数只与图中结点个 数有关，与边数无关 收集于网络，如有侵权请联系管理员删除 63.D．用邻接表存储图，占用的存储空间数只与图中边数有 关，与结点个数无关 64.( D )适合用邻接表表示。 65.A．稠密图 B．有向完全图 66.C．无向完全图 D．稀疏图 67.一般，图的DFS生成树的高度( C )BFS生成树的高度。 68.A．小于 B．等于 C．大于 D．小于或等于 69.从一棵二叉排序树中查找一个元素时，其平均时间复杂度 为( C )。 A．O(1) B．O(n) C．O(1og2n) D．O(n2) 70.二分查找法要求查找表中各元素的键值必须是( A )排列。 71. A．递增或递减 B．递增 C．递减 D．无序 72.向具有n个结点的、结构均衡的二叉排序树中插入一个元 素的时间复杂度为 ( B )。 A．O(1) B．O(log2n) C．O(n) D．O(nlog2n) 73.线性表必须是( D )，才能进行二分查找。 74.A．用向量存储的线性表 B．用链表存储的有序表 75.C．用链表存储的线性表 D．用向量存储的有序表 收集于网络，如有侵权请联系管理员删除 龙源期刊网 https://www.doczj.com/doc/8817280844.html, 案例教学法在数据结构教学中的应用 作者：王星捷李春花 来源：《教育界》2013年第03期 【摘要】案例教学法是一种运用实际案例进行教学的方法。本文作者结合具体教学实 践，就数据结构采用案例教学法开展教学活动进行了探讨和实践。 【关键词】案例教学法数据结构 案例教学法可促使学生学会学习。案例教学法是开放的、发展的。在案例教学中，通过有意识的引导，让学生自主查资料、学习，通过个体独立或群体合作的方式做出分析和判断，积极寻找多种解决方案。经过多次的积淀后，培养了学生自主学习的方法，锻炼了学生分析问题和解决问题的能力。 1 案例教学法对数据结构的重要性 数据结构重在训练学生的思考问题和解决问题的能力，教学的目的是训练理论联系实践，解决实际生活中出现的实际算法问题。每一个案例都是数据结构算法中的具体应用实体，教学关键是要调动学生积极参与探索知识的活动，开动大脑，积极思维。 目前众多的大学院校采用了案例教学法，但是学生课后，对数据结构中的算法仍然是似懂非懂，十分茫然。具体表现在： （1）教学内容与实际算法应用联系不够，环境真实性不够。很多还停留在基础性算法教学，与实际应用的真正内涵差距明显，不能达到教学效果。 （2）教材与实际应用有差距。教材要尽量与实际算法案例相结合，贴近实际。但很多的教材类似于算法字典。我们都清楚教材在教学中有极其重要的地位，因此教材的质量非常重要。教材不仅是算法字典，而是根据实际生活中需要解决的算法问题而进行设计，拥有很强的实用性。不能用纯理论的说教压给学生。 （3）教学体系建设缺乏科学性，实际操作性不强。仅仅局限于简单的教学是不能让学生整体的职业素质得到大幅度提高的，还必须向学生提供实用的教学体系。教学中的知识要符合用人单位的人才需求，在教学体系建设中可参考市场上实际的软件公司的人才需求情况，同时对教师进行更高层次的师资培训。 从这些问题及与现实接轨的矛盾可以看出，案例教学法更显其重要地位。推行案例实训教学，可以再提高教学效果。 2案例教学法在数据结构中的具体实施 《数据结构》教学纲要(doc 9页) 《数据结构》教学大纲 2001年9月 一、开课系（部）：经济信息管理系 二、教学对象：信息管理与信息系统专业本科 三、教学目的： 数据结构是高等教育计算机信息管理专业中的一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。 四、教学要求： 1. 从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构。 2. 掌握在各种常用的数据结构上实现的排序和查找运算。 3. 对算法的时间和空间复杂性有一定的分析能力。 4. 针对简单的应用问题.应能选择合适的数据结构及设计有效的算法解决之。 五、教学课时： 教学内容课内学时 第1章绪论 2 第2章线性表 4 第3章栈和队列 6 第4章串 4 笫5章数组和广义表 4 第6章树和二叉树 6 第7、8章略 第9章查找 4 第10章内部排序 4 课程总复习 2 六、考核形式： 期末考试与平时讨论相结合（80%和20%）。 期末试卷结构： 单项选择填空简答应用算法设计 20 15分20分15分30分 态。 3.3 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 第2章线性表 (一)课程内容 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较 (二)学习目的与要求 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 (三)考核知识点与考核要求 1. 线性表的逻辑结构，要求达到“识记”层次。 1.1 线性表的逻辑结构特征。 1.2 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。 2. 线性表的顺序存储结构.要求达到“综合应用”层次。 2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 2.2 顺序表上的插入、删除操作及其平均时间性能分析。 2.3 利用顺序表设计算法解决筒单的应用问题。 3. 线性表的链式存储结构，要求达到“综合应用”层次。 3.1 链表如何表示线性表中元素之间的逻辑关系。 3.2 链表中头指针和头结点的使用。 3.3 单链表、双链表、循环链表链接方式上的区别。 3.4 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 3.5 循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。 3.6 双链表的定义及其相关的算法。 3.7 利用链表设计算法解决简单的应用问题。 4.顺序表和链表的比较.要求达到“领会”层次。 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 《数据结构》教学大纲 课程性质专业必修课 课程名称数据结构课程编号*04069 适用专业计算机科学与技术/软件工程开课学期第3学期 总学时64 理论50 学分数 4 实践14 一、课程性质与目标 数据结构课程属于专业必修课。通过本课程数据结构的学习，学生应实现如下目标： 1.知识目标：本课程主要讲述线性表、栈、队列、字符串、数组、树、二叉树、图、查找表、内部排序等常用数据结构的基本概念、操作及其典型应用例子。通过本课程的学习，应使学生掌握数据结构的概念及不同的存储结构、掌握一些典型算法原理和方法，且能够在不同存储结构上实现编程，同时，对于算法设计的方式和技巧也有所体会。 2.能力目标 （1）独立获取知识的能力——逐步掌握科学的学习方法，不断地扩展知识面，增强独立思考的能力，更新知识结构； （2）科学观察和思维的能力——运用数据结构的基本理论，熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 （3）分析问题和解决问题的能力——学会利用数据结构原理分析实际问题，提高发现问题与解决问题的能力。对部分优秀的学生，培养其在知名程序设计在线评测系统（如POJ等）中求解实际问题的能力。 （4）求实精神——通过数据结构理论课程教学，培养学生严谨求实的科学态度和刻苦钻研的作风。 （5）实践能力——通过学习，有意识地培养学生编写高质量、高效率程序的能力和风格。 3.素质目标：使学生具备一定的计算思维，热爱算法设计和程序实现，面对实际问题能转换为计算机能够求解的过程并选择合适的数据结构，设计出在时间和空间上具备一定高效率的程序，培养学生学习算法设计与实现的细心和耐心，培养学生坚韧不拔，攀登技术高峰的优秀品质。让部分优秀的学生热爱上湖南省大学生程序设计竞赛，体会ACM程序设计竞赛的魅力。 二、课程教学基本要求 课程前应该认真预习，特别是前导课程相关知识体系; 课中应该认真听课，参与教学过程中的互动、回答问题及联系实际编程; 课后积极做好复习、认真完成作业及课程设计相关实践教学的环节。作业应具备一定实用性的数据结构和算法实现为主，对部分优秀学生，引入一定量的知名程序设计在线评测系统（如POJ等）中与数据结构相关的题目进行编程并在线提交验证正确性与时间、空间效率。 三、教学内容与学时分配 《数据结构》教学设计方案 1 课程的一般信息 1.1 教学对象 计算机科学与技术专业2012级本科学生 1.2 课程名称 《数据结构》 1.3 课程教材及分析 1.3.1 中文教材及分析 数据结构(C语言版)，严蔚敏，北京：清华大学出版社(国家精品课程配套教材)，2011.11。 该教材为国内关于数据结构最知名的教材之一，受到国内计算机教育界广泛的认可。 1.3.2 教材选取的背景 选取本教材的原因主要是受到本人对于该课程的教学改革驱动，在该课程教学中强调实践性，注重理论联系实际。 1.4 课程类型 专业必修课（开设时间为计算机科学学院各专业本科生二年级第一学期） 1.5 教师的基本信息 肖冰，1981年生，博士，讲师，计算机科学学院。主要研究方向为模式识别、机器学习、智能信息处理等。博士毕业后从事一线教学和科研工作，主讲了《计算机基础》、《ACCESS 数据库应用技术》，《数据结构》、《数据库原理与设计》及相关课程设计等课程。在Pattern Recognition（SCI二区）、Neurocomputing（SCI三区）、Signal Processing（SCI三区）、电子学报（中、英文版）等国际、国内权威期刊和会议上发表论文15篇，其中SCI检索6篇，EI检索9篇，在重要期刊上发表教学论文一篇。主持国家博士后科学基金、陕西省博士后科学基金、陕西师范大学中央高校基本科研业务费、西安电子科技大学优秀博士学位论文资助基金、陕西师范大学青年基金各一项，以第三完成人参与国家自然科学基金、博士点基金等多项科研项目。授权专利三项，获得陕西省科学技术奖一等奖（第三完成人）一项，陕西省自然科学优秀学术论文二等奖（第一完成人）一项。 2 该单元的教学目标 2.1 单元内容概要 第9章查找 第3节哈希表 03 《数据结构》考试大纲 主要参考教材：严蔚敏、吴伟民编著，《数据结构（C语言版）》，清华大学出版社 谭国律等编著《数据结构》，浙江大学出版社。 总体要求： “数据结构”是一门专业技术基础课。目的就是要培养他们的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并掌握分析算法的时间和空间复杂度的技术。 考生在复习时，重点掌握基本概念、基本算法。考题以基本内容为主，题目以基础知识题为主，各章较难内容、较偏内容不考。课本所有加“*”号章节不考，第8章动态存储管理不考。外部排序，文件部分不考。 各章考试内容及要求： 一、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之 间的关系；了解抽象数据类型的定义、表示和实现方法；熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式；理解算法五个要素的确切含义；掌握计算语句频度和估算算法时间复杂度的方法。 二、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线 性表的两类存储结构（顺序存储和链式存储）上实现基本操作；一元多项式的抽象数据类型定义、表示及加法的实现。 三、栈和队列：栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作和栈 和队列在程序设计中的应用。（离散事件模拟不考） 四、串：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆 分配存储结构；串的各种基本操作的实现及应用；串的朴素模式匹配算法。 五、数组：数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实 现；（广义表不考）。 六、树和二叉树：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法 的各种描述形式；树和森林的定义、存储结构、树和森林与二叉树的转换、遍历；树的多种应用；本章是该课程的重点内容之一。 七、图：图的定义和术语；图的邻接矩阵存储结构、邻接表存储结构：图的两种遍历策略： 深度优先搜索和广度优先搜索；图的最小生成树prim算法、Kruskal 算法；拓扑排序算法；单源最短路径问题的Dijstra 算法。 八、查找：讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表、 树表和哈希表；关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论。（静态树表、平衡二叉树、B树不考） 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 《数据结构》课程教学大纲 一、课程基本信息 二、课程教学目标 本课程介绍软件设计中常用的线性表、栈、队列、串、数组、广义表、树、二叉树、图结构等几种基本的数据结构及其存储结构和所施加的运算与实现等。另外，还介绍软件设计中常用的几种查找和排序算法，以及递归技术等，在介绍各项内容的同时，还涉及到算法设计与分析的基本技术和面向对象程序设计的理论与技术等内容。 通过本课程的学习，达到以下目标： 熟练掌握上述结构及其运算的实现和性能特点， 掌握各种排序和查找运算以及递归技术， 能对给定的实际问题，建立准确的问题模型，设计有效的问题求解方法，选择合理的数据结构及其运算集，设计有效的算法。 三、教学学时分配 《数据结构》课程理论教学学时分配表 ＊理论学时包括讨论、习题课等学时。 《数据结构》课程实验内容设置与教学要求一览表 四、教学内容和教学要求 第一章绪论（2学时） （一）教学要求 1．了解数据结构的各种基本概念和术语； 2．了解数据类型和抽象数据类型的概念； 3．理解算法的设计目标； 4．掌握算法的时间复杂度概念和算法的时间复杂度分析方法。 （二）教学重点与难点 教学重点：数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系 教学难点：算法复杂度的分析方法。 （三）教学内容 第一节什么是数据结构 1．数据结构的定义 2．逻辑结构类型 3．存储结构类型 4．数据结构和数据类型 第二节算法及其描述 1．什么是算法 2．算法描述 第三节算法分析 1．算法设计的目标 2．算法效率分析 3．算法存储空间分析 本章习题要点：基本概念、算法复杂度的分析方法 第二章线性表（10学时） （一）教学要求 1．理解线性表的逻辑结构和基本操作； 2．理解线性表的顺序存储结构和实现方法； 3．理解线性表的链式存储结构和实现方法； 4．了解单循环链表和双向链表的概念和插入、删除等操作方法。 （二）教学重点与难点 教学重点：顺序表和单链表上实现的各种基本算法及相关的时间性能分析。 教学难点：链表本质及其操作的实现算法、线性表相关的应用。 （三）教学内容 第一节线性表 1．线性表的定义 2．线性表的抽象数据类型描述 第二节线性表的顺序存储结构 1．线性表的顺序存储结构——顺序表 2．顺序表基本运算的实现 第三节线性表的链式存储结构 1．线性表的链式存储结构——链表 2．单链表基本运算的实现 3．双链表 4．循环链表 本章习题要点： 第三章栈和队列（12学时） 《数据结构》教学大纲 课程编号：071213A 课程类型：□通识教育必修课□通识教育选修课 □专业必修课□专业选修课 ■学科基础课 总学时：48讲课学时：32 实验（上机）学时：16 学分：3 适用对象：计算机科学与技术专业 先修课程： 程序设计基础与应用、计算机基础 一、教学目标 本课程是计算机科学与技术专业的必修课。本课程是计算机科学与技术专业的核心课程，既重视学生相关理论的系统学习，又强调培养学生发现问题、分析问题和解决问题的实践能力。《数据结构》在计算机科学中是一门综合性的专业主干课，它是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，而且是操作系统、数据库系统及其它系统程序的大型应用程序设计的基础，同时又直接为从事各类计算机应用的技术人员提供了必要的基本知识和解决实际问题的多种方法。 用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。《数据结构》主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。该课程逻辑上以线性结构、层次结构、网状结构为主线，物理上分顺序存储、链式存储，分别介绍基本数据结构的特点和算法。并重点介绍有关各种检索、排 序和文件组织的常用算法。通过上述知识的学习和能力的提高，为后续学习和实际工作打下良好的知识基础和能力基础。 目标1：通过对数据结构基本知识进行讲解，让学生理解并掌握数据的逻辑结构和物理结构，并掌握算法设计的基本思想。 目标2：培养学生分析算法复杂度的初步能力，锻炼学生逻辑思维能力和想象能力，并使之了解数据结构的各种应用场景。 目标3：鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实际的能力。 二、教学内容及其与毕业要求的对应关系 （一）教学内容 1．知识体系 第一部分：数据结构的基本概念，包括数据、数据元素、数据项等基本概念、数据类型、抽象数据类型、算法的定义、算法的特性、算法的时间代价、算法的空间代价； 第二部分：线性表的逻辑结构特性，以及线性表的两种存储实现方式；顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算；单链表的类定义、构造函数、单链表的插入与删除算法及其平均比较次数的计算； 第三部分：栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表示以及相应操作的实现；队列的定义、特性和队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现； 第四部分：串的定义，串的表示和实现，串的操作的定义； 第五部分：数组的两种存储表示方法；矩阵的压缩存储； 第六部分：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型；二叉树的概念、性质及二叉树的表示；二叉树的遍历方法；线索化二叉树的特性及寻找某结点的前驱和后继的方法；树与森林的实现，重点在用二叉树实现；森林与二叉树的转换；树的遍历算法；二叉树的计数方法及从二叉树遍历结果得到 数据结构经典案例 1.停车场问题 停车场管理员的任务就是帮助车主把车停放在停车场中，或者是帮助车主将车开出乘车场。然后停车场中能够停放的车辆数目很多，这就使得让莫辆车开出停车场变得复杂。比如：要开走一辆车，则管理员需要把他前面的车全部暂时清除，然后等这辆车开出后再将这些车重新放入停车场。当然了，这个时候腾出了一个空位置，此位置由后面的车占据。 任务：编程模拟这样的情况，这里假设停车场最多可停放5辆车。data.txt记录了某一时间段内，该停车场车辆的到来与离开记录，刚开始，停车场是空的。其中大写字母A--P是车辆的代号，arrives--到来，departs---离开。 程序需要从data.txt中读取这些信息，并且用这些数据来模拟停车场的车辆调度情况。 data.txt内容如下： A arrives A departs B arrives C arrives D arrives C departs E arrives F arrives G arrives B departs H arrives D departs E departs I arrives I departs J arrives F departs K arrives L arrives M arrives H departs N arrives J departs K departs O arrives P arrives P departs O departs L departs 实现代码如下： 模拟停车场问题.cpp（没有再继续分.h文件，混为一体了，主要.h文件过于简单） 【最新整理，下载后即可编辑】 XX师范学院大学本科专业教学大纲中文课程名称：数据结构 英文课程名称：Data Structures 适用专业：信息管理与信息系统 制定单位：商学院 执笔人： 审核人： 单位负责人： 制定时间：2017-2-10 XX师范学院教务处 二〇一七年一月 《数据结构》课程教学大纲 一、课程基本信息 （一）课程代码及课程名称 1.课程代码：06151090 2.课程名称（中/英文）：数据结构/Data Structures （二）课程类别及课程性质 专业教育必修课程 （三）学时及学分： 总学时数：64；总学分数：3。 其中，讲授学时：32 ，实践（实验）学时：32。 （四）适用专业及开设学期 适用专业：信息管理与信息系统（本科） 开设学期：第二学期 （五）先修课程与后续课程 先修课程：大学计算机基础、高等数学、C语言程序设计 后续课程：数据库原理与应用、管理信息系统分析与设计、管理信息系统、Java程序设计(高级) 二、课程简介 “数据结构”是信息管理与信息系统专业一门重点专业基础 课程，也是学科专业核心专业基础课程之一，属于专业学位必修课程。本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础。此外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。 三、教学目的与基本要求 （一）该课程教学目的与专业培养要求对应关系矩阵 ［收稿日期］ 2016－01－01［基金项目］计算机科学与技术国家级特色专业（TS11576）；国家自然科学基金（41001251）；河南省科技公关项目（152102410042、132102210212）；河南省教育厅资助项目（13A520011）；河南省青年骨干教师项目（2011－148）；安阳师范学院《数据结构》精品资源共享课程。 ［作者简介］刘国英（1979－），男，博士， 副教授，主要从事遥感影像信息提取研究。数据结构案例教学—二叉树在图像分割中的应用 刘国英，王煜龙，陈双浩 （安阳师范学院计算机与信息工程学院，河南安阳455002） ［摘要］数据结构是计算机相关专业的核心基础课。掌握数据结构有关知识对学生进一步学习后续课程起着至关重要的作用，有助于提高学生设计复杂软件的能力。然而，传统的教学方法过于强调抽象数据类型的定义及对应的实现方法，而使得让学生觉得枯燥和困难。本文以二叉树在图像分割中的应用为案例，利用最优二叉树的性质、二叉树的遍历方法等知识点，设计图像分割算法，并进行了简单分析。教学实践表明，数据结构的案例教学比传统教学更能提高教学质量。 ［关键词］数据结构；二叉树；图像分割；案例教学［中图分类号］ G642［文献标识码］ A ［文章编号］ 1671－5330（2016）02－0128－04数据结构是计算机及相关专业的一门核心课程，对学生深入学习计算机专业知识具有至关重 要的作用。二叉树作为一种应用极其广泛的数据结构，是学生必须掌握的一个知识点。然而，该结构相对线性结构更加抽象和复杂，常用教材中采用的案例非常少，这对学生理解产生巨大障碍。虽然有教师设计了不同的案例方法［1］ ，但仍然显 不够。 当前，多媒体智能信息处理技术一直引领计算机学科的发展。其中，图像分割是图像及视频信息处理的一个基础研究课题，在遥感、农业、军事等领域应用非常广泛。图像分割技术的深入研究对数据结构理论体系的发展和应用提出了更高的要求。很多人在图像分割领域进行了研究 ［2－5］ 。因此，为了拓展学生的知识面，提高学生 学习的热情，本文以图像分割为背景，设计数据结构中二叉树的案例教学方法。 1基本知识 1．1图像分割与二叉树结构 对图像分割的研究一直是图像处理中的重点 和热点［2］ 。图像分割的目的是将图像划分为互 不重叠的图像区域，并要求图像区域内部的像素具有相同的属性，比如颜色和纹理。在图像分割中，获得的图像区域个数就成为图像的类别数。 二叉树是指树种任一结点的度小于2的树，即任一结点最多有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒 ［6］ 。这表明二叉树 或为空，或为一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。这两棵子树也是二叉树。因此，二叉树是递归定义的。因为二叉树不同子树上的节点是互不相交的，这与图像分割中各个分割区域之间互不重叠的要求是一致的。所以，利用二叉树的性质设计图像分割算法符合该研究问题的特点。1．2 二叉树的遍历 遍历二叉树是指按照某条搜索路径巡访树中 DOI:10.16140/https://www.doczj.com/doc/8817280844.html,ki.1671-5330.2016.02.033 数据结构期末复习提纲（2012级） A、总体要求： 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度的分析。 3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言和C++语言设计与实现算法的能力。 一、基本概念 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、图的连通性、连通图、连通分量的概念。 26、有向无环图的概念及特点。 27、查找、查找表、关键字的概念。 28、顺序查找、折半查找、分块索引查找的概念。 29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。 30、B_树的定义及存储结构特点。 31、哈希函数、哈希表、哈希冲突、哈希查找的概念。 32、哈希表装填因子的定义及作用。 33、内部排序、外部排序、排序方法、传统排序和优化排序的概念。 34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。 35、排序方法的稳定性概念。 《数据结构》课程教学大纲 Data Structure 执笔人：编写日期： 一、课程基本信息 1. 课程编号： 2. 课程性质/类别：必修课 / 专业主干课 3. 学时/学分： 48 学时（另实验16学时） / 4 学分 4. 适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业 二、课程教学目标及学生应达到的能力 数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。 三、课程教学容与基本要求 （一）绪论（ 3 学时） 1．主要容： （1）介绍什么是数据结构； （2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型； （3）抽象数据类型的表示与实现； （4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。 2．基本要求 （1）了解学习数据结构的重要性； （2）掌握数据结构的定义及相关概念和术语； （3）了解抽象数据类型的定义、表示与实现方法； （4）理解算法的概念、特点并掌握度量其效率的基本方法。 3．自学容： 类C语言的书写规。 （二）线性表（ 6 学时） 1．主要容： （1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等； （2）线性表顺序存储表示和基本操作的实现； （3）线性表的链式存储表示和基本操作的实现； （4）稀疏多项式的抽象数据类型定义、表示和加法的实现。 《数据结构》教案 信息技术学院 软件教研室 课程说明 【目的】 1.数据结构是研究数据组织、存储和运算的一般方法的学科。 ——理解并掌握数据的各种数据结构的原理与算法。 2. 学会分析研究计算机加工的数据结构的性质，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。 3.数据结构是编程的基础。程序=数据结构+算法 ——能够以数据结构为基础，进行复杂程序编程,且符合软件工程的规范。 4.数据结构课程重点是培养学生的数据抽象能力。 【内容】 1.数据结构的基本概念（第1章） 2、线性表（第2、 3、 4、5章） 3、树（第6章） 4、图（第7章） 5、查找和排序（第9、10、11章） 【参考书】 1．数据结构严蔚敏清华大学出版社 2. 数据结构（c语言篇）——习题与解析（修订版）李春葆清华大学出版社 【教学安排】 第1章绪论 【教学目的】 1.数据结构的基本概念,介绍数据和数据结构等名词和术语。 2.描述算法的类C语言 3.从时间和空间角度分析算法的方法 【教学要求】 掌握基本概念，了解抽象数据类型，掌握计算语句频度和估算算法时间复杂度，熟悉类C语言的书写规范。 【教学重点与难点】 描述算法的类C语言；抽象数据类型的概念；算法复杂性的分析方法 【教学追记】 1、熟悉各名词、术语的含义，掌握基本概念，特别是数据结构的三个方面（逻辑结构、存储结 构、及其运算）。数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2、了解抽象数据类型的定义、表示和实现方法。 3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入 执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。 4、掌握计算语句频度和估算算法时间复杂度的方法。 5、熟悉类C语言的书写规范，对学过C++的学生，比较输入/输出语句cin /cout；动态分配内存 语句new与C语言的区别。 6、本章的授课方法：讲授为主，自学为辅，通过练习掌握概念和方法，可以通过1个编程，理解抽象数据类型的概念 【教学内容】 1.什么是数据结构 2.基本概念和术语 3.抽象数据类型的表示与实现 4.算法和算法分析 1.1什么是数据结构 一、计算机解决具体问题的步骤 1、从具体问题抽象出一个适当的数学模型； 2、设计解此数学模型的算法； 3、编程，进行测试、调整直至得到最终解答。 对数值计算问题可以用数学方程来描述。但是，对许多非数值计算问题无法用数学方程加以描述。需要用表、树、图等数学模型来描述。 二、非数值问题的三个例子 1、图书馆的书目检索系统自动化问题；——表 2、计算机和人对弈问题；——树 3、多叉路口交通灯的管理问题。——图 《数据结构》课程教学大纲 一、课程说明： 《数据结构》是英语翻译专业机器翻译方向的一门选修课。该课程教学使学生深透地理解数据的逻辑结构和物理结构的基本概念以及有关算法；熟悉它们在计算机科学中最基本的应用；了解编写算法的基本方法；为后继课程的学习打下一个理论基础及实践基础。从第四学期至第八学期，学生可根据具体情况在其中任一学期选修该课程。 二、教学目的及要求： 该课程教学旨在使学生掌握如何根据问题的需求合理地组织数据，在计算机中有效地存储数据和处理数据，并初步了解算法设计和分析。本课程从数据结构及其实现两个层次和相互关系的角度，系统地学习和掌握常用基本数据结构，包括线性表、栈、队列、树、二叉树、图、查找表和排序等，及它们的不同实现，包括不同的存储结构和算法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现（算法）的原则和方法。 三、教学重点及难点： 重点：系统地学习和掌握各种常用基本数据结构及它们的不同实现，不同的存储结构和实现算法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现（算法）的原则和方法。难点：树、二叉树、图、查找和排序的综合应用及实现算法。 四、与其它课程的关系： 先修课程：《高等数学》和《程序设计》；后续课程：《操作系统》、《数据库》等。 五、学时与学分： 学时：54学时（包括上机18学时）。 学分：3学分（课堂教学2学分，上机1学分）。 六、教学内容： 第一章概论 本章主要教学内容： 基本概念和术语。 学习数据结构的意义。 算法的描述和分析。 本章教学目的及要求： 本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。 本章教学重点及难点： 本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 第二章线性表 本章主要教学内容： 第 16 期2013 年 8 月 25 日计算机教育 Computer Education 中图分类号：G642 90 0 引 言 数据结构是高等学校计算机科学与技术相关专业的一门必修基础课，对于训练学生进行复杂程序设计和养成良好程序设计习惯具有重要作用。它上承计算机导论、程序设计语言、离散数学等基础课程，下启算法设计与分析和计算复杂性理论，是数据库、软件工程、编译原理、操作系统等计算机专业核心课程的先修课，只要学生毕业后还从事与计算机软、硬件开发相关的工作，数据结构的知识必然会或多或少地用到。此外，该课程中的很多结构和算法也是更高层次的计算机应用技术领域，如人工智能、模式识别、机器学习、网络信息处理、多媒体技术等课程的根基所在。 目前，数据结构课程的教学多以传授知识、描述抽象数据结构及其存储和算法为主，并辅以一定的上机实验。由于该课程知识点较多，且相对独立，许多学生在学完该课程后，大都能看懂数据结构的算法描述却无法针对实际问题设计相关的结构和算法[1]。案例教学是一种非常有发展潜力的教学模式，在课堂教学中，如果能够设计有具体应用背景及可满足不同层次学生需要的综合性案例，并指导学生对其进行积极的思考、分析、讨论和编程实现，将会极大地帮助学生深刻理解问题的原理和本质，起到举一反三、融会贯通的效果。 1 数据结构课程教学中的主要问题 数据结构是一门实践性很强的课程，其内容涵盖了线性表、栈、队列、数组、串、树、图、查找和排序等许多知识，目前的教学主要强调不同类型数据的逻辑结构、存储结构和基本运算的实现。由于不同类型的结构之间相对分离，知识点相互独立，学生在学习的过程中并不能很好地将课程的内容连贯在一起形成一个整体。另外，课堂教学中的举例一般只偏重于某个具体的知识点，使得课程综合性不够，而且与实际应用联系不够紧密。学生在学习该课程的过程中并没有学 文章编号：1672-5913(2013)16-0090-05 “数据结构”课程教学中的案例设计及应用 袁和金 （华北电力大学 计算机系，河北 保定 071003） 摘 要：针对目前数据结构课程教学中存在的理论与实践脱节，以及学生运用所学知识解决实际问题能力不强的问题，探讨案例在数据结构教学中的作用和意义，并以图的拓扑排序算法为例详细说明案例的设计方法和原则。 关键词：案例；数据结构；拓扑排序 作者简介：袁和金，男，副教授，研究方向为模式识别、计算机视觉，yhj_1977@https://www.doczj.com/doc/8817280844.html,。 2019年北京理工大学889《数据结构》考试大纲 考试内容： 数据结构主要考查考生以下几个方面： 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为： 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构（C语言版）严蔚敏吴伟民清华大学出版社案例教学法在数据结构教学中的应用
《数据结构》教学纲要(doc 9页)
数据结构提纲及答案
数据结构课程教学大纲
《数据结构》教学设计方案
《数据结构》课程考试大纲
数据结构复习提纲(整理)
《数据结构》课程教学大纲(计算机)
数据结构-教学大纲
数据结构经典案例教学文案
数据结构教学大纲(完整资料).doc
数据结构案例教学_二叉树在图像分割中的应用_刘国英
数据结构期末试题提纲
《数据结构》课程教学大纲
《数据结构》教案
《数据结构》课程教学大纲
_数据结构_课程教学中的案例设计及应用_袁和金
2019 北京理工大学 889《数据结构》 考试大纲
相关主题
文本预览