2023年电大数据结构本期末复习指导.doc

中央广播电视大学数据结构（本）期末复习指导第一部分 课程考核说明一、考核说明数据结构（本）是中央广播电视大学计算机科学与技术（本科）专业的一门统设必修、学位课程4学分，72学时，其中实验24学时，开设一学期课程重要内容涉及：数据结构和算法的基本概念、线性表、栈和队列、串、数组和广义表、树和图、查找和排序等目的是使学生通过该课程的学习，进一步地理解数据的逻辑结构和物理结构以及有关算法，掌握基本的程序设计技能，学会编制高效可靠的程序，为学习后续课程奠定基础　　现将有关考核的几个问题说明如下：　　1．考核对象　　2023年秋季起入学的计算机科学与技术专业（本科）学生　　2．考核依据　　以数据结构（本）课程教学大纲为依据编制，考核说明是本课程形成性考核和终结性考试命题的基本依据　　3．考核方式　　采用形成性考核和终结性考试相结合的方式　　4．课程总成绩的记分方法　　课程总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％60分为合格，可以获得课程学分本课程的学位课程学分为70分，即课程总成绩达成70分及以上者有资格申请专业学位5．形成性考核的规定、形式及手段形成性考核重要考核学生形成性作业和实验的完毕情况，占课程总成绩的30%。

形成性考核以作业册的形式下发，由各地电大根据学生作业和实验的完毕情况进行考核中央电大将不定期随机抽检各地电大学生的形成性作业及课程实验报告　　6．终结性考试的规定及方式　　（1） 考试规定考核规定分为了解、理解和掌握三个层次：了解：是指（1）学习本课程主干知识点所需要的概念、方法、预备知识和相关内容2）就大部分学生目前的知识结构和基础理解和掌握有一定困难，有待此后进一步学习的内容3）在主干知识点基础上拓展的内容这部分不属考核的重要内容理解：是指规定学生准确全面领略的概念、方法和思绪等相关内容是本课程的主干知识点，规定学生能融汇贯通，并能运用所学知识分析解决相关问题这部分是考核的重要范围掌握：是指本课程最重要的知识点，能充足体现本课程的教学规定，规定学生在理解所学知识的基础上能灵活应用能结合课程的不同知识点解决综合性的问题和简朴应用问题这部分是考核的重点内容2） 考核方式中央电大统一命题，闭卷考试3）组卷原则　　在考核说明所规定的内容和规定之内命题在教学内容范围之内，按照理论联系实际原则，考察学生对所学知识应用能力的试题，不属于超纲试题的难易限度和题量适当，按难易限度分为易、中、难三个层次：易占25%，中占45%，难占30%。

题量安排以大多数考生能在规定的考试时间内做完并有一定期间检查为原则4）试题类型及试卷结构试题题型有单项选择题、填空题、综合题和程序填空题四种题型试卷结构如下：单项选择题：每小题2分，共30分填空题： 每小题2分，共24分　　综合题： 每小题10分，共30分程序填空题：每空2分，共16分共100分　　 　 （5）答题时限答题时限为90分钟 二、考核内容和规定 第1章 绪论（2学时）[考核知识点]1．数据结构的基本概念2．算法和算法分析的基本概念[考核规定]1．理解数据结构的基本概念2．掌握逻辑结构、物理结构的概念及互相关系3．掌握本书介绍的四种基本结构的特点4．理解算法及其特性5．了解算法分析的一般概念第2章 线性表（8学时）[考核知识点]1．线性表的定义、逻辑结构、顺序存储结构、链式存储结构 2．线性表在顺序结构和链式结构上的基本操作和应用 3．双向链表、循环链表的原理和相关操作[考核规定]1．理解线性表的定义及两种存储结构2．理解线性表顺序存储的特点、实现方法和应用3．掌握顺序表的基本操作（涉及建立链表、遍历链表、删除、插入、查找）和应用。

特别规定可以运用链表的操作和相关的程序设计技术编制有一定难度的程序4．了解双向链表、循环链表的原理和相关操作第3章 栈和队列（6学时）[考核知识点]1．栈的定义、栈的存储结构（顺序存储、链式存储）和基本操作、栈的应用2．队列的定义、队列的存储结构（顺序存储、链式存储）、队列的应用3．循环队列的概念和实现方法[考核规定]1．掌握栈和队列的操作特点2．理解顺序栈、顺序队列的基本操作3．了解在实际编程中栈和队列的不同应用理解循环队列的概念、实现方法掌握循环队列判空、判满的条件4．能按照后续章节（例如二叉树、排序等）的规定运用递归程序设计技术实现相关算法第4章 串（2学时）[考核知识点]1．串类型定义、C语言中字符串的特点和解决方法2．串的顺序存储结构和链式存储结构3．串的基本运算和实现方法[考核规定]1．理解串的定义和存储方法2．了解串的基本操作和相关算法3．掌握用C语言解决字符串的语法规则第5章 数组和广义表（2学时）[考核知识点]1．数组的定义和存储结构2．特殊矩阵和稀疏矩阵的存储结构3．广义表的定义和存储结构[考核规定]1．了解数组的存储结构2．掌握特殊矩阵进行压缩存储的下标转换公式。

3．理解稀疏矩阵的压缩存储原理4．掌握运用三元组表达稀疏矩阵的方法5．了解广义表的概念和存储结构第6章 树和二叉树（10学时）[考核知识点]1．树的基本概念2．二叉树的性质和存储结构3．二叉树的遍历和线索二叉树4．哈夫曼树及其应用[考核规定]1．了解树和二叉树的定义2．掌握二叉树的基本性质，能运用相关性质解决简朴计算问题3．了解二叉树的顺序存储结构4．掌握二叉树的链式存储结构、相关操作5．掌握二叉树的有关算法并能编程实现6．掌握运用遍历序历构造二叉树的规则和具体环节7．掌握哈夫曼树的定义、性质和构造方法8．了解哈夫曼树的应用第7章 图（6学时）[考核知识点]1．图的基本概念2．图的存储结构3．图的遍历4．最小生成树和最短途径[考核规定]1．了解图的基本概念2．掌握图的存储方法（邻接矩阵、邻接表）3．掌握图的深度优先和广度优先遍历的规则和环节4．理解在连通图中求最小生成树的方法了解求图的最短途径等相关算法及其应用第8章 查找（6学时）[考核知识点]1．线性表的查找（顺序查找、折半查找、分块查找）2．二叉排序树的查找3．哈希表（哈希表的定义、哈希函数的构造、解决冲突的方法、哈希表的查找和分析）。

[考核规定]1．了解查找的相关概念2．掌握顺序表的查找方法、环节、程序实现、时间复杂度和平均查找长度3．掌握在有序的顺序表上进行折半查找的方法、环节、程序实现4．掌握折半查找的鉴定树的构造方法能运用鉴定树求平均查找长度5．掌握二叉排序树的确切定义，掌握建立二叉排序树的环节和方法理解在二叉排序树中进行输入、删除操作的规则6．了解哈希表的相关概念和原理，了解常用哈希函数的构造和解决冲突的方法理解哈希函数和哈希表的关系及在查找中的应用第9章 排序（6学时）[考核知识点]1．插入排序（直接插入排序、希尔排序）2．互换排序（冒泡排序、快速排序）3．选择排序（简朴选择排序、堆排序）4．归并排序[考核规定]1．掌握教材中介绍的各种排序算法的基本原理、环节2．能针对小规模具体实例，按相关排序算法的规则人工完毕排序；能通过度析排序的中间结果判断所用的排序算法3．能对的理解相关排序算法的程序实例，并重点掌握算法中的关键环节和关键语句4．掌握堆和特殊的完全二叉树的相应关系掌握建堆、筛选算法和完全二叉树相关操作的相应关系三、试题类型及答案一、单项选择题（每小题2分，共30分）1.数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理2.下述各类表中可以随机访问的是（ ）A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素则原顺序表的长度为（ ）A. 21 B. 20 C. 19 D. 254.元素2，4，6按顺序依次进栈，则该栈的不也许的输出序列是（ ）A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ ）A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.也许有多种情况6. 串函数StrCmp（“d”，“D”）的值为（ ） A．0 B．1 C．-1 D．37．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。

A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ ）个结点A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1)9.对如图1所示二叉树进行中序遍历，结果是（ ）A. dfebagc B. defbagc C. defbacg D.dbaefcg图1cbcdefga 10 . 任何一个无向连通图的最小生成树（ ）A.至少有一棵 B.只有一棵 C.一定有多棵 D.也许不存在11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ ）A．33 B．32 C．85 D．4112 . 一组记录的关键字序列为（37，70，47，29，31，85），运用快速排序，以第一个关键字为分割元素，通过一次划分后结果为（ ）。

A．31，29，37，85，47，70 B．29，31，37，47，70，85C．31，29，37，70，47，85 D．31，29，37，47，70，8513 . 对n个元素进行冒泡排序，规定按升序排列，程序中设定某一趟冒泡没有出现元素互换，就结束排序过程对某n个元素的排序共进行了3n-6次元素间的比较就完毕了排序，则（ ）A.原序列是升序排列B.原序列是降序排列C.对序列只进行了2趟冒泡D. 对序列只进行了3趟冒泡14．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行（ ）A.x=top->data;top=top->next; B. top=top->next ; x=top;C.x=t。