《数据结构-用C语言描述第三版》课后答案 第一章

---

        前段时间，看到一篇文章，是批判中国教材的，说国内的教材粗制滥造，不过是为了评一些奖项荣誉，反观国外的教材确细致入微，生怕学生看不懂，我不否认这种观点，但是，我认为，我们更改努力学习，改变这不足之处。最近在学习数据结构，是耿国华老师主编的《数据结构--用c语言描述》一书的第三版，学过之后，本想做做课后题，对对答案，奈何找不到教材答案，找到的一些答案似乎也是旧版本的，内容有所不同，干脆一想，既然自己在学，就把内容写成博客吧，遂有此篇。

---

1.简述下列术语或概念

（1）数据结构

     数据结构是指相互之间存在一种或多种特定关系的数据元素集合，数据结构包括数据元素集合及元素间关系的集合，即数据的组织形式。

（2）数据结构的四个基本逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图或网状结构

（3）数据结构的物理结构

       也叫数据的存储结构，是逻辑结构在计算机中的存储映像，主要分为两种，顺序存储结构和非顺序存储结构，又可分为顺序存储、链式存储、索引存储、散列存储

（4）数据类型

       数据类型是一组相同的值集合以及定义在这个值集合上的一组操作的总称，分为原子类型（值不可再分的数据类型）、结构类型（值可分解为若干成分的数据类型）、抽象数据类型（一个数学模型及定义在该数学模型上的一组操作）

（5）线性结构与非线性结构的差别

        线性结构中数据元素之间存在着一一对应的关系，除了第一个元素和最后一个元素外，其余元素均有一个直接前驱和直接后继，而非线性结构数据元素之间存在着一对多、多对多的关系，线性结构有线性表、栈、队列、串、数组、广义表，非线性结构有树、图

（6）抽象数据类型

        抽象数据类型（Abstract data type,ADT）定义了一个数据对象、数据对象中各元素间的结构关系以及一组处理数据的操作。

        抽象数据类型的两个特点：数据抽象与信息隐藏。

        抽象数据类型的特征：使用与实现分离，实现封装和信息隐藏。（抽象数据类型的定义是独立于实现的）

（7）数据结构的形式化定义、数据结构两个构成要素的含义

ADT<ADT名>
{
    数据对象：<数据对象的定义>
    结构关系：<结构关系的定义>
    基本操作：<基本操作的定义>
}ADT<ADT名>

数据结构的两个构成要素是数据元素集合以及元素间关系。

（8）算法的特性以及设计要求

算法的特性：

1. 输入
2. 输出
3. 有限型
4. 可行性
5. 准确性

设计要求：

1. 可读性
2. 正确性
3. 健壮性
4. 高效性和低存储量

（9）算法的时间复杂度

        一个算法的执行时间是指算法中所有语句执行时间的总和，语句的执行受编译程序、计算机软硬件环境影响，因此用算法中基本操作重复执行的频度作为度量标准，记T(n) = O(f(n))

（10）函数参数传递的主要方式及特点

1. 传值
   • 只为操作提供待输入或处理的数据
2. 传地址
   • 既能为操作提供待输入或处理的数据，也能返回操作结构

2.选择题

（1）设某数据结构的二元组形式表示为A=｛D，R｝，D=｛1，2，3，4，5，6，7，8，9｝，R=｛r｝,r={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,<3,7>,<3,8>,<3,9>｝,则数据结构A是（B）

A.线性结构        B.树形结构        C.物理结构        D.图结构

（2）数据的最小单位（A）

A.数据项        B.数据类型        C.数据元素        D.数据变量

（3）若需要利用形式参数直接访问修改实参值，则应将形参说明为（A）参数

A.指针        B.值参数        C.数值        D.整型

（4）下列程序的时间复杂度为（A）

i=0;
s=0;
while(s<n){
    s+=i;
    i++;
}

A.O()        B.O()        C.O()        D.O()

解析：

设执行次数为k次，则s = 0+1+2+3+...+(k-1)>=n

s =  >=n

则O(n)=

（5）执行下面程序时，语句s的执行次数为（）

for(i=0;i<=n;i++)
    for(j=0;j<=i;j++)
        S

A.O()        B.O()        C.O()        D.O()

3.计算下列程序段中x=x+1的语句频度

for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            x=x+1

解析：

i=1时，语句执行1次

i=2时，语句执行1+2=3次

......

i=n时，语句执行1+2+...+n=次

则计算an=的前n项和Sn

Sn = =

4.编写算法，求一元多项式的值，并确定算法中的每一个语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，算法中不能使用求幂函数。注意：本题中的输入为(i=0,1,2...,n)、x和n,输出为.通常算法的输入和输出可采用下列两种方式之一：

1. 通过参数表中的参数显示传递
2. 通过全局变量隐式传递

void func(double a[],int  n,double x){
    int i;
    double xtemp=1;
    double psum=0;
    for(i=0;i<n;i++){
        psum+=a[i]*xtemp;
        xtemp*=x;
    }
}

尾记：如有错误，望指正，我会及时修改