数据结构考核说明

1、清华大学计算机科学与技术专业数据结构考核说明I. 考核说明II. 考核内容和要求第一章 有关数据结构和算法分析的基本知识第二章 数组第三章 链接表第四章 栈与队列第五章 递归与广义表第六章 树与森林第七章 集合与搜索第八章 图第九章 排序第十章 索引与散列结构附录：试题类型及规范解答举例I. 考核说明数据结构是大学计算机科学与技术专业本科生的专业基础课程之一，该课程是后续课程如操作系统、计算机网络等课程的先修课程，在整个教学体系中占据非常重要的地位。该课程主要介绍在软件开发中如何进行数据结构和算法的设计。因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学生需要

2、掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，需要通过课程的学习和实践，不断加深对这些先进软件开发方法的理解和体会。因此，在课程中将按照软件工程思想，进一步介绍用面向过程和面向对象方法进行数据设计和程序设计的基本思想，在必要的课程实践中逐步熟练掌握。教学考核的主要目的也在于此。现将有关考核的几个问题说明如下：1、考核对象：计算机科学与技术专业本科生。2、命题依据：本考核说明以清华大学计算机科学与技术系本科生数据结构教学大纲为依据编制。本考核说明是考试命题的依据。3、考核要求：本课程是以实用为最终目的，因此，考核的重点是考察学生对各种数据结构的理解程度和基于这些数据结构进行算法

3、设计的能力。不要求学生死记具体的定义，但需要学生在实践过程中逐步熟练运用。具体考核要求分为几个层次： 理解：要求学生理解各种数据结构的层次、各种数据结构的特点、各种数据结构设计的基本思想。这是学生学习数据结构课程的基本要求，但是理解，不是死记硬背。 掌握：要求学生能较好地理解和运用所介绍的方法和解题思路解决问题和进行简单的算法设计，考察学生解决问题的基本能力。 综合应用：要求学生能综合运用多个知识点的内容进行比较复杂的应用程序开发，考察学生综合解决问题的能力。不同的综合层次将考察学生的综合能力的高低。4、命题原则 在教学大纲和考核说明所规定的目的、要求和内容范围之内命题。在教学内容范围之内，按

4、照理论联系实际原则，考察学生对所学知识应用能力的试题，不属于超纲。 试题的考察要求覆盖面广，并适当突出重点。 试题兼顾各个能力层次，理解占40%，简单运用占40%，综合运用占20%。 试题的难易程度和题量适当，按难易程度分为四个层次：容易占20%，较易占30%，较难占30%，难占20%。题量安排以平时基本能够独立完成作业者，他们能在规定的考试时间内作完并有一定时间检查为原则。5、试题题型有单选题、填空题、简答题、理解问答题和综合编程题等五种题型。 单选题：给出一些有关数据结构性质、特点及一些简单算法性能的不完全叙述，要求学生从题后给出的供选择的答案中选择合适的答案，补足这些叙述。这类题目主要考

5、察学生对各种数据结构和算法设计方法相关知识的掌握程度。 填空题：给出程序说明及一段部分语句缺失的程序，让学生补充成为完整的程序。这类题目主要考察学生基于数据结构或算法，阅读理解程序的能力。 简答题：应用作图方法或简单计算，使用给定数据建立或操作一些数据结构。这类题目主要考察学生的理解问题与解决问题的基本能力。 理解问答题：给出一段程序，就程序回答一些问题，如给出程序运行结果、根据要求进行适当修改等。目的在于考核学生对数据结构与算法的相关知识点的掌握程度，如递归、回溯、排序、搜索等。 综合算法题：给出算法设计要求，编制出部分算法程序，用来考察若干个知识点。考察学生综合运用所学习知识解决问题的能力

6、。如通过栈实现一些非递归算法的能力、综合运用树与图等数据结构实现一些有关漫游问题等。具体形式见后面所附“试题类型及规范解答举例”。6、考核形式：采用期末考核与平时成绩相结合的方式。其中 平时考核：视平时作业（包括笔做题和上机题）的完成情况给分，占考核总成绩的20%，能够按时、按质、按量完成平时作业者方可得满分； 期中考核: 采用笔试，它占总成绩的20%，考试方式为闭卷，答题时限90分钟。 期末考核：采用笔试，它占总成绩的80%，考试方式为闭卷，答题时限120分钟。以上三项成绩累计60分以上（包括60分）算考核通过。II. 考核内容和要求第一章 有关数据结构和算法分析的基本知识考核目的：考核学生

7、对有关数据、数据结构、抽象数据类型、面向对象思想的基本概念的理解、算法及简单的算法分析的掌握情况考核的知识点：什么是数据结构抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言算法定义性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度考核要求：理解：数据结构基本概念理解：抽象数据类型及面向对象概念理解：算法的定义及算法的特性掌握：算法的性能分析与度量方法第二章 数组考核目的：考核学生对数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构的基本理解和掌握程度考

8、核的知识点：作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组的相关操作的实现顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例字符串：字符串的抽象数据类型；字符串操作的实现；字符串的简单模式匹配考核要求：理解：作为抽象数据类型的数组的定义理解：顺序表的定义方式及实现掌握：应用顺序表作为集合的简单操作理解：字符串的定义及实现综合应用：应用字符串实现简单的文本编辑中的操作第三章 链接表考核目的：考核学生对链接表抽象数据类型（包括单链表、循环链表、双向链表）的理解及用链表实现并求解应用问题（如多项式操作）的应用能力。考核的知识点：单链表：单链表的

9、结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表循环链表：循环链表的类定义；用循环链表解约瑟夫问题多项式及其相加：多项式的类定义；多项式的加法双向链表考核要求：掌握：单链表、循环链表及双向链表的定义及实现理解：多项式类的定义及其加法运算第四章 栈与队列考核目的：考核学生对栈、队列、优先级队列等限制存取点的表的掌握程度和应用它们解决应用问题的能力。考核的知识点：栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示；栈的应用队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；队列的应用举例优先级队列：优先级队列的定义；优先级队列的存

10、储表示考核要求：理解：栈的定义及实现掌握：表达式求值理解：队列的定义及实现 掌握：按层次输出二项展开式的系数（杨辉三角形）理解：优先级队列的定义及链表实现算法第五章 递归与广义表考核目的：考核学生对递归问题求解方法的掌握情况以及对广义表的递归解法的掌握程度，并考察学生应用递归方法求解应用问题的能力。考核的知识点：递归概念：递归的定义、递归的数据结构、递归问题的解法迷宫问题：递归求解思路递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用；用栈实现的迷宫问题非递归解法广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的建立、访问、求深度、删除等算法考核要求：理解：递归的

11、概念、递归问题的递归求解方法理解：递归过程的机制与利用递归工作栈实现递归的方法掌握：利用栈实现迷宫问题的非递归解法理解：广义表的定义及其实现方法掌握：广义表的递归算法第六章 树与森林考核目的：考核学生对树、二叉树等重要数据结构的理解程度和特定的应用（如堆、霍夫曼树等）的掌握情况。考核的知识点：树和森林的概念：树的定义；树的术语；树的抽象数据类型二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型二叉树的表示：数组表示；链表存储表示二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化堆：堆的定义；堆的建立；堆的插入与删除树与森

12、林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历二叉树的计数霍夫曼树：路径长度；霍夫曼树；霍夫曼编码考核要求：理解：树和森林的概念理解：二叉树的概念、性质及二叉树的表示掌握：二叉树的遍历算法及其它应用算法理解：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：堆的定义及其实现的方法，以及用来实现优先级队列的算法掌握：树与森林的实现和树的遍历算法理解：二叉树的计数方法及从二叉树的前序和中序遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法及霍夫曼编码的概念第七章 集合与搜索考核目的：考核学生对集合结构、集合的应用、与集合相关的搜索方法和简单的性能分析方法的理解和掌握情况。考核的知识点

13、：集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用向量实现集合抽象数据类型；用有序链表实现集合的抽象数据类型并查集 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的折半搜索二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除AVL树：AVL树的定义；平衡化旋转；AVL树的插入和删除；AVL树的结点个数与高度的关系考核要求：掌握：集合及其表示方法，包括数组及有序链表的表示及其相关操作的实现算法掌握：并查集的实现方法掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法掌握：AVL树的构

14、造、插入、删除时的调整方法及其性能分析第八章 图考核目的：考核学生对图和网络结构的存储表示、图的遍历、最小生成树、活动网络等重要应用求解方法的理解和掌握情况。考核的知识点：图的基本概念：图的基本概念；图的抽象数据类型图的存储表示：邻接矩阵；邻接表；邻接多重表，典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法图的遍历与连通性：深度优先搜索和广度优先搜索算法；连通分量；重连通分量最小生成树：Kruskal算法；Prim算法单源最短路径：Dijkstra算法活动网络：用顶点表示活动的网络；用边表示活动的网络考核要求：理解：图的基本概念掌握：图的存储表示掌握：图的两种遍历算法

15、与求解连通性问题的方法理解：求解关节点及构造重连通图的方法掌握：构造最小生成树的Prim算法和Kruskal方法掌握：求解单源最短路径的dijkstra算法掌握：活动网络的拓扑排序算法掌握：求解关键路径的方法第九章 排序考核目的：考核学生对各种典型排序方法及其性能分析方法的理解和掌握情况。考核的知识点：概念：排序的定义、排序的时间代价、排序方法的稳定性插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序交换排序：起泡排序；快速排序选择排序：直接选择排序；链表选择排序；锦标赛排序；堆排序归并排序：归并；迭代的归并排序算法；递归的链表归并排序基数排序：多关键码排序；链式基数排序外排序：外排

16、序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树考核要求：理解：排序的基本概念和性能分析方法掌握：插入排序（直接插入排序；折半插入排序；链表插入排序）、交换排序（起泡排序；快速排序）、选择排序（直接选择排序；链表选择排序；锦标赛排序；堆排序）、归并排序等内排序的方法、算法及其性能分析方法理解：基数排序方法及其性能分析方法理解：多路平衡归并等外排序方法及败者树构造方法理解：生成初始归并段及败者树构造方法理解：最佳归并树的建立方法第十章 索引与散列结构考核目的：考核学生对索引与散列结构（即用于外部搜索的文件结构）的了解程度和掌握情况。考核的知识点：静态索引结构：线性索引；倒排表；m路静态搜

17、索树动态索引结构：动态的m路搜索树；B树；B树的插入；B树的删除；B+树的插入与删除散列：散列表与散列方法；散列函数；处理冲突的闭散列方法；处理冲突的开散列方法；散列表分析 考核要求：掌握：静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法掌握：动态索引结构，包括B树、B+树的搜索和构造方法掌握：散列法，包括散列函数的构造、解决冲突的方法附录：试题类型及规范解答举例一、单选题 从供选择的答案中选出正确的答案，将其编号填入括号中。1、在数据结构的讨论中把数据结构从逻辑上分为（ ）。 A: 内部结构与外部结构 B: 静态结构与动态结构C: 线性结构与非线性结构 D 紧凑结构与非紧凑结

18、构2、采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。 A: 必须是连续的 B 部分地址必须是连续的C: 一定是不连续的 C: 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。 A: nB: n/2C: (n-1)/2 D: (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。 A: slink = plink; plink = s;B: plink = s; slink = q;C: plink = slink; slink = p;D: qlink = s; slink = p;5、如果想

19、在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。 A: 起泡排序 B: 堆排序 C: 锦标赛排序 D: 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A: 求子串 B: 模式匹配 C: 串替换 D: 串连接7、在数组A中，每一个数组元素Ai, j 占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。 A: 80 B: 100 C: 240 D: 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 A: 栈 B: 队列 C: 循环队列D: 优先队列

20、9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ ）。 A: 4, 3, 2, 1 B: 2, 4, 3, 1 C: 1, 2, 3, 4 D: 3, 2, 1, 410、在循环队列中用数组A0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 A: ( front - rear + 1) % m B: ( rear - front + 1) % mC: ( front - rear + m) % m D: ( rear - front + m) % m二、阅读理解题给出下列递归过程的执行结果。(1) void unknown

21、( int w ) if ( w ) unknown ( w-1 ); for ( int i = 1; i = w; i+ ) cout w; cout endl; 调用语句为 unknown (4)。 (2) void unknown ( int m ) cout n % 10 ; if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); 调用语句为unknown ( 582 )。(3) int unknown ( int m ) int value; if ( ! m ) value = 3; else value = unknown ( m-1

22、 ) + 5; return value;执行语句为 cout unknown (3)。 三、填空题设单链表结构为 struct ListNode int data ; ListNode * link ; ;下面的程序是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间, 排序过程中不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。在初始状态下, 所有待排序记录链接在一个以r为头指针的单链表中。例如, 在算法实现时，利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数

23、据类型为Queue, 其可直接使用的相关操作有n 置空队列操作：makeEmpty ( ); n 将指针x加入到队列的队尾操作：EnQueue ( ListNode * x ); n 退出队头元素, 其值由函数返回的操作：ListNode *DlQueue ( );n 判队列空否的函数, 空则返回1, 不空则返回0：int IsEmpty( )。 解决方法提示： 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。 当队列不空时, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。 如果队列中退出一个有序子链

24、表后变成空队列, 则算法结束。这个有序子链表即为所求。在算法实现时有 6 处语句缺失，请阅读程序后补上。(1) 两路归并算法void merge ( ListNode * ha, * hb; ListNode *& hc ) ListNode *pa, *pb, *pc ; if ( hadata = hbdata ) hc = ha; pa = halink; pb = hb; else hc = hb; pb = hblink; pa = ha ; pc = hc; while ( pa & pb ) if ( ) pclink = pa; pc = pa; ; else pclink =

25、 pb; pc = pb; ; if ( pa ) pclink = pa; else pclink = pb; ;(2) 归并排序主程序void mergesort ( ListNode * r ) ListNode * s, t; Queue Q ; if ( ! r ) return; s = r; ; while ( s ) t = slink; while ( t != 0 & sdata = tdata ) s = t; t = tlink; if ( t ) slink = 0; s = t; ; while ( !Q.IsEmpty( ) ) r = Q.DlQueue( );

26、 if ( Q.IsEmpty( ) ) break; s = Q.DlQueue( ); merge( r, s, t ); ; 四、简答题(1) 在一个有n个元素的顺序表的第i个元素（1 i n）之前插入一个新元素时，需要向后移动多少个元素？(2) 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？(3) 简单（直接）选择排序是一种稳定的排序方法吗？试举例说明？(4) 设有序顺序表为 10, 20, 30, 40, 50, 60, 70 ，采用折半搜索时，搜索成功的平均搜索长度是多少？五、综合算法题试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访