算法与数据结构---C语言描述（第三版）
第1章 绪论
1、解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法，贪心法，回溯法，分治法。
答：
(1) 逻辑结构（数学模型）：
指数据元素之间地逻辑关系。
具体解释：指数学模型（集合，表，树，和图）之间的关系。
描述方式：B = <K,R>, K是节点的有穷集合，R是K上的一个关系。
(2) 存储结构（物理结构）：
数据的逻辑结构在计算机存储器中的映射（或表示）。
(3) 操作（行为）：
指抽象数据类型关心的的各种行为在不同的存储结构上的具体算法（或程序）。
(4) 数据结构：
传统观念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据。
②根据面向对象的观点：数据结构是抽象数据类型的物理实现。
(5) 数据结构的表示：
(6) 数据结构的实现：
(7) 抽象数据类型：
(8) 算法：
是由有穷规则构成（为解决某一类问题）的运算序列。
-算法可以有若干输入（初始值或条件）。
-算法通常又有若干个输出（计算结果）。
-算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。
-算法应该具有确定性。算法的每一步，必须有确切的定义。
-算法应该有可行性。算法中国的每个动作，原则上都是能够有机器或人准确完成的。
(9) 算法的时间代价：
(10) 算法的空间代价：
(11) 大O表示法：
-更关注算法复杂性的量级。
-若存在正常数c和n0，当问题的规模n>=c*f(n), 则说改算法的时间（或空间）代价为O（f(n)）
(12) 贪心法：
    当追求的目标是一个问题的最优解是，设法把整个问题的求解工作分成若干步来完成。在其中的每一个阶段都选择都选择从局部来看是最优的方案，以期望通过各个阶段的局部最有选择达到整体的最优。
例如：着问题：先用一种颜尽可能多的节点上，然后用另一种颜在为着节点中尽可能多的节点上，如此反复直到所有节点都着为止；
(13) 回溯法
有一些问题，需要通过彻底搜索所有的情况寻一个满足某些预定条件的最优解。由于彻底搜索的运算量非常大，所以采用一步一步向前试探，当有多重选择是可以任意选择一种，只要目前可行就继续向前，一旦发现失败或问题就后退，回到上一步重新选择，借助于回溯技巧和中间增加判断，这样常常可以大大地减少搜索的时间。
-常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。
(14) 分治法
    把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题进行求解，即对问题分而治之。如果一个问题的规模仍然比较大，不能很容易的求解，就可以对这个子问题重复地应用分治策略。
-二分法检索就是用分治法策略的典型例子。
2、理解以下关系：
答：
算法与数据结构的关系：
    算法+数据结构=程序
    程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。
    算法与数据结构是程序设计中相辅相成、不可分割的两个方面。
数据结构与抽象数据类型的关系：
算法和数据结构问题的求解关系：
3.为整数定义一个抽象数据类型。它包含整数的常见运算，每一个运算对应一个函数，由它的输入/输出定义。
4.什么叫数据结构？试举一个简单的例子说明。
答：传统的概念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据。
根据面向对象的观点：数据结构是抽象的数据类型的物理实现。
5.从逻辑上可以把数据结构分成哪几类？
答：（1）给定B=<K,R>, 若<K1,K2>∈R, 则称K1为K2的前驱，K2为K1的后继。没有前驱的结点为开始结点，没有后继结点为终端结点。
（2）根据R的特点可以将数据结构分为以下三类：
线性结构：K中每个结点最多只有一个前驱和一个后继；
树形结构：K中每个结点做多有一个前驱，单可以有多个后继；
复杂结构：K中节点的前驱、后继结点的个数都不做限制；
集合结构：当R为空集时，K中结点间没有约束关系；
7.将下列复杂度由小到大重新排序：
A、2n                    B、n!
C、n5                    D、10000   
E、n * log₂n
【答】DECAB
8.将下列复杂度由小到大重新排序：
A．n*log2(n)              B．n + n2 + n3
    C．24                    D．n0.5
【答】24< n0.5< n*log2(n) < n + n2 + n3        CDAB
                                                                                                                             
9.用大O表示法描述下列复杂度：
A．5n5/2 + n2/5 
B．6 * log2(n) + 9n 
C．3n4 + n * log2(n)     
D．5n2 + n3/2
数据结构与算法分析答案
【答】A: O(n5/2)    B: O(n)    C: O(n4)    D: O(n2)
10.按照增长率从低到高的顺序排列以下表达式：4n2, log3n, 3n, 20n, 2000, z, n2/3。又
n！应排在第几位?
【答】按照增长率从低到高依次为： 2000, log3n, log2n, n2/3, 20n, 4n2, 3n
n!: 增长率比她们中的每一个要打，应该排在最后一位。
算法分析题
1.计算下列程序片段的时间代价：
int i = 1;
while(i<=n){
printf("i = %d\n",i);
i = i + 1;
}
【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环的n，共执行n次。所以该程序的总时间代价为：
T(n) = 1 + n + (n+n)
= 1+3n
=O(n)
2. 计算下列程序片段的时间代价：
    int i = 1;
    while(i<=n){
        int j = 1;
        while(j<=n){
            int k = 1;
            while(k<=n){
                printf("i = %d, j = %d, k = %d\n", i, j, k);
                k = k + 1;
            }
            j=j+1;
        }
        i = i + 1;
    }
【答】循环变量i从1增加到n，最外层循环体执行n次；循环变量j从1增加到n，中间层循环体执行n次；循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：
T(n) = 1+n+n{1+n+n[1+n+n(n+n)+1]+1}
    = 1+n+n+n2+n2[3n+2]+n
    = 1+2n+n2+3n3+2n2+n
    = 1+3n+3n2+3n3
    =O(n3)   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。