中国传媒大学 824 数据结构考研真题参考书目大纲复习资料
点这里查询各专业24复试25初试考研资料
封面
【初试】2023 年中国传媒大学
824 数据结构考研精品资料
考研精品资料
第 2 页 共 538 页
【初试】2023 年中国传媒大学 824 数据结构考研精品资料
一、中国传媒大学 824 数据结构考研真题汇编及考研大纲
1．中国传媒大学 824 数据结构 2002-2006 年考研真题，暂无答案。
说明：分析历年考研真题可以把握出题脉络，了解考题难度、风格，侧重点等，为考研复习指明方向。
2 . 中国传媒大学 824 数据结构考研大纲
①2022 年中国传媒大学 824 数据结构考研大纲。
②2021 年中国传媒大学 824 数据结构考研大纲。
说明：考研大纲给出了考试范围及考试内容，是考研出题的重要依据，同时也是分清重难点进行针对性复
习的首选资料，本项为免费提供。
二、2023 年中国传媒大学 824 数据结构考研资料
3．《数据结构》考研相关资料
（1）《数据结构》[笔记+课件+提纲]
①2023 年中国传媒大学 824 数据结构之《数据结构》考研复习笔记。
说明：本书重点复习笔记，条理清晰，重难点突出，提高复习效率，基础强化阶段必备资料。
②2023 年中国传媒大学 824 数据结构之《数据结构》本科生课件。
说明：参考书配套授课 PPT 课件，条理清晰，内容详尽，非本校课件，版权归属制作教师，本项免费赠送。
③2023 年中国传媒大学 824 数据结构之《数据结构》复习提纲。
说明：该科目复习重难点提纲，提炼出重难点，有的放矢，提高复习针对性。
（2）《数据结构》考研核心题库（含答案）
①2023 年中国传媒大学 824 数据结构考研核心题库之单项选择题精编。
②2023 年中国传媒大学 824 数据结构考研核心题库之算法设计题精编。
③2023 年中国传媒大学 824 数据结构考研核心题库之应用题精编。
说明：本题库涵盖了该考研科目常考题型及重点题型，根据历年考研大纲要求，结合考研真题进行的分类
汇编并给出了详细答案，针对性强，是考研复习首选资料。
（3）《数据结构》考研题库[仿真+强化+冲刺]
①2023 年中国传媒大学 824 数据结构考研专业课五套仿真模拟题。
说明：严格按照本科目最新专业课真题题型和难度出题，共五套全仿真模拟试题含答案解析。
②2023 年中国传媒大学 824 数据结构考研强化五套模拟题及详细答案解析。
说明：专业课强化检测使用。共五套强化模拟题，均含有详细答案解析，考研强化复习必备。
③2023 年中国传媒大学 824 数据结构考研冲刺五套模拟题及详细答案解析。
说明：专业课冲刺检测使用。共五套冲刺预测试题，均有详细答案解析，最后冲刺必备资料。
三、电子版资料全国统一零售价
4．本套考研资料包含以上一、二部分（高清 PDF 电子版，不含教材），全国统一零售价：[￥]
考研精品资料
第 3 页 共 538 页
特别说明：
①本套资料由本机构编写组按照考试大纲、真题、指定参考书等公开信息整理收集编写，仅供考研复习参
考，与目标学校及研究生院官方无关，如有侵权、请联系我们将立即处理。
②资料中若有真题及课件为免费赠送，仅供参考，版权归属学校及制作老师，在此对版权所有者表示感谢，
如有异议及不妥，请联系我们，我们将无条件立即处理！
四、2023 年研究生入学考试指定/推荐参考书目（资料不包括教材）
5．中国传媒大学 824 数据结构考研初试参考书
《数据结构》（C 语言版）
严蔚敏、吴伟民著 清华大学出版社。
五、本套考研资料适用院系/专业及考试题型
经济与管理学院
试题类型
选择题、应用题、算法设计题等。
版权声明
编写组依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面
上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由
于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在
此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您
沟通处理。
因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读
者批评指正。
考研精品资料
第 4 页 共 538 页
目录
封面............................................................................................................................................................. 1
目录............................................................................................................................................................. 4
2023 年中国传媒大学 824 数据结构备考信息 ............................................................................................. 7
中国传媒大学 824 数据结构考研初试参考书目
............................................................................................... 7
中国传媒大学 824 数据结构考研招生适用院系及考试题型............................................................................ 7
中国传媒大学 824 数据结构历年真题汇编.................................................................................................. 8
中国传媒大学 824 数据结构 2006 年考研真题（暂无答案）.......................................................................... 8
中国传媒大学 824 数据结构 2005 年考研真题（暂无答案）........................................................................ 12
中国传媒大学 824 数据结构 2004 年考研真题（暂无答案）........................................................................ 16
中国传媒大学 824 数据结构 2003 年考研真题（暂无答案）........................................................................ 20
中国传媒大学 824 数据结构 2002 年考研真题（暂无答案）........................................................................ 24
中国传媒大学 824 数据结构考研大纲 ........................................................................................................27
2021 年中国传媒大学 824 数据结构考研大纲................................................................................................. 27
2022 年中国传媒大学 824 数据结构考研大纲................................................................................................. 30
2023 年中国传媒大学 824 数据结构考研核心笔记.....................................................................................33
《数据结构》考研核心笔记.......................................................................................................................33
第 1 章 绪论...................................................................................................................................................... 33
考研提纲及考试要求...........................................................................................................................................33
考研核心笔记........................................................................................................................................................33
第 2 章 线性表.................................................................................................................................................. 45
考研提纲及考试要求...........................................................................................................................................45
考研核心笔记........................................................................................................................................................45
第 3 章 栈和队列.............................................................................................................................................. 60
考研提纲及考试要求...........................................................................................................................................60
考研核心笔记........................................................................................................................................................60
第 4 章 串.......................................................................................................................................................... 64
考研提纲及考试要求...........................................................................................................................................64
考研核心笔记........................................................................................................................................................64
第 5 章 数组和广义表...................................................................................................................................... 71
考研提纲及考试要求...........................................................................................................................................71
考研核心笔记........................................................................................................................................................71
第 6 章 树和二叉树.......................................................................................................................................... 77
考研提纲及考试要求...........................................................................................................................................77
考研核心笔记........................................................................................................................................................77
考研精品资料
第 5 页 共 538 页
第 7 章 图........................................................................................................................................................ 101
考研提纲及考试要求.........................................................................................................................................101
考研核心笔记......................................................................................................................................................101
第 8 章 动态存储管理.................................................................................................................................... 119
考研提纲及考试要求.........................................................................................................................................119
考研核心笔记......................................................................................................................................................119
第 9 章 查找.................................................................................................................................................... 127
考研提纲及考试要求.........................................................................................................................................127
考研核心笔记......................................................................................................................................................127
第 10 章 内部排序.......................................................................................................................................... 143
考研提纲及考试要求.........................................................................................................................................143
考研核心笔记......................................................................................................................................................143
第 11 章 外部排序.......................................................................................................................................... 153
考研提纲及考试要求.........................................................................................................................................153
考研核心笔记......................................................................................................................................................153
第 12 章 文件.................................................................................................................................................. 159
考研提纲及考试要求.........................................................................................................................................159
考研核心笔记......................................................................................................................................................159
2023 年中国传媒大学 824 数据结构考研辅导课件...................................................................................164
《数据结构》考研辅导课件 ........................................................................................................................... 164
2023 年中国传媒大学 824 数据结构考研复习提纲...................................................................................275
《数据结构》考研复习提纲 ........................................................................................................................... 275
2023 年中国传媒大学 824 数据结构考研核心题库...................................................................................278
《数据结构》考研核心题库之选择题精编 ................................................................................................... 278
《数据结构》考研核心题库之算法设计题精编 ........................................................................................... 290
《数据结构》考研核心题库之应用题精编 ................................................................................................... 341
2023 年中国传媒大学 824 数据结构考研题库[仿真+强化+冲刺] .............................................................373
中国传媒大学 824 数据结构考研仿真五套模拟题........................................................................................ 373
2023 年数据结构五套仿真模拟题及详细答案解析（一）..........................................................................373
2023 年数据结构五套仿真模拟题及详细答案解析（二）..........................................................................384
2023 年数据结构五套仿真模拟题及详细答案解析（三）..........................................................................394
2023 年数据结构五套仿真模拟题及详细答案解析（四）..........................................................................406
2023 年数据结构五套仿真模拟题及详细答案解析（五）..........................................................................417
中国传媒大学 824 数据结构考研强化五套模拟题........................................................................................ 427
2023 年数据结构五套强化模拟题及详细答案解析（一）..........................................................................427
2023 年数据结构五套强化模拟题及详细答案解析（二）..........................................................................439
2023 年数据结构五套强化模拟题及详细答案解析（三）..........................................................................451
考研精品资料
第 6 页 共 538 页
2023 年数据结构五套强化模拟题及详细答案解析（四）..........................................................................463
2023 年数据结构五套强化模拟题及详细答案解析（五）..........................................................................474
中国传媒大学 824 数据结构考研冲刺五套模拟题........................................................................................ 486
2023 年数据结构五套冲刺模拟题及详细答案解析（一）..........................................................................486
2023 年数据结构五套冲刺模拟题及详细答案解析（二）..........................................................................496
2023 年数据结构五套冲刺模拟题及详细答案解析（三）..........................................................................508
2023 年数据结构五套冲刺模拟题及详细答案解析（四）..........................................................................518
2023 年数据结构五套冲刺模拟题及详细答案解析（五）..........................................................................529
考研精品资料
第 7 页 共 538 页
2023 年中国传媒大学 824 数据结构备考信息
中国传媒大学 824 数据结构考研初试参考书目
《数据结构》（C 语言版） 严蔚敏、吴伟民著 清华大学出版社。
中国传媒大学 824 数据结构考研招生适用院系及考试题型
经济与管理学院
试题类型
选择题、应用题、算法设计题等。
考研精品资料
第 8 页 共 538 页
中国传媒大学 824 数据结构历年真题汇编
中国传媒大学 824 数据结构 2006 年考研真题（暂无答案）
考研精品资料
第 9 页 共 538 页
考研精品资料
第 10 页 共 538 页
考研精品资料
第 11 页 共 538 页
考研精品资料
第 27 页 共 538 页
中国传媒大学 824 数据结构考研大纲
2021 年中国传媒大学 824 数据结构考研大纲
考研精品资料
第 28 页 共 538 页
考研精品资料
第 29 页 共 538 页
考研精品资料
第 30 页 共 538 页
2022 年中国传媒大学 824 数据结构考研大纲
考研精品资料
第 33 页 共 538 页
2023 年中国传媒大学 824 数据结构考研核心笔记
《数据结构》考研核心笔记
第 1 章 绪论
考研提纲及考试要求
考点：数据（Data）
考点：数据对象（DataObject）
考点：数据抽象与抽象数据类型
考点：逻辑结构
考点：数据结构课程地位
考研核心笔记
【核心笔记】数据结构的基本概念（定义）
1.数据（Data）
定义
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。
例如对 C 源程序
2.数据元素（DataElement）
定义
数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。
例如：
3.数据对象（DataObject）
定义
数据对象是性质相同的数据元素的集合，是数据的一个子集。
例如：整数集合：N={0，±1，±2，…}无限集
字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集
4.数据结构（Data Structure）
（1）定义
考研精品资料
第 34 页 共 538 页
数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它
指的是数据元素之间的相互关系，即数据的组织形式。例如表结构：
（
2）树型结构
（
3）图结构
5.数据类型(DataType)
定义
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
如在高级语言中，整型类型的取值范围为：
-32768~+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%
（1）高级语言中的数据类型分为两大类：
①原子类型，其值不可分解。如 C 语言中的标准类型（整型、实型、字符型、）。
②结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构
的，也可以是结构的。
6.数据抽象与抽象数据类型
（1）数据的抽象
（
2）抽象数据类型(AbstractDataType)
（
3）抽象数据类型实现
（
4）ADT 的表示与实现
（
5）面向对象的概念
（
6）结构化的开发方法与面向对象开发方法不同点
【核心笔记】数据结构的内容
1.逻辑结构
考研精品资料
第 35 页 共 538 页
（1）定义
数据的逻辑结构是指数据元素之间逻辑关系描述。
（
2）形式化描述：Data_Structure=（D,R）其中 D 是数据元素的有限集，R 是 D 上关系的有限集。
（
3）四类基本的结构
集合结构、线性结构、树型结构、图状结构。
2.集合结构
（1）定义：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
例如
集合
3.线性结构
定义：结构中的数据元素之间存在着一对一的线性关系。
例如：线性表
4.树型结构
定义：结构中的数据元素之间存在着一对多的层次关系。
例如：树
5.图状结构或网状结构
定义：结构中的数据元素之间存在着多对多的任意关系。
例如
6.逻辑结构
综上所述，数据的逻辑结构可概括为
逻辑结构
线性结构——线性表、栈、队、字符串数组、广义表
非线性结构——树、图
7.存储结构
（1）定义：存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的
考研精品资料
第 36 页 共 538 页
实现，它包括数据元素的表示和关系的表示。
（
2）形式化描述：
D 要存入机器中，建立一从 D 的数据元素到存储空间 M 单元映象 S，D→M，即对于每一个 d，d∈
D,都有唯一的 z∈M 使 S（D）=Z,同时这个映象必须明显或隐含地体现关系 R。
（
3）逻辑结构与存储结构的关系为：
存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。
（
4）数据元素之间关系在计算机中的表示方法：
顺序映象（顺序存储结构）
非顺序映象（非顺序存储结构）
8.运算集合
例如工资表
9.数据结构的内容
综上所述，数据结构的内容可归纳为三个部分
逻辑结构、存储结构和运算集合：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放
在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。
【核心笔记】算法
1.算法（Algorithm）定义
定义：算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
2.算法的特性
（1）有限性：有限步骤之内正常结束，不能形成无穷循环
（
2）确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。
（
3）输入：有多个或 0 个输入
（
4）输出：至少有一个或多个输出
（
5）可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成
3.算法设计的要求
（1）算法特征
①算法的正确性
②可读性
③健壮性
④高效率和低存储量
【核心笔记】算法描述的工具
考研精品资料
第 164 页 共 538 页
2023 年中国传媒大学 824 数据结构考研辅导课件
《数据结构》考研辅导课件
考研精品资料
第 165 页 共 538 页
考研精品资料
第 166 页 共 538 页
考研精品资料
第 167 页 共 538 页
考研精品资料
第 275 页 共 538 页
2023 年中国传媒大学 824 数据结构考研复习提纲
《数据结构》考研复习提纲
考研精品资料
第 276 页 共 538 页
考研精品资料
第 277 页 共 538 页
考研精品资料
第 278 页 共 538 页
2023 年中国传媒大学 824 数据结构考研核心题库
《数据结构》考研核心题库之选择题精编
1．
向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动__________个元素。
A.8
B.63.5
C.63
D.7
【答案】B
2． 下面关于树和二叉树的叙述中，正确的是__________。
A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序
遍历结果序列的最后一个结点
B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序
遍历结果序列的最后一个结点
C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的
前序遍历结果序列的最后一个结点
D.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的
中序遍历结果序列的最后一个结点
【答案】C
3． 一个有 n 个顶点的无向图最多有__________条边。
A.n
B.
C.
D.2n
【答案】C
4． (1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i
无关；
(2)静态链表中能容纳的元素个数的最大数在定义时就确定了，以后不能增加；
(3)静态链表与动态链表在元素的插入、删除上类似，不需作元素的移动；
以上错误的是_________。
A.(1)、(2)
B.(1)
C.(1)、(2)、(3)
D.(2)
【答案】B
5． 若一个栈的输入序列是
，输出序列的第一个元素是 i，则第 j 个输出元素是__________。
A.
B.
C.
D.不确定的
考研精品资料
第 279 页 共 538 页
【答案】D
6． 设栈的输入序列为
，输出序列为
，若存在
使得
，则当
时， 为
__________。
A.
B.
C.不确定
【答案】C
7． 在带头结点的链队列中，队头指针指向链表的__________
A.最后一个元素结点
B.第一个元素结点
C.头结点
D.都不是
【答案】C
8． 计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、__________。
A.可行性、可移植性和可扩充性
B.可行性、有穷性和确定性
C.确定性、有穷性和稳定性
D.易读性、稳定性和确定性
【答案】B
9． 数据采用链式存储结构时，要求__________。
A.每个节点占用一片连续的存储区域、
B.所有节点占用一片连续的存储区域
C.节点的最后一个数据域是指针类型
D.每个节点有多少个后继就设多少个指针域
【答案】A
10．以下属于逻辑结构的是__________。
A.顺序表
B.哈希表
C.有序表
D.单链表
【答案】C
11．对 AOE 网的关键路径，下面的说法__________是正确的。
A.提高关键路径上的一个关键活动的速度，必然使整个工程缩短工期
B.完成工程的最短时间是从始点到终点的最短路径的长度
C.一个 AOE 网的关键路径只有一条，但关键活动可有多个
D.任何一项活动持续时间的改变都可能影响关键路径的改变
【答案】D
12．若串
，其字串的个数是__________。
A.15
B.95
考研精品资料
第 280 页 共 538 页
C.35
D.105
【答案】D
13．设广义表
，则 L 的长度和深度分别为__________。
A.1和1
B.1和3
C.1和2
D.2和3
【答案】C
14．假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关键字存入散列表中，至少要进行__________
次探测。
A.K-1 次
B.K 次
C.K+1 次
D.
次
【答案】D
15．循环队列存储在数组
中，则入队时的操作为__________。
A.
B.
C.
D.
【答案】D
16．若用冒泡排序对关键字序列
从小到大进行排序，则需要交换的总次数为__________。
A.3
B.6
C.12
D.15
【答案】D
17．在下列两种求图的最小牛成树的算法中，__________算法适合于求边稀疏的网的最小生成树。
A.PRIM
B.KRUSKAL
【答案】B。
18．在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的先后顺序__________
A.都不相同
B.先序和中序相同，而与后序不同
C.完全相同
D.中序和后序相同，而与先序不同
【答案】C
考研精品资料
第 281 页 共 538 页
19．在下列算法中，__________算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终
的位置上。
A.堆排序
B.冒泡排序
C.插入排序
D.快速排序
【答案】C
20．B 树和 B+树__________。
A.都能有效地支持顺序检索
B.都不是平衡的多分树
都不能用于文件的索引结构
D.都能有效地支持随机检索
【答案】D
21．对有 n 个顶点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是
__________。
A.
B.
C.
D.
【答案】C
22．下列有关二叉树的说法正确的是__________。
A.二叉树的度为2;
B.一棵二叉树的度可以小于2;
C.二叉树中至少有一个结点的度为2;
D.二叉树中任何一个结点的度都为2。
【答案】B
23．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是__________。
A.直接插入
B.二分法插入
C.快速排序
D.归并排序
【答案】B
24．将 s 所指结点加到 P 所指结点的右边，见下图，其语句应为__________
图
A.
考研精品资料
第 373 页 共 538 页
2023 年中国传媒大学 824 数据结构考研题库[仿真+强化+冲刺]
中国传媒大学 824 数据结构考研仿真五套模拟题
2023 年数据结构五套仿真模拟题及详细答案解析（一）
一、选择题
1． 在定义 ADT 时，除数据对象和数据关系外，还需说明__________。
A.数据元素
B.算法
C.基本操作
D.数据项
【答案】C
2． 在待排序的元素序列基本有序的前提下，效率最高的排序方法是__________。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
【答案】A
3． 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别是 0 和 3。当从队列中删
除一个元素，再加上两个元素后，rear 和 front 的值为__________。
A.1 和 5
B.2 和 4
C.4 和 2
D.5 和 1
【答案】B
4． 用数组 r 存储静态链表,结点的 next 域指向后继，工作指针 j 指向键中结点,使 j 沿链移动的操作为
__________。
A.
B.
C.
D.
【答案】D
5． 对稀疏矩阵进行压缩存储的目的是__________。
A.便于进行矩阵运算
B.便于输入和输出
C.节省存储空间
D.降低运算的时间复杂度
【答案】C
考研精品资料
第 374 页 共 538 页
6． 求字符串 T 在字符串 S 中首次出现的位置的操作称为__________。
A.求串的长度
B.求子串
C.串的模式四配
D.串的连接
【答案】C
7． 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、__________等五个
特性。
A.可执行性、可移植性和可扩充性；
B.可执行性、有穷性和确定性；
C.确定性、有穷性和稳定性；
D.易读性、稳定性和确定性。
【答案】B
8． 任何一个无向连通图的最小生成树__________。
A.有一棵或多棵
B.只有一棵
C.一定有多棵
D.可能不存在
【答案】A
9． 在待排序的元素序列基本有序的前提下，效率最高的排序方法是__________。
A.插入排序
B.选择
C.快速排序
D.归并排序
【答案】A
10．排序方法中，从未排序序列中挑选元素，并将其一次放入已排序序列(初始时为空)的一端的方法，称
为__________。
A.希尔排序
B.归并排序
C.插入排序
D.简单选择排序
【答案】D
11．算术表达式
转为后缀表铸式后为___________
A.
B.
C.
D.
【答案】D
考研精品资料
第 375 页 共 538 页
12．下列排序方法中，辅助空间为
的是__________。
A.希尔选择
B.冒泡排序
C.堆排序
D.归并排序
【答案】D
二、算法设计题
13．有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表
示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。
计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关
键码小。假设针对某一个记录，统计出的计数值为 c，那么这个记录在新的有序表中的合适的存放位置即
为 c。
(1)给出适用于计数排序的数据表定义；
(2)使用 Pascal 或 C 语言编写实现计数排序的算法；
(3)对于有 n 个记录的表，关键码比较次数是多少？
(4)与简单选择排序相比较，这种方法是否更好？为什么？
【答案】(1)数据表定义为：
或
(2)用 C 语言编写的计数排序的算法为：
(3)对于有 n 个记录的表，关键码比较次数是 。
(4)简单选择排序比这种排序好，因为对具有 n 个记录的数据表进行简单选择排序只需进行
次比较，且可在原地进行排序。
14．计数排序方法要求待排序表的所有数据元素的关键字互不相同，并针对表中的每个记录，扫描待排序
表一趟，统计表中有多少个记录的关键字比该关键字小。假设对某一个记录，统计出的数值为 k，则该记
录在有序表中的存放位置为 k。
(1)给出适用于计数排序的数据表的定义。
(2)编写实现计数排序的算法。
(3)对于有 n 个记录的表，比较次数是多少？
(4)与直接选择排序相比，这种方法是否更好，为什么？
【答案】(1)由于计数排序要求对表结构进行随机访问，故应选择顺序存储结构，数组、类型定义如
下：
考研精品资料
第 376 页 共 538 页
(2)计数排序算法伪代码如下。
(3)对于含 n 个记录的表，关键字比较次数为
。
(4)简单选择排序算法比本算法好。简单选择排序的比较次数是
，需要一个交换记录的辅助存
储空间。而计数排序方法的比较次数为
，且需要一个跟原数组一样大的辅助存储空间。
15．设整数序列
，给出求解最大值的递归程序。
【答案】
16．写出从哈希表中删除关键字为 K 的一个记录的算法，设哈希函数为 h,解决冲突的方法为链地址法。
【答案】算法描述如下：试读已结束
激活后可查看剩余未读页数！
<< 上一篇
网友留言（0 条）