总复习2013-2014-1

一． 基本概念和术语

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 术语：数据、数据元素、数据对象、数据结构、抽象数据类型、算法。

数据的逻辑结构：（四类基本结构）线性结构、树型结构、图状结构、集合

一对一、一对多、多对多、同属于一个集合

数据的存储结构（物理结构）：主要有顺序存储结构（以存储地址相邻来表示逻辑上的相邻关系），链式存储结构（用指针来指示逻辑上的相邻关系） 算法的定义，算法的5个重要特性。对特定问题求解步骤的一种描述。有穷性、确定性、可行性、输入、输出

二． 算法的时间复杂度和空间复杂度

算法的评价：正确性、可读性、健壮性、高效率、低存储量 求语句频度、时间复杂度 三． 线性表的定义

线性结构的特点：存在唯一一个被称作第一个的数据元素；最后一个；出第一个外都有前驱；出最后一个外都厚后继。

四． 线性表的存储结构

1． 顺序存储结构（顺序表）：随机存取

插入/删除元素时，需移动元素的次数。最少0个，最多n个。O（n）

2． 链式存储结构（链表，分为单(向)链表、双(向)链表）：非随机存取（顺序存取）

带头结点的链表和不带头结点的链表； 循环/非循环的链表；

链表空与非空的情况（判断条件）。循环是等于头指针，非循环是空 3． 两种存储结构的优缺点比较，各适合那些场合。

顺序:移动量大，可随机存取 链表：移动少，不能随机存取

五． 线性表操作的实现（算法描述）

插入元素、删除元素、查找、判表是否满足某种特性、逆置等。

判断题：1. 线性表的逻辑顺序与存储顺序总是一致的。错

2. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。错 3. 线性表的链式存储结构优于顺序存储结构。错 选择题：线性表L在( B )情况下适于使用链表结构实现。

A. 不需修改L的结构 B. 需不断对L进行删除、插入 C. 需经常修改L中结点值 D. L中含有大量结点

填空题：1. 对于顺序表，在第i个元素前插入一个元素需移动 个元素，要删除第i个元素，需移动 个元素。

2. 在双向循环链表中某结点（由指针p指示）之后插入s指针所指结点的操作是： ； ； ； ；。 六． 栈

1． 栈的定义、特点（后进先出）仅在表尾进行插入或删除操作的线性表 2． 栈的存储结构：顺序存储结构 链式存储结构

3． 栈的应用：二叉树的先序、中序、后序遍历算法 图的深度优先遍历算法

（将递归算法改写为非递归算法可借助栈来完成；

递归算法的执行需用栈来实现。）

七． 队列

1． 队列的定义、特点 先进先出的线性表（先进先出） 2． 队列的存储结构：顺序存储结构（循环队列），链式存储结构 3． 队列的应用：二叉树层序遍历算法 图的广度优先遍历算法 4． 循环队列：·队空、队满的判断条件

·求队列的长度

判断题：因为栈是特殊的线性表，所以对线性表的所有操作都可以用于对栈操作。错 填空题：循环队列队满的条件是 。

八． 树、二叉树的定义 九． 二叉树

1． 二叉树的性质（5条）1.在二叉树的第i层上至多有2i-1个节点（i）>=1）2.深度为k的二叉树至多有2k -1个节点

3.对任何二叉树T，如果终端节点数位n0,度为2的节点数为n2,则n0=n2+1. 4.n个节点完全二叉树深度log2n下取整+1.

2． 二叉树的存储结构：顺序存储结构（按完全二叉树层序存放）

链式存储结构（二叉链表、三叉链表）（空链域的个数）

3． 遍历二叉树：先序、中序、后序、层序

应用：给定二叉树的先序和中序（或后序和中序）序列，画出相应的二叉树。

十． 树和森林

1． 树的存储结构：双亲表示法 孩子表示法 孩子-兄弟（二叉树）表示法 2． 树（森林）与二叉树的相互转换

3． 树的遍历：先根、后根次序遍历 二叉树的先、中 4． 森林的遍历：先序、中序遍历 二叉树的先、中

十一． 赫夫曼树及其应用

1． 构造最优二叉树（赫夫曼树），求WPL 权*层次的和 2． 赫夫曼编码

十二． 各种二叉树概念的区分

1． 满二叉树（若深度为k，结点数？）2k-1

2． 完全二叉树（若深度为k，结点数至多k、至少？log2n下取整+1） 3． 正则二叉树（严格二叉树;不存在度为一的节点）（若深度为k，结点数至多、至少？） 4． 最优二叉树

5． （折半查找的）判定树

6． 二叉排序（二叉查找树）树 7． 平衡二叉树 8． 堆

十三． 二叉树有关的递归算法

判断题：1. 已知二叉树的先序序列和后序序列并不能唯一地确定这棵二叉树，因为不知道二叉树的根结点是哪一个。对

i-1k

2. 一般二叉树的第i层上有2个结点，深度为k的二叉树有2-1个结点。 选择题：1. 下列二叉树中，( a )可用于实现符号不等长高效编码。

A. 最优二叉树 B. 二叉查找树 C. 平衡二叉树 ?? D. 二叉排序树 2．结点数为ｎ的二叉树高度至多为( b )。

A. 不定 B.ｎ C. ?logn?+1 D. logn

22

填空题：1. 将满/完全二叉树（含n个结点）中各结点从上到下，从左到右进行编号（根结点编号为1），则编号为i的结点，其双亲编号为 ，其左孩子编号

为 ，其右孩子编号为 。

2. 对树的遍历有先根次序遍历树和后根次序遍历树。若以二叉链表作树的存储结构,则树的先根遍历可借用二叉树的 遍历算法来实现,而树的后根遍历可借用二叉树的 遍历算法来实现。

应用题：1. 已知某二叉树的先序遍历序列是ABCDEFGHI，中序遍历序列是BDCEAGHFI，画出该二叉树。

2. 以数据集(4,5,6,7,10,12,18)为叶结点权值，构造一棵赫夫曼树，给出每个叶子的赫夫曼编码，并求其带权路径长度。

一. 图的定义和术语

无向图:、有向图、（无向/有向）完全图、子图、（强）连通图、（强）连通分量、生成树

二． 图的存储结构

无向图（或网）：邻接矩阵、邻接表

有向图（或网）：邻接矩阵、邻接表、逆邻接表

三． 图的遍历（针对具体的存储结构进行）

深度优先搜索遍历图（利用栈） 广度优先搜索遍历图（利用队列）

四． 图的遍历的应用

求无向图的连通分量、生成树（生成森林）

五． 图的应用

求最小生成树（无向网）：Prim算法、Kruskal算法

分别用这两种方法依次得到最小生成树边的过程

判断题：一个连通图的连通分量是包含该图中的所有（n个）顶点和任意n-1条边的子图。

应用题：已知图G如下，画出该有向图的邻接矩阵和邻接表，并根据你的邻接表分别写出深度优先遍历和广度优先遍历的顶点序列。

一． 静态查找表

1. 顺序查找表（设置岗哨）从最后一个开始往前查

2. 有序查找表（折半/二分查找） 要求：元素值有序的顺序表 查找算法，折半查找的判定树

二． 动态查找表

1． 二叉排序树（二叉查找树）

定义、查找、插入、删除 特征：中序遍历有序

从空树开始，依次插入元素，创建一棵二叉排序树 2． 平衡二叉树

定义、查找、插入

从空树开始，依次插入元素，创建一棵平衡的二叉排序树

3． n个元素的二叉排序树、平衡二叉树的（最大、最小）深度

三． 哈希表

1． 哈希表的定义

2． 哈希函数的构造方法 3． 处理冲突的方法 4． 哈希表的造表、查找

5． 装填因子影响哈希表的查找效率

四． 平均查找长度的计算

1． 等概率情况下，查找成功时的平均查找长度ASL 2． 查找不成功时的查找长度

判断题： 1. 任一个二叉排序树的平均查找长度都小于用顺序查找法查找同样结点的线性表的平均查找长度。 2. 当二叉排序树是一棵平衡树时，其平均查找长度为O(log2n)。 选择题：1. 折半查找算法要求被查找的表是( c )。

A. 键值有序的链表 B. 键值不一定有序的链表 C. 键值有序的顺序表 D. 键值不一定有序的顺序表 2. 若查找表是一个有序的单链表，则应采用( )方法。

A. 顺序查找 B. 折半查找 C. 分块查找 D. 哈希查找 3．设线性表中元素的关键字序列为（8,16,24,29,35,40,46,58,66,73,87,98），用折半查找法查关键字等于87的元素时，需依次比较关键字（ ）。 A. 40,58,87 B. 46,87 C. 40,66,87 D. 46,66,87

应用题：1. 已知如下所示长度为8的表: (12，71，36，45，47，50，2，9)，按表中元素顺序构造一棵平衡的二叉排序树，请画出该树。（二叉排序树）

2. 设哈希表长为16，哈希函数为H(key)=key mod 13，用开放定址法的二次探测再散列处理冲突。依次存入10个元素：17,24,36,21,83,96,13,34,57,46，请画出

它们在散列表中的分布情形，并计算等概率时的ASL。

3. 对于上题，如果采用链地址法处理冲突，请画出相应的散列表，并计算等概率时的ASL。

五． 内部排序的方法（排序过程）

1． 直接插入排序 2． 希尔排序 3． 起泡排序 4． 快速排序

5． 简单选择排序 6． 堆排序 7． 归并排序

六． 各种内部排序方法的比较

（最好、最坏、平均）时间复杂度 平均空间复杂度

三 ．排序方法的稳定性

哪些是稳定的排序方法，哪些是不稳定的排序方法？

判断题：归并排序和堆排序的平均时间和最坏情况下的时间性能都是O(nlogn),因此，它们在最坏情况下的时间性能比快速排序好。 应用题：若要按升序对关键字序列(36,45,85,16,23,16,58,22,59,74,12,46)进行排序，请写出：(1). 堆排序初始建堆(大顶堆)的结果；

(2). 以第一个元素为枢轴的快速排序一趟扫描的结果； (3). 起泡排序第一趟的结果；

(4). 希尔排序第一趟（增量5）的结果

一．

void Merge(Linklist A, Linklist B, Linklist &C)

{ C=(Linklist)malloc(sizeof(LNode)); pa=A->next; pb=B->next; pc=C; while(pa&&pb)

{ pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;

if(pa->data<=pb->data)

{ pc->data=pa->data; pa=pa->next;} else

{ pc->data=pb->data; pb=pb->next;} }

if(!pa) pa=pb; while(pa)

{ pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;

pc->data=pa->data; pa=pa->next; }

pc->next=NULL; } 2.

BiTree CopyTree(BiTree T) {

if (!T ) return NULL;

if (!(newT = (BiTNode*)malloc(sizeof(BiTNode)))) exit(Overflow); newT-> data = T-> data;

newT-> lchild = CopyTree(T-> lchild); newT-> rchild = CopyTree(T-> rchild); return newT; } // CopyTree