数据结构(本)考核说明(审定稿).doc

《数据结构(本)考核说明(审定稿).doc》由会员分享，可在线阅读，更多相关《数据结构(本)考核说明(审定稿).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（本）课程考核说明（审定稿）一、考核说明数据结构（本）是中央广播电视大学计算机科学与技术（本科）专业的一门统设必修、学位课程。4学分，72学时，其中实验24学时，开设一学期。课程主要内容包括：数据结构和算法的基本概念、线性表、栈和队列、串、数组和广义表、树和图、查找和排序等。目的是使学生通过该课程的学习，深入地理解数据的逻辑结构和物理结构以及有关算法，掌握基本的程序设计技能，学会编制高效可靠的程序，为学习后续课程奠定基础。现将有关考核的几个问题说明如下：1考核对象2007年秋季起入学的计算机科学与技术专业（本科）学生。2考核依据以数据结构（本）课程教学大纲为依据编制，考核说明是本课程形

2、成性考核和终结性考试命题的基本依据。3考核方式采用形成性考核和终结性考试相结合的方式。4课程总成绩的记分方法课程总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70。60分为合格，可以获得课程学分。本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。5形成性考核的要求、形式及手段形成性考核主要考核学生形成性作业和实验的完成情况，占课程总成绩的30%。形成性考核以作业册的形式下发，由各地电大根据学生作业和实验的完成情况进行考核。中央电大将不定期随机抽检各地电大学生的形成性作业及课程实验报告。6终结性考试的要求及方式（1） 考试要求考核要求分为了解、理

3、解和掌握三个层次：了解：是指（1）学习本课程主干知识点所需要的概念、方法、预备知识和相关内容。（2）就大部分学生目前的知识结构和基础理解和掌握有一定困难，有待今后进一步学习的内容。（3）在主干知识点基础上拓展的内容。这部分不属考核的主要内容。理解：是指要求学生准确全面领会的概念、方法和思路等。相关内容是本课程的主干知识点，要求学生能融汇贯通，并能利用所学知识分析解决相关问题。这部分是考核的主要范围。掌握：是指本课程最重要的知识点，能充分体现本课程的教学要求，要求学生在理解所学知识的基础上能灵活应用。能结合课程的不同知识点解决综合性的问题和简单应用问题。这部分是考核的重点内容。（2） 考核方式中

4、央电大统一命题，闭卷考试。（3）组卷原则在考核说明所规定的内容和要求之内命题。在教学内容范围之内，按照理论联系实际原则，考察学生对所学知识应用能力的试题，不属于超纲。试题的难易程度和题量适当，按难易程度分为易、中、难三个层次：易占25%，中占45%，难占30%。题量安排以大多数考生能在规定的考试时间内做完并有一定时间检查为原则。（4）试题类型及试卷结构试题题型有单项选择题、填空题、综合题和程序填空题四种题型。试卷结构如下：单项选择题：每小题2分，共30分填空题： 每小题2分，共24分综合题： 每小题10分，共30分程序填空题：每空2分，共16分共100分 （5）答题时限答题时限为90分钟。 二

5、、考核内容和要求 第1章 绪论（2学时）考核知识点1数据结构的基本概念2算法和算法分析的基本概念考核要求1理解数据结构的基本概念2掌握逻辑结构、物理结构的概念及相互关系3掌握本书介绍的四种基本结构的特点4理解算法及其特性5了解算法分析的一般概念第2章 线性表（8学时）考核知识点1线性表的定义、逻辑结构、顺序存储结构、链式存储结构2线性表在顺序结构和链式结构上的基本操作和应用 3双向链表、循环链表的原理和相关操作考核要求1理解线性表的定义及两种存储结构2理解线性表顺序存储的特点、实现方法和应用。3掌握顺序表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用。特别要求能够利用链表的操作和

6、相关的程序设计技术编制有一定难度的程序。4了解双向链表、循环链表的原理和相关操作。第3章 栈和队列（6学时）考核知识点1栈的定义、栈的存储结构（顺序存储、链式存储）和基本操作、栈的应用2队列的定义、队列的存储结构（顺序存储、链式存储）、队列的应用3循环队列的概念和实现方法考核要求1掌握栈和队列的操作特点2理解顺序栈、顺序队列的基本操作3了解在实际编程中栈和队列的不同应用。理解循环队列的概念、实现方法。掌握循环队列判空、判满的条件4能按照后续章节（例如二叉树、排序等）的要求利用递归程序设计技术实现相关算法第4章 串（2学时）考核知识点1串类型定义、C语言中字符串的特点和处理方法2串的顺序存储结构

7、和链式存储结构3串的基本运算和实现方法考核要求1理解串的定义和存储方法2了解串的基本操作和相关算法3掌握用C语言处理字符串的语法规则第5章 数组和广义表（2学时）考核知识点1数组的定义和存储结构2特殊矩阵和稀疏矩阵的存储结构3广义表的定义和存储结构考核要求1了解数组的存储结构。2掌握特殊矩阵进行压缩存储的下标转换公式。3理解稀疏矩阵的压缩存储原理。4掌握利用三元组表示稀疏矩阵的方法。5了解广义表的概念和存储结构。第6章 树和二叉树（10学时）考核知识点1树的基本概念2二叉树的性质和存储结构3二叉树的遍历和线索二叉树4哈夫曼树及其应用考核要求1了解树和二叉树的定义2掌握二叉树的基本性质，能利用相

8、关性质解决简单计算问题3了解二叉树的顺序存储结构4掌握二叉树的链式存储结构、相关操作5掌握二叉树的有关算法并能编程实现6掌握利用遍历序历构造二叉树的规则和具体步骤7掌握哈夫曼树的定义、性质和构造方法8了解哈夫曼树的应用第7章 图（6学时）考核知识点1图的基本概念2图的存储结构3图的遍历4最小生成树和最短路径。考核要求1了解图的基本概念2掌握图的存储方法（邻接矩阵、邻接表）3掌握图的深度优先和广度优先遍历的规则和步骤4理解在连通图中求最小生成树的方法。了解求图的最短路径等相关算法及其应用第8章 查找（6学时）1线性表的查找（顺序查找、折半查找、分块查找）。2二叉排序树的查找。3哈希表（哈希表的定

9、义、哈希函数的构造、处理冲突的方法、哈希表的查找和分析）。考核要求1了解查找的相关概念。2掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度。3掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现。4掌握折半查找的判定树的构造方法。能利用判定树求平均查找长度。5掌握二叉排序树的确切定义，掌握建立二叉排序树的步骤和方法。理解在二叉排序树中进行输入、删除操作的规则。6了解哈希表的相关概念和原理，了解常用哈希函数的构造和处理冲突的方法。理解哈希函数和哈希表的关系及在查找中的应用。第9章 排序（6学时）考核知识点1插入排序（直接插入排序、希尔排序）2交换排序（冒泡排序、快速排序）3选择排

10、序（简单选择排序、堆排序）4归并排序考核要求1掌握教材中介绍的各种排序算法的基本原理、步骤。2能针对小规模具体实例，按相关排序算法的规则人工完成排序；能通过分析排序的中间结果判断所用的排序算法。3能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句。4掌握堆和特殊的完全二叉树的对应关系。掌握建堆、筛选算法和完全二叉树相关操作的对应关系。三、试题类型及答案一、单项选择题（每小题2分，共30分）1.数据结构中，与所使用的计算机无关的是数据的（ ）结构。A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理2.下述各类表中可以随机访问的是（ ）。A. 单向链表 B. 双向链表 C.单

11、向循环链表 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”）的值为（ ）。 A0 B1 C-1 D37在一个单链表中，p、q分别指向表中两个相邻的结点，且q所

12、指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。 Ap=qnext Bpnext=q Cpnext=qnext Dqnext=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，采用压缩存储的方

13、式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ ）。A33 B32 C85 D4112 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A31，29，37，85，47，70 B29，31，37，47，70，85C31，29，37，70，47，85 D31，29，37，47，70，8513 . 对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了

14、排序，则（ ）。A.原序列是升序排列B.原序列是降序排列C.对序列只进行了2趟冒泡D. 对序列只进行了3趟冒泡14在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行（ ）。A.x=top-data;top=top-next; B. top=top-next ; x=top;C.x=top;top=top-next ; D. x=top-data;15串函数StrCat（a,b）的功能是进行串（ ）。 A比较 B复制 C赋值 D连接 二、填空题（每小题2分，共24分）1在一个单向链表中p所指结点之后插入一个s所指的新结点，应执行s-next=p-next；和_操作。2根据

15、数据元素间关系的不同特性，通常可分为_、 、 、 四类基本结构。3在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为_。 (结点的指针域为next)4._遍历二叉排序树可得到一个有序序列。5.一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_个叶结点。6.如图1所示的二叉树，其中序遍历序列为_ _。efgibachd 图17.对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的_、_和_三项信息。8 . 有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82的结点，经_次比较后查找成功

16、。9 .图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是_的。(回答正确或不正确) 10哈希法既是一种存储方法，又是一种 。1144.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_次。12栈和队列的操作特点分别是_和 _。三、综合题（每小题10分，共30分）1已知序列11，19，5，4，7，13，2，10 ，（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。2设有序表为（13，19，25，36，48，51

17、，63，84，91，116，135，200），元素的下标依次为1,2,12. （1）说出有哪几个元素需要经过3次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到.3 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题（每空2分，共16分）1以下冒泡法程序对存放在a1，a2，an中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程

18、序按升序排列。Void bsort (NODE a , int) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break; 程序中flag的功能是（5） 7以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域为data，其数据类型为字符型，BT指向根结点）。Void Postorder (struct BTree Node

19、 *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 试题答案；一、单项选择题（每小题2分，共30分）1A 2D 3B 4B 5A 6C 7C 8B 9A 10A 11A 12D 13D 14A 15D二、填空题（每小题2分，共24分）1.p-next=s; 2.集合、线性、树形、图状 3. f=f-next;4.中序5.n6. dgbaechhif 7.行号、列号、元素值8.4次9.正确10查找方法113次12先进后出 先进先出三、综合题（每小题10分，共30分）1(1) 初始 11，19，5，4，7，13，2，10第一趟 11，194，57，132，10第二趟 4，5，

20、11，192，7，10，13 第三趟 2，4，5，7，10，11，13，19(2)13510111972421011519741371310131011254191924719911152 (1)13,36,63,135 471285211110639(2) (3)3次53(1)14218647163(2)中序遍历中序 2，3，4，5，6，7，14，16，18四、程序填空题（每空2分，共16分）1（1）j=n-1（2）i=n-j（3）ai=ai+1（4）ai+1=temp（5）当某趟冒泡中没有出现交换则已排好序，结束循环 2（1） Postorder(BTleft)（2）Postorder(BTright)（3） printf(“%c”,BTdata)