数据结构第一周作业

1、数据的特征是什么？下面的对象中有哪些是数据？你能举出生活中一些不是数据的对象吗？

（1）PDF版的数据结构教程
（2）计算机内的GPU芯片
（3）网站内的网页
（4）MOOC中心的视频课程
（5）报纸 （6）病毒疫情信息
（7）C语言源程序 （8）手机App

答：数据的特征是
1、种类，数据类型的多样性；
2、速度，指获得数据的速度；
3、可变性，妨碍了处理和有效地管理数据的过程；
4、真实性，数据的质量；
5、复杂性，数据量巨大，来源多渠道。

(1)(3)(4)(7)
西瓜，水杯，粉笔，口罩

2. 数据的逻辑结构

数据的逻辑结构描述的是数据之间的逻辑关系，解决的是数据如何组织的问题。

数据的物理结构

数据的物理结构描述的是数据在计算机中的物理表示方式问题，解决的是数据如何存储到计算机中的问题。

3. 如何理解一个算法的正确性？

正确性（Correctness）∶算法应当满足具体问题的需求，对问题的输入、输出和处理必须有明确而正确的描述。
所谓"正确"，大致包含四层意义∶

◆一是，程序不含语法错误;
◆ 二是，程序对几组输入数据能够得出满足问题说明所要求的结果;
◆三是，程序对于精心选择的典型、苛刻的输入数据和边界条件数据也能够满足要求;
四是，程序对一切合法的输入数据都能产生满足规格需求说明的结果。

一般通过哪些方法可以进行验证或评估？

测试样例，循环不变量。

4. 算法和程序有哪些异同和联系？

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中一条指令表示一个或者多个操作。
程序是计算机指令的有序集合,是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。

算法在描述上一般使用半形式化的语言，而程序是用形式化的计算机语言描述的。

联系：一个算法可以用不同的编程语言写出不同的程序。

程序 = 算法 + 数据结构

5、已知m、n为正整数，请用流程框图和C语言分别写出计算m和n最小公倍数的算法。

算法基本步骤如下：
（1）计算 m×n 的值，并存储到变量 r 中；
（2）若 m 等于 n，返回最小公倍数 r/m，算法结束；
（3）若 m 大于 n，计算 m-n，结果存入m；否则计算 n-m，结果存入 n；
（4）转步骤（2）。

flowchat
st=>start: 开始
e=>end: 结束
op=>operation: 输入m,n
cond=>condition: m=n？
cond1=>condition: m>n?
cond2=>condition: m<n?
op0=>operation: 输出n
op1=>operation: m=m-n
op2=>operation: n=n-m
st->op->cond
cond(yes)->op0->e
cond(no)->cond1(yes)->op1->cond
cond(no)->cond1(no)->cond2(yes)->op2->cond

#include <stdio.h>

int main(){
    int m,n;
    scanf("%d %d",&m,&n);
    int r = m*n;
    while(1){
        if(m==n){
            printf("%d",r/m);
            break;
        }else if(m>n){
            m = m-n;
        }else{
            n = n-m;
        }
    }
    return 0;
}