广东理工学院2024年本科插班生招生考试。
数据结构与算法》考试大纲。
i考试的性质。
普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。《数据结构与算法》课程是广东理工学院招收专科毕业生入读计算机科学与技术、网络工程、软件工程专业的考试课程之一。学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。
该考试具有较高的信度、较高的效度、必要的区分度和适当的难度。
ii考试内容和要求。
一、考试基本要求。
着重考核应试者对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以及综合运用数据结构及算法的编程能力，检查学生是否达到了《高等学校计算机类专业数据结构与算法教学大纲》所规定的基本要求。
1、基本理论知识。
l）数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。（2）线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。
3）栈和队列的定义、存储结构、实现和典型应用。（4）串的定义及其基本操作。（5）数组的定义、运算和顺序存储。
6）树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。
7）图的定义和术语、图的存储结构及其各种操作。（8）各种查找方法的算法、适用范围及时间复杂度的分析。
9）多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。
2、基本技能。
1）能阅读用类c语言编写的算法。
2）能分析算法所完成的功能、运行结果和时间复杂度。（3）能根据要求用类c语言编写算法。
二、考核知识点及考核要求。
第一章绪论1、考核知识点。
1）数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。
2）算法、算法的特性、如何用类c语言来描述算法。
3）算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。2、考核要求。
1）识记：有关数据结构的基本概念，四种基本数据结构的特点。（2）理解：
四种基本数据结构的基本运算，算法复杂度度量的基本概念。（3）应用：用类c语言描述算法。
第二章线性表1、考核知识点。
1）线性表的定义和基本操作。
2）线性表的顺序存储结构和基本操作。
3）线性表的链式存储，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的表示和查找、插入、删除等基本操作。
2、考核要求。
1）识记：线性表基本概念、基本运算，各种链表的表示。
2）理解：顺序存储和链式存储的比较，各种链表的基本操作算法。第三章排序1、考核知识点。
1）排序的目的、分类和排序方法的稳定性的定义。（2）简单排序方法。
插入排序的思想和算法。
冒泡排序的思想和算法。（3）先进排序方法。
快速排序的思想和算法。归并排序的思想。堆的定义、堆排序的思想。（4）基数排序。
5）各种排序方法的综合比较。2、考核要求。
1）识记：插入排序、冒泡排序、简单选择排序的思想。
2）理解：快速排序、堆排序、归并排序的思想，各种排序方法的稳定性、平均比较次数、平均移动次数。
3）应用：用类c或者c语言编写插入排序、冒泡排序、简单选择排序等排序算法。
第四章栈和队列1、考核知识点。
1）栈和队列的定义、基本运算。
2）栈和队列的顺序实现及其运算的实现。（3）栈和队列的链接实现及其运算的实现。（4）栈和队列的应用。2、考核要求。
1）识记：栈和队列的概念、功能、操作特点、主要运算。
2）理解：栈和队列与一般线性表对比的特殊性，栈和队列的顺序存储和链式存储。
3）应用：栈和队列的常见的使用场合。第五章串和数组1、考核知识点。
1）串和数组的定义、基本操作。
2）串和数组的顺序存储结构及在顺序存储结构下基本操作的实现。（3）二维数组的按行存储及按列存储和计算数组元素的地址计算公式。
2、考核要求。
1）识记：串和数组的有关概念、基本操作。（2）理解：串和数组的顺序存储结构及其基本操作。（3）应用：串和数组基本操作的使用。第六章二叉树和树1、考核知识点。
1）树的定义和基本概念。
2）二叉树(完全二叉树、满二叉树)的定义和性质、二叉树的存储结构（顺序表示法和二叉链表表示法）。
3）二叉树遍历算法（先序、中序、后序）。
4）树和森林转换为二叉树的方法（孩子兄弟表示法）。
5）树的路径长度、树的带权路径长度、huffman树的构造方法。2、考核要求。
1）识记：树的基本概念。
2）理解：二叉树的存储结构、遍历算法，孩子兄弟表示法，树的路径长度，哈夫曼树的构造方法。
3）应用：利用哈夫曼树解决一些最优化问题。第七章图和广义表1、考核知识点。
1）广义表的定义和存储结构。（2）图的定义和基本术语。
图及无向图、有向图、网、子图、连通图、强连通图。顶点的度、入度、出度。顶点间路径、路径长度、环。（3）图的存储结构邻接矩阵。
邻接表(含逆邻接表)。（4）遍历图。
深度优先搜索遍历图的算法。
广度优先搜索遍历图的思想。（5）生成树、最小生成树的概念。（6）拓扑排序的概念。（7）求最短路径的算法。2、考核要求。
1）识记：图的基本概念和术语，最小生成树、拓扑排序、最短路径的概念。（2）理解：图的存储方式和基于该存储方式的基本操作（求入度、出度、下一条边等）
3）应用：求拓扑序列的方法，求最短路径的方法第八章查找表1、考核知识点。
1）查找、关键字、平均查找长度等概念。（2）静态查找表顺序查找折半查找分块查找（3）动态查找表。
二叉排序树定义、构造过程及其查找算法和效率。平衡二叉树的定义。2、考核要求。
1）识记：有关查找的基本概念，静态查找表和动态查找表的概念。（2）理解：各种静态查找算法的比较次数分析，二叉排序树定义的构造过程和查找算法。
3）应用：分析各种查找算法的比较次数。第九章文件（不要求）
第十章数据结构程序设计示例（不要求）
iii考试形式及试卷结构。
一、考试形式。
闭卷，笔试，试卷满分为100分，考试时间为120分钟。二、试卷内容比例第一章约占8%第二章约占20%第三章约占15%第四章约占10%第五章约占8%第六章约占15%第七章约占14%第八章约占10%三、试卷题型比例。
试题分为客观题和主观题。客观题一般有填空题、选择题、名词解释、程序填空题等类型；主观题一般有简答题、算法设计题等类型。试题对不同能力层次要求的分数比例：
识记约占30%，理解约占40%，应用约占30%。
四、试卷难易度比例。
试题按其难度分为容易题、中等题、难题，三种试题分值的比例为4:4:2。
iv参考书目。
主要参考书：
1、《数据结构及应用算法教程（修订版）》,严蔚敏、陈文博编著，清华大学出版社，2024年。
2、《数据结构与算法》,陈卫卫、王庆瑞编著，高等教育出版社，2024年。
v题型示例。
一、填空题。
1、一棵深度为8（根的层次号为1）的满二叉树有个叶子结点。2、串的长度是指。
二、选择题。
1、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是。
a .e d c b a b. d e c b a c. d c e a b d. a b c d e2、对于栈操作数据的原则是。
a.先进先出b.后进先出c.后进后出d.不分顺序。
三、名词解释。
1、连通图2、完全二叉树。
四、程序填空题。
下面的程序段是在一棵二叉排序树中查找给定的关键字，找到返回1，找不到返回0。请把该程序补充完整。
tree定义如下：
struct tree;
keytype key; /关键字其他数据项*/
int find(tree * boot, elemtype item);
请用函数原型：
singlelink *linkaandb( elemtype a,int n, singlelink *b);
数组a和要链接的单链表b通过函数参数传递，n是数组的规模。函数返回值是生成的链表。
elemtype data;singlelink *next;
数据结构与算法考试大纲
数据结构与算法 考试大纲。题型分布 1 选择题 15题，每题2分，共30分。2 填空题 10空，每空2分，共20分。3 简答题 4小题，每题6 8分，共30分。4 设计题 2小题，每题10分，共20分。第1章绪论。1 数据 数据元素 数据项 数据类型 抽象数据类型等基本概念和术语的含义 2 数据结构...
《数据结构与算法》考试大纲
计算机系考试大纲计算机网络与通信。计算机网络与通信 考试大纲。一 考试说明。考试对象 计算机科学与技术专业及相近专业专科生命题原则 1 在教学大纲和考试大纲所规定的知识点范围内命题。2 试题的考察要求覆盖面广 区分度高。3 试题兼顾各个能力层次，难易程度和题量。适当，按难易程度分为四个层次 容易占3...
数据结构与算法考试大纲
i.考查目标。考试目标是了解常见数据结构的概念，掌握数据结构的构造方法以及相应的算法思想，会对重点数据结构的操作方法和算法进行简单的伪 编写。ii.考试形式和试卷结构。一 试卷总分及考试时间。试卷总分为150分，考试时间180分钟。二 答题方式。答题方式为闭卷 笔试。iii 考查内容。第一章 线性表...