1.6 本 章 小 结
1.6 本 章 小 结
本章主要介绍了贯穿全书的基本概念和基本思想。数据是能够由计算机接受和处理的对象。数据结构主要描述数据中各种元素间的相互关系，往往是给出了有关这些元素的一组运算。数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构指数据元素之间的逻辑关系，数据的物理结构指数据元素在计算机存储器中的表示和安排。
算法指的是有穷的规则序列，这些规则决定了解决某一问题的一系列运算。而评价一个算法主要是研究算法的时间复杂度和空间复杂度。
通过学习本章的知识，首先要对数据结构在程序设计中的重要作用有一个充分全面的认识，并需掌握数据结构的基本概念，了解数据结构的分类及算法的设计、描述方法。其次，对算法的概念及评价方法要有所了解。
1.7 练 习 题
1．选择题
（1）要求同一逻辑结构的所有数据元素具有相同特性，这意味着 。
A．数据元素具有同一个特点
B．不仅数据元素包含的数据项个数要相同，而且对应数据项的类型要一致
C．每个数据元素都是一个样式
D．数据元素所包含的数据项的个数要相等
（2）数据结构是一门研究非数值计算的程序设计问题中计算机的 和运算的学科。
A．操作对象 B．计算方法
C．逻辑存储 D．数据映像
（3）数据结构被形式地定义为(D, R)，其中D是 的有限集合。
A．算法 B．数据元素
C．数据操作 D．逻辑结构
（4）在数据结构中，从逻辑上可以把数据结构分为 。
A．动态结构和静态结构
B．紧凑结构和非紧凑结构
C．线性结构和非线性结构
D．内部结构和外部结构
（5）线性表的顺序存储结构是一种 的存储结构。
A．随机存取 B．顺序存取
C．索引存取 D．散列存取
（6）算法分析的目的是 。
A．找出数据结构图的合理性
B．研究算法中输入和输出的关系
C．分析算法的效率以求改进
D．分析算法的易懂性和文档性
（7）计算机算法指的是解决某一问题的有限运算序列，它必须具备输入、输出和
5个特征。
A．可行性、可移植性和可扩充性
B．可行性、确定性和有穷性
C．确定性、有穷性和稳定性
D．易读性、稳定性和安全性
（8）线性表若采用链表存储结构，要求内存中可用存储单元的地址 。
A．必须是连续的 B．部分必须是连续的
C．一定是不连续的 D．连续不连续都可以
（9）在以下的叙述中，正确的是 。
A．线性表的线性存储结构优于链式存储结构
B．二维数组是每个数据元素为一个线性表的线性表
C．栈的操作方式是先进先出
D．队列的操作方式是先进后出
（10）根据数据元素之间关系的不同特性，以下4类基本的逻辑结构反映了4类基本的数据组织形式，其中解释错误的是 。
A．集合中任何两个节点之间都有逻辑关系但组织形式松散
B．线性结构中节点按逻辑关系依次排列形成一条“锁链”
C．树形结构具有分支、层次特性，其形态有点像自然界中的树
D．图状结构中的各个节点按逻辑关系互相缠绕，任何两个节点都可以邻接
（11）以下说法正确的是 。
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．数据结构是带有结构的数据元素的集合
2．填空题
（1）数据逻辑结构包括3种类型 、 和 ，树形结构和图形结构合称为 。
（2）在线性结构中，第一个节点 前驱节点，其余每个节点有且只有 个前驱节点；最后一个节点 后续节点，其余每个节点有且只有 个后续节点。
（3）在树形结构中，树根节点没有 节点，其余每个节点有且只有 个前驱节点；叶子节点没有 节点，其余每个节点的后续可以 。
（4）在图形结构中，每个节点的前驱节点数和后续节点数可以 。
（5）线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。
（6）算法的5个重要特性是 、 、 、 和 。
（7）算法分析的目的是 。
（8）称算法的时间复杂度为O(f (n))，其含义是指算法的执行时间和 的数量级相同。
|
图1-2 逻辑结构图
|
（1）叙述数据结构包含的3个方面，并举例说明。
（2）什么是算法（Algorithms）？
（3）设有如图1-2所示的逻辑结构图，给出它的数据结构定义，并说明是什么类型的数据结构。
（4）以下有几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别属于何种结构。
① A=(K,R)，其中
K={a,b,c,d,e}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>}
② B=(K,R)，其中
K={a,b,c,d,e}
R={r}
r={<a,b>,<a,c>,<b,d>,<c,e>}
③ C=(K,R)，其中
K={a,b,c,d,e}
R={r}
r={(a,b),(a,c),(b,d),(c,e)}
4．上机操作题
（1）用C语言描述算法：对于输入的任意3个整数，将它们按从小到大的顺序输出。
（2）用C语言描述算法：对于输入的任意n个整数，输出其中的最大元素和最小元素。
（3）设n为正整数，给出下列各种算法关于n的时间复杂度。
①void fun1(int n)
{
i=1,k=100;
while (i<n)
{
k=k+1;i+=2;
}
}
② void fun2(int b[],int n)
{
int i,j,k,x;
for (i=0;i<=n-1;i++)
{
k=i;
for (j=i+1;j<n;j++)
if (b[k]>b[j]) k=j;
x=b[i];
b[i]=b[k];
b[k]=x;
}
}
③ void fun3(int n)
{
int i=0,s=0;
while (s<n)
{
i++;
s=s+i;
}
}
（4）计算出下列程序段中x=x+1语句的执行次数。
①int i;
for(i=1;i<=100;i+=2)
x=x+1;
②int i=1;
while(++i<=100)
x=x+1;
③int i=1;
do
{
x=x+1;
}
while(x++<=100);