写在前面
该习题答案非标准答案，正确不保证，如有错误望指正。
知识点导图
严蔚敏版习题
一、单项选择题（部分）
2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（C、逻辑结构）
逻辑结构是从具体问题抽象出来的数学模型 ，从逻辑关系上描述数据，它与数据的存储无关，也就是说与数据本身的具体形式、内容、相对位置、个数无关。
5、算法的时间复杂度取决于（D、问题的规模和待处理数据的初态）
算法的时间复杂度不仅与问题的规模有关，还与问题的其他元素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。
8、下面程序段的时间复杂度是（C、O(n log?n)）
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;
内层循环条件j<=n，因此内层循环执行n次，时间复杂度为O(n)；外层循环条件k<=n，增量定义为k×2，可知循环次数为k<=log?n，时间复杂度为O(log?n)。
对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度为T(n)=T1(n)×T2(n)=O(n)×O(log?n)=O(n log?n)。
计算算法的时间复杂度
a)加法规则：T(n)=O(max(f(n),g(n)))
b)乘法规则：T(n)=O(f(n)×g(n))
10、以下程序段中语句“x++;”的语句频度为（D、n(n+1)(n+2)/6）
for(i=1;i=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
“x++;”的语句频度为：
∑∑∑ 1 =∑∑ j =∑∑ i ( i+1 ) / 2
=?(∑ i2 + ∑ i )
=?( n(n+1)(2n+1) / 6 + n(n+1) / 2 ) = n(n+1)(n+2)/6
12、设一维数组中有n个数组元素，则读取第 i 个数组元素的平均时间复杂度为（C、O(1)）
读取第 i 个数组元素可以直接通过数组的下标定位，与 n 无关，因此平均时间复杂度为O(1)。
17、数据结构是（A、数据元素的组织形式）
19、设数据结构 A =(D , R)，其中 D = {1 , 2 , 3 , 4}，R = {r}，r={< 1,2 > , < 2,3 > , < 3,4 > , < 4,1 >}，则数据结构 A 是（C、图）
数据元素之间多或多的关系，因此是图结构。
20、数据在计算机存储机构内表示时，物理地址与逻辑地址不相同的，称之为（C、链式存储结构）
21、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储结构比顺序存储要（B、高）
顺序存储结构要求所有的元素依次存放在一段连续的存储空间中，必须预先分配；而链式存储结构用一组任意的存储单元存储数据元素，这组存储单元可以连续、也可以不连续，不需要预先分配空间。
因此，在存储空间使用的灵活性上，链式存储更高。
24、以下与数据的存储结构有关的术语是（B、链表）
数据的逻辑结构不涉及数据的存储情况。
26、算法是（D、解决问题的有限运算序列）
算法是为了解决某类问题而规定的一个有限长的操作序列。
27、下面的关于算法说法正确的是（C、算法的可行性是指指令可以有二义性）
算法的可行性是指算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
30、以下解释错误的是（D、高效性即达到所需要的时间性能）
高效性包括时间和空间两个方面
二、应用题
1、简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
数据:是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录树中棋盘的一个格局(状态)图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合 N={0，±1，±2，…}，字母字符数据对象是集合C={'A’，'B’，…，'Z’，'а’，'b’，…，'z’}，学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作从具体问题抽象出来的数学模型。
存储结构:是数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型:是由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合
2、试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
略
3、简述逻辑结构的四种基本关系并画出它们的关系图。
(1)集合结构
别无其他关系。例如，确定一名学生是否为
数据元素之间除了“属于同一集合”的关系外，兄班级成员，只需将班级看作一个集合结构。
(2)线性结构
数据元素之间存在一对一的关系。例如，将学生作信息数据按照其人学报到的时间先后顺序进行排列，将组成一个线性结构。
(3)树结构
数据元素之间存在一对多的关系。例如，在班级的的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。
(4)图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。
其中，集合结构、树结构和图结构都属于非线性线结构。
4、存储结构有哪两种基本的存储方式实现。
(1)顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借程序设计语言的数组类型来描述。
(2)链式存储结构
顺序存储结构要求所有的元素依次存放在一段连续的存储空间中，而链式存储结构无需占用一整块存储空间，但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助程序设计语言的指针类型来描述。
5、试分析下列各算法的时间复杂度。
（1）
x=90;
y=100
while(y>0)
if(x>100){
x=x-10;
y--;
}
else x++;
时间复杂度为O(1)
（2）
for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j]=0;
时间复杂度为O(n×m)
（3）
s=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s+=B[i][j];
sum=s;
时间复杂度为O(n2)
（4）
i=1;
while(i<=n)
i=i*s;
时间复杂度为O(log?n)
※（5）
x=0;
for(i=0;i<n;i++)
for(j=1;j<=n-1;j++)
x++;
时间复杂度为O(n2)
※（6）
x=n; //n>1
y=0;
while(x>=(y+1)*(y+1))
y++;
时间复杂度为O(√n)
设基本语句“y++;”的执行次数f(n)，则x≥(f(n)+1)2，又由于x=n，所以f(n)≤√n-1，即T(n)=O(√n)。
王曙燕版习题
1、简述下列概念：
数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
略
2、类C语言与标准C语言的主要区别是什么？
类C语言是从C语言选出一个核心子集，并添加了C++的引用调用参数传递方式等。
类C是面向对象的，而C是面向过程的，类c的特性是可以继承，重载，多态。
3、试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。
略
4、常用的存储表示方式有哪几种？
(1）顺序存储结构
①用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系有元素的存储位置来表示。
②C语言中用数组来实现顺序存储结构。
(2）链式存储结构
①用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系有元素的指针来表示。
②C语言中用指针来实现链式存储结构。（指针即地址）
5、设函数 f、g、h 分别为f(n) = 70n3+n2+500，g(n) = 65n3+7600n2，h(n) = n^1.5+800n lg n，请判断下列关系是否成立。
(1) f(n) = O(g(n))
(2) g(n) = O(g(n))
(3) h(n) = O(n^1.5)
(4)h(n) = O(n lg n)
? (1) f(n) = O(g(n))
? (2) g(n) = O(g(n))
? (3) h(n) = O(n^1.5)
? (4)h(n) = O(n lg n)
6、设n为正整数，请估算以下程序段的时间复杂度。
（1）
i=0;
k=0;
while(i<=n-1)
{ k=k+10 * i;
i++;
}
时间复杂度为O(n)。
（2）
i=0;
j=0;
while(i+j<=n)
{ if(i>j)
j++;
else i++;
}
时间复杂度为O(n)。
※（3）
x=n; //n>1
y=0;
while(x>=(y+1)*(y+1))
y++;
时间复杂度为O(√n)
设基本语句“y++;”的执行次数f(n)，则x≥(f(n)+1)2，又由于x=n，所以f(n)≤√n-1，即T(n)=O(√n)。
（4）
x=90;
y=100
while(y>0)
if(x>100){
x=x-10;
y--;
}
else x++;
时间复杂度为O(1)
7、算法的时间复杂度仅与问题的规模相关吗？
算法的时间复杂度不仅与问题的规模有关，还与问题的其他元素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。
8、略
※9、算法设计：设计求解下列问题的类C语言算法，并分析其最坏情况下的时间复杂度。
（1）在数组 A [ 1…n ]中查找值为 K 的元素，若找到则输出其位置 i（1≤i≤n），否则输出0作为标志。
int Find(datatype A[0，……n],datetype k)
{
int i=1;
for(i=0;i<n;i++)
{
if(A[i]==k)
break;
}
if(i<=n)
return i ;
else
return 0 ;
}
当查找不成功即最坏情况时，T(n)=O(n)。
（2）找出数组A[1…n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作)。
void max(datetype A[n],x,y)
{
datetype x=A[0];
datetype y=A[0];
int i=1;
for(i=1;i<n;i++)
{
if(x<A[i])
{
y=x;
x=[i];
}
else
if(y<A[i])
y=A[i];
}
}
for语句执行n-1次即情况最坏时，T(n)=O(n)。