2026年自考《数据结构与算法》高频考点与预测试卷及答案解析

《数据结构与算法》是高等教育自学考试计算机及应用、计算机科学与技术、软件工程等专业的核心必修课程。本课程内容涉及线性表、栈与队列、树与二叉树、图、查找与排序等数据结构，以及基本算法设计与分析方法，是计算机专业的基石课程。

本文基于考试大纲和历年真题，梳理高频考点并整理预测试卷（含完整答案解析），供广大自考生考前冲刺使用。

第一部分：高频考点梳理

一、基本概念与算法分析

• 数据结构的三要素：逻辑结构、存储结构、数据运算
• 逻辑结构分类：线性结构（线性表、栈、队列）和非线性结构（树、图）
• 存储结构：顺序存储和链式存储的特点及适用场景
• 算法分析方法：时间复杂度（大O表示法）、空间复杂度

二、线性表

• 顺序表：插入、删除和查找操作的时间复杂度分析
• 单链表：头插法、尾插法建表，插入、删除操作
• 双向链表：双向链表的插入与删除操作
• 循环链表：循环链表与单链表的区别
• 顺序表与链表的比较：存取方式、逻辑结构与物理结构、插入/删除效率等

三、栈与队列

• 栈（Stack）：后进先出（LIFO），入栈与出栈操作，栈的应用（括号匹配、表达式求值、递归）
• 队列（Queue）：先进先出（FIFO），入队与出队操作
• 循环队列：队空和队满的判断条件
• 链栈与链队列：基本操作实现

四、串

• 串的模式匹配：朴素模式匹配算法（BF算法）
• KMP算法：next数组的求解方法、KMP匹配过程

五、树与二叉树

• 二叉树的性质：第i层最多2^(i-1)个结点；深度为k的二叉树最多2^k-1个结点
• 满二叉树与完全二叉树：定义及特点
• 二叉树的遍历：先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层序遍历
• 二叉树的存储结构：顺序存储和链式存储（二叉链表）
• 线索二叉树：线索化的目的和基本方法
• 树与森林：树转换为二叉树、森林转换为二叉树
• 哈夫曼树（Huffman Tree）：构造方法、哈夫曼编码
• 二叉排序树（BST）：查找、插入和删除操作
• 平衡二叉树（AVL树）：平衡因子、旋转调整（LL、RR、LR、RL）

六、图

• 图的存储结构：邻接矩阵、邻接表
• 图的遍历：深度优先搜索（DFS）、广度优先搜索（BFS）
• 最小生成树：Prim算法、Kruskal算法
• 最短路径：Dijkstra算法（单源最短路径）、Floyd算法（多源最短路径）
• 拓扑排序：AOV网、拓扑排序算法
• 关键路径：AOE网、事件最早/最晚发生时间、活动最早/最晚开始时间、关键路径的确定

七、查找

• 顺序查找：平均查找长度（ASL）
• 二分查找（折半查找）：适用条件（有序顺序表）、ASL计算
• 分块查找：索引顺序表的查找过程
• 二叉排序树查找：查找效率分析
• 散列查找（哈希查找）：哈希函数构造方法、冲突处理方法、ASL计算

八、排序

• 插入排序：直接插入排序、折半插入排序、希尔排序
• 交换排序：冒泡排序、快速排序
• 选择排序：简单选择排序、堆排序
• 归并排序：二路归并排序
• 基数排序：多关键字排序、分配与收集
• 各种排序算法的比较：时间复杂度、空间复杂度、稳定性

第二部分：预测试卷

一、单项选择题（每题2分，共30分）

1. 以下关于数据结构的说法，正确的是（ ）。

A. 数据的逻辑结构反映了数据在计算机中的存储方式

B. 数据的存储结构独立于计算机的硬件环境

C. 数据的逻辑结构分为线性结构和非线性结构

D. 算法的时间复杂度与数据规模无关

答案：C

解析：数据的逻辑结构是从逻辑关系角度描述数据，分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。A错误，存储结构才反映数据在计算机中的存放方式；B错误，存储结构依赖于硬件环境；D错误，算法时间复杂度通常随数据规模增长而变化。

2. 在一个长度为n的顺序表中，在第i个元素之前插入一个新元素，需要移动的元素个数为（ ）。

A. n - i

B. n - i + 1

C. i

D. n - i - 1

答案：B

解析：在顺序表的第i个位置插入元素，需要将第i个至第n个元素（共n-i+1个）全部后移一位。

3. 栈和队列的共同点是（ ）。

A. 都是先进先出

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

答案：C

解析：栈和队列都是操作受限的线性表，栈只允许在一端（栈顶）进行插入和删除，队列只允许在队尾插入、在队头删除，它们的共同点是只允许在端点处进行操作。

4. 循环队列的队满条件是（ ）。

A. (rear + 1) % maxsize == front

B. rear == front

C. rear + 1 == front

D. (rear - 1) % maxsize == front

答案：A

解析：循环队列通常牺牲一个存储单元来区分队空和队满。队空条件为front==rear；队满条件为(rear+1)%maxsize==front。

5. 一棵完全二叉树共有100个结点，则该二叉树中叶结点的个数是（ ）。

A. 49

B. 50

C. 51

D. 52

答案：B

解析：完全二叉树中，最后一个非叶结点是第n/2个结点（向下取整）。当n=100时，最后一个非叶结点是第50个结点，所以叶结点为第51-100号，共50个。

6. 对一棵二叉排序树进行中序遍历，得到的遍历序列是（ ）。

A. 递增有序

B. 递减有序

C. 无序

D. 先增后减

答案：A

解析：二叉排序树的定义是左子树所有结点均小于根结点，右子树所有结点均大于根结点。中序遍历（左-根-右）正好按关键字递增顺序输出所有结点。

7. 哈希查找中，出现冲突的主要原因是（ ）。

A. 哈希函数选择不当

B. 哈希表装填因子过大

C. 多个关键字映射到了同一个哈希地址

D. 哈希表长度设置不当

答案：C

解析：哈希冲突是指不同的关键字通过同一个哈希函数计算得到了相同的哈希地址。冲突是哈希存储中不可避免的现象，只能通过选择合适的哈希函数和冲突处理方法减少冲突。

8. 下列排序算法中，平均时间复杂度为O(nlog₂n)的是（ ）。

A. 直接插入排序

B. 冒泡排序

C. 简单选择排序

D. 快速排序

答案：D

解析：快速排序的平均时间复杂度为O(nlog₂n)。直接插入排序、冒泡排序和简单选择排序的平均时间复杂度均为O(n²)。

9. 一个有n个顶点的无向图，最多有（ ）条边。

A. n

B. n(n-1)

C. n(n-1)/2

D. 2n

答案：C

解析：有n个顶点的无向图，任意两个顶点之间最多有一条边，因此最大边数为n(n-1)/2。

10. 在Dijkstra算法中，每次从未确定最短路径的顶点集合中选出的顶点是（ ）。

A. 距离源点最近的顶点

B. 距离源点最远的顶点

C. 顶点编号最小的顶点

D. 随机选取

答案：A

解析：Dijkstra算法采用贪心策略，每轮从未确定最短路径的顶点中选出当前距离源点最近的顶点将其标记为已确定，然后更新其邻接顶点的距离值。

二、填空题（每空2分，共20分）

11. 数据的存储结构包括__________和__________两种基本方式。

答案：顺序存储；链式存储

12. 栈的插入操作称为__________，删除操作称为__________。

答案：入栈（压栈）；出栈（弹栈）

13. 深度为k的完全二叉树至少有__________个结点，至多有__________个结点。

答案：2^(k-1)；2^k-1

14. 拓扑排序算法每次输出的是__________的顶点。

答案：入度为0

15. 在有序表(12, 24, 36, 48, 60, 72, 84)中二分查找关键字72，需要比较__________次。

答案：2

三、简答题（每题8分，共24分）

16. 简述顺序表和链表的优缺点比较。

答案要点：

顺序表：优点——支持随机存取（O(1)），存储密度高（不需额外指针空间），访问效率高；缺点——插入和删除需要移动大量元素（O(n)），需要预先分配固定大小的存储空间，扩容不便。

链表：优点——插入和删除操作只需修改指针（O(1)时间），不需要预先分配存储空间，按需动态分配；缺点——不支持随机存取（查找需从头遍历，O(n)），需要额外的指针存储空间，存储密度较低。

17. 简述二叉树先序遍历、中序遍历和后序遍历的访问顺序。

答案要点：

先序遍历（Preorder）：先访问根结点，再先序遍历左子树，最后先序遍历右子树，即"根左右"。

中序遍历（Inorder）：先中序遍历左子树，再访问根结点，最后中序遍历右子树，即"左根右"。

后序遍历（Postorder）：先后序遍历左子树，再后序遍历右子树，最后访问根结点，即"左右根"。

18. 快速排序的基本思想是什么？

答案要点：

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，再分别对这两部分继续进行排序，直到整个序列有序。具体操作是选取一个枢轴（pivot）元素，通过一趟划分将比枢轴小的元素放到左边、比枢轴大的放到右边。

四、算法设计题（共26分）

19.（12分） 编写一个递归算法，计算二叉树中叶子结点的个数。

参考答案：

int CountLeaf(BiTree T) {
    if (T == NULL)
        return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return 1;
    return CountLeaf(T->lchild) + CountLeaf(T->rchild);
}

解析：递归思路简洁清晰。空树返回0；如果当前结点是叶结点（左右孩子均为空），返回1；否则递归统计左子树和右子树中的叶子结点个数并求和。

20.（14分） 编写算法，实现二分查找（折半查找）在有序表中的查找过程。

参考答案：

int BinarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == arr[mid])
            return mid;      // 查找成功，返回下标
        else if (key < arr[mid])
            high = mid - 1;  // 在左半部分继续查找
        else
            low = mid + 1;   // 在右半部分继续查找
    }
    return -1;               // 查找失败
}

解析：二分查找每次将查找范围缩小一半，因此时间复杂度为O(log₂n)。但前提是待查表必须是有序的顺序表（支持随机存取）。平均查找长度ASL约等于log₂(n+1)-1。

第三部分：备考建议

《数据结构与算法》课程内容丰富、概念较多，备考时建议：

• 重视概念理解：理解各类数据结构的特点和适用场景是解题的基础
• 熟练掌握遍历：二叉树的三种遍历、图的DFS和BFS是高频考点
• 动手模拟算法：排序、查找、图算法等建议亲手模拟执行过程，理解每一步的变化
• 注意代码实现：常见操作（插入、删除、遍历、查找、排序）的算法实现要能写出来
• 多做历年真题：熟悉出题风格和考查重点，找出自己的薄弱环节

⚠️ 重要提醒：本文内容基于考试大纲和历年真题整理，仅供考生复习参考。具体考试范围、题型及分值以各省教育考试院发布的《数据结构与算法》课程考试说明为准。高频考点和预测试卷不保证考试中一定出现，请考生以教材和考纲为主线进行全面复习。

---

咨询联系：郭老师 13662661040
深大办公室：广东省深圳市南山区深圳大学粤海校区汇星楼（科技楼）——学校北门入
龙华办公室：深圳市龙华新区工业西路龙胜时代大厦1009室
服务范围：自考课程考前辅导、复习资料、押题冲刺、学历提升规划