下载可编辑
中央广播电视大学
数据结构（本）期末复习指导
第一部分 课程考核说明
一、考核说明
数据结构（本）是中央广播电视大学计算机科学与技术（本科）专业的一门统设必修、学位课程。4学分，72学时，其中实验24学时，开设一学期。课程主要容包括：数据结构和算法的基本概念、线性表、栈和队列、串、数组和广义表、树和图、查找和排序等。目的是使学生通过该课程的学习，深入地理解数据的逻辑结构和物理结构以及有关算法，掌握基本的程序设计技能，学会编制高效可靠的程序，为学习后续课程奠定基础。 现将有关考核的几个问题说明如下： 1．考核对象
2007年秋季起入学的计算机科学与技术专业（本科）学生。 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. 25
4.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（ ）。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是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．3
7．在一个单链表中，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
a c b c
d g
e f
图1
10 . 任何一个无向连通图的最小生成树（ ）。
A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在
11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ ）。
A．33 B．32 C．85 D．41 12 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A．31，29，37，85，47，70 B．29，31，37，47，70，85
C．31，29，37，70，47，85 D．31，29，37，47，70，85
13 . 对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（ ）。
A.原序列是升序排列 B.原序列是降序排列
C.对序列只进行了2趟冒泡 D. 对序列只进行了3趟冒泡
14．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行
.专业.整理.
电大数据结构(本)期末复习指导
