本站原创广播电视大学计算机科学与技术专业
数据结构课程考核说明(2006年版)
一,考核说明
《数据结构》是全国电大计算机科学与技术专业(专科起点本科)的基础课程之一.该课程是后续课程如操作系统,计算机网络,软件工程等课程的先修课程,在整个专业教学中占有核心地位.该课程主要介绍在软件开发中如何进行数据结构和算法的设计.因此,用抽象数据类型以及面向对象的方法组织,存储各种数据并进行查找,插入,删除等数据处理运算是本课程的重点.面向对象方法与结构化方法的结合是建立高质量软件的基础,学员需要通过课程的学习和实践,不断加深对这些先进软件开发方法的理解和体会.在课程中将按照软件工程思想,介绍用面向过程和面向对象方法进行数据结构设计和程序设计的基本思想和具体实现.
现将考核的有关问题说明如下:
1.考核对象全国电大系统开放教育试点计算机科学与技术专业(专科起点本科)学生.
2.教学媒体
主教材《数据结构》殷人昆编着清华大学出版社出版.
实验教材《数据结构实验(本科)》徐孝凯等编广播电视大学出版社出版,从2004年开始出版使用.
辅助教材《数据结构习题解析》殷人昆徐孝凯编清华大学出版社出版,选用.
录象教材10讲殷人昆主讲广播电视大学音像出版社出版.
复习资料《数据结构期末复习指导》电大教育杂志社出版发行.
作业练习《数据结构形成性考核作业册》电大教育杂志社出版发行.
网上辅导在电大在线计算机科学与技术《数据结构》课程网页上发表.
3.命题依据本考核说明以电大计算机科学与技术专业《数据结构教学大纲》为依据编制.本考核说明是考试命题的依据.
4.考核要求本课程是以实用为最终目的,因此,考核的重点是考察学员对各种数据结构的理解程度和基于这些数据结构进行算法设计的能力.具体考核要求分为如下三个层次:
理解:要求学员理解各种数据结构的定义和特点,在各种数据结构上进行插入,删除等运算的思路和方法.
应用:要求学员会分析现成的数据结构算法,能够根据实际数据处理要求采用合适的数据结构和处理方法设计出较好地算法.
综合应用:要求学员能综合运用多个知识点进行比较复杂的算法分析和设计,考察学员综合分析和解决问题的能力.
5.命题原则
(1)在教学大纲和考核说明所规定的知识范围内命题.在教学知识范围之内,需要灵活运用才能够解决问题的试题不属于超纲.
(2)试题的考察要求覆盖面广,区分度高.
(3)试题兼顾各个能力层次,理解占40%,简单运用占40%,综合运用占20%.
(4)试题的难易程度和题量适当,按难易程度分为四个层次:容易占20%,较易占30%,较难占30%,难占20%.题量安排以平时能够独立完成作业者,使他们能在规定的考试时间内做完并有一定时间检查为原则.
6.试题题型
单项选择题:给出有关数据结构概念,性质,特点或简单算法的不完整叙述,要求考生从题后给出的四种选择答案中选择合适的一种答案,补充完整.
填空题:给出一段有关数据结构概念,性质,特点或简单算法的叙述,其中在划有横线的地方缺少内容,要求考生填写完整.
判断题:给出一段有关数据结构概念,性质或特点叙述,要求考生判断正误(或对错).
运算题:通过分析,计算或作图,对一些数据结构进行运算,得到运算结果.如得到树或图的遍历结果,得到图的最小生成树,得到数据散列存储的散列表,得到对数据进行某种排序的结果等.
算法分析题:给出一段算法或程序,通过阅读和分析回答一些问题.如根据给定输入数据写出程序运行结果,指出算能,按算能把算法中缺少的内容补充完整.
算法设计题:给出算法设计要求和相应数据结构表示,编写出满足要求的算法.
7.考核形式
采用期末考核与形成性考核相结合的方式.形成性考核分为两种,一种视作业完成情况和实验完成情况而定,占总成绩的15%,另一种为期末上机考核,占总成绩的15%,完成一个指定题目的程序开发和调试,由各省级电大在省内统一命题,时间为60分钟.期末考核占总成绩的70%,为闭卷考试,由电大统一命题,答卷时限从2006年下学期开始为120分钟.总成绩满分为100分,合成成绩达60分及以上者可获得该课程规定的4学分,否则不获得该课程学分.
二,考核内容和要求
第一部分有关数据结构和算法分析的基本知识
考核目的:
考核学员对有关数据,数据结构,抽象数据类型,面向对象思想的基本概念等的理解情况,以及对算法的定义和性能分析的掌握情况.
考核的知识点:
数据逻辑结构和存储结构的定义和分类,
数据类型与抽象数据类型的概念,
面向对象的概念,
算法的特性,
算法的性能分析与度量,时间复杂度,空间复杂度,时间复杂度和空间复杂度的渐进表示法.
考核要求:
理解:有关数据结构的基本概念.
理解:抽象数据类型及面向对象的概念.
理解:算法的定义及算法的特性.
应用:算法的性能分析与度量方法.
第二部分数组
考核目的:
考核学员对数组,顺序表,字符串的类的定义与实现,对一般数组和特殊数组的顺序存储分配的方法和元素地址的计算,对稀疏矩阵的概念等内容掌握的程度.
考核的知识点:
作为抽象数据类型的数组:数组类的定义和初始化,相关操作的实现.
顺序表:顺序表类的定义,顺序表的查找,插入和删除算法.
稀疏矩阵:稀疏矩阵的抽象数据类型和压缩表示.
字符串:字符串类的定义和有关操作的实现.
考核要求:
理解:数组类的定义和操作实现.
理解:顺序表类的定义及操作实现.
理解:字符串类的定义及操作实现,稀疏矩阵的定义和表示.
应用:能够分析和设计带有数组类,顺序表类,字符串类的成员函数并分析其时间和空间复杂度.
应用:会把三角矩阵,对称矩阵,三对角矩阵等特殊矩阵用一维数组存储起来,并进行相应元素地址的计算.
第三部分链接表
考核目的:
考核学员对链接表(包括单链表,循环链表,双向链表)的构成和使用的掌握程度,对利用链表求解应用问题(如多项式操作)的能力.
考核的知识点:
单链表:单链表的结构,单链表的类定义,单链表中的插入与删除,带表头结点的单链表,用模板定义的单链表类,静态链表.
循环链表:循环链表的类定义.
多项式及其相加:多项式的类定义,多项式的加法.
双向链表及其操作.
考核要求:
理解:单链表,循环链表及双向链表的定义及实现.
理解:多项式类的定义及其加法运算.
应用:针对单链表的各种插入,删除等运算的算法及性能分析.
第四部分栈与队列
考核目的:
考核学员对栈,队列,优先级队列等限制存取点的表的掌握程度和应用它们解决实际问题的能力.
考核的知识点:
栈:栈的抽象数据类型,栈类的顺序存储表示和运算,栈类的链接存储表示和运算,利用栈进行表达式的计算.
队列:队列的抽象数据类型,队列类的顺序存储表示和运算,队列类的链接存储表示和运算.
优先级队列:优先级队列的定义,优先级队列的存储表示和操作实现.
考核要求:
理解:栈的定义及操作的实现.
理解:队列的定义及操作的实现.
理解:优先级队列的定义及操作的实现.
应用:表达式的各种表示法,相互转换和求值过程.
应用:按层次输出二项展开式的系数(杨辉三角形).
应用:利用栈和队列进行算法的分析和设计.
第五部分递归与广义表
考核目的:
考核学员对递归问题求解方法的掌握情况以及对广义表的递归解法的掌握程度,并考察学员采用递归方法求解应用问题的能力.
考核的知识点:
递归概念:递归的定义,递归的数据结构,递归问题的解法.
迷宫问题:递归求解思路.
递归过程与递归工作栈:递归过程实现的机制及递归工作栈的引用.
广义表:广义表的概念,广义表的表示及操作,广义表存储结构的实现.
考核要求:
理解:递归的概念,递归问题的递归求解方法.
理解:递归过程的机制与利用递归工作栈实现递归的方法.
理解:广义表的定义及其存储表示.
应用:利用递归的思想进行递归求解的算法设计.
第六部分树与森林
考核目的:
考核学员对树,二叉树,堆,哈夫曼(Huffman)树等数据结构的掌握程度和应用能力.
考核的知识点:
树和森林:树和森林的概念,树的定义和性质,树的抽象数据类型.
二叉树:二叉树的定义,性质和抽象数据类型.
二叉树的存储结构:数组表示,链表存储表示.
二叉树遍历:中序遍历,前序遍历,后序遍历,层次遍历等的方法与算法.
二叉树的其他运算的方法与算法:如建立二叉树,查找二叉树,求叶子结点数,求二叉树深度等.
堆:堆的定义,堆的建立过程,堆的插入与删除运算的算法.
树与森林:树的存储表示,森林与二叉树的转换,树的先根,后根和按层遍历方法与算法,森林的遍历方法.
霍夫曼树:霍夫曼树的概念和建立过程,霍夫曼编码.
考核要求:
理解:树和森林的概念.
理解:二叉树的概念,性质及二叉树的表示,霍夫曼编码的概念.
理解:堆的概念,堆的建立方法,哈夫曼树的概念,构造哈夫曼树的过程,进行哈夫曼编码的方法.
应用:二叉树的各种遍历算法及有关其它运算的算法.
应用:树的各种遍历算法.
应用:利用二叉树的遍历结果确定二叉树的方法与过程.
应用:霍夫曼树的带权路径长度的计算.
综合应用:运用二叉树,堆的知识解决较复杂的应用问题.
第七部分集合与搜索
考核目的:
考核学员对集合,顺序和折半搜索,二叉搜索树运算,平衡二叉树(L)树运算的理解掌握程度.
考核的知识点:
集合:集合的概念,位向量表示和链表表示,对集合并,交,差等运算的算法.
搜索:搜索的概念,顺序搜索方法和算法,折半搜索的方法和算法.
二叉搜索树:二叉搜索树的定义和特性,在二叉搜索树上进行查找,插入,删除等运算的方法和递归及非递归算法.
L树:L树的定义,各种平衡化旋转的方法,在L树上插入和删除元素的过程.
考核要求:
理解:集合的概念和表示,顺序和折半搜索的方法,在二叉搜索树上进行各种运算的过程.
理解:L树的构造,插入和删除元素时的调整方法及其性能分析.
应用:分析和设计对集合的各种运算的算法.
应用:基于数组的顺序搜索和折半搜索的算法分析与设计.
应用:二叉搜索树的查找,插入,删除等算法的分析与设计.
第八部分图
考核目的:
考核学员对图的存储表示和遍历,求图的最小生成树,最短路径,拓扑排序,关键路径等内容的的理解和掌握程度.
考核的知识点:
图的基本概念:图的基本概念,图的抽象数据类型.
图的存储表示:图的邻接矩阵,邻接表,邻接多重表,边集数组等表示
图的简单运算:如求邻接顶点,求顶点出度和入度等.
图的遍历与连通性:深度优先搜索和广度优先搜索的方法与算法,求连通分量及关节点的方法,重连通分量的概念.
最小生成树:Kruskal算法和Prim算法求图的最小生成树的过程.
最短路径:Dijkstra算法求图中一顶点到其余各顶点的过程.
活动网络:求AOV网的拓扑序列的方法和算法,求AOE网的关键路径的方法.
考核要求:
理解:图的基本概念和存储表示.
理解:图的深度优先搜索和广度优先搜索的过程.
理解:求图的最小生成树,最短路径,拓扑排序,关键路径的方法和过程.
理解:求图的连通性的方法,求图的关节点及构造重连通图的方法.
应用:图的两种遍历的算法.
应用:求AOV网的拓扑排序的算法描述.
第九部分排序
考核目的:
考核学员对各种典型排序方法及性能的理解和掌握程度.
考核的知识点:
概念:排序的概念,排序的时间时间和空间复杂度,排序方法的稳定性.
插入排序:直接插入排序,链表插入排序,希尔排序等.
交换排序:起泡排序,快速排序.
选择排序:直接选择排序,链表选择排序,堆排序.
归并排序:两有序表合并,一躺归并,在顺序表上进行归并排序的非递归算法,在链表上进行归并排序的递归算法.
外排序:外排序的基本过程,k路平衡归并的过程和趟数计算.
基数排序:基数排序的方法.
考核要求:
理解:排序的基本概念和性能分析方法.
理解:各种排序的方法和过程,它们的时,空间复杂度分析和稳定性分析.
理解:多路平衡归并的过程.
应用:直接插入排序,直接选择排序,快速排序,堆排序,归并排序等的算法描述.
综合应用:对顺序表或链表,综合运用搜索,排序,插入,删除等运算解决数据处理问题.
第十部分索引与散列结构
考核目的:
考核学员对索引与散列存储结构的理解与掌握程度.
考核的知识点:
静态索引结构:索引的概念,线性索引,倒排表,m路静态搜索树.
动态索引结构:B树的结构特点,B树的查找,插入和删除的方法.
散列:散列的概念,散列表与散列方法,散列函数,装填因子,处理冲突的闭散列方法,处理冲突的开散列方法,散列存储的性能分析.
考核要求:
理解:索引与散列的概念,线性索引与B树索引的方法,散列存储的方法.
应用:B树的查找,插入和删除元素的方法与过程.
应用:散列函数的构造,解决冲突的方法,在散列表上进行查找,插入,删除元素的过程与算法描述.
三,期末考核试题样例及解答
一,单选题从供选择的答案中选出正确的答案,将其编号填入括号中.
1.在数据结构的讨论中把数据结构从逻辑上分为().
A.内部结构与外部结构B.静态结构与动态结构
C.线性结构与非线性结构D.紧凑结构与非紧凑结构
2.采用线性链表表示一个向量时,要求占用的存储空间地址().
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.可连续可不连续
3.采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为().
A.nB.n/2C.(n-1)/2D.(n+1)/2
4.在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行().
A.s→link等于p→link,p→link等于s,B.p→link等于s,s→link等于q,
C.p→link等于s→link,s→link等于p,D.q→link等于s,s→link等于p,
5.如果想在4092个数据中只需要选择其中最小的10个,采用()方法最好.
A.起泡排序B.堆排序C.直接选择排序D.快速排序
6.设有两个串t和p,求p在t中首次出现的位置的运算叫做().
A.求子串B.模式匹配C.串替换D.串连接
7.在数组A中,每一个数组元素A[i,j]占用3个存储字,行下标i从1到8,列下标j从1到10.所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字数是().
A.80B.100C.240D.270
8.将一个递归算法改为对应的非递归算法时,通常需要使用().
A.栈B.队列C.循环队列D.优先队列
9.一个队列的进队列顺序是1,2,3,4,则出队列顺序为().
A.4,3,2,1B.2,4,3,1
C.1,2,3,4D.3,2,1,4
10.在循环队列中用数组A[0..m-1]存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是().
A.(front-rear+1)%mB.(rear-front+1)%m
C.(front-rear+m)%mD.(rear-front+m)%m
二,判断题判断下列各个叙述的正误.对,在题号前的括号内填入"(",错,在题号前的括号内填入"(".
()1.算法的运行时间涉及加,减,乘,除,转移,存,取等基本运算.要想准确地计算总运算时间是不可行的.
()2.二维数组是数组元素为一维数组的线性表,因此二维数组元素之间是线性结构.
()3.顺序表用一维数组作为存储结构,因此顺序表是一维数组.
()4.通常使用两个类来协同表示单链表,即链表的结点类和链表类.
()5.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同.
()6.在使用后缀表示实现计算器类时用到一个栈类的实例,其作用是暂存运算对象.
()7.具有n个结点的完全二叉树的高度为(log2n(+1.(n(0,根在第0层)
()8.为度量一个搜索算法的效率,需要在时间和空间两个方面进行分析.
()9.闭散列法通常比开散列法时间效率更高.
()10.一棵m阶B树中每个结点最多有m个关键码,最少有2个关键码.
三,填空题把合适的内容添到横线上.
1.对于一个单链接存储的线性表,检测定表头指针指向链表的第一个结点,则在表头插入结点的时间复杂度为________,在表尾插入结点的时间复杂度为________.
2.检测定一棵三叉树(即度为3的树)的结点个数为50,则它的最小高度为________,检测定树根结点为第0层.
3.一棵高度(检测定树根结点为第0层)为4的完全二叉树中的结点数最少为________个,最多为________个.
4.在一个具有n个顶点的无向图中,要连通所有顶点则至少需要________条边.
5.从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时,其查找长度分别为________和________.
6.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个________.
7.在开散列表中,处理冲突的方法为________法,在闭散列表中,处理冲突的方法为____________法.
8.在堆排序的过程中,对任一分支结点进行筛运算(即调整为子堆的过程)的时间复杂度为________,整个堆排序过程的时间复杂度为________.
9.快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为________.
10.在二路归并排序中,对n个记录进行归并的趟数为________.
四,运算题
1.检测定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d),分别写出先根,后根,按层遍历的结果.
先根:
后根:
按层:
2.若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},从顶点A开始分别对该图进行深度优先搜索和广度优先搜索,要求顶点值小的邻接点被优先访问,则写出得到的深度优先搜索和广度优先搜索的顶点序列.
深度优先搜索得到的顶点序列:
广度优先搜索得到的顶点序列:
3.已知一个二叉搜索树的广义表表示为38(25(16),52(,74(68(,72),90))),在下表中填写出每个元素的比较次数.
12345678
3825521674689072
4.检测定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探测法处理冲突,试求出每一元素在闭散列表中的初始散列地址和最终散列地址,画出最后得到的散列表,求出平均查找长度.
12345678910
元素32752963489425461870
初始散列地址
最终散列地址
0123456789101112
散列表
平均查找长度:
5.已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每一趟的排序结果.
五,算法分析题
1.给出下列每个递归过程的执行结果.
(1)voidunknown(intw){
if(w){
unknown(w-1),
for(inti等于1,i<,等于w,i++)cout<,<,w,
cout<,<,endl,
}
}
调用语句为unknown(4).
(2)voidunknown(intn){
cout<,<,n%10,
if(n/10)unknown(n/10),
}
调用语句为unknown(582).
(3)intunknown(intm){
intvalue,
if(！m)value等于3,
elsevalue等于unknown(m-1)+5,
returnvalue,
}
执行语句为cout<,<,unknown(3).
2.请写出下面算法的功能,其中Stack表示栈类,Queue表示队列类.
voidunknown(Queue&,Q)
{
StackS,intd,
S.InitStack(),//初始化S为空栈
while(！Q.IsEmpty()){//队列Q不为空则循环
Q.DeQueue(d),//出队列元素的值由变量d带回
S.Push(d),//d的值压入S栈
}
while(！S.IsEmpty()){//栈S不为空则循环
S.Pop(d),//出栈元素的值由变量d带回
Q.EnQueue(d),//d的值插入队列Q中
}
}
算能:
3.检测定btnode为二叉树中的结点类型,它含有数值域data,左指针域lchild和右指针域rchild,下面函数中的参数BT指向一棵二叉树的树根结点,X为给定元素,请给出该函数的功能.
btnode*AAA(btnode*BT,datatypeX)
{
if(BT等于等于NULL)returnNULL,
else{
if(BT->,data等于等于X)returnBT,//返回值为X结点的指针
else{
btnode*mt,
if(mt等于AAA(BT->,lchild,X))returnmt,
elseif(mt等于AAA(BT->,rchild,X))returnmt,
elsereturnNULL,
}
}
}
六,算法设计题
1.设计一个算法,从树根指针为rbitreptr的二叉树中删除结点值为x的子树,若删除成功则返回1,否则返回0.检测定在算法中不要求回收被删除子树中的所有街道,算法中的bitreptr为结点指针类型,所指结点类型包含三个域,即值域data,左指针域lchild和右指针域rchild.
intdeleteSubtree(bitreptr&,r,datatypex),
2.已知二叉搜索树中的结点类型用BtreeNode表示,被定义为:
structBtreeNode{ElemTypedata,BtreeNode*left,*right,},
其中data为结点值域,left和right分别为指向左,右孩子结点的指针域.检测定具有BtreeNode*类型的指针参数BST指向一棵二叉搜索树的根结点,试根据下面的函数声明编写一个非递归算法,向BST树中插入值为item的结点,若树中不存在item结点则进行插入并返回1表示插入成功,若树中已存在item结点则不插入并返回0表示插入失败.
intInsert(BTreeNode*&,BST,constElemType&,item),
参考解答
一,单选题:
1.C2.D3.D4.D5.B6.B7.C8.A9.C10.D
二,判断题
1.(2.(3.(4.(5.(6.(7.(8.(9.(10.(
三,填空题
1.O(1)O(n)
2.4
3.1631
4.n-1
5.13
6.有序序列
7.链接开放定址
8.O(log2n)O(nlog2n)
9.O(nlog2n)O(n2)
10.(log2n(
四,运算题
1.先根:a,b,e,c,f,h,i,j,g,d,
后根:e,b,h,i,j,f,g,c,d,a,
按层:a,b,c,d,e,f,g,h,i,j
2.深度优先搜索得到的顶点序列:A,B,D,E,F,C
广度优先搜索得到的顶点序列:A,B,C,D,F,E
3.12345678
3825521674689072
12233445
4.平均查找长度为14/10.
12345678910
元素32752963489425461870
初始散列地址6103119312755
最终散列地址6103119412758
0123456789101112
散列表29941832467048756325
5.
12345678910
(0)[46745314263886652734]
(1)[3414263827]46[86655374]
(2)[271426]343846[746553]86
(3)[2614]27343846[5365]7486
(4)[1426]2734384653657486
五,算法分析题
1.
(1)1
22
333
4444
(2)285
(3)18
2.利用"栈"作为辅助数据结构,将队列Q中的元素逆置(即按相反次序放置).
3.从BT为树根指针的二叉树上查找值为X的结点,若查找成功则返回该结点指针,否则返回空.
六,算法设计题
1.//从二叉树中删除根结点值为x的子树,若删除成功则返回1,否则返回0
intdeleteSubtree(bitreptr&,r,datatypex)
{
if(r等于等于NULL)return0,
else{
if(r->,data等于等于x){r等于NULL,return1,}
else{
if(deleteSubtree(r->,lchild,x))return1,
if(deleteSubtree(r->,rchild,x))return1,
}
}
}
2.//向二叉搜索树插入元素
intInsert(BTreeNode*&,BST,constElemType&,item)
{
//查找插入位置
BTreeNode*t等于BST,*parent等于NULL,
while(t！等于NULL){
parent等于t,
if(item等于等于t->,data)return0,
elseif(item<,t->,data)t等于t->,left,
elset等于t->,right,
}
//建立值为item,左,右指针域为空的新结点
BTreeNode*p等于newBTreeNode,
p->,data等于item,
p->,left等于p->,right等于NULL,
//将新结点插入到二叉搜索树中的确定位置上
if(parent等于等于NULL)BST等于p,
elseif(item<,parent->,data)parent->,left等于p,
elseparent->,right等于p,
}
2