数据结构
考情分析
专心备考 • 助你上岸
01
前言
云南专升本《数据结构》考情分析，旨在让大家对于考试难易程度、分值分布、考试题型、考试内容有一定的了解，特做一下考情分析，希望能够帮助大家掌握考试情况，精准出击！
01
考试时间
每年4月份第二个星期周末
14:30-16:30
02
考试时长
120分钟
03
考试题型
客观题
02
考试内容占比
第一章 绪论 5%
第二章 线性表 10%
第三章 栈和队列 15%
第四章 串 5%
第五章 数组和广义表 5%
第六章 树和二叉树 15%
第七章 图 15%
第九章 查找 15%
第十章 内部排序 15%
考试重点
第六、七、九、十章
主要考概念
第一章、第四章、第五章
计算主要考
第六章、第七章、第九章、第十章
算法主要考
第二章、第六章、第九章、第十章
03
难易程度
较易试题 50%
中等试题 30%
较难试题 20%
较易
试题
概念，书本上直接写出来，只需要记忆，Eg.数据的基本单位；
计算题，书本上有直接公式Eg.二叉树的5大性质；
算法题，书本上的算法，且容易理解或容易记忆，Eg.二叉树的先序递归遍历；
中等
试题
概念，书本上没有直接写出来的，需要深入理解，Eg.二叉树的度可能为0或1或2；
计算题，书本上没有直接给出公式，需要自行理解整理，Eg.高度为h的完全二叉树的最少节点数；
算法题顺序表和链表的优缺点，书本上有或者简单变形，不太好记，需要一定的理解，Eg.排序算法；
较难
试题
概念，书本上没有，但是是一些常识，Eg.算法的健壮性；
计算题，书本上有或没有，需要自己总结，Eg.已知两种遍历序列，反求另一种；
算法，书本上没有，是基本算法的应用，Eg.栈的应用"括号匹配"；
04
考试题型
判断题：1分*10=10分
（2020年-2021年：1分*15=15分）
单选题：2分*25=50分
多选题：4分*5=20分
（2020年-2021年：3分*6=18分）
算法阅读题：3.5分*10=35分
（2020年-2021年：4分*8=32分）
综合应用题 ：7分*5=35分
（2020年-2021年：5分*4=20分）
注：每年可能题量和分值会有细微差别，但题目类型未变
05
学生学习情况
1.学生普遍可得90分
2. 学生比较难学部分：树、图、查找、各类排序算法及其特性
06
考试内容
第一章绪论
数据、数据元素、数据项、数据对象、数据结构、逻辑结构和物理结构等概念；
算法的定义、特性，时间复杂度和空间复杂度计算。
第二章线性表
线性表的定义；
顺序表的实现和常用算法：插入、删除等；
（带头/不带头）的单链表的常用算法：插入、删除、建表等；
双链表和循环链表的实现方法和常用算法：插入、删除等；
顺序表、单链表、双链表、循环链表等各自的优缺点。
第三章栈和队列
栈的定义、特点，顺序栈的实现方式和常用算法：入栈、出栈、获取栈顶元素；
计算出栈的可能序列；
队列的定义、特点，循环队列的实现方式和常用算法：入队、出队，队空和队满的判定条件，计算队列中元素的个数；
栈和队列的经典应用：数制转换、括号匹配、树的层次遍历、图的广度遍历等。
第四章串
串的定义，空串和空格串的区别，两个串相等，串的存储结构；
串的一些基本操作：求串长、子串的位置、串截取、串联接、串的模式匹配。
第五章数组和广义表
1.数组的特点，二维数组按行优先（列优先）存储时元素的下标和地址计算；
2. 特殊矩阵的定义和压缩存储：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵；
3.广义表的有关概念：表头、表尾、表长、表深顺序表和链表的优缺点，并学会计算。
第六章树和二叉树
树的基本概念和有关术语；
二叉树、完全二叉树、满二叉树的定义，二叉树的3大性质，完全二叉树的2大性质；
二叉树的存储结构，二叉树的常用算法：遍历递归算法、层次遍历算法、求叶子结点数量算法、求树的深度算法等；
二叉树的线索化，有关线索树的常用算法：在中序线索二叉树中查找结点的前驱、在中序线索二叉树中查找结点的后继；
树的存储结构，树和森林转换成二叉树的方法；
哈夫曼树的概念，构造哈夫曼树并求其带权路径长度。
第七章图
图的定义；
图的相关术语：无向图、有向图、有向完全图、无向完全图、子图、连通图、强连通图、连通分量、顶点的度、入度、出度、顶点间的路径、路径长度等；
图的两种存储结构：邻接矩阵、邻接表（逆邻接表）；
图的两种遍历方式：深度优先搜索遍历、广度优先搜索遍历
生成树和最小生成树的概念，最小生成树的构造方法：Prim、
求拓扑排序序列
求最短路径的和Floyd
第九章 查找
1.查找、查找表、平均查找长度等相关概念；
2．静态查找表：顺序查找、折半查找、分块查找；
3．动态查找表：二叉排序树的概念、构造及其查找算法，平衡二叉树的概念；
4．哈希表的相关概念：构造哈希函数、冲突处理方法，平均查找长度的计算。
第十章内部排序
插入类排序：直接插入排序、折半插入排序、希尔排序；
交换类排序：冒泡排序，快速排序；
交换类排序：简单选择排序，堆的定义，堆排序；
归并排序和基数排序的概念；
学会各种排序算法的比较：稳定、平均时间复杂度、最好/坏时间复杂度、空间复杂度，学会根据不同情形选择合适的排序算法。
会写排序序列
07
题目示例
较易
试题
【判断题】算法的特性中要求一个算法有零个或多个输入，一个或多个输出。( )
【单选题】在栈中进行入栈和出栈的一端为（ ）
A.队尾
B.栈顶
C.栈底
D.队头
【单选题】按照传统的方法线索化二叉树时，通常把结点中空的左指针指向它的（ ）
A.后继
B.左孩子
C.右孩子
D.前趋
中等
试题
【单选题】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){
p,q;
p=(L,i-1);//p指向第i-1个位置的数据元素的结点
//删除前已检测第i个元素结点存在
q=p->next;
free(q); //释放q
1;
G.p->next=q;
H.(0);
I.p=q->next;
J.p->next=q->next;
K.p=q;
较难
试题
【综合应用题】 一个双链表的结点结构如下：
{
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);