第九章数据结构与算法基础.docx

第九章数据结构与算法基础.docx

《第九章数据结构与算法基础.docx》由会员分享，可在线阅读，更多相关《第九章数据结构与算法基础.docx（11页珍藏版）》请在冰点文库上搜索。

第九章数据结构与算法基础

解题思路

多代入法

二叉树

度

叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。

注意树的度和图的度区别

叶子结点

二叉排序树

完全二叉树

若设二叉树的深度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；

最优二叉树（就是哈弗曼树）

平衡二叉树

平衡二叉树，又称AVL树。

它或者是一棵空树，或者是具有下列性质的二叉树：

它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

满二叉树

满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。

也可以这样理解，除叶子结点外的所有结点均有两个子结点。

节点数达到最大值。

所有叶子结点必须在同一层上.

本题主要考查一些特殊二叉树的性质。

若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

二叉排序树的递归定义如下：

二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；

（3）左右子树也都是二叉排序树。

在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。

最优二叉树即哈夫曼树。

排序

各种排序的大致思路？

各种排序适用于什么情况？

各种排序的时间，空间复杂度？

快速排序

1.快速排序（Quicksort）是对冒泡排序法的一种改进，它的基本思想是：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；在对一个基本有序的数组进行排序时适合采用快速排序法。

2.快速排序的平均运行时间为O（nlogn）。

算法排序试题32（2015年下半年试题64-65）

在某应用中，需要先排序一组大规模的记录，其关键字为整数。

若这组记录的关键字基本上有序，则适宜采用（ ）排序算法。

若这组记录的关键字的取值均在0到9之间（含），则适宜采用（ ）排序算法。

（64）A．插入 

B.归并 

C.快速 

D.计数 

（65）A．插入 

B.归并 

C.快速 

D.计数

试题分析

插入排序中的希尔排序的基本思想是：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

所以当数列基本有序时，采用插入排序算法是比较合适的。

计数排序是一个非基于比较的排序算法，该算法于1954年由HaroldH.Seward提出。

它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο（n+k）（其中k是整数的范围），快于任何比较排序算法。

试题答案

（64）A（65）D

哈弗曼树哈夫曼序列

折半查找经常考啊

优先队列

算法

试题59（2013年下半年试题64-65）

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（ ）算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ ）算法设计策略。

（64）A．分治 

B.动态规划 

C.贪心 

D.回溯 

（65）A．动态规划 

B.贪心 

C.回溯 

D.分支限界

试题分析

分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。

动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。

若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。

贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。

回溯法是一种既带有系统性又带有跳跃性的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。

题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。

而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

试题答案

（64）B（65）C

线性表与链表

试题60（2013年上半年试题51）

采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为（ ）。

（51）A．O

（1）O

（1） 

B.O

（1）O（N） 

C.O（N）O

（1） 

D.O（N）O（N）

试题分析

 顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。

采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表（Linkedlist）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。

由于不必按顺序存储，链表在插入的时候可以达到O⑴的复杂度，比另一种线性表：

顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O（n）的时间，而顺序表相应的时间复杂度分别是O（logn）和O⑴。

试题答案

（51）B

把二叉查找树　变成　矮胖的　Ｂ－树

贪心算法

试题81（2012年上半年试题63-64）

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。

在两个地点i和j之间运输货物存在费用Cij。

为求解旅行费用总和最小的运输路径，设计如下算法：

首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2，…，每次在需访问的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。

刚该算法采用了（ ）算法设计策略，其时间复杂度为（ ）。

（63）A．分治 

B.动态规划 

C.贪心 

D.回溯 

（64）A．

B.

C.

D.

试题分析

试题答案

（63）C（64）A

四种算法介绍

试题90（2011年下半年试题62）

迪杰斯特拉（Dijkstra）算法用于求解图上的单源点最短路径。

该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（ ）策略的算法。

（62）A．分治

B.动态规划

C.贪心

D.回溯

试题分析

分治法：

对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

动态规划法：

这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。

贪心算法：

它是一种不追求最优解，只希望得到较为满意解的方法。

贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。

贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。

回溯算法（试探法）：

它是一种系统地搜索问题的解的方法。

回溯算法的基本思想是：

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

其实现一般要用到递归和堆栈。

针对单源最短路径问题，由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。

若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。

这是一种典型的贪心策略，就是每递增一次，经对所有可能的源点、目标点的路径都要计算，得出最优。

带权图的最短路径问题即求两个顶点间长度最短的路径。

其中：

路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。

试题答案

（62）C

拓扑序列蛮好理解的。

。

试题105（2010年下半年试题59）

（ ）是右图的合法拓扑序列。

（59）A．654321 

B.123456 

C.563421 

D.564213

试题分析

本题主要考查拓扑序列。

在给出拓扑图求拓扑序列时，我们应该掌握一个关键因素，那就是箭头的画出节点在箭头指向节点前，如果一个节点被很多箭头所指，那么应该要在所有这些箭头的画出节点之后才是本节点。

拓扑序列的开始节点应该是没有箭头所指的节点，在本题中应该是5或6，这里需要注意它们谁在最前面都可以。

那么按照这个原则我们就可以知道本题的拓扑序列应该为654321或者564321。

试题答案

（59）A

KMP字符串求next