《数据结构复习汇编》由会员分享，可在线阅读，更多相关《数据结构复习汇编（52页珍藏版）》请在金锄头文库上搜索。
1、题型： 1. 单选 15分 每题1分 2. 判断 10分 每题1分 3. 填空 12分 每空1分 4. 程序分析题 （写出运行结果）18分 每题6分 5. 应用题 30分 每题10分 6. 编程题 15分 两小题任选其一 数据结构复习 2012/11/101 应用题： 1. 分析算法的时间复杂度（最好、最差、平均情况） 2. 串 KMP算法（看习题）给出目标串做模式匹配，计算 next函数值，利用算法写出匹配过程（每趟的结果） 3. 二叉树的构造 给两个遍历序列画出二叉树，并写出另 外一种遍历序列 4.哈夫曼算法的应用 给出字符的出现频率，构造哈夫曼 树，编写二进制编码，计算最有WPL值 5.
2、排序 快速、冒泡、直插、希尔排序四种排序的基本思 路，排序过程，给出关键字会写每趟的结果 编程题 1.写出算法的基本思路（可以用图示法和文字叙述）3分 2. 定义相应的数据结构 2分 3. 代码 10分 2012/11/102 第一章 基本概念: 数据元素：是数据（集合）中的一个“个体” ， 是数据的基本单位。也称为结点、顶点、记录 等。通常作为一个整体来处理。 数据项：是具有独立含义的数据最小单位 ，也称 为字段或域。 数据结构：是指数据以及数据元素相互之间的联 系。可以看作是相互间存在一种或多种关系的数 据元素集合。 数据结构组成的三要素：数据的逻辑结构、存储 结构、数据的运算。 2012
3、/11/103 4/49 学号姓名性别班号 1张斌男9901 8刘丽女9902 34李英女9901 20陈华男9902 12王奇男9901 26董强男9902 5王萍女9901 数据元素 数据项 数据结构实学生表 2012/11/10 逻辑结构类型 (1) 集合 结点之间关系：无。 (2) 线性结构 结点之间关系：一对一。 特点：开始结点和终端结点都是惟一的,除了开始结点和终端结点以 外,其余结点有且仅有一个直接前驱和直接后继结点。如学生表、成 绩表、档案表、索引表等都属于线性结构。 (3) 树形结构 结点之间关系：一对多。 特点：每个结点最多只有一个直接前驱结点，但可以有多个直接后 继结点。
4、高校的行政结构示意图、家族族谱图、书的目录、操作系 统的目录结构、系统内部的表达式计算等都是树形结构。 (4) 图形结构 结点之间关系：多对多。 特点：每个结点的直接前驱和直接后继结点的个数都是任意的。交 通网、通信网、万维网、赛事日程安排、课程安排和最短路径问题 等都属于图形结构。 2012/11/105 常见逻辑结构的类型 1.集合 2.线性结构：顺序表 3.树形结构 4.图形结构 （ 3 2. 指针类型 int *p; 3. 数组类型 int a10; 4. 结构体类型 struct student int sno; char sname10; char ssex2; int sage;
5、 5. 自定义类型 typedef char ElemType; 2012/11/109 算法分析方法，即算法的渐近时间复杂度分析 方法一 统计从开始到终止算法所需的总程序步数, 并 将其视为问题规模n的函数T(n)； 方法二 在算法中选取一种基本操作；计算基本操作 执行总步数，并将其记作T(n)。 T(n)称为算法的时间复杂度。 时间复杂度的大O表达法：当问题的规模n趋向无穷大 时, 时间复杂度T(n)的数量级f(n)称为算法的渐进时间 复杂度,记作T(n)=O(f(n)。 T(n)=2n+3=O(n) T(n)=3n2+1=O(n2) 也就是只求出T(n)的最高阶，忽略其低阶项和常系数.
6、2012/11/1010 平均复杂度(The Average Case): 所有可能输入数据 集的期望值。 最坏情况复杂度(The Worst Case): 估算最坏情况下 时间复杂度的一个上界。这也是通常所指的复杂度。 一个没有循环的算法的基本运算次数与问题规模n 无关,记作O(1),也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规 模n的增长呈线性增大关系,记作O(n),也称线性阶。 重点：例1.81.9及相关习题（P33最坏情况、最好情 况、平均时间复杂度的分析） 2012/11/1011 12/49 各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O
7、(n*log2n)O(n2) O(n3)O(2n)length+1)return 0; i-; for (j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=e; L-length+; /*顺序表长度增1*/ return 1; 2012/11/1016 2. 删除数据元素ListDelete（L，i，e） 思路： 判断参数i是否为合法值； 保留第i个元素的值； 将顺序表表尾至第i个元素前移一位; 顺序表长度减1。 int ListDelete(SqList * if (iL-length)return 0; i-; e=L-datai; for (j=i
8、;jlength-1;j+) L-dataj=L-dataj+1; L-length-; return 1; 2012/11/1017 单链表线性表中每个元素至多只有一个前驱元素和一个后继元素， 所以链表中每个结点除包含有数据域外,只设置一个指针域, 以指向其后 继结点, 这样的链接表称为单链表。 双链表每个结点中除包含有数值域外,设置两个指针域,分别指向其前 驱结点和后继结点,这样的链接表称之为线性双向链接表, 简称双链表。 循环链表循环链表是表中最后一个结点的指针指向头结点，使链表 构成环状 2012/11/1018 LinkList类型定义（单链表） typedef struct Lno
9、de ElemType data； struct Lnode *next； LinkList； DLinkList类型定义（双链表） typedef struct Lnode ElemType data； struct Dnode *prior； struct Dnode *next； DLinkList； 2012/11/1019 单链表基本运算的实现 重点掌握头插法、尾插法建立单链表 1. 头插法 操作接口：CreateListF(L, a, n) 2012/11/1020 void CreateListF(LinkList * int i; L=(LinkList *)malloc(si
10、zeof(LinkList); L-next=NULL; for (i=0;idata=ai; s-next=L-next; L-next=s; 2012/11/1021 2.尾插法 2012/11/1022 void CreateListR(LinkList *int i; L=(LinkList *)malloc(sizeof(LinkList); r=L； for (i=0;idata=ai; r-next=s r=s; r-next=NULL; 2012/11/1023 比较顺序表和链表两种存储结构（差异、适用情形） 存储分配方式比较 顺序表采用顺序存储结构，即用一段地址连续的存储 单
11、元依次存储线性表的数据元素，数据元素之间的逻 辑关系通过存储位置来实现。 单链表采用链接存储结构，即用一组任意的存储单元 存放线性表的元素。用指针来反映数据元素之间的逻 辑关系。 2012/11/1024 时间性能比较 时间性能是指实现基于某种存储结构的基本操作 （即算法）的时间复杂度。 顺序表的时间为(1)，是随机存取； 单链表的时间为(n)，是顺序存取。 顺序表需移动表长一半的元素，时间为(n)； 单链表不需要移动元素，在给出某个合适位置的 指针后，插入和删除操作所需的时间仅为(1)。 2012/11/1025 空间性能比较 空间性能是指某种存储结构所占用的存储空间的 大小。 定义结点的存
12、储密度： 2012/11/1026 空间性能比较 结点的存储密度： 顺序表中每个结点的存储密度为1（只存储数据 元素），没有浪费空间； 单链表的每个结点的存储密度0）个互不相交的有限集合T1,T2, ,Tm ，其中每个集合又是一棵树，并称为这个根结点 的子树。 2012/11/1039 2. 树的表示 树形图表示法：是树结构的主要表示方法。 括号表示法 文氏图表示法 凹入表示法 3. 树的基本术语 （1）结点的度与叶子结点：树中某个结点的子 树的个数称为该结点的度。树中各结点的度的最 大值称为树的度，通常将度为m的树称为m次 数。 （2）分支结点与叶子结点：度不为零的结点称 为非终端结点，又叫
13、分支结点。度为零的结点称 为终端结点或叶子结点。在分支结点中，每个结 点的分支数就是该结点的度。 2012/11/1040 （3）路径与路径长度：对于任意两个结点ki和kj，若 树中存在一个结点序列ki，ki1，ki2，kin，kj，使 得序列中除ki外的任一结点都是在其序列中的前一个结 点的直接后继，则称该结点序列为由ki到kj的一条路径 ，用路径所通过的结点序列（ ki，ki1，ki2，kin ，kj）表示这条路径。路径的长度等于路径所通过的结 点数目减1（及路径上分支数目）。 （4）孩子结点、双亲结点和兄弟结点：在一棵树中每 个结点的直接后继被称作该结点的孩子结点（或子女 结点）。相应的，该结点被称作孩子结点的双亲结点 （或父母结点）。具有同一双亲的孩子结点互为兄弟 结点。 （5）结点的层次和树的高
