自考14253数据结构与数据库考试大纲（2026年版）

湖南 省高 等教 育自 学考 试课 程考 试大 纲数据结构与数据库 （课程代码：14253） 湖南省教育考试院组编 2026 年 8 月14253 数据结构与数据库考试大纲第 1页（共 21 页） 高等教育自学考试课程考试大纲课程名称：数据结构与数据库课程代码：14253

第一部分课程性质与目标

一、课程性质与特点

数据结构与数据库是高等教育自学考试信息管理与信息系统专业的必考课程。

本课程在讲述基本数据结构理论的基础上，系统阐述了关系数据库的基本理论、实现技术和设计方法。内容主要包括两个部分：第一部分为数据结构，系统地介绍线性表、栈与队列、串、数组、树与二叉树、图等基本数据结构，以及常用的查找和排序算法；第二部分为数据库技术，讲述数据库系统的基本原理、关系模型、SQL 语言标准、规范化理论、数据库设计步骤、事务管理、数据库安全性与完整性控制等。该课程既强调严谨的理论逻辑，又注重解决实际工程应用的能力，是集理论、 实践与创新于一体的典型课程。

二、课程目标与基本

要求（一）课程目标本课程的教学总目标是使考生能够从算法和存储两个维度理解数据的组织、操作与控制，具备设计高效数据结构和优化数据库系统结构的能力。

（二）基本要求

1．掌握基本数据结构的逻辑特征、在计算机内存中的物理存储表示方法以及相关经典算法的 C 语言或伪代码实现。

2．理解常用查找（折半、二叉排序树、散列）和内部排序算法（插入、交换、选择、归并）的原理、性能，初步具备算法时间与空间复杂度分析的能力。

3．掌握数据库系统的三级模式结构、二级映像功能及数据独立性保障原理。

4．熟练掌握关系代数运算和 SQL 语言标准，能够熟练运用 SQL 进行复杂多表连接、嵌套子查询、视图的操作和基本数据更新。

5．掌握关系数据库设计的六个基本步骤，能够针对具体的企业信息系统进行14253 数据结构与数据库考试大纲第 2页（共 21 页） 需求分析和 E-R 概念模型设计。

6．深刻理解规范化设计理论，掌握函数依赖计算与分解算法，能熟练对关系模式进行判定，并将其规范分解至符合 3NF/BCNF 规范。

7．理解事务的 ACID 特性，掌握并发控制的三级封锁协议、两段锁协议、以及撤销（Undo）/重做（Redo）数据库故障恢复原理。

8．熟悉 Transact-SQL 编程基础，能够独立在主流 DBMS（如 SQL Server）上进行游标操作、编写符合规范的存储过程和触发器。

9．具备综合应用数据结构与数据库技术开发中小型应用系统的初步设计与开发能力。

三、与本专业其他课程的关系

本课程是一门理论与实践结合极其紧密的专业核心课程。先行课程为高级语言程序设计（如 C 语言）、离散数学，离散数学中的集合、关系、树、图等概念为本课程提供了数学基础，而高级语言为算法的表达和实现提供了工具。本课程的后续课程为软件工程、面向对象程序设计、Web 开发技术等，本课程所传授的数据处理能力和物理存储设计是后续系统级软件架构、大型 Web 系统构建和应用开发不可或缺的数据底层与技术基石。

14253 数据结构与数据库考试大纲第 3页（共 21 页）

第二部分考核内容与考核目标第

1 章绪论本章主要考核数据结构的基本概念和算法分析基础。考生应熟练掌握数据结构中数据、元素、逻辑结构和物理结构的定义，掌握算法的特征及其时间/空间复杂度的度量方法，能够进行简单程序段的复杂度分析。

（一）数据结构的基本概念（重点）识记：1．数据、数据元素、数据项、数据对象及数据结构的定义

2．逻辑结构的四种基本关系（集合、线性、树、图）与存储结构的四种基本映射方式（顺序、链式、索引、散列）

3．抽象数据类型（ADT）的定义与表示理解：1．数据逻辑结构与物理存储（映像）结构之间的区别与联系

2．抽象数据类型（ADT）在面向对象和模块化设计中的重要作用

3．算法与程序的异同、算法必须满足的五个特征（二）算法和算法分析（重点）识记：1．算法时间复杂度和空间复杂度的概念

2．大 O 表示法的含义理解：1．算法的时间性能度量（语句频度估计）、空间复杂度度量指标

2．最坏情况、最好情况和平均情况复杂度的区别和联系应用：计算给定简单程序段（如单重循环、双重嵌套循环）的语句执行频度，并给出其大 O 时间复杂度度量

第 2 章线性表

本章主要考核线性表的逻辑结构与物理存储。要求深刻理解线性表的逻辑特征，熟练掌握顺序表和链表（单链表、双向链表、循环链表）的存储结构特点和基14253 数据结构与数据库考试大纲第 4页（共 21 页） 本运算，能够手写核心算法并分析其复杂度（一）线性表的逻辑结构（次重点）识记：线性表的定义、前驱、后继理解：线性表基本操作的语义定义（二）顺序表（重点）识记：顺序存储结构的定义、随机存取特性理解：1．顺序存储结构的优点与缺点

2．顺序表进行插入和删除运算时，元素移动次数的平均情况计算及分析应用：在顺序存储结构上，手写实现顺序表的初始化、查找、插入和删除操作算法，并进行时间复杂度分析（三）链表（重点）识记：1．单链表、头指针、头结点、首元结点的定义

2．循环链表、双向链表的定义与存储结构理解：1．链式存储结构非随机存取的特点，以及其与顺序存储在空间利用率和时间性能上的对比

2．单链表上增加头结点的目的和作用

3．单循环链表、双向链表上指针链的变化规则应用：1．使用头插法或尾插法手写建立单链表的算法实现

2．在单链表上独立编写元素的查找、插入和条件删除的完整算法实现

3．双向链表、循环链表上插入、删除结点的指针修改操作代码实现

第 3 章特殊线性表

本章主要考核栈、队列和串的概念与应用。考生需要牢固掌握栈的后进先出 （LIFO）特性、队列的先进先出（FIFO）特性，并掌握其顺序和链式表示方法， 熟练进行循环队列相关指针变化的计算与应用。

14253 数据结构与数据库考试大纲第 5页（共 21 页）

（一）栈（重点）

识记：1．栈的逻辑定义、栈顶、栈底、LIFO 特征

2．顺序栈、链栈的存储表示理解：1．栈空、栈满时的栈顶指针变化规律与边界条件判断

2．栈的适用场景（如函数调用、递归实现、表达式求值等）

应用：顺序栈和链栈上初始化、入栈（Push）、出栈（Pop）、取栈顶元素的算法实现（二）队列（重点）识记：1．队列的逻辑定义、队头、队尾、FIFO 特征

2．链队列、循环队列的存储表示理解：1．顺序队列的“假溢出”现象及其产生的原因

2．循环队列中模运算的应用原理

3．循环队列在设计时判空和判满的条件（牺牲一个存储空间或设置计数标志法）

应用：1．循环队列判空、判满的条件公式编写

2．循环队列中入队（EnQueue）、出队（DeQueue）的算法实现（三）串（一般）识记：串定义、子串、主串、空串、空格串理解：1．串的定长顺序存储和块链存储结构差异

2．串的基本运算（拼接、提取子串、长度计算）的实现思路

第 4 章数组

本章主要考核特殊矩阵和稀疏矩阵的压缩存储。考生应掌握二维数组的物理地址转换，并深刻理解特殊对称矩阵在一维空间中的下标转换关系，掌握稀疏矩阵的三元组压缩存储表示。

（一）二维数组的物理存储（一般）识记：行优先存储与列优先存储的映射模型14253 数据结构与数据库考试大纲第 6页（共 21 页）

理解：基于起始地址、元素大小计算二维数组任意元素的物理内存地址（行优先/列优先）

（二）特殊矩阵与稀疏矩阵的压缩存储（次重点）识记：1．对称矩阵、三角矩阵、对角矩阵在一维数组中的压缩存储

2．稀疏矩阵、非零元素、装填因子

3．稀疏矩阵的三元组顺序表示法与十字链表理解：1．特殊矩阵进行压缩存储时的地址映射变换原理

2．稀疏矩阵中三元组表结构对随机存取的限制应用：推导对称矩阵在一维压缩存储中，元素 A[i][j] 在一维数组中对应的索引公式（区分 i >= j 和 i < j 情况）

第 5 章树与二叉树

本章为数据结构的考核重点和难点。考生必须深刻理解树和二叉树的区别与性质，熟练掌握二叉树的 5 个数学性质和二叉链表存储方法，熟练进行二叉树的遍历 （先序、中序、后序），掌握哈夫曼树的构建与编码应用。

（一）树的基本概念与术语（一般）识记：树的度、顶点的度、叶子、孩子、双亲、兄弟、祖先、子孙、深度（高度）、路径理解：树结构非线性（一对多）分支关系（二）二叉树及其性质（重点）识记：1．二叉树定义、左子树、右子树、满二叉树、完全二叉树

2．二叉树的一维顺序存储和二叉链表存储结构理解：1．二叉树的前 5 个数学性质，以及叶子结点数 n0 和度为 2 的结点数n2 之间的固定关系

2．完全二叉树根据序号进行父子结点检索的特点应用：已知树的总结点数、或分支结点数，求其叶子结点数、树的深度等计算应用14253 数据结构与数据库考试大纲第 7页（共 21 页）

（三）二叉树的遍历（重点）识记：先序（前序）遍历、中序遍历、后序遍历的定义与思想理解：已知先序和中序序列（或中序和后序序列），重构二叉树并画出其结构的唯一性原理应用：1．写出给定二叉树结构的先序、中序和后序遍历序列

2．在二叉链表存储结构上，写出实现先序/中序/后序遍历的递归算法

第 6 章图

本章为数据结构中的重点考核内容。要求深刻掌握图的术语与基本结构，熟练写出图的邻接矩阵和邻接表存储表示，掌握图的深度优先（DFS）和广度优先 （BFS）遍历算法与过程描述。

（一）图的基本术语（次重点）识记：有向图、无向图、度、入度、出度、网（带权图）、路径、路径长度、连通图、强连通图、连通分量、生成树、有向无环图（DAG）

理解：图结构的多对多拓扑联系（二）图的存储结构（重点）识记：1．邻接矩阵存储表示法

2．邻接表（含逆邻接表）存储表示法理解：1．邻接矩阵的空间复杂度，以及如何从矩阵中计算顶点的度（区分有向图和无向图）

2．邻接表头结点与边结点的定义，以及存储优势

3．邻接矩阵与邻接表在表示同一张图时的唯一性及差异性应用：对于给定的具体图（有向/无向，带权/不带权），写出其邻接矩阵和对应的邻接表表示（三）图的遍历（重点）识记：1．深度优先搜索（DFS）遍历思想

2．广度优先搜索（BFS）遍历思想14253 数据结构与数据库考试大纲第 8页（共 21 页）

理解：1．DFS 的递归实现和栈的应用、时间复杂度

2．BFS 的非递归实现中队列的辅助作用，以及时间复杂度

3．辅助标记数组 visited[] 的防循环访问机制应用：给定起点，写出无向图或有向图在 DFS 和 BFS 下的顶点访问序列（强调根据邻接矩阵或邻接表链顺序排列的唯一序列）

第 7 章查找

本章主要考核各种查找表的检索思想和平均查找长度（ASL）的计算。考生应熟练掌握折半查找算法、二叉排序树（BST）的插入和构建，掌握哈希表散列函数的构造和解决冲突方法（线性探测与链地址），并准确计算 ASL 值。

（一）静态查找表（次重点）识记：1．顺序查找、折半查找、索引顺序查找（分块查找）。

2．平均查找长度（ASL）的定义公式。

理解：1．折半查找的基本思想、前提（顺序存储且有序）与 ASL 计算。

2．顺序查找中在 0 号位置设置“哨兵”防越界的作用。

应用：画出给定有序表在折半查找时的判定树，计算在查找成功和查找失败时的平均查找长度。

（二）动态查找表——二叉排序树（重点）识记：二叉排序树（BST）的定义与性质。

理解：1．二叉排序树查找和插入操作的过程。

2．中序遍历二叉排序树得到递增有序序列的特性。

应用：根据给定的关键字输入序列，手绘逐步插入构建二叉排序树（BST）的过程，并计算查找成功的 ASL 值。

（三）散列表（哈希表）的查找（重点）识记：1．哈希函数、散列表、冲突、装填因子。

2．直接定址法、除留余数法。

理解：1．处理冲突的两大方法：开放定址法（线性探测再散列、二次探14253 数据结构与数据库考试大纲第 9页（共 21 页） 测、随机探测）、链地址法（拉链法）

2．装填因子与平均查找长度的关系应用：给定关键字序列和散列函数（如除留余数法），利用线性探测法或链地址法解决冲突，构建完整的散列表，计算在成功查找和失败查找下的 ASL

第 8 章排序

本章考核内部排序算法的原理与性能对比。考生应熟练掌握直接插入排序、冒泡排序、简单选择排序、快速排序和 2-路归并排序的基本思想、每趟执行结果、时间复杂度、空间复杂度与稳定性特征。

（一）内部排序的基本概念（一般）识记：1．排序稳定性（稳定与不稳定排序）。

2．内部排序与外部排序。

理解：稳定性在实际多关键字复合检索排序中的作用。

（二）插入排序与选择排序（次重点）识记：1．直接插入排序、希尔排序（Shell’s Sort）的思想。

2．简单选择排序的思想。

理解：1．直接插入排序在最好（已正序）和最坏（逆序）下的时间复杂度差异

2．希尔排序的增量序列选取标准。

应用：写出给定关键字序列进行直接插入和希尔排序（给定增量）每趟的排序结果（三）交换排序与归并排序（重点）识记：冒泡排序思想、快速排序（Quick Sort）思想、2-路归并排序思想。

理解：1．快速排序中划分（Partition）轴值（枢轴）的选择对算法性能的影响

2．快速排序在平均和最好情况下（O(nlogn)）与在最差情况（O(n^2)）下的时间复杂度差异14253 数据结构与数据库考试大纲第 10页（共 21 页）

3．归并排序合并两个有序子序列的辅助空间开销应用：写出给定关键字序列在一趟快速排序（指明高低指针移动和轴值落位）以及冒泡排序、2-路归并每趟结束后的排序结果（四）排序算法性能综合对比（重点）

理解：各种排序算法（直接插入、希尔、冒泡、快速、简单选择、归并）在平均时间复杂度、最坏时间复杂度、辅助空间开销以及稳定性上的综合比对规律应用：熟练默写并应用排序性能比对表解决最优算法选择问题

第 9 章数据库系统概述

本章开始进入第二部分：关系数据库技术。考核重点是数据库系统的基础术语与体系结构。考生应深刻掌握数据管理发展的阶段，熟练掌握数据库系统的三级模式和二级映像结构，掌握 DBMS 的主要特征与功能。

（一）数据管理技术的发展（一般）识记：数据管理发展的四个阶段理解：人工管理、文件系统、数据库系统阶段的主要差异特点（二）数据库基本术语与 DBMS（重点）识记：数据库（DB）、数据库管理系统（DBMS）、数据库系统（DBS）、数据字典（DD）、数据库管理员（DBA）

理解：1．DBS 的五部分组成和 DBA 的日常核心职责

2．DBMS 的六大主要功能（定义、操纵、存储组织、控制、维护、通信）

（三）数据库系统体系结构（重点）识记：外模式、概念模式（模式）、内模式理解：1．三级模式结构的内容及定义

2．二级映像（外模式/模式映像、模式/内模式映像）如何保证数据具有高度的物理独立性和逻辑独立性14253 数据结构与数据库考试大纲第 11页（共 21 页）

第 10 章关系模型与关系代数

本章主要考核关系数据库理论的核心定义与关系运算。考生应掌握关系的三类完整性约束并能够分析主外键关系，重点掌握关系代数各种基本运算在进行数据操作时的描述和运用方法。

（一）关系模型与完整性约束（重点）识记：1．关系、属性、元组、域、笛卡尔积、度、关系实例、主属性、非主属性

2．主键、候选键、超键、外码（外键）

理解：1．实体完整性规则的内容与主属性不为空要求

2．参照完整性规则的外码落值限制（外码或为空，或等于被参照表主键值）

3．用户自定义完整性含义应用：针对具体给定的数据库实例表结构，分析出每个表的候选键、主键和外键约束关联（二）关系代数（重点）识记：并（U）、差（-）、交（∩）、广义笛卡尔积（×）

理解：1．选择（σ）运算与投影（π）运算的方向和范围特征

2．等值连接、自然连接（⋈）、外连接（左外、右外、全外连接）的含义

3．除运算（÷）的逻辑含义及多属性列条件筛选应用：针对多张关联表，手写写出能够正确表达多表关联查找特定数据条件的关系代数表达式

第 11 章关系数据库标准语言

——SQL14253 数据结构与数据库考试大纲第 12页（共 21 页） 本章为本课程的考核核心。考生必须在熟练理解 SQL 语言特点的基础上，具备极强的 SQL 数据定义、复杂关联嵌套查询、视图控制与数据更新编程应用能力。

（一）数据定义（DDL）（重点）识记：SQL 支持的基本数据类型及定义语法理解：基本表列级属性约束与表级完整性约束（PRIMARY KEY, FOREIGNKEY, CHECK, UNIQUE, NOT NULL）

应用：1．使用 CREATE TABLE 编写带有多表外键参照、级联更新、取值区间检查的建表 SQL 语句

2．使用 ALTER TABLE 在表中增加、删除或修改字段与完整性约束

3．使用 CREATE INDEX 建立唯

一、聚集索引，并能用

DROP 删除表和索引（二）数据查询（DML）（重点）识记：SELECT 语句的六大基本子句（SELECT, FROM, WHERE, GROUPBY, HAVING, ORDER BY）的顺序与执行逻辑理解：1．连接查询与外连接查询的 SQL 执行语义

2．聚合函数（COUNT, SUM, AVG, MAX, MIN）与分组（GROUPBY）的语义机制

3．嵌套子查询（带有 IN, EXISTS, 比较运算符）的执行路径及多表子查询嵌套原则应用：1．编写单表复杂选择、条件匹配和排序查询

2．编写多表多条件自然连接、等值连接、自连接、左/右外连接查询语句

3．编写使用 GROUP BY … HAVING … 及聚合函数组合的条件过滤分组统计语句

4．编写复杂的带有嵌套 IN、相关子查询或 EXISTS 量词的多层嵌套SQL 查询语句

5．编写利用 UNION, INTERSECT, EXCEPT 的集合合并查询（三）数据更新（DML）与视图（重点）识记：1．INSERT INTO, UPDATE … SET …, DELETE FROM 语法14253 数据结构与数据库考试大纲第 13页（共 21 页）

2．视图的逻辑实现在数据库系统中的特征（虚表）

理解：1．视图与基本表的联系和本质差别，以及视图的五大积极作用

2．通过视图进行数据更新时所受到的各种合理机制限制应用：1．编写单行数据插入和通过子查询结果集批量插入数据的 SQL 语句

2．编写带有 WHERE 复杂条件的批量数据修改、表间级联数据修改和数据删除 SQL 语句

3．使用 CREATE VIEW 创建视图（包括带 WITH CHECK OPTION）和使用 DROP 删除视图，通过视图编写查询

第 12 章数据库设计及优化

本章为全书理论难度最高、逻辑性极强的重点核心章节。考生需掌握数据库设计的 6 个步骤；重点熟练掌握概念设计中 E-R 图的绘制，以及逻辑设计中 E-R 图转关系模式的映射法则；重点精通规范化理论中 1NF~3NF/BCNF 的判定、候选键求解与模式分解算法。

（一）数据库设计基本步骤（次重点）识记：数据库设计的六个阶段划分理解：各设计阶段的主要任务和主要交付文档物（如数据流图 DFD、数据字典 DD、E-R 图、物理模式等）

（二）概念设计（E-R 模型）与逻辑结构设计（重点）识记：概念模式、E-R 图三大要素（实体、属性、联系）

理解：1．多 E-R 图集成时的命名冲突、结构冲突及属性冲突解决原则

2．E-R 图向关系模式映射的黄金法则：1:1、1:n 及 m:n 联系的转换外键指向和独立成表标准应用：1．针对给定的应用场景，进行需求抽象，手绘出完整的含有各个主属性、各实体、联系并标注联系类型的概念 E-R 图

2．将设计好的 E-R 图转换为关系模式集合，明确列出各关系的主键和外键14253 数据结构与数据库考试大纲第 14页（共 21 页）

（三）关系模式规范化理论（重点）识记：1．函数依赖（FD）、完全函数依赖、部分函数依赖、传递函数依赖、非平凡函数依赖

2．1NF、2NF、3NF、BCNF 范式的定义特征理解：1．数据冗余和插入、删除、更新异常在模式设计中的产生原理（由于不合理的 FD 导致）

2．求解候选键的闭包属性计算法

3．各种范式之间的递进包容级别关系应用：1．计算给定关系模式的属性闭包，并根据算法寻找出该模式的候选键

2．对给定的关系模式及函数依赖集，逐级判定其所属的最高范式（1NF、2NF、3NF 或 BCNF），详细论证其理由（如指明是否存在非主属性对码的部分依赖或传递依赖）

3．使用无损连接和保持函数依赖的模式分解方法，将不合理的低级关系模式规范化分解至 3NF 或 BCNF 关系模式集

第 13 章数据库安全性与完整性

本章主要考核数据库的安全权限管理、完整性约束控制及服务端的高级 T-SQL 编程技术。考生应掌握授权控制语法，熟练掌握游标的编写方法，熟练掌握服务端存储过程、DML 触发器的编写与应用。

（一）数据库安全性与完整性控制（次重点）识记：1．自主访问控制（DAC）、强制访问控制（MAC）

2．角色（Role）的定义理解：通过角色简化和安全管理数据库权限分配的机制应用：编写 GRANT、REVOKE 语句对用户和角色在特定表上分配或收回SELECT、UPDATE、INSERT 等安全性存取权限（二）服务端 Transact-SQL 高级编程（重点识记：游标（Cursor）定义、存储过程、触发器（Trigger）、存储函数。

14253 数据结构与数据库考试大纲第 15页（共 21 页）

理解：1．游标在处理行级数据集时的行指针定位推进逻辑

2．触发器的分类和触发机制（前触发/后触发、替代触发），以及inserted 和 deleted 两张内置临时过渡表的工作原理应用：1．手写编写完整的 T-SQL 游标编程段（游标声明 DECLARE、打开OPEN 、 推进 FETCH INTO 循环 处理 、 关闭 CLOSE 与释 放 DEALLOCATE）

2．使用 T-SQL 编写功能完整的、带有参数输入输出、包含事务回滚和错误捕获的存储过程

3．编写高级 DML 触发器，实现复杂的自动业务限制、数据库参照级联操作或跨表更新同步（如自动控制图书库存和借阅数量关联限制）

第 14 章事务管理与恢复

本章主要考核事务在 DBMS 中的工作和保障原理。考生需深刻掌握事务的 ACID 特性，熟练掌握并发调度的可串行化判断，掌握封锁锁类型和两段锁协议， 掌握数据库故障（UNDO/REDO）的恢复逻辑。

（一）事务与 ACID 特性（重点）识记：1．事务（Transaction）的逻辑定义、BEGIN TRANSACTION, COMMIT,ROLLBACK 事务生命周期

2．原子性（A）、一致性（C）、隔离性（I）、持久性（D）四大事务基本特性理解：事务 ACID 各个特性对应的后台 DBMS 组件保证机制（原子性和持久性由恢复管理器保证，隔离性由并发控制管理保证，一致性由前三者共同支持）

（二）并发控制与封锁协议（重点）识记：1．丢失修改、脏读（读脏数据）、不可重复读等三大并发不一致性现象特征

2．排他锁（X 锁 / 写锁）、共享锁（S 锁 / 读锁）

14253 数据结构与数据库考试大纲第 16页（共 21 页）

3．两段锁协议（2PL）的严格定义理解：1．封锁的一级、二级、三级封锁协议在防范并发异常中的层级作用差别

2．可串行化调度、冲突可串行化调度的定义

3．死锁和活锁的成因，死锁预防（超时法、等待图法）和解除原理。

应用：1．判定给定的多个并发事务交叉调度历史，是否属于冲突可串行化调度

2．分析给定封锁指令下，事务是否符合两段锁协议（2PL），并判断是否可能导致死锁出现（三）数据库恢复技术（重点）识记：1．事务故障、系统故障、介质故障

2．日志文件（LOG）、Undo、Redo 机制理解：1．检查点（Checkpoint）技术在数据库系统崩溃恢复中过滤未提交、已提交事务，缩短 Undo/Redo 扫描范围的优势和原理

2．数据转储（备份）的模式（静态/动态备份，全量/增量备份）

应用：根据给定的包含检查点的事务日志执行序列，写出系统崩溃故障发生后，恢复管理器如何分划出需要重做（Redo List）和撤销（Undo List）的事务清单，并陈述具体修复步骤

第 15 章数据库

应用开发本章主要考核数据库系统的物理架构和现代数据访问接口。考生应理解两层与多层体系架构的特点，掌握 ADO.NET 的核心数据访问接口对象，理解通过数据库连接接口访问和修改数据库的核心编程思路。

（一）应用系统体系结构（一般）识记：客户机/服务器（C/S）架构、浏览器/服务器（B/S）架构理解：两层 C/S 架构与三层 B/S 架构各自的数据处理、部署维护优缺点（二）数据库访问接口技术（次重点）

14253 数据结构与数据库考试大纲第 17页（共 21 页）识记：ODBC、JDBC、OLEDB、ADO.NET 的技术定位理解：ADO.NET 体系中：Connection、Command、DataReader、DataAdapter、DataSet 五个最基础、最核心对象的作用及协作数据流动路径应用：使用 ADO.NET 或通用高级语言数据库接口，手写编写创建 Connection连接 、 指定 Command 语句、 利用 DataReader 检索数据 ，或利 用 DataAdapter 填充 DataSet 的完整开发代码14253 数据结构与数据库考试大纲第 18页（共 21 页）

第三部分有关说明与实施要求

一、考核的能力层次表述

本大纲在考核目标中，按照“识记”“理解”“应用”三个能力层次规定其应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是：识记：能知道有关的名词、概念、知识的含义，并能正确认识和表述，是低层次的要求。

理解：在识记的基础上，能全面把握基本概念、基本原理、基本方法，能掌握有关概念、原理、方法的区别与联系，是较高层次的要求。

应用：在理解的基础上，能运用基本概念、基本原理、基本方法联系学过的多个知识点分析和解决有关的理论问题和实际问题，是最高层次的要求。

二、教材

1．指定教材：《数据结构与数据库应用教程》，于秀丽，清华大学出版社，2019 年版（第 1 版）

2．参考教材：

《数据结构（C 语言版）（第 2 版）》严蔚敏、李冬梅、吴伟民，人民邮电出版社，2021 年版 《数据库系统概论（第 6 版）》王珊、杜小勇、陈红，高等教育出版社，2023 年版

三、

自学方法指导

1．在开始阅读指定教材某一章之前，先翻阅大纲中有关这一章的考核知识点及对知识点的能力层次要求和考核目标，以便在阅读教材时做到心中有数，有的放矢。

2．阅读教材时，要逐段细读，逐句推敲，集中精力，吃透每一个知识点，对基本概念必须深刻理解，对基本理论必须彻底弄清，对基本方法必须牢固掌握。

3．在自学过程中，既要思考问题，也要做好阅读笔记，把教材中的基本概念、 原理、方法等加以整理，这可从中加深对问题的认知、理解和记忆，以利于突出 重点，并涵盖整个内容，可以不断提高自学能力。

4．完成书后作业和适当的辅导练习是理解、消化和巩固所学知识，培养分析问题、解决问题及提高能力的重要环节，在做练习之前，应认真阅读教材，按考核14253 数据结构与数据库考试大纲第 19页（共 21 页） 目标所要求的不同层次，掌握教材内容，在练习过程中对所学知识进行合理的回顾与发挥，注重理论联系实际和具体问题具体分析，解题时应注意培养逻辑性，针对问题围绕相关知识点进行层次（步骤）分明的论述或推导，明确各层次（步骤）间的逻辑关系。

四、对社会助学的要求

1．应熟知考试大纲对课程提出的总要求和各章的知识点。

2．应掌握各知识点要求达到的能力层次，并深刻理解对各知识点的考核目标。

3．辅导时，应以考试大纲为依据，指定的教材为基础，不要随意增删内容，以免与大纲脱节。

4．辅导时，应对学习方法进行指导，宜提倡“认真阅读教材，刻苦钻研教材，主动争取帮助，依靠自己学通”的方法。

5．辅导时，要注意突出重点，对考生提出的问题，不要有问即答，要积极启发引导。

6．注意对考生能力的培养，特别是自学能力的培养，要引导考生逐步学会独立学习，在自学过程中善于提出问题，分析问题，做出判断，解决问题。

7．要使考生了解试题的难易与能力层次高低两者不完全是一回事，在各个能力层次中会存在着不同难度的试题。

8.助学学时：本课程共 4 学分，建议总课时 72 学时，其中助学课时分配如下：

章次 章节内容学 时

第 1 章绪论第

2 章线性表第 3 章特殊线性表第 4 章数组第 5 章树与二叉树第 6 章图 第 7 章查找第 8 章排序第 9 章数据库系统概述第 10 章关系模型与关系代数14253 数据结构与数据库考试大纲第 20页（共 21 页） 第 11 章关系数据库标准语言——SQL 第 12 章数据库设计及优化第 13 章数据库安全性与完整性第 14 章事务管理与恢复第 15 章数据库应用开发合 计

五、关于命题考试的若干规定

1．本大纲各章所提到的内容和考核目标都是考试内容。试题覆盖到章，适当突出重点。

2．试卷中对不同能力层次的试题比例大致是：“识记”为 30% 、“理解”为40% 、“应用”为 30%。

3．试题难易程度应合理：容易、中等、难比例为 3:4:3。

4．每份试卷中，各类考核点所占比例约为：重点占 60% ，次重点占 30% ，一般占 10%。

5．试题类型一般分为：单项选择题、填空题、名词解释题、简答题、应用题、案例分析题。

6．考试采用闭卷笔试，考试时间 150 分钟，采用百分制评分，60 分合格。

六、题型示例（样题）

一、单项选择题

（本大题共 10 小题，每小题 1 分，共 10 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”上的相应字母涂黑。错涂、多涂或未涂均无分。

1．下列内部排序算法中，在最坏情况下时间复杂度依然为 O(n log2 n) 并且属于稳定排序的是 A．快速排序 B．直接插入排序 C．2-路归并排序 D．简单选择排序

二、填空题

（本大题共 10 小题，每小题 1 分，共 10 分）

11．栈是一种限制在表的一端进行插入和删除操作的线性表，其操作原则遵循_________特征。

14253 数据结构与数据库考试大纲第 21页（共 21 页）

三、名词解释题

（本大题共 5 小题，每小题 3 分，共 15 分）

21．连通图（数据结构）

四、简答题

（本大题共 4 小题，每小题 5 分，共 20 分）

26．简述线性表顺序存储结构与链式存储结构各自的优缺点及适用应用场景。

五、

应用题（本大题共 3 小题，每小题 10 分，共 30 分）

30．已知一棵二叉树的先序（前序）遍历序列为 ABDECFG，其中序遍历序列为 DBEAFCG。请按要求完成：

（1）手绘画出该二叉树的完整拓扑结构图；

（3）写出该二叉树的后序遍历序列；

（3）计算该二叉树的叶子结点数量并给出其度为 1 的结点数。

六、案例分析题

（本大题共 1 小题，每小题 15 分，共 15 分）

33．某图书管理系统中涉及如下实体、属性及关联：

– 读者：读者号、姓名、专业类别、借书上限；

– 图书：图书号、书名、作者、出版社、单价；

– 借阅关系：一个读者可以借阅多本不同的图书，一本图书也可以被多名不同的读者借阅，借阅时必须记录具体的借阅日期和应归还日期。根据以上业务需求，完成以下设计任务：

（1）画出该图书管理系统的概念模型 E-R 图（标注实体主键、联系类型）；

（2）将该 E-R 图转换为相应的符合 3NF 要求的关系模式集合；

（3）明确指出转换结果中每个关系模式的主键和外键（如果存在的话）。