数据结构考情分析一 考试内容占比
第一章 绪论 5%
第二章 线性表 10%
第三章 栈和队列 15%
第四章 串 5%
第五章 数组和广义表 5%
第六章 树和二叉树 15%
第七章 图 15%
第九章 查找 15%
第十章 内部排序 15%
二 难易程度
较易试题 50%
中等试题 30%
较难试题 20%
三 考试题型
判断题：1分*10=10分
单选题：2分*25=50分
多选题：4分*5=20分
算法阅读题：3.5分*10=35分
综合应用题 ：7分*5=35分
注：每年可能题量和分值会有细微差别，但题目类型未变
四 难点重点
树、图、查找、排序
五考试内容
第一章绪论
1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构和物理结构等概念；
2.算法的定义、特性，时间复杂度和空间复杂度计算。
第二章线性表
1.线性表的定义；
2.顺序表的实现和常用算法：插入、删除等；
3.（带头/不带头）的单链表的常用算法：插入、删除、建表；
4.双链表和循环链表的实现方法和常用算法：插入、删除等；
5.顺序表、单链表、双链表、循环链表各自的优缺点。
第三章栈和队列
1.栈的定义、特点，顺序栈的实现方式和常用算法：入栈、出栈、获取栈顶元素；
2.计算出栈的可能序列；
3.队列的定义、特点，循环队列的实现方式和常用算法：入队、出队，队空和队满的判定条件，计算队列中元素的个数；
4.栈和队列的经典应用：数制转换、括号匹配、树的层次遍历、图的广度遍历等。
第四章串
1.串的定义，空串和空格串的区别，两个串相等，串的存储结构；
2.串的一些基本操作：求串长、子串的位置、串截取、串联接、串的模式匹配。
第五章数组和广义表
1.数组的特点，二维数组按行优先（列优先）存储时元素的下标和地址计算；
2.特殊矩阵的定义和压缩存储：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵；
3.广义表的有关概念：表头、表尾、表长、表深，并学会计算。
第六章树和二叉树
1.树的基本概念和有关术语；
2.二叉树、完全二叉树、满二叉树的定义，二叉树的3大性质，完全二叉树的2大性质；
3.二叉树的存储结构，二叉树的常用算法：遍历递归算法、层次遍历算法、求叶子结点数量算法、求树的深度算法；
4.二叉树的线索化，有关线索树的常用算法：在中序线索二叉树中查找结点的前驱、在中序线索二叉树中查找结点的后继；
5.树的存储结构，树和森林转换成二叉树的方法；
6.哈夫曼树的概念，构造哈夫曼树并求其带权路径长度。
第七章图
1.图的定义；
2.图的相关术语：无向图、有向图、有向完全图、无向完全图、子图、连通图、强连通图、连通分量、顶点的度、入度、出度、顶点间的路径、路径长度等；
3.图的两种存储结构：邻接矩阵、邻接表（逆邻接表）；
4.图的两种遍历方式：深度优先搜索遍历、广度优先搜索遍历
5.生成树和最小生成树的概念，最小生成树的构造方法：Prim、
6.求拓扑排序序列
7.求最短路径的和Floyd
第九章 查找
1．查找、查找表、平均查找长度等相关概念；
2．静态查找表：顺序查找和折半查找算法，分块查找的概念；
3．动态查找表：二叉排序树的概念、构造及其查找算法，平衡二叉树的概念；
4．哈希表的相关概念：构造哈希函数、冲突处理方法，构造函数为除留余数法，冲突处理为线性探测再散列时散列地址和平均查找长度的计算。
第十章 内部排序
1.插入类排序：直接插入排序和折半插入排序算法，了解希尔排序算法思想；
2. 交换类排序：冒泡排序算法，了解快速排序算法思想；
3. 交换类排序：简单选择排序算法，堆的定义，堆排序思想；
4. 归并排序和基数排序的概念；
5. 学会各种排序算法的比较：稳定、平均时间复杂度、最好/坏时间复杂度、空间复杂度，学会根据不同情形选择合适的排序算法。
6. 会写排序序列；
六 题目
1.简单
【判断题】算法的特性中要求一个算法有零个或多个输入，一个或多个输出。( )
【判断题】通过头插法创建的单链表与创建时输入的数据元素顺序相反。 ( )
【单选题】在栈中进行入栈和出栈的一端为（ ）
A.队尾 B.栈顶
C.栈底 D.队头
【单选题】按照传统的方法线索化二叉树时，通常把结点中空的左指针指向它的（ ）
A.后继 B.左孩子
C.右孩子 D.前趋
2.中等
【单选题】C 语言中一个 9×9 的二维数组，按行序为主的存储方式进行存储，则第 24 个元素对应的是（ ）
A.[5][2] B.[2][4]
C.[4][2] D.[2][5]
【综合应用题】已知一组权值2,3,4,11，请构造一颗哈夫曼树，其带权路径长度（WPL）值为（ ）
A.32 B.34
C.53 D.40
【算法阅读题】删除单链表List中第i个位置的数据元素，请选择（ ）
node{
data;
node *next;
} *;
int ( L， int i) {
,q;
P=(L,i-1);//p指向第i个位置的数据元素的结点
//删除前已检测第i个元素结点存在
q=p->next;
free(q); //释放q
;
G.p->next=q;
H.(0);
I.p=q->next;
J.p->next=q->next;
K.p=q;
3.难题
【综合应用题】一个双链表的结点结构如下：
{
data;
*prior , *next ;
} ;
P是指向双链表中某一结点的指针，请选择在p前插入结点q的正确代码( )
G.p->prior=q;q->prior=p->prior;q->next=p;p->prior->next=q;
H.q->next=p;p->prior=q;q->prior=p->prior;p->prior->next=q;
I.q->next=p;p->prior=q;p->prior->next=q;q->prior=p->prior;
J.q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;
K.q->prior=p->prior;q->next=p;p->prior=q;p->prior->next=q;
L.p->prior=q;p->prior->next=q;q->prior=p->prior;q->next=p;
【综合应用题】对于序列 49，14，38，74，96，65，8，51，72，25 使用第一个数据元素为支点，经过一次快速排序后得到的序列是（ ）
G.14，38，49，74，96，65，8，51，72，25
H.14，38，49，8，25顺序表和链表的优缺点，51，65，72，74，96
I.25，8，14，49，38，51，65，72顺序表和链表的优缺点，74，96
J.8，14，25，38，49，51，65，72，74，96
K.8，14，25，38，49，65，51，96，74，72
L.25，14，38，8，49，65，96，51，72，74
【算法阅读题】从v出发广度优先搜索图G的算法。请选择合适的选项（ ）
void BFS (Graph G ，int v) {
for (i=0 ; ;i++)
[i]=FALSE ; /* 访问标志初始化 */
(Q);
if (![v]){
(Q，V)；
while(!(Q)){
u=(Q)；
[u]=TRUE；
visit(u);
for (w=(G,u); w; w=(G,u,w)) {
if (![w]) {
}}}}
G.[i]=TRUE; H.[i]=FALSE;
I.(Q,w); J.(Q);
K.w=(Q);