数据结构习题之绪论
第一章 概 论
一. 基本要求重点、难点
对本章的学习，主要是要熟悉各名词和术语的含义；掌握各种基本概念，特别是数据结构的逻辑结构、存储结构、数据运算3方面的内容及这3方面的相互关系；熟悉C语言的书写规范，理解算法的5个要素的确切含义，即有穷性、确定性、可行性及有输入、有输出，从而掌握计算语句频度和估计算法时间复杂度的方法等，为学习数据结构打下基础。
二. 考核目标和考核要求
要求达到识记层次的有：数据、数据元素、数据项、数据结构等的基本概念；数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系；数据结构的两大逻辑结构和四种常用的存储表示方法；数据结构在各种软件系统中所起的作用；选择合适的数据结构是解决应用问题的关键步骤。
要求达到理解层次有：算法、算法的时间复杂度和空间复杂度、最坏情况下的时间复杂度和平均时间复杂度等概念；算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态；算法描述和算法分析的方法，对于一般算法能力分析出时间复杂度。
要求达到简单应用的有：时间复杂度的算法
三. 练习题
1. 单项选择题
1.1在数据结构中，从逻辑上可以把数据结构分为（ B ）
A） 紧凑结构和非紧凑结构
B） 线性结构和非线性结构
C） 内部结构和外部结构
D） 动态结构和静态结构
数据结构中从逻辑上可以把数据结构分为线性结构和非线性结构
1.2线性表的顺序存储结构是一种（ C ）的存储结构
A） 顺序存取
B） 索引存取
C） 随机存取
D） 散列存取
线性表的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。
1.3逻辑关系是指数据元素的（ A ）
A） 关联
B） 存储方式
C） 结构
D） 数据项
1.4下列时间复杂度中最坏的是（ D ）
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.5下列时间复杂度最好的是（ A ）
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.6下列算法是时间复杂度是（ D ）
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=i+j;
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.7算法分析的两个主要方面是（ D ）
A） 正确性和简明性
B） 数据复杂性和程序复杂性
C） 可读性和可维护性
D） 时间复杂性和空间复杂性
1.8线性表若采用链式存储结构存储时，要求内存中可用存储单元地址（ A ）
A） 不一定连续的
B） 部分地址必须是连续的
C） 必须是连续的
D） 一定是不连续的
1.9算法指的是（ D ）
A） 计算机程序
B） 解决问题的计算方法
C） 排序算法
D） 解决问题的有限运算序列
1.10数据的基本单位是（ B ）
A） 文件
B） 数据元素
C） 符号
D） 关键字
2. 填空题
2.1数据结构一般包括[逻辑结构]、存储结构和数据运算三个方面的内容。
2.2从数据结构S中找出满足条件的结点在S中的位置的运算是[查找]
2.3从数据结构S中读出结构中指定位置上的内容的运算是[读取]
2.4从数据结构S中的某指定位置上增加一个结点的运算是[插入]
2.5从数据结构S中撤消结构中指定位置上结点的运算是[删除]
2.6从数据结构S中修改结构中某指定结点内容的运算是[更新]
2.7数据的存储结构（物理结构）可以用顺序存储、链式存储、[索引存储]及散列存储等四种存储方法表示。
2.8选用算法除了首先考虑“正确性”外，主要考虑[执行算法所需要的时间]、执行算法所需要的存储空间、算法易于理解，易于编程，易于调试
2.9数据结构是研究数据的物理结构和[逻辑运算]以及它们之间的相互关系，并对这种结构定义相应的运算
2.10数据的逻辑结构是从逻辑关系上描述数据，它与数据的[存储结构]无关，是独立于计算机的。
3. 简答题
3.1简述数据与数据元素的关系与区别
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单位，是数据的一个元素。数据元素与数据之间的关系是元素与集合之间的关系。
3.2简述数据、数据元素、数据类型、数据结构、存储结构、线性结构、非线性结构的概念
答：数据：数据是信息的载体，它能够被计算机识别、存储和加工处理
数据元素：是数据的基本单位。有时一个数据元素包含几个数据项
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称
数据结构：指的是数据之间的逻辑关系也称数据的逻辑结构。它包括线性结构和非线性结构两大类。
存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
线性结构：如果结构非空，则有且仅有一个开始结点和一个终端结点，并且所有的结点都最多只有一个直接前驱和一个直接后继
非线性结构：该结构的逻辑特征是一个结点可能有多个直接前驱和直接后继
3.3简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别
答：顺序存储结构是将各数据元素的存储位置按其之间的逻辑关系存放在一块连续的存储空间内，由数据元素的存储位置体现数据元素之间的逻辑关系。链式存储结构各数据元素不一定是存储在连续的一块存储空间内，数据元素之间的逻辑关系与存储位置没有一一对应的关系，数据元素之间的逻辑关系，是依靠附加在存储数据元素的结点中的指针表示。
3.4通常从哪几个方面评价算法的质量
答：
a.算法必须是正确的
b.执行算法所耗费的时间
c.执行算法所耗费的空间，其中主要考虑辅助存储空间
d.算法应易于理解、易于编码、易于调试等
4. 应用题
4.1求下述算法的时间复杂度
for(i=1;i<=n;i++)
{
y=y+1;
for(j=1;j<=2*n;j++)
x=x+1;
}
答：其中语句y=y+1的频度是n-1，语句x=x+1的频度是（n-1）（2n+1）。所以该程序的算法时间复杂度是：T（n）=O（（n-1）（2n+1））=O（n2）
4.2求下述算法的时间复杂度
x=1;
sum=0;
for(i=1;i<=n;i++)
{
x=x*i;
sum=sum+x;
}
答：由于嵌套最深的语句的频度为n，所以其算法的时间复杂度为O（n）。